Eight queens puzzle (Forth)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C | Forth

The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such that none of them attack one another (no two are in the same row, column, or diagonal). More generally, the n queens problem places n queens on an n×n chessboard.

This means of solving the N-queens puzzle uses bitmasks to represent attacks along files and diagonals. Thus, boards up to 32x32 can be represented using standard Forth cells.

[edit] Bit utilities

bits takes the board dimensions and generates a mask containing that many bits. For example, 8 bits generates 255. This is used for the initial set of unused rows.

lowBit takes a mask and returns the lowest bit. lowBit- takes that mask and removes the lowest bit. These are used to iterate through all the unused rows.

third is a common name for a stack operator that returns the third item on the stack. It is similar to over, but going one item deeper.

<<utilities>>=
 : bits ( bits -- mask ) 1 swap lshift 1- ;
 : lowBit  ( mask -- bit ) dup negate and ;
 : lowBit- ( mask -- mask ) dup 1- and ;
 : third ( a b c -- a b c a ) 2 pick ;

[edit] Recursive routine

poss returns a mask representing the possible rows on which a queen can stand. It is calculated by ANDing together the available diagonals and rows.

next3 takes the single-bit mask for the queen under consideration, and removes it from the next diagonals and row to consider for subsequent levels of recursion.

try is the recursive routine

<<recursion>>=
 variable solutions
 variable nodes
 : poss ( a b c -- a b c a&b&c ) dup 2over and and ;

 : next3 ( dl dr f Qfilebit -- dl dr f dl' dr' f' )
   invert >r
   third r@ and 2* 1+
   third r@ and 2/
   third r> and ;

 : try ( dl dr f -- )             \ bitmasks for unused diagonals and files
   dup if 1 nodes +!  poss
     begin ?dup while
       dup >r lowBit next3 recurse r> lowBit-
     repeat
   else ( .sol) 1 solutions +! then
   drop drop drop ;

[edit] Main program

queens takes a board size, calculates how many solutions there for that board, and prints the solution (along with the number for nodes visited to find the solution).

<<queens.4th>>=
utilities
recursion
 0 value N
 : queens ( n -- ) to N
   0 solutions ! 0 nodes !
   -1 dup N bits try
   N . ." queens: " solutions @ . ." solutions, " nodes @ . ." nodes" ;
Download code
hijacker
hijacker
hijacker
hijacker