94 lines
2.9 KiB
Text
94 lines
2.9 KiB
Text
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
|