This is documentation for the QUEENS.4TH file. The code is intended to be a supplement to the NOVICE.4TH and LIST.4TH files.

*******************************************************************************
*******************************************************************************
*******************************************************************************

QUEENS.4TH is a solution to the famous N-Queens problem.

The QUEENS function finds a single solution. It takes one parameter, which is the size of the board (8 for an 8x8 board). QUEENS leaves the solution on the stack. The SHOW-SOLUTION function displays this on the screen. The HEURISTIC-QUEENS function also finds a single solution, using a different algorithm. 

The ALL-QUEENS function finds all of the solutions. It takes one parameter, which is the size of the board. ALL-QUEENS stores the solutions in a linked list stored in the SOLUTIONS handle. The function SHOW-SOLUTIONS displays the solutions on the screen.

The program is currently limited to board sizes of 30x30. The algorithms used will work for any size. The 30x30 limitation is imposed only to ensure that the solution display will fit on the screen.

******
****** Algorithm.
******

I originally intended to write this code to use coroutines (see YIELD in the novice package), similar to ICON. I had Griswold's book, "The ICON Programming Language," which has an N-Queens program --- and has a picture of the solved N-Queens board on the front cover. Coroutines didn't work out at all for QUEENS because there is no consumer. They would have been possible in ALL-QUEENS, but they would have complicated the code considerably to no advantage that I could see, so I wrote ALL-QUEENS using ordinary functions too.

Because I started out intending to use coroutines, my code is iterative. Most N-Queens programs are recursive from what I've read. I do backtracking --- I just hold the data on the stack and back up over it as necessary. QUEENS and ALL-QUEENS are my own algorithm. I didn't have any reference except Griswold's book, and I couldn't figure that code out due to my lack of knowledge of ICON. I don't think my algorithm is very similar to his. My program turned out to be a pretty good demonstration of Forth functions' ability to access a variable amount of data on the stack. This would be difficult to do in C/C++ because the functions have to declare what their parameters are. A few functions, such as PRINTF and SCANF, have variable amounts of data on the stack, but this is very complicated to write and is rarely done. In Forth it is easy.

The HEURISTIC-QUEENS algorithm came from the Wikipedia article. I don't know how algorithms such as this get developed. All I did was implement the algorithm using my list package.

In the QUEENS program, I have some arrays that represent the columns and diagonals on the board (I don't need an array to represent rows, because I am incrementing through the rows). The arrays contain a TRUE if that column or diagonal is already occupied by a queen. The functions PLACE-QUEEN and REMOVE-QUEEN set the flags appropriately. The use of arrays of flags came from Griswold's book; this is the only idea in that program that I figured out. BAD-SQUARE? tell me if a square is bad, in the sense that a queen can't be placed there due to a conflict with an already-placed queen. 

In Forth, the typical way to deal with variable numbers of parameters, is to put them on the stack with a zero-sentinel underneath. This works out well in our program, because the coordinates on the board are in the range [1,size], so zero is an invalid datum and it can be used as a sentinel.

The heart of the QUEENS program is the FIND-GOOD function. This takes a stack of good coordinate pairs (possibly none) as well as a try-out coordinate-pair, and returns a stack of good coordinate pairs. FIND-GOOD may add the try-out coordinate pair (called a row/col in the comments) to the good ones. If the try-out isn't any good, the FIND-GOOD will increment the row on the try-out to obtain the next try-out (with the NEXT function) and try that one out. If FIND-GOOD runs off then end of the board, then it realizes that its existing stack of good coordinate pairs isn't any good; it is a dead end. In this case, it backs up and considers the top good coordinate pair to be a try-out, and it increments it with NEXT, and so forth. If FIND-GOOD backs up all the way to the zero sentinel, then it throws an error indicating that there is no solution. In QUEENS, this only happens if the board size is 2 or 3 --- every other size has at least one solution.

The <QUEENS> function calls FIND-GOOD repeatedly, for each row. The QUEENS function just initializes some data and provides the CATCH for FIND-GOOD's THROW, and calls <QUEENS> that does the work. This is pretty typical in my code (and all Forth code, afaik) --- there is a pointy-bracket word that does the work, and a higher-level word that sets preps it.

The ALL-QUEENS function is an extension of the QUEENS functions. The <ALL-QUEENS> function just calls FIND-GOOD repeatedly, for each row. When it gets a valid solution, it stashes this solution in the SOLUTIONS list. Then it calls TRY-ANEW. This function just removes the last good queen from the flags' arrays, and tries the next one (using NEXT). It is similar to FIND-GOOD in that it throws an error if it backs up to the zero sentinel. This happens quite often. After all of the valid solutions have been found, we continue to search for more solutions and we run into a dead end. ALL-QUEENS pretty much always exits via THROW.

ALL-QUEENS was very much complicated by the need to store the valid solutions in global memory (the SOLUTIONS list). Unfortunately, THROW restores the parameter stack, so I couldn't just leave the solutions on the stack (with DUP-STACK). I would really like to see ANS-Forth be upgraded with a THROW that doesn't restore the parameter stack, which would allow me to write search programs that leave their discovered data on the stack rather than in global memory. I don't think this will happen; the Forth-200x committee seems to be pretty much entirely focused on standardizing legacy code, which limits it to only supporting code that can be written in ANS-Forth.