John F. Dumas Vulcan Ware
_blank_
n queens
 queens.cpp - Solving the 'n' queens problem

 This program is a generalization of the classic computer
 science problem:

    How many ways can 8 queens be arranged on a chess board
    such that no queen can capture any of the others?

 Here is an example of a solution to the 8 queens problem

    [ ][ ][ ][ ][Q][ ][ ][ ]
    [ ][ ][ ][ ][ ][ ][Q][ ]
    [ ][Q][ ][ ][ ][ ][ ][ ]
    [ ][ ][ ][ ][ ][Q][ ][ ]
    [ ][ ][Q][ ][ ][ ][ ][ ]
    [Q][ ][ ][ ][ ][ ][ ][ ]
    [ ][ ][ ][Q][ ][ ][ ][ ]
    [ ][ ][ ][ ][ ][ ][ ][Q]

 Note that no row or column contains more than one queen
 and that there are no diagonal collisions either.

 The "no row or column contains more than one queen" gives a
 hint as to how to attack this problem.  Consider a row
 of cells containing the numbers from 1 -> 8.

              [3][6][4][2][8][5][7][1]
 cell number:  1  2  3  4  5  6  7  8

 Treating the cell number as the column and the contained
 value as the row, we can see that the above cells correspond
 the the 8 queens solution shown above.

 Note that the row of cells is simply a permutation of
 the numbers from 1 -> 8.  Given that no two queens
 can share a row or a column, the set of all permutations
 of the numbers from 1 -> 8 represent a set of possible
 solutions to the 8 queens puzzle.

 Of course, we'll have to ensure that each permutation
 does not produce diagonal queen collisions but we've
 now reduced this problem from a truly staggering number
 of possible solutions:

    (64 * 63 * 62 * 61 * 60 * 59 * 58 * 57)
    --------------------------------------- => 4,426,165,368
           (8 * 7 * 6 * 5 * 4 * 3 * 2)

 To a far more manageable number:

    8! => (8 * 7 * 6 * 5 * 4 * 3 * 2) => 40,320

 So, instead of investigating more than 4 billion possible
 solutions, we've reduced that number down by more than 100,000
 times to a more manageable 40,320.

 For each candidate solution, to check the diagonals
 we start with an empty chess board:

    [ ][ ][ ][ ][ ][ ][ ][ ]
    [ ][ ][ ][ ][ ][ ][ ][ ]
    [ ][ ][ ][ ][ ][ ][ ][ ]
    [ ][ ][ ][ ][ ][ ][ ][ ]
    [ ][ ][ ][ ][ ][ ][ ][ ]
    [ ][ ][ ][ ][ ][ ][ ][ ]
    [ ][ ][ ][ ][ ][ ][ ][ ]
    [ ][ ][ ][ ][ ][ ][ ][ ]

 And as we examine the position of each queen we "mark off"
 all the diagonals representing spaces she could capture.
 Using our earlier solution, going position-by-position
 where 'x' represents a capturable position ...

    [ ][ ][ ][ ][ ][x][ ][ ]
    [ ][ ][ ][ ][x][ ][ ][ ]
    [ ][ ][ ][x][ ][ ][ ][ ]
    [ ][ ][x][ ][ ][ ][ ][ ]
    [ ][x][ ][ ][ ][ ][ ][ ]
    [Q][ ][ ][ ][ ][ ][ ][ ]
    [ ][x][ ][ ][ ][ ][ ][ ]
    [ ][ ][x][ ][ ][ ][ ][ ]

    [ ][ ][ ][x][ ][x][ ][ ]
    [x][ ][x][ ][x][ ][ ][ ]
    [ ][Q][ ][x][ ][ ][ ][ ]
    [x][ ][x][ ][ ][ ][ ][ ]
    [ ][x][ ][x][ ][ ][ ][ ]
    [Q][ ][ ][ ][x][ ][ ][ ]
    [ ][x][ ][ ][ ][x][ ][ ]
    [ ][ ][x][ ][ ][ ][x][ ]

 and so on through all 8 positions.  Because no queen's
 position lands on an 'x', we've found a solution.

 To compile this program:

    unix:
       g++ -W -Wall -o queens queens.cpp

    win32:
       cl -W3 -GX queens.cpp

 Running the program without arguments presents solutions
 to the 8 queens problem, if run with a positive integer
 argument 'N' then solutions to the 'N' queens problem
 are presented.
              

Source Code


Return to Main