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.

 : 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

 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-
   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).

 0 value N
 : queens ( n -- ) to N
   0 solutions ! 0 nodes !
   -1 dup N bits try
   N . ." queens: " solutions @ . ." solutions, " nodes @ . ." nodes" ;
Download code