Faisant suite
au précédent article concernant la résolution de puzzle et problèmes combinatoires, je me suis demandé comment résoudre le problème des 8 reines à l'aide de LinQ.
Le puzzle consiste à placer 8 reines sur un échiquier de telle façon qu'aucune d'entre-elles ne puisse être en position d'en capturer une autre.
Pour rappel, une reine peut se déplacer d'autant de case qu'elle le désire dans l'une des directions suivantes:
* Horizontale
* Verticale
* Diagonales (les deux sens)
Pour résoudre le problème, il faut qu'une nouvelle reine à placer sur l'échiquier n'occupe pas une case sur la même ligne, même colonne, même diagonale qu'une des autres reines placées sur l'échiquier.
Principe de résolution
Pour résourdre ce problème il faut:
- Identifier, de façon simple, la position d'une reine à l'aide sur l'échiquier.
- Trouver un processus mathématique qui vérifie si deux reines sont sur une même ligne (ou colonne).
Problème trivial.
- Trouve un processus mathématique qui vérifie si deux reines partages une des diagonales.
Pourquoi des processus mathématique?
Ayant la volonté de résoudre ce problème avec LinQ, l'utilisation de fonction mathématique correspond mieux à la philosophie de résolution (évitant ainsi l'utilisation de boucles/itérations ou tests en cascade).
Identification de la position d'une reine
Bien qu'il soit possible d'identifier la position d'une reine à l'aide d'une structure, cette option n'est pas très efficace car elle nécessite la manipulation d'une structure et la mise en place de double boucles, de vérifications plus poussées, etc.
Le code repris ci-dessous repris à titre de support ne sera donc pas utilisé.
struct QueenPos
{
public int row; // 1 à 8
public int column; // de 1 à 8
public QueenPos( int iRow, int iCol ){
row = iRow; column = iCol;
}
};
public static void RunSnippet()
{
QueenPos Queen1 = new QueenPos( 1, 5 );
}
Une alternative plus intéressante sur le plan mathématique étant la numérotation des cases (de 1 à 64) de l'échiquier.
La position d'une reine est alors identifié à l'aide d'une valeur numérique UNIQUE de 1 à 64.
Puisqu'un échiquier est un carré de 8 par 8, il est possible de déduire la ligne et la colonne d'une reine à partir de sa position. Il est même possible de déduire la diagonale sur laquelle elle se trouve (mais on reparlera de cela plus loin).
 |
| Echiquer où chacune des cases est numérotée |
Une reine placée en 3ième lignes, 4ième colonne portera la position 20.
Les positions possibles d'une reine (
iQueenPos) peut donc être pris en charge par une simple boucle "For" ou une énumération de 1 à 64. Une approche idéale pour un traitement LinQ.
Position de la reine (ligne et colonne)
Puisque la position d'une reine(
iQueenPos) varie de 1 à 64, il faut être capable de transformer cette valeur numérique en ligne et colonne.
Puisque l'échiquier est un carré parfait, la ligne et la colonne peuvent être retrouvé à l'aide de fonctions mathématiques.
/// <summary>
/// Return the Column where the Queen is placed
/// </summary>
/// <param name="QueenPos">The current position of the queen in the GameBoard (Cell 1 to 64)</param>
/// <returns>The column number. Value between 1 and 8.</returns>private int QueenCol(int QueenPos) {
return ((QueenPos - 1) % 8) + 1;
}
/// <summary>
/// Return the Row where the Queen is placed
/// </summary>
/// <param name="QueenPos">The current position of the queen in the GameBoard (Cell 1 to 64)</param>
/// <returns>The Row number. Value between 1 and 8.</returns>
private int QueenRow(int QueenPos)
{
return ((QueenPos - 1) / 8) + 1;
}
Le test de ces fonctions produit le résultat suivant (avec le code de test repris ci-après).
// Code affichant le résultat des colonnes et lignes
// calculées pour chacune des positions possibles
// d'une reine
//
//lst is a ListBoxControl
lst.Items.Add("--- Rows ------------------------");
for (int i = 1; i <= 64; i++)
{
int iRow = QueenRow(i);
s = s + iRow.ToString().PadLeft(2) + ",";
if ((i % 8) == 0)
{
lst.Items.Add(s);
s = "";
}
}
lst.Items.Add(s);
lst.Items.Add("--- Columns --------------------");
for (int i = 1; i <= 64; i++)
{
int iCol = QueenCol(i);
s = s + iCol.ToString().PadLeft(2) + ",";
if ((i % 8) == 0)
{
lst.Items.Add(s);
s = "";
}
}
lst.Items.Add(s);
Position de la reine (les diagonales)
Il est possible d'identifier la diagonale sur laquelle se trouve une reine à l'aide d'une simple opération mathématique.
/// <summary>
/// Identify the Diagonal (/) on which the Queen is Placed
/// </summary>
/// <param name="QueenPos">The current position of the queen in the GameBoard (Cell 1 to 64)</param>
/// <returns>The diagonal number on which the queen is placed. Each diagonal has a unique number.</returns></returns>private int QueenDiag(int QueenPos) {
return QueenRow(QueenPos) + QueenCol(QueenPos);
}
/// <summary>
/// Identify the Anti-Diagonal (\) on which the Queen is Placed
/// </summary>
/// <param name="QueenPos">The current position of the queen in the GameBoard (Cell 1 to 64)</param>
/// <returns>The anti-diagonal number on which the queen is placed. Each anti-diagonal has a unique number.</returns></returns>
private int QueenAntiDiag(int QueenPos)
{
return QueenRow(QueenPos) - QueenCol(QueenPos);
}
En utilisant une code similaire à "position Lignes/Colonnes de la reine" il est possible d'évaluer la valeur des diagonales (et anti-diagonales) pour chacune des positions possible d'une reine.
Ainsi donc, les reines en positions 15 et 57 se gênent l'une l'autre puisqu'elles partagent la même diagonal (la diagonale n° 9).
Quand deux reines se gênent t-elles?
Le test devient alors relativement simple.
Deux reines (Reine 1 en position
newQueenPos, Reine 2 en position
otherQueenPos ) se gênent si elles partagent la même colonne ou la même ligne ou la même diagonale ou la même anti-diagonale.
Ce qui produit le code suivant (ainsi que la routine de test pour N reines):
/// <summary>
/// Test if 2 queens will be killing each oter because of their positions on the Chessgame
/// </summary>
/// <param name="NewQueenPos">Position of the new Queen placed on the game board (Position to be tested against another queen)</param>
/// <param name="OtherQueenPos">Position of an existing queen.</param>
/// <returns>True if the 2 Queens kill each other.</returns>private bool KillingPosition(int newQueenPos, int otherQueenPos)
{
// 2 Queens cannot be on the same row
int Q1Row = QueenRow( newQueenPos );
int Q2Row = QueenRow( otherQueenPos );
if( Q1Row == Q2Row)
return true;
// 2 Queens Cannot be on the same column
int Q1Col = QueenCol( newQueenPos );
int Q2Col = QueenCol( otherQueenPos );
if( Q1Col == Q2Col )
return true;
// 2 Queens Cannot be on the same "/" diagonal // ((Q1Col + Q1Row) == (Q2Col + Q2Row))
if( QueenDiag( newQueenPos ) == QueenDiag( otherQueenPos ) )
return true;
// 2 Queens Cannot be on the same "\" diagonal
// ((Q1Row - Q1Col) == (Q2Row - Q2Col))if( QueenAntiDiag( newQueenPos ) == QueenAntiDiag( otherQueenPos ) )
return true;
// The 2 queens will not kill each other.
return false;
}
/// <summary>
/// Test a new queen placed on the board to check if she is about to be killed by any of the other queens already placed on the GameBoard
/// </summary>
/// <param name="newQueenPos">The Position of the New Queen to be placed on GameBoard</param>
/// <param name="otherQueensPos">The position of all the other queens already placed on the GameBoard</param>
/// <returns>True if the new queen placed at newQueenPos is killed by an existing queen placed on the GameBoard</returns>
private bool KillingPosition(int newQueenPos, int[] otherQueensPos) {
foreach (int queenOnGameBoard in otherQueensPos)
if( KillingPosition( newQueenPos, queenOnGameBoard ) )
return true;
return false;
}
Résolution du poblème?
Armé de tout ces éléments il est maintenant possible de résoudre ce problème à l'aide de LinQ.
var Solutions =
from Q1 in Enumerable.Range( 1, 64 )
from Q2 in Enumerable.Range( 1, 64 ).Where( q2Value => !KillingPosition( q2Value, Q1 ) )
from Q3 in Enumerable.Range(1, 64).Where(q3Value => !KillingPosition(q3Value, new int[] {Q1, Q2} ))
from Q4 in Enumerable.Range(1, 64).Where(q4Value => !KillingPosition(q4Value, new int[] { Q1, Q2, Q3 }))
from Q5 in Enumerable.Range(1, 64).Where(q5Value => !KillingPosition(q5Value, new int[] { Q1, Q2, Q3, Q4 }))
from Q6 in Enumerable.Range(1, 64).Where(q6Value => !KillingPosition(q6Value, new int[] { Q1, Q2, Q3, Q4, Q5 }))
from Q7 in Enumerable.Range(1, 64).Where(q7Value => !KillingPosition(q7Value, new int[] { Q1, Q2, Q3, Q4, Q5, Q6 }))
from Q8 in Enumerable.Range(1, 64)
where !KillingPosition( Q8, new int[]{Q1, Q2, Q3, Q4, Q5, Q6, Q7})
select new int[]{ Q1, Q2, Q3, Q4, Q5, Q6, Q7, Q8 };
Par contre, contrairement à ce que je pensais, il n'y a pas que quelques solutions mes plusieurs dizaines de milliers (sans distinction des doublons).
J'ai donc interrompu l'exécution après 87.000 solutions et bricolé à la va-vite un petit code d'affichage.
A préciser, quand même, que je ne teste pas les doublons.
// LinQ expression (déjà présenté ci-dessus)
var Solutions =
from Q1 in Enumerable.Range( 1, 64 )
... ;
int iSolutionCount = 0;
// lst is a ListBoxControl display control
// Each Solution is composed of an Array of int
foreach( var Solution in Solutions ){
iSolutionCount++;
// Display a solution every 500 solutions
if (iSolutionCount > 10 )
break;
lst.Items.Add( String.Format("--- Solution #{0}", iSolutionCount ) );
// Display the positsion of Queens
foreach( int QueenPos in Solution.ToList() ){
lst.Items.Add( String.Format( " R: {0}, C: {1}. Cell: {2}", QueenRow( QueenPos ), QueenCol( QueenPos ), QueenPos ) );
}
// Display in a ChessBoard
lst.Items.Add("Queens on GameBoard:");
for (int row = 1; row <= 8; row++)
{
string s = row.ToString().PadLeft(2) + ": ";
for (int col = 1; col <= 8; col++)
{
int iCurrentCell = (row-1)*8+col;
if (Solution.Contains(iCurrentCell))
s = s + " Q,";
else
s = s + " ,";
}
lst.Items.Add(s);
}
}
Il est intéressant de noter que le code d'affichage des solutions est plus long que l'expression LinQ permettant de les identifier :-)
