The "N Queens" problem

The "N Queens" problem is a puzzle where you take an NxN chequers or chess board (it's usually 8x8 but this works for the general case) on which you have to place N queens in such a way that none of them threaten or are threatened by any of the others.

Reminder: in the game of chess, a queen can move as many squares as she likes horizontally, vertically or diagonally but cannot jump over any of the other pieces on the board like a knight. This means that any piece in her direct line of sight on the same line, in the same column or on a diagonal to her is fair game.

With this in mind, it is clear that there is only one solution to the problem on a 1x1 board, i.e. a single square (you just plonk a queen on it and you're done), and that there is no way to organise two queens on a 2x2 board or three queens on a 3x3 board without them threatening each other. For a 4x4 or greater board, there is more than one solution.

I thought I'd have a go at solving the general case on an HP-71B and the program listed in its entirety below does just that. There's also a brief video of the 71B in action finding all the solutions to the problem for a 5x5 board in just over 30 seconds.

Here is a line-by-line explanation of the algorithm:

10 DESTROY ALL @ DELAY 0

Clear up any variables currently in memory and tell the 71B not to waste time pausing after displaying something on screen. This is going to be slow enough as it is :)

20 OPTION BASE 1 @ STD

I want the elements in the array that I'm creating later to be numbered from 1 onwards rather than 0, and we need integers to be displayed with no decimals or we're going to get a string overflow (and something far too long to display on screen) in line 200.

30 INTEGER R,C,S,T,F,N,K
40 REAL W

OK, let's set up a few variables.

R and C are going to represent the row and column of the square on the board where I want to see if I can place a queen.

S is the size of the board.

T will be used as a counter while I'm seeing if a queen that I place on the board is being threatened by one placed earlier on a row with a lower number.

F is the running count of solutions found so far.

N is the number of nodes of the puzzle examined so far. Each time a queen is tentatively placed on the board, this is a puzzle node.

K will be used as a counter while building the string representing the solution that was found.

W, the only real variable used here, holds the time of day when the run was started for most of the life cycle of this program. At the end it is replaced by the time, in seconds, that it took to find all the solutions to the puzzle.

50 INPUT "Board size 1-9: ";S
60 IF S>9 OR S<1 THEN 50

Ask the user what size board to work with. Anything below 1 makes no sense and anything above 9 will just take far too long to solve. It already takes about 50 minutes to solve for an 8x8 board...

70 INTEGER B(S) @ DISP "Working..."
80 R=0 @ F=0 @ N=0 @ W=TIME

We start by creating an array of integers B() with as many elements as there are rows on the board. This array will hold the number of the column where there is a queen on each row. We then display something on screen to let the user know that we've started crunching numbers. Depending on the size of the board we're working with, it can take a while to find the first solution.

We then initialize the row counter and the running counts and we make a note of the time when we started.

90 R=R+1 @ IF R>S THEN 190
100 C=0

This is the point in the algorithm where we move on to the next row. If we've only just started then the "next" row is actually the first row. Otherwise, we come here when we've successfully placed a queen on the board and we want to try and place one on the next row.

However, if we were already on the last row of the board and we try and count beyond that number, then it means that we just placed a queen on the last row, i.e. we found a solution! In this case we go off to line 190, where this situation is handled. If not, then we reset the column counter so that we can look at all of the squares in this row one after the other.

110 C=C+1 @ IF C>S THEN 170

So, we move on to the next column. If we've only just started looking at the current row then this is the first column. Otherwise it means that we couldn't place a queen in the previous column or that we could, but we're looking for solutions that involve placing her on a different square in the same row.

However, if there are no more columns, i.e. if we attempt to count beyond the size of the board, then it means that we need to backtrack a row and start looking for solutions with a queen in a different column of the previous row. This is handled in line 170.

120 T=0
130 N=N+1

We're still on the board so now we need to see if a queen placed in the square identified by R and C is safe. We're going to use the variable T as a counter iterating through all the rows previous to R to see if a queen in any of those rows would threaten one here. We also increment the variable N to indicate that we've found a new node to examine.

140 T=T+1 @ IF T>=R THEN 160

We're going to look at the next row now, but if the next row happens to be this row (R), then it means we've found no threat coming from previous rows and a queen placed on the square that we're looking at right now is safe. This is handled in line 160.

150 IF B(T)=C OR ABS(B(T)-C)=R-T THEN 110 ELSE 140

This is where we determine if the queen in row T is a threat to us in row R, column C.

Remember, the array B() holds the column numbers of the queens in each row. Thus, B(1) holds the column of the queen in row 1, B(2) that of the queen in row 2 etc. B(T) is the column of the queen in row T. If the queen in that row is in this column (if B(T)=C) then she would be a threat to us. Similarly, if she is removed from us by as many columns as rows (if the absolute value of B(T)-C is the same as R-T) then that queen is on the same diagonal as us and would be a threat. In either case, we can't place a queen on this square, so we go back to line 110 where we look at the next column.

If, however, the queen in line T would not be a threat to us then we can look at the next line by jumping back to line 140.

160 B(R)=C @ GOTO 90

If we make it here then it means that we can place a queen on row R, column C. How do we do this? By setting the relevant element of the B() array, B(R), to the column where we're placing the queen. We then go back to line 90 so that we can move on to the next row.

170 R=R-1 @ IF R=0 THEN 230
180 C=B(R) @ GOTO 110

We came here from line 110 when we tried to look at a column beyond the last one in the current row. This meant that we couldn't place a queen anywhere (else) in this row, so we have to backtrack a row and continue the search. So we start by decrementing the current row counter.

However, if we were on the first row anyway and we can't place a queen in that row now, then we have reached the end of the puzzle. There are no more solutions possible! This is handled in line 230.

If we were able to backtrack, then we set the column counter C to the column of the queen in this earlier row and we go back to line 110 so that we can look at solutions with a queen in the next column.

190 F=F+1
200 F$ = "Found " @ FOR K=1 TO S @ F$ = F$ & STR$(B(K)) @ NEXT K
210 F$ = F$ & " (" & STR$(F) & ")" @ DISP F$

We wind up here if we found a solution.

So, we start by incrementing the running count of solutions found. Lines 200 and 210 construct and display a string indicating the solution just found and the number of solutions found so far. It ends up looking something like:

Found 53142 (10)

The five digits after "Found" indicate that this was a 5x5 puzzle and that the tenth solution found (indicated by "(10)" at the end of the line) was to place a queen in each of columns 5, 3, 1, 4 and 2 of rows 1 to 5 respectively.

220 R=R-1 @ GOTO 110

Remember, we got here by incrementing R beyond the total number of rows in the puzzle (see line 90)? Before we go back into the puzzle to look at the next column of the last row, we need to decrement the row again to bring it back within the bounds of the problem. We then go back to line 110.

230 W=TIME-W @ IF W<0 THEN W=W+86400

This is the end of the puzzle!

We find out how long it took to crunch through all of the possible solutions by subtracting the time of day now from the time of day when we started in line 80. There is, however, one pitfall to this. TIME is a function that reads the clock to give you the time of day in the form of the number of seconds elapsed since midnight, to the nearest 100th of a second. This value can therefore be anything from 0.00 (dead on midnight) to 86399.99 (0.01 second before midnight). Reminder: disregarding leap seconds, there are 60x60x24=86400 seconds in a day.

What happens if you're like me and you sometimes leave a test to run its course overnight after you've gone to bed, resulting in the test starting before midnight and ending after midnight?

Say the test starts at 11:50pm and finishes at 12:10am. 11:50pm is 10 minutes (600 seconds) to midnight, so TIME will return 86400-600=85800. Come 12:10am and the end of the test, TIME will return 600, so TIME-W will be 600-85800=-85200. Congratulations on the negative test duration. You were able to complete the test 23h and 40 minutes before you started...

The HP-71B is a great machine, granted, but it hasn't quite mastered time travel yet. If the duration computed is negative then we compensate for the date flipping over by adding the number of seconds in a day to the result we found. -85200+86400=1200, which looks more like the 20 minutes expected.

240 DISP "SOLUT:" & STR$(F) & ", NODES:" & STR$(N)

We construct and display the string indicating how many solutions were found and how many nodes were examined to find them.

The short video below shows all of this in action, and the complete listing is provided below that.

As shown at the end of the video, the variable W contains the time in seconds taken to complete the puzzle, F is the number of solutions found, N is the number of nodes examined and F$ indicates the last solution found.

10 DESTROY ALL @ DELAY 0
20 OPTION BASE 1 @ STD
30 INTEGER R,C,S,T,F,N,K
40 REAL W
50 INPUT "Board size 1-9: ";S
60 IF S>9 OR S<1 THEN 50
70 INTEGER B(S) @ DISP "Working..."
80 R=0 @ F=0 @ N=0 @ W=TIME
90 R=R+1 @ IF R>S THEN 190
100 C=0
110 C=C+1 @ IF C>S THEN 170
120 T=0
130 N=N+1
140 T=T+1 @ IF T>=R THEN 160
150 IF B(T)=C OR ABS(B(T)-C)=R-T THEN 110 ELSE 140
160 B(R)=C @ GOTO 90
170 R=R-1 @ IF R=0 THEN 230
180 C=B(R) @ GOTO 110
190 F=F+1
200 F$ = "Found " @ FOR K=1 TO S @ F$ = F$ & STR$(B(K)) @ NEXT K
210 F$ = F$ & " (" & STR$(F) & ")" @ DISP F$
220 R=R-1 @ GOTO 110
230 W=TIME-W @ IF W<0 THEN W=W+86400
240 DISP "SOLUT:" & STR$(F) & ", NODES:" & STR$(N)