Eight queens puzzle solutions

This article shows algorithmic solutions to the eight queens puzzle implemented in various computer programming languages. For specific outcomes of these algorithms, see the main eight queens puzzle article.

Board representations

* The naive representation is a 2-dimensional bool [N] [N] array indicating for every square whether it contains a queen.:* Partial solutions simply have less than N queens marked.:* Queen conflicts are hard to check: you need to go in all 8 directions looking for occupied squares.

* In a valid solution, there is exactly one queen in each row. So it's sufficient to use an int [N] array telling for each row at which column the queen is. This representation is more compact, efficient and easy to use.:* Queen conflicts are easier to check:::* There can be no horizontal conflicts - there is no way to represent 2 queens in the same row.::* There is a vertical conflict if any two columns in the list are equal. (In other words, a valid solution is a permutation of N numbers.)::* There is a diagonal conflict if the absolute difference between two columns in the list equals the absolute difference between their positions in the list (i.e. their rows).:* Partial solutions with queens only at first M rows (M < N) can be represented by shorter lists.

A standard backtracking solution

Backtracking improves upon brute-force search by building solutions step-by-step, and being able to discard a partial solution together with all solutions that would be built from it. This works for the 8-queens problem: we start from an empty board and add queens one-by-one; the moment we add a queen that creates a conflict, we know adding more queens will not remove the conflict, so we can avoid all solutions that would be generated from it.

A backtracking depth-first search (DFS) solution in C:
#include

intis_safe(int rows [8] , int x, int y) { int i;

for (i=1; i <= y; ++i) { if (rows [y-i] = x || rows [y-i] = x-i || rows [y-i] = x+i) return 0; }

return 1;} voidputboard(int rows [8] ) { static int s = 0; int x, y;

printf(" Solution #%d: --------------------------------- ", ++s); for (y=0; y < 8; ++y) { for (x=0; x < 8; ++x) printf(x = rows [y] ? "| Q " : "| "); printf("| --------------------------------- "); voideight_queens_helper(int rows [8] , int y){ int x;

for (x=0; x < 8; ++x) { if (is_safe(rows, x, y)) { rows [y] = x; if (y = 7) putboard(rows); else eight_queens_helper(rows, y+1); }

intmain(){ int rows [8] ;

eight_queens_helper(rows, 0);

return 0;}

The Python functions below can generate all solutions for an "n"-queens problem, using a recursive breadth-first search (BFS). Note that using BFS for the 8-queens problem is silly, since all solutions lie at the same depth (8), so there is no benefit compared to DFS &mdash; and BFS requires more memory.

# As always in Python, rows and columns are indexed from zero.

def n_queens(n, width): """ Return a list of solutions to the `n`-queens problem on an `n`-by-width board. A solved board is expressed as a list of column positions for queens, indexed by row. """ if n = 0: return # one solution, the empty list else: return add_queen(n-1, width, n_queens(n-1, width))

def add_queen(new_row, width, previous_solutions): """ Try all ways of adding a queen to a column of row `new_row`, returning a list of solutions. `previous_solutions` must be a list of `new_row`-queens solutions. """ solutions = [] for sol in previous_solutions: # Try to place a queen on each column on row new_row. for new_col in range(width): # print 'trying', new_col, 'on row', new_row if safe_queen(new_row, new_col, sol): # No interference, so add this solution to the list. solutions.append(sol + [new_col] ) return solutions

def safe_queen(new_row, new_col, sol): """ Is it safe to add a queen to `sol` at `(new_row, new_col)`? Return True if so. `sol` must be a solution to the `new_row`-queens problem. """ # Check against each piece on each of the new_row existing rows. for row in range(new_row): if (sol [row] = new_col or # same column clash abs(sol [row] - new_col) = abs(row - new_row)): # diagonal clash return 0 return 1

for sol in n_queens(8, 8): print sol

A constraint logic programming solution

The constraint logic programming (over finite domains) approach to this kind of problem is very efficient. The GNU Prolog program below resolved a 100-queens problem in less than a tenth of a second. It finds a permutation of the first "n" naturals such that the distance between any two is not the normal distance (for example, 1 is normally three away from 4).

/* Generates a list which represents a single solution with the specified length and ensures that the list has each value from 1 to N once and only once. */nqueens(N,Ls) :- length(Ls,N), fd_domain(Ls,1,N), fd_all_different(Ls), constraint_queens(Ls), fd_labeling(Ls, [variable_method(random)] ).

/* Ensures that all positions are valid */constraint_queens( [] ).constraint_queens( [X|Xs] ) :- noattack(X,Xs,1), constraint_queens(Xs).

/* Ensures that no queens share diagonals */noattack(_, [] ,_).noattack(X, [Y|Xs] ,N) :- X#=Y+N, X#=Y-N, T=N+1, noattack(X,Xs,T).

An iterative solution

The following J verb generates all solutions for an "n"-queens problem, using an iterative approach.

queens=: 3 : 0 z=.i.n,*n=.y. for. }.z do. b=. -. (i.n) e."1 ,. z +"1 _ ((-i.){:$z) */ _1 0 1 z=. ((+/"1 b)#z),.(,b)#(*/$b)$i.n end. )

A "k"-arrangement x has "k" queens on a "k"-by-"n" board where none ofqueens attack each other. To generate all "k+1"-arrangements leading from x,place a queen on all the places on row "k" which are not on the any of the columns or diagonals attacked by the queens in x. The "1"-arrangements are 0, 1, 2, ..., "n"-1; the "n"-arrangements are all the solutions to the "n"-queens problem.

For example, 0 2, 0 3, and 0 4 are valid 2-arrangements for the 8-queens problem. The 3-arrangements leading from these are: 0 2 4 0 2 5 0 2 6 0 2 7 0 3 1 0 3 5 0 3 6 0 3 7 0 4 1 0 4 6 0 4 7

Here is a C# example, built on the .NET Framework 2.0, for an iterative approach. public class Queens { List position; int queens = 8;

///

/// Class that holds the position information for a piece ///

protected class PiecePosition { int _column; int _row;

public PiecePosition(int column, int row) { _column = column; _row = row; }

public int Column { get { return _column; } set { _column = value; } }

public int Row { get { return _row; } set { _row = value; } }

public bool IsOrigin { get { return _column = 0 && _row = 0; } }

public bool IsCrossSection { get { return _column = _row; } } }

///

/// Main method outputs to the console ///

/// Number of queens to solve for public void Solve(int NoOfQueens) { int iterations = 0; queens = NoOfQueens;

position = new List(); int conflictIndex, newConflictIndex; PlaceQueens();

conflictIndex = GetHighestConflict(-1); PiecePosition newPiecePosition; while (conflictIndex > -1) { newPiecePosition = GetLowestConflictPosition(conflictIndex); if (newPiecePosition = null) break; position [conflictIndex] = newPiecePosition;

if (iterations > (queens *2 )) { iterations = 0; PlaceQueens(); }

newConflictIndex = GetHighestConflict(-1); if (newConflictIndex = conflictIndex) conflictIndex = GetHighestConflict(newConflictIndex); else conflictIndex = newConflictIndex;

iterations++; } Console.WriteLine("-----------------------------------------------------------------"); Console.WriteLine("{0} x {0} board", queens); Console.WriteLine("{0} steps needed", iterations); for (int index = 0; index < queens; index++) { Console.WriteLine("{0} : {1} ", new object [] { position [index] .Column, position [index] .Row }); }

Console.WriteLine("-----------------------------------------------------------------"); }

///

/// Places the queens one per column and one per row on the chessboard, . ///

protected void PlaceQueens() { int [] pos = new int [queens] ;

for (int i = 0; i < queens; i++) { pos [i] = i; }

for (int i = 0; i < queens; i++) { pos = Shuffle(pos); }

position.Clear(); for (int i = 0; i < queens; i++) { position.Add(new PiecePosition(i, pos [i] )); } }

///

/// Gets the Piece with the highest number of conflicts. ///

/// Is the index of the piece to skip if it returns as the highest more than once /// the index of the piece with the highest number of conflicts. protected int GetHighestConflict(int SkipIndex) { int conflictCount = 0; int highest = 0; int pos = -1; for (int pieceIndex = 0; pieceIndex < queens; pieceIndex++) { if (pieceIndex = SkipIndex) continue;

conflictCount = GetPieceConflicts(pieceIndex);

if (highest < conflictCount) { highest = conflictCount; pos = pieceIndex; } }

return pos; }

///

/// Gets the number of conflicts a piece has. ///

/// Index of piece being checked /// Number of conflicts protected int GetPieceConflicts(int index) { int conflicts = 0; for (int pieceIndex = 0; pieceIndex < queens; pieceIndex++) { if (pieceIndex = index) continue;

if ((position [index] .Row = position [pieceIndex] .Row) || (position [index] .Column = position [pieceIndex] .Column)) conflicts++; else if (AreDiagonal(position [index] , position [pieceIndex] )) conflicts++; }

return conflicts; }

///

/// Gets the number of conflicts that a position has. ///

/// Column of the position /// Row of the position /// Number of conflicts protected int GetPositionConflicts(int column, int row) { int conflicts = 0; for (int i = 0; i < queens; i++) { if ((row = position [i] .Row) || (column = position [i] .Column)) conflicts++; else if (AreDiagonal(new PiecePosition(column, row), position [i] )) conflicts++; }

return conflicts; }

///

/// Gets the position in the same column as the chosen piece that has the least number of conflicts ///

/// Index of the piece /// New piece position protected PiecePosition GetLowestConflictPosition(int index) { int conflictCount = 0; int lowest = 7; int row = -1; for (int iRow = 0; iRow < queens; iRow++) { if (iRow = position [index] .Row) continue;

conflictCount = GetPositionConflicts(position [index] .Column, iRow);

if (lowest > conflictCount) { lowest = conflictCount; row = iRow; } } if (row < 0) return null; else return new PiecePosition(position [index] .Column, row); }

///

/// Shuffles an array ///

/// The array to be shuffled protected int [] Shuffle(int [] arr) { int curValue = 0, newPos = 0; Random rand = new Random(); int max = arr.Length; for (int i = 0; i < max; i++) { newPos = rand.Next(0, max); curValue = arr [i] ; arr [i] = arr [newPos] ; arr [newPos] = curValue; }

return arr; }

///

/// Determines if two pieces are diagonal from each other ///

/// First piece /// Second piece /// Boolean true if they are diagonal, or false if they are not protected static bool AreDiagonal(PiecePosition piece1, PiecePosition piece2) { if (piece1.IsCrossSection && piece2.IsCrossSection) return true; else if (piece1.IsOrigin || piece2.IsOrigin) return false;

int diffRow = Math.Abs(piece1.Row - piece2.Row); int diffCol = Math.Abs(piece1.Column - piece2.Column);

return diffRow = diffCol; } }