# n-queens problem, displaying more than one solution available

as some of you may know, n-queens problem is a set of algorithm puzzle that given a 'n x n' where n is the board size of a (let's say) chessboard, and the main goal is for the n queens (where n is the number of the queens) not be able to 'attack' one another in the board.

now I have a set of console code where user can input the board size (with an exception of less than 4x4), and the program will display one solution for the board size inputted. here's the code sample in C++:

#include <windows.h>
#include <iostream>
#include <string>

using namespace std;

class point
{
public:
int x, y;
point() { x = y = 0; }
void set( int a, int b ) { x = a; y = b; }
};

class nQueens
{
public:
void solve( int c )
{
_count = c;
int len = (c + 1) * (c + 1);
_queens = new bool[len]; memset( _queens, 0, len );
_cl = new bool[c]; memset( _cl, 0, c );
_ln = new bool[c]; memset( _ln, 0, c );
point pt; pt.set( rand() % c, rand() % c );
putQueens( pt, c );
displayBoard();
delete [] _queens; delete [] _ln; delete [] _cl;
}

private:
void displayBoard()
{
system( "cls" );
const string t = "+---+", q = "| Q |", s = "|   |";
COORD c = { 0, 0 };
HANDLE h = GetStdHandle( STD_OUTPUT_HANDLE );
for (int y = 0, cy = 0; y < _count; ++y)
{
int yy = y * _count;
for ( int x = 0; x < _count; x++ )
{
SetConsoleCursorPosition( h, c ); cout << t;
c.Y++; SetConsoleCursorPosition( h, c );
if (_queens[x + yy]) cout << q; else cout << s;
c.Y++; SetConsoleCursorPosition( h, c );
cout << t; c.Y = cy; c.X += 4;
}
cy += 2; c.X = 0; c.Y = cy;
}
}

bool checkD( int x, int y, int a, int b )
{
if ( x < 0 || y < 0 || x >= _count || y >= _count ) return true;
if ( _queens[x + y * _count] ) return false;
if ( checkD( x + a, y + b, a, b ) ) return true;
return false;
}

bool check( int x, int y )
{
if ( _ln[y] || _cl[x] )        return false;
if ( !checkD( x, y, -1, -1 ) ) return false;
if ( !checkD( x, y,  1, -1 ) ) return false;
if ( !checkD( x, y, -1,  1 ) ) return false;
if ( !checkD( x, y,  1,  1 ) ) return false;
return true;
}

bool putQueens( point pt, int cnt )
{
int it = _count;
while (it)
{
if ( !cnt ) return true;
if ( check( pt.x, pt.y ) )
{
_queens[pt.x + pt.y * _count] = _cl[pt.x] = _ln[pt.y] = true;
point tmp = pt;
if ( ++tmp.x >= _count ) tmp.x = 0;
if ( ++tmp.y >= _count ) tmp.y = 0;
if ( putQueens( tmp, cnt - 1 ) ) return true;
_queens[pt.x + pt.y * _count] = _cl[pt.x] = _ln[pt.y] = false;
}
if ( ++pt.x >= _count ) pt.x = 0;
it--;
}
return false;
}

int          _count;
bool*        _queens, *_ln, *_cl;
};

int main( int argc, char* argv[] )
{
nQueens n; int nq;
while( true )
{
system( "cls" );
cout << "Enter board size bigger than 3 (0 - 3 to QUIT): "; cin >> nq;
if ( nq < 4 ) return 0;
n.solve( nq ); cout << endl << endl;
system( "pause" );
}
return  0;
}


now, as the code only display one solution only, where 4x4 should have more than one solution available, your challenge is to make the code to be able to display more than one solution should it's possible, and displaying the 'graphic' solution (console is recommended). C++ is recommended, but other programming language is more than welcome. Good luck!

• Removed code-challenge tag since no objective winning criterion was given. – Howard Jan 7 '14 at 9:28
• i added the objective, is it good enough? sorry, first time on this site – Abie Giordano Jan 7 '14 at 9:53
• It is perfectly fine for popularity-contest to not have a objective criterion. Popularity-contest and code-challenge are mutually exclusive - either you judge by most votes or by some objective criterion (i.e. based solely on the solution, no matter how many people voted for the answer). Of course in any case a solution has to fulfill all requirements specified in the puzzle. So it's up to you what kind of challenge you want to have. – Howard Jan 7 '14 at 10:40

## Python 2.7

Nice object-oriented solution:

class Queen(object):
def __init__(self, row, col):
self.row = row
self.col = col

@property
def u(self):
'Return the SW-NE diagonal by starting row'
return self.col + self.row

@property
def v(self):
'Return the NW-SE diagonal by starting column'
return self.col - self.row

class Solver(object):
'''
Solver which iterates over solutions.  Each iterator produces a
string representation of a valid solution.
'''
def __init__(self, n):
self.n = n
self.queens = [Queen(r, 0) for r in range(n)]

def __iter__(self):
return self

def next(self):
self.step()
while not self.is_valid():
self.step()
# Draw the solution
line = ('+---' * self.n) + '+\n'
text = line
for row in range(self.n):
text += '| %s |\n' % ' | '.join(' Q'[c == self.queens[row].col] for c in range(self.n))
text += line
return text

def step(self, _row=None):
'Increment the solution one step'
if _row == -1:
raise StopIteration
if _row is None:
_row = self.n - 1
self.queens[_row].col += 1
if self.queens[_row].col == self.n:
self.queens[_row].col = 0
self.step(_row - 1)

def is_valid(self):
'Return True if the queens are all safe'
qc = len(self.queens)
return all(len(set(getattr(q, p) for q in self.queens)) == qc for p in ['row', 'col', 'u', 'v'])

if __name__ == '__main__':
n = int(raw_input('Enter n:'))
for s in Solver(n):
print(s)


## PHP

Using a simple recursive approach.

<?
function q($n,$t=[],$r=1,$S=str_repeat){
foreach($r>$n?$t:[]as$v)echo$f=$S('+---',$n)."+\n",$S('|   ',$n)."|\n"|$S(' ',$v*4-2).q; for(;$s<$n?$r-$s^abs($c=$p-$t[$s++])&&$c:q($n,$t+[$r=>$p],$r+1)?:$n>=$p+=$s=1;);echo$f; } q(4);  Sample output for $n=4:

+---+---+---+---+
|   | q |   |   |
+---+---+---+---+
|   |   |   | q |
+---+---+---+---+
| q |   |   |   |
+---+---+---+---+
|   |   | q |   |
+---+---+---+---+
+---+---+---+---+
|   |   | q |   |
+---+---+---+---+
| q |   |   |   |
+---+---+---+---+
|   |   |   | q |
+---+---+---+---+
|   | q |   |   |
+---+---+---+---+

• first answer, and a nice one :) – Abie Giordano Jan 8 '14 at 8:17

# Mathematica

The positions of n queens on an n x n chessboard can be represented as a permutation of n. For example, The permutation, {3, 1, 4, 2}, is shorthand for the idea that there are 4 queens at {{row3, col1}, {row1, col2}, {row4, col3}, {row2, col4}.

array[{3, 1, 4, 2}] returns the complete array, with 1' s now representing queens.

{{0, 1, 0, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}, {0, 0, 1, 0}}

This could be displayed as a grid through Grid@array[{3, 1, 4, 2}]. or as a board, using board[{3, 1, 4, 2}]. The black squares are those occupied by a queen. solutionQ[{3, 1, 4, 2}] displays the board and whether or not that board is a solution. array[pos_]:=ReplacePart[ConstantArray[0,{l=Length[pos],l}],Partition[Riffle[pos,Range[Length[pos]]],2]/.{{a_,b_}:> ({a,b}-> 1)}]
board[pos_]:=ArrayPlot[array[pos],ImageSize->120,Mesh-> True]

solutionQ[pos_]:=
Module[{b,safeQ, len=Length[pos],files},
b=array[pos];
safeQ[b1_]:=(Max[Tr/@Table[Diagonal[b1,k],{k,-(len-2),len-2}]])<2;
{board[pos],safeQ[b]\[And]safeQ[Reverse/@b]}]

solutions[gridSize_]:=Cases[solutionQ/@Permutations[Range[gridSize]],{_,True}][[All,1]]


## Results

Table[Print[n , " queens solutions: ", Row@solutions[n]], {n, 4, 6}] Table[Print[ "Number of solutions in a ", n, " by ", n, " table: ", solutions[n] // Length],
{n, 7, 8}]


Number of solutions in an 7 by 7 table: 40
Number of solutions in an 8 by 8 table: 92

• nice explanation and graphics, great job! – Abie Giordano Jan 8 '14 at 8:13

# Haskell (ideone)

import System.Environment (getArgs)

data Board = Board {
field :: [Int],
size :: Int
}

-- | Checks whether the board has a conflict
conflict :: Board -> Bool
conflict b = any (==x) xs || step (-1) x xs || step 1 x xs
where (x:xs) = field b
step _ _ [] = False
step s p (x:xs)
| (s+p) == x = True
| otherwise  = step (s+p) p xs

-- | Returns all boards one can get by placing a queen in the next column
place :: Board -> [Board]
place b = place' b 1
where place' b s
| s > size b        = []
| conflict newboard = rest
| otherwise         = newboard:rest
where newboard = Board newfield (size b)
newfield = s:(field b)
rest     = place' b (s+1)

-- | Returns all boards one can get for the n-th queen problem
placeAll :: Int -> [Board]
placeAll n = foldl (>>=) [Board [] n] (replicate n place)

-- | Creates a String from a board
prettyPrint :: Board -> String
prettyPrint b = unlines.map prettyLine.field$b where prettyLine n = replicate (n - 1) '.' ++ "@" ++ replicate ((size b) - n) '.' -- | Shows the first two solutions obtained by placeAll main = do [s] <- getArgs mapM_ putStrLn . map prettyPrint . take 2 . placeAll . read$ s


Sample output

$runghc nqueens.hs 12 ...........@ ........@... ..........@. .@.......... .........@.. .......@.... .....@...... ...@........ ......@..... ....@....... ..@......... @........... ..........@. ........@... ...........@ .@.......... .........@.. .......@.... .....@...... ...@........ ......@..... ....@....... ..@......... @...........$ time runghc nqueens.hs 48
..............................................@.
...........................................@....
...............................................@
.............................................@..
.........................................@......
............................................@...
..........................................@.....
........................................@.......
......................................@.........
....................................@...........
.......................................@........
.....................................@..........
...................................@............
.................................@..............
...............................@................
..................................@.............
................................@...............
..............................@.................
............................@...................
..........................@.....................
.............................@..................
...........................@....................
.........................@......................
.......................@........................
.....................@..........................
........................@.......................
......................@.........................
....................@...........................
..................@.............................
................@...............................
...................@............................
.................@..............................
...............@................................
.............@..................................
...........@....................................
..............@.................................
............@...................................
..........@.....................................
........@.......................................
.@..............................................
.........@......................................
.......@........................................
.....@..........................................
...@............................................
......@.........................................
....@...........................................
..@.............................................
@...............................................

...............................................@
.............................................@..
...........................................@....
..............................................@.
.........................................@......
............................................@...
..........................................@.....
........................................@.......
......................................@.........
....................................@...........
.......................................@........
.....................................@..........
...................................@............
.................................@..............
...............................@................
..................................@.............
................................@...............
..............................@.................
............................@...................
..........................@.....................
.............................@..................
...........................@....................
.........................@......................
.......................@........................
.....................@..........................
........................@.......................
......................@.........................
....................@...........................
..................@.............................
................@...............................
...................@............................
.................@..............................
...............@................................
.............@..................................
...........@....................................
..............@.................................
............@...................................
..........@.....................................
........@.......................................
.@..............................................
.........@......................................
.......@........................................
.....@..........................................
...@............................................
......@.........................................
....@...........................................
..@.............................................
@...............................................

runghc nqueens.hs 48  0,16s user 0,02s system 93% cpu 0,189 total


Ocaml :

let print_list list =
List.iter print_int list;
print_newline();;

let infect x y list =
let rec infect_rec x y n  = function
[] -> false
| a :: r -> if (y = a) then true
else if ( y = a + x - n ) then true
else if ( y = a - x + n ) then true
else infect_rec x y (n-1) r in
infect_rec x y (x-1) list;;

let rec add_queen x n queen =
if x > n then print_list queen
else
for i = 1 to n do
if (infect x i queen) = false
then add_queen (x+1) n (i :: queen)
done
;;

add_queen 1 8 [];;


My short but quite readable Python solution:

def nqueens(n):
def state(n):
return set((i,j) for i in range(n) for j in range(n))
def move(i,j,n):
line = lambda ci,cj: set((i+d*ci,j+d*cj) for d in range(-n,n+1))
return line(1,0) | line(0,1) | line(1,1) | line(1,-1)
def solve(n1, s=state(n), r=()):
if n1==0: yield tuple(sorted(r))
for x in s: yield from solve(n1-1, s-move(x,x,n), r+(x,))
return solve(n)


The state of computation is represented as possible moves, and a move as the possibilities is going to remove from current state, so applying a move to a state is just set difference.

Can also generate all the solutions.

Printing the (first) solution:

def sol2str(s,n):
return '\n'.join(' '.join('X' if (row,col) in s else '.' for col in range(n)) for row in range(n))

n = 8
print(sol2str(next(nqueens(n)),n))

. . . . . X . .
X . . . . . . .
. . . . X . . .
. X . . . . . .
. . . . . . . X
. . X . . . . .
. . . . . . X .
. . . X . . . .


This solution is a slight trolling, but since it's not specified what solutions are considered to be the same, I guess it should qualify :). Let the original program be compiled as queens. Then the extension is:

#!/bin/bash
queens "\$@" >tmpfile
cat tmpfile
tac tmpfile


Explanation: A mirrored solution is obviously also a solution. And it must be different from the original one: Pick a queen not positioned in the middle row from the original solution and Let (x,y) be its position (so y != n-y-1). Then the original and mirrored solutions differ at (x,n-y-1). There is a queen at (x,n-y-1) in the mirrored solution, but the position must be empty in the original one.

Groovy

s = (0..7).permutations().findAll{
def x=0,y=0
Set a=it.collect{it-x++}
Set b=it.collect{it+y++}
a.size()==it.size()&&b.size()==it.size()
}


Delivers a list of all queen solutions like this:

[ [4, 7, 3, 0, 6, 1, 5, 2],
[6, 2, 7, 1, 4, 0, 5, 3],
... ]


For graphical representation add:

s.each { def size = it.size()
it.each { it.times { print "|_" }
print "|Q"
(size-it-1).times { print "|_" }
println "|"
}
println ""
}


which looks like this (2 examples of the 92 solutions):

|Q|_|_|_|_|_|_|_|
|_|_|_|_|_|_|Q|_|
|_|_|_|Q|_|_|_|_|
|_|_|_|_|_|Q|_|_|
|_|_|_|_|_|_|_|Q|
|_|Q|_|_|_|_|_|_|
|_|_|_|_|Q|_|_|_|
|_|_|Q|_|_|_|_|_|

|_|_|_|_|Q|_|_|_|
|_|Q|_|_|_|_|_|_|
|_|_|_|_|_|Q|_|_|
|Q|_|_|_|_|_|_|_|
|_|_|_|_|_|_|Q|_|
|_|_|_|Q|_|_|_|_|
|_|_|_|_|_|_|_|Q|
|_|_|Q|_|_|_|_|_|


Explanation:

My first Groovy experiment. I am loving the closures and the conciseness of this language!

Lets take it apart:

   (0..7).permutations()


// returns a list of all permutations of the sequence [0,1,2,3,4,5,6,7]

   .findAll{


Find and return all elements for which the following closure returns true

Here is how we check if all queens are safe:

   def x=0,y=0
Set a=it.collect


Transform all integers in the permutations using the closure:

        {  it-x++ }


We need to check if 2 queens are on the same diagonal.

Mathematically a diagonally rising line is: y = x + const

   Set b=it.collect{it+y++}


A falling line is y = -x + const Our closures return const = x+y (or x-y respectively)

We add them to a Set to find duplicates. A Duplicate means 2 queens have the same function (are on the same diagonal).

   a.size()==it.size()&&b.size()==it.size() }


The last statement in the closure returns true if there are no duplicates, so all queens are safe!