Eight queens puzzle (Forth)
- 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.
 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 ;
 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 ;
 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>>= 0 value N : queens ( n -- ) to N 0 solutions ! 0 nodes ! -1 dup N bits try N . ." queens: " solutions @ . ." solutions, " nodes @ . ." nodes" ;