

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


divert(-1)
 
The following macro find one solution to the eight-queens problem:
 
define(`solve_eight_queens',`_$0(1)')
define(`_solve_eight_queens',
`ifelse(none_of_the_queens_attacks_the_new_one($1),1,
            `ifelse(len($1),8,`display_solution($1)',`$0($1`'1)')',
        `ifelse(last_is_eight($1),1,`$0(incr_last(strip_eights($1)))',
                `$0(incr_last($1))')')')
 
It works by backtracking.
 
Partial solutions are represented by strings. For example, queens at
a7,b3,c6 would be represented by the string "736". The first position
is the "a" file, the second is the "b" file, etc. The digit in a given
position represents the queen's rank.
 
When a new queen is appended to the string, it must satisfy the
following constraint:
 
define(`none_of_the_queens_attacks_the_new_one',
       `_$0($1,decr(len($1)))')
define(`_none_of_the_queens_attacks_the_new_one',
       `ifelse($2,0,1,
               `ifelse(two_queens_attack($1,$2,len($1)),1,0,
                       `$0($1,decr($2))')')')
 
The `two_queens_attack' macro, used above, reduces to `1' if the
ith and jth queens attack each other; otherwise it reduces to `0':
 
define(`two_queens_attack',
`pushdef(`file1',eval($2))`'dnl
pushdef(`file2',eval($3))`'dnl
pushdef(`rank1',`substr($1,decr(file1),1)')`'dnl
pushdef(`rank2',`substr($1,decr(file2),1)')`'dnl
eval((rank1) == (rank2) ||
     ((rank1) + (file1)) == ((rank2) + (file2)) ||
     ((rank1) - (file1)) == ((rank2) - (file2)))`'dnl
popdef(`file1',`file2',`rank1',`rank2')')
 
Here is the macro that converts the solution string to a nice display:
 
define(`display_solution',
`pushdef(`rule',`+----+----+----+----+----+----+----+----+')`'dnl
rule
_$0($1,8)
rule
_$0($1,7)
rule
_$0($1,6)
rule
_$0($1,5)
rule
_$0($1,4)
rule
_$0($1,3)
rule
_$0($1,2)
rule
_$0($1,1)
rule`'dnl
popdef(`rule')')
define(`_display_solution',
`ifelse(index($1,$2),0,`|  Q ',`|    ')`'dnl
ifelse(index($1,$2),1,`|  Q ',`|    ')`'dnl
ifelse(index($1,$2),2,`|  Q ',`|    ')`'dnl
ifelse(index($1,$2),3,`|  Q ',`|    ')`'dnl
ifelse(index($1,$2),4,`|  Q ',`|    ')`'dnl
ifelse(index($1,$2),5,`|  Q ',`|    ')`'dnl
ifelse(index($1,$2),6,`|  Q ',`|    ')`'dnl
ifelse(index($1,$2),7,`|  Q ',`|    ')|')
 
Here are some simple macros used above:
 
define(`last',`substr($1,decr(len($1)))')        Get the last char.
define(`drop_last',`substr($1,0,decr(len($1)))') Remove the last char.
define(`last_is_eight',`eval((last($1)) == 8)')  Is the last char "8"?
define(`strip_eights',
  `ifelse(last_is_eight($1),1,`$0(drop_last($1))',
          `$1')')           Backtrack by removing all final "8" chars.
define(`incr_last',
       `drop_last($1)`'incr(last($1))')      Increment the final char.
 
The macros here have been presented top-down. I believe the program
might be easier to understand were the macros presented bottom-up;
then there would be no "black boxes" (unexplained macros) as one reads
from top to bottom.
 
I leave such rewriting as an exercise for the reader. :)
 
divert`'dnl
dnl
solve_eight_queens