3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Removed code-challenge tag since no objective winning criterion was given. \$\endgroup\$ – Howard Jan 7 '14 at 9:28
  • \$\begingroup\$ i added the objective, is it good enough? sorry, first time on this site \$\endgroup\$ – Abie Giordano Jan 7 '14 at 9:53
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Howard Jan 7 '14 at 10:40
2
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

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 |   |   |
+---+---+---+---+
\$\endgroup\$
  • \$\begingroup\$ first answer, and a nice one :) \$\endgroup\$ – Abie Giordano Jan 8 '14 at 8:17
4
\$\begingroup\$

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}].

grid

or as a board, using board[{3, 1, 4, 2}]. The black squares are those occupied by a queen.

board

solutionQ[{3, 1, 4, 2}] displays the board and whether or not that board is a solution.

solutionQ

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}]

solutions


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

\$\endgroup\$
  • \$\begingroup\$ nice explanation and graphics, great job! \$\endgroup\$ – Abie Giordano Jan 8 '14 at 8:13
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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 [];;
\$\endgroup\$
1
\$\begingroup\$

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[0],x[1],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 . . . .
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.