Eight queens puzzle (Forth)
From LiteratePrograms
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 is a standard depth-first backtracking solution to the N queens problem. It uses bitmasks for the lists, thus it will only work for values of N less than or equal to the cell size of your Forth (usually 32 bits).
Contents |
Board Representation
We track the available files in the current rank with bitmasks in which a '1' bit represents a safe file, and a '0' bit represents a file which is under attack by one or more queens. We use three bitmasks, one for each of the three possible angles of attack. One bitmask represents the files which already contain a queen (and thus are under attack vertically). The other two bitmasks represent the files which are under attack on a diagonal. These two bitmasks are shifted over by one bit when we move to the next rank.
Thus an empty board of size N consists of diagonals which are all clear (all '1' bits for easier shifting), and N clear vertical files.
<<board manipulation>>= \ board is left-diagonal, right-diagonal, and vertical attacks. : board ( n -- l r v ) >r -1 -1 1 r> lshift 1- ;
To get the safe positions in the current rank, we simply use a bitwise AND to keep only the files which are not under attack from any angle. We also have two fancy bit-manipulation words (which depend on twos-complement math) to get the first '1' bit (file) from the set, and to clear the first '1' bit so we can move on to trying the next one.
<<board manipulation>>= : safe-files ( l r v -- l r v files ) dup 2over and and ; : first ( files -- first-file ) dup negate and ; : rest ( files -- files' ) dup 1- and ;
When we recurse, we want to make a copy of the board (leaving the old copy for backtracking), add a queen in the current rank, and move up to the next rank. So we take a bit representing the file in which to place the new queen, clear that bit in all three bitmasks, and shift the bitmasks representing diagonal attacks to get the bitmasks for the next rank.
<<board manipulation>>= : place-queen ( l r v file -- l r v l' r' v' ) invert >r 2 pick r@ and 2* 1+ 2 pick r@ and 2/ 2 pick r> and ;
The Recursive Solver
Now it's pretty straightforward to write the actual solver. If all files contain a queen (i.e. are under attack), we have a solution. Otherwise, we recurse over all safe files.
<<solver>>= : try ( l r v -- ) dup 0= if count solution else count position safe-files begin ?dup while dup >r first place-queen recurse r> rest repeat then drop drop drop ;
Then we wrap the recursive part in a top-level loop:
<<solver>>= : queens ( n -- ) clear counts dup board try . ." queens: " show counts ;
Counting
We use two variables to keep track of how many solutions are found and how many partial positions we looked at to find them.
<<counters>>= variable positions variable solutions
<<count solution>>= 1 solutions +!
<<count position>>= 1 positions +!
<<clear counts>>= 0 solutions ! 0 positions !
<<show counts>>= solutions @ . ." solutions (tried " positions @ . ." positions)."
Miscellany
Forth requires words to be defined before they can be used, so we have to declare everything in the right order.
<<queens.4th>>= board manipulation counters solver
| Download code |