N-Queens problem

By Michael Doornbos

October 12, 2023 - 7 minutes read - 1473 words

N-Queens Problem

The N-Queens problem is a classic in computer science. Place N queens on an NxN chessboard such that no queen can attack another queen.

Wut.

Imagine you’ve got a chessboard and a bunch of queen pieces. Your mission is to place these queens on the board so that none of them can attack each other. That means no two queens can be in the same row, column, or diagonal. It’s like a puzzle where you’ve got to keep the peace in the royal family by making sure each queen has her own personal space.

Backtracking

There are A LOT of combinations to try. So how do we solve this?

Backtracking.

Imagine you’re solving this puzzle with a real chess board and 8 Queen pieces. You place a piece, check if it fits, and if it doesn’t, you take it back and try another one. That’s backtracking in a nutshell.

Backtracking is a go-to method for tackling problems where you have a bunch of rules to follow—think Sudoku, maze-solving, or even … arranging queens on a chessboard so they don’t attack each other. You start by picking an option and move forward step-by-step, always checking if you’re still playing by the rules.

The moment you realize you’ve hit a dead-end, you backtrack—rewind to the last point where you still had other options to explore and try a different route. You keep doing this until you find a solution or exhaust all your options.

It’s all about building up potential answers piece by piece and knowing when to say, “This isn’t working, let’s pivot.”

Recursive Backtracking vs Iterative Backtracking

There are two main ways to implement backtracking: recursive backtracking and iterative backtracking.

Iterative Backtracking: The Methodical Explorer

Imagine Iterative Backtracking as that friend who plans every detail of a road trip. They’ve got a map, a checklist, and they tick off each point as they go. If they hit a roadblock, no worries! They just backtrack to the last fork in the road and try a different path. It’s all very organized, like a well-oiled machine. They don’t need to ask for directions because they’ve got their trusty map (a.k.a. a loop in the code) to guide them.

Recursive Backtracking: The Free-Spirited Wanderer

Now, Recursive Backtracking is more like that spontaneous friend who says, “Let’s just drive and see where the road takes us!” They dive headfirst into the maze of life, making choices on the fly. And if they hit a dead-end? No biggie! They’ve got this magical ability to “remember” their last decision point (thanks to the call stack) and just zip back to try something new. It’s like having a built-in time machine!

The Showdown: Iterative vs Recursive

So, which one’s better? Well, it depends on what you’re into. If you like keeping things neat and structured, go for Iterative. It’s usually easier on your computer’s memory too. But if you’re all about that dive-deep-and-see-what-happens vibe, Recursive is your jam. Just keep in mind, it can be a bit heavy on the memory, like trying to remember every turn on a cross-country road trip.

In the end, both methods get you where you want to go; they just take different routes to get there. So, whether you’re a planner or a wanderer, there’s a backtracking style that’s just right for you! 🌟

On the Commodore 64, we’re going to use iterative backtracking because we’re limited on memory. In practice you can only recurse about 25 times before you run out.

Commodore BASIC Program


3 PRINT CHR$(5):PRINT CHR$(147): PRINT "N-QUEENS PROBLEM SOLVER"
4 PRINT "ENTER BOARD SIZE (4-8): ";: INPUT BS : REM GET BOARD SIZE
5  TI$="000000": CT = 0 : REM COUNT OF SOLUTIONS
10 CL=0:BT=0: REM LOOP, BACKTRACK COUNTER
20 DIM Q(BS) : REM QUEEN POSITIONS
30 FOR I=1 TO BS: Q(I)=0: NEXT I
40 C=1 : R=1: REM INITIAL ROW, COLUMN
50 FL=0
60 REM CHECK FOR ATTACKS
65 FOR I=1 TO C-1
70   IF Q(I)=R OR ABS(Q(I)-R)=C-I THEN GOTO 150
75  CL=CL+1
80 NEXT I
90 Q(C)=R : REM PLACE QUEEN
95 IF C=1 AND R=1 AND FL=1 THEN 600 : REM ALL SOLUTIONS FOUND
100 IF C=BS THEN GOSUB 200: REM ALL QUEENS PLACED, PRINT BOARD
105 FL=1 : REM SET FLAG TO INDICATE FIRST SOLUTION FOUND
110 C=C+1 : REM MOVE TO NEXT COLUMN
120 R=1 : REM RESET ROW TO 1
130 GOTO 60
140 REM BACKTRACK
150 R=R+1
155 REM GOSUB 500 : UNCOMMENT TO WATCH LOOPS
160 IF R>BS THEN GOSUB 300 : REM BACKTRACK SUBROUTINE
170 GOTO 60 : REM CHECK FOR ATTACKS
200 REM PRINTING THE BOARD
205 CT=CT+1 : REM INCREMENT SOLUTION COUNTER
207 PRINTCHR$(147) : REM CLEAR SCREEN
210 PRINT "SOLUTION:"; CT : PRINT: REM PRINT SOLUTION NUMBER
215 REM GOTO 285 : REM UNCOMMENT TO SKIP TO PRINT Q ARRAY ONLY
220 FOR I=1 TO BS 
230   FOR J=1 TO BS
240     IF Q(I)=J THEN PRINT "Q";: GOTO 260
250     PRINT "-"; 
260   NEXT J
270   PRINT
280 NEXT I
285 PRINT:GOSUB 500 : REM PRINT Q ARRAY
290 RETURN
300 REM BACKTRACKING SUBROUTINE
305 BT=BT+1: REM INCREMENT BACKTRACK COUNTER
310 C=C-1 : REM MOVE BACK TO PREVIOUS COLUMN
330 R=Q(C)+1 : REM MOVE TO NEXT ROW
340 Q(C)=0 : REM REMOVE QUEEN
350 IF R>BS THEN GOSUB 300 : REM BACKTRACK AGAIN
360 RETURN
500 REM PRINT Q ARRAY
510 FOR K=1 TO BS
520 PRINT MID$(STR$(Q(K)),1);
530 NEXT K
540 PRINT
550 RETURN
600 PRINT:PRINT:PRINT CT"SOLUTIONS FOUND":PRINT"TIME: ";:?TI/60/60;" MINUTES"
610 PRINT "BACKTRACKS: ";BT
620 PRINT "LOOPS: ";CL:END
625 FORI=1TO92:PRINTA$(I);:NEXTI

How this works

Here’s a line-by-line explanation:

Initialization and Input

Line 3: Clears the screen and prints the title “N-QUEENS PROBLEM SOLVER”.
Line 4: Asks the user to input the board size (BS) between 4 and 8.
Line 5: Initializes the time (TI$) and solution counter (CT).

Variable Setup

Line 10: Initializes loop (CL) and backtrack (BT) counters.
Line 20: Declares an array Q to hold queen positions.
Line 30: Initializes all elements of Q to 0.
Line 40: Initializes the current column (C) and row (R) to 1.
Line 50: Initializes a flag (FL) to 0.

Main Loop for Checking Attacks

Line 60-80: Loops through each column to check if the current queen (R) is attacking any other queen.
Line 90: Places the queen at the current row and column.
Line 95: Checks if all solutions have been found.
Line 100: If all queens are placed, it prints the board.
Line 105-130: Moves to the next column and resets the row, then goes back to checking for attacks.

Backtracking

Line 140-170: If a queen can’t be placed, it backtracks to the previous column and tries the next row.

Printing the Board

Line 200-290: Prints the current solution board and increments the solution counter.

Backtracking Subroutine

Line 300-360: Handles the backtracking logic, moving back to the previous column and trying the next row.

Debugging and Output

Line 500-550: Prints the Q array for debugging.

Line 70

This is the real meat of the program. The program checks if the current queen is attacking any other queen. If the current queen is attacking any other queen, the program backtracks and tries the next row.

Here’s the breakdown:

Q(I): The row position of the queen in the Ith column.
R: The row position of the queen in the current column C.
C: The current column where you’re trying to place a new queen.
I: The column you’re checking against, which is less than C.

The line checks for two conditions:

Q(I)=R: This checks if another queen is already present in the same row R. If true, the queens would attack each other horizontally.
ABS(Q(I)-R)=C-I: This checks for diagonal attacks. The absolute difference between the rows of the two queens (ABS(Q(I)-R)) is compared to the difference between their columns (C-I). If these are equal, then the queens are on the same diagonal and would attack each other.

If either of these conditions is true, the program jumps to line 150, which is the beginning of the backtracking logic. This means that placing a queen in the current row R and column C would result in an attack, so the algorithm needs to try the next row.

Results

Pretty neato right?

9-Queens

This will solve for any board size. These are easy for a modern computer to solve, but on a home computer from 1983, it’s an interesting challenge. Let’s add 1 more square to the board and see what happens.

Just under 2 hours, not bad!

Extra credit

Try to solve for 10 queens.
Port this to other old computers and see how they do.
Try to solve this in a different language.

Can you make this faster? Can you make it more efficient? Can you make it more readable?

Double dog dare you. Have fun!

Resources

https://en.wikipedia.org/wiki/Eight_queens_puzzle