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

## [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 ) 1swaplshift1- ; : lowBit ( mask -- bit )dupnegateand; : lowBit- ( mask -- mask )dup1-and; : third ( a b c -- a b c a ) 2pick;

## [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>>=variablesolutionsvariablenodes : poss ( a b c -- a b c a&b&c )dup2overandand; : next3 ( dl dr f Qfilebit -- dl dr f dl' dr' f' )invert>r third r@and2* 1+ third r@and2/ third r>and; : try ( dl dr f -- ) \ bitmasks for unused diagonals and filesdupif1 nodes +! possbegin?dupwhiledup>r lowBit next3recurser> lowBit-repeatelse( .sol) 1 solutions +!thendropdropdrop;

## [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 0valueN : queens ( n -- )toN 0 solutions ! 0 nodes ! -1dupN bits try N . ." queens: " solutions @ . ." solutions, " nodes @ . ." nodes" ;

Download code |