solving the 8 Queens Puzzle Using Recursion

BlitzMax Forums/BlitzMax Tutorials/solving the 8 Queens Puzzle Using Recursion

TomToad(Posted 2008) [#1]
Solving the 8 Queens puzzle using recursion

The Puzzle

The 8 Queens puzzle is an old puzzle created in 1848 by Max Bezzel. The idea is to try and place 8 queens on a standard 8x8 chessboard so that no queen is attacking another queen.
I am going to show you how to solve this problem by writing a program using recursion. If you haven't tried solving this puzzle before, you might want to give it a try on your own before having the solution spoiled by the program.

Solving the Puzzle

There are several ways to go about solving this problem. One way would be to put the queens on the board in some random combination, then see if that combination results in a solution. If not, then replace the queens in another, untried combination. Since there are 178,462,987,637,760 possible combinations, that will potentially take a lot of time to compute. In the worse case scenario, being there is no possible solutions, if the computer calculates 100 combinations per millisecond, then it would take over 56 years to go through all the combinations.
I am going with a much simpler method. My program will place each queen on the board one by one. If a queen is successfully placed on the board, then the program will try the next queen. If there are no spaces the queen can be placed on, then the program will go back to the previous queen and move it to a new location, then try the next queen again. If the previous queen has gone through all possible locations without a solution being found, then the program will backtrack to the queen before that and move it, and so on.
To make the program even better, we can use the fact that no two queens can occupy the same row and therefore each row must contain one queen. That reduces the number of possible combinations to 16,777,216. Now the program will only take, worse case senario, about 15 minutes.
Not only that, but if a queen cannot be placed anywhere on it's row, there is no sense on checking where the next queen should go. Also, since each queen will be placed in order, you only need to check for capture on the rows that contain a queen already. Now I'm not completely sure how many checks I'd need in a worse case scenario, but I wrote a version of the solver that finds all possible solutions, not just any solution, which would take the same amount of time as no solutions. It took 13 milliseconds to find them all on my 1.5 Ghz Intel Celeron laptop.
There is a method which is even faster, but this tutorial is meant to teach you how to solve problems with recursion. The faster method will only work for the 8 queens puzzle and most likely you won't be able to apply it to solving other puzzles. However, I did put an example of this method at the end so you can see what it looks like.

Recursion

Now to talk a little bit about what recursion is. Basically, recursion is when a function calls itself, or when a function calls another function that eventually calls the calling function. Here are two examples of recursive functions:
Function A()
	A()
End Function
Function A()
	B()
End Function

Function B()
	A()
ENd Function


If you are still confused about what recursion is, just go back and read the section titled "recursion."

We will be using recursion in our program by having a function call itself every time another queen is to be placed. If the queen is placed successfully, then it will call itself again for the next queen. If it fails to place the queen, then the function will return, backing up to the previous call which still holds the placement of the previous queen.

The Program
First and foremost, we are going to put Superstrict at the top of our code. Using Superstrict will help prevent us from making some of the most common mistakes in the program. It will also flag the compiler to create a more optimized, and therefor faster, program. Next we will define a constant which will be the number of queens we want. This way, we can later change the constant to solve for 6 queens on a 6x6 board, or 20 queens on a 20x20 board. After that, we will create an array for the board.
SuperStrict
Const n:Int = 8
Global Board:Int[n,n]

Next we will define the function to place the queens. The function will take for it's parameter the row it will check. If the function cannot place a queen in that row, then it will return false to indicate a failure. If it succeeds in placing a queen in that row, and all successive queens succeed in being placed, then the function will return True.
Function Test:Int(Row:Int)

Next we will define a variable to hold the current column we are checking and initialize it to 0 (the first column)
	Local col:Int = 0 'initialize to the first column

After that, we will use a While/Wend loop to iterate through all the columns
	While col < n 'keep looping until all columns are checked

Now we need to define a variable which will flag if a capture is found or not, and initialize it to False.
		Local Capture:Int = False 'initialize the capture flag to False

Next we check if the queen is the first one. If it is, there is no need to check if a capture is possible since there are no other queens on the board.
		If Row > 0 'First row doesn't need to check for capture

Now we check if the queen is in position to capture another queen. We check first if another queen is in it's column. If so, we set the capture flag to True.
			'test column
			For Local r:Int = 0 To Row - 1
				If Board[r,col] 'Queen here?
					Capture = True
					Exit
				End If
			Next

We only need to check from the first row up to the current row. There is no need to check higher rows since those queens have not been placed.
Next we will check the diagonals, first up and to the left, then up and to the right, stopping when either a capture has been found or the board's edge has been reached. Before we check, we first test to see if the capture flag is set. If a capture has already been found, there is no need to test for another one.
			'test to the left
			If Not capture
				For Local r:Int = Row - 1 To 0 Step -1
					Local c:Int = col - (Row - r)
					If c < 0 Then Exit 'if off board, exit loop
					
					If Board[r,c]
						Capture = True
						Exit
					End If
				Next
			End If
			'test to the right
			If Not capture
				For Local r:Int = row - 1 To 0 Step -1
					Local c:Int = col + (Row - r)
					If c >= n Then Exit 'check if off board
					
					If Board[r,c]
						Capture = True
						Exit
					End If
				Next
			End If
		End If

Now if we get this far without a capture found, we can store this position in the array and call the function for the next queen.
But first we need to check if this is the last queen or not. If it is the last queen, then the puzzle has been solved and we can return from this function with True. If it is not the last queen, then we call the function and test for the return condition. If True has been return, that means that all successive queens has been placed and we can return True back to the next lower level.
		'Was a capture detected from this column?
		If Not Capture 'no
			If Row < n-1 'check for last row
				Board[Row,col] = True 'Flag queen in this position
				If Test(Row + 1) Then Return True 'Place a queen on the next row.  Return success if all successive queens can be placed
			Else 'We are on the last row and the puzzle has been solved
				Board[Row,col] = True 'Place queen
				Return True 'Puzzle is solved
			End If
		End If

Now if a capture has been detected or successive rows could not be placed successfully, then we add one to the column number and continue the loop to try again.
		'if we are here, that means a capture has been detected or succeeding rows could not be completed
		Board[Row,col] = False 'remove queen from this position
		col :+ 1 'try next column
	Wend

When all the columns have been tried, the loop will exit. We then return False to indicate failure. That is all, so we end the function.
	'if we are here, all columns have been tried and failed.  So we return false
	Return False
End Function

Now we need to kick off the function by calling it with Row 0 and storing the result
Local Result:Int = test(0) 'Start the whole thing off

If the function returns True, a solution has been found and the array holds the solution, so we then display it. If it returns false, then no solution was found and we print that out.
If Result 'A solution has been found
	Graphics 800,600
	Local width:Int = 600/n

	While Not KeyHit(KEY_ESCAPE) And Not AppTerminate()
		Local StartColor:Int = False

		For Local x:Int = 0 To n-1
			Local White:Int = StartColor
			For Local y:Int = 0 To n-1
				If white
					SetColor 255,255,255
					white = False
				Else
					SetColor 0,0,0
					white = True
				End If
				DrawRect x*Width,y*width,Width,Width
				If Board[y,x]
					SetColor 255,0,0
					DrawOval x*Width,y*Width,Width,Width
				End If
			Next
			If StartColor
				StartColor = False
			Else
				StartColor = True
			End If
		Next
		Flip
	Wend
Else 'no solution found
	Print "No solution found!"
End If

The entire program looks like this


Playing around with the program

Now run the program and see the solution for the 8 queens puzzle. Actually there are 92 solutions, this program displays only the first one it finds. For a nice little project, try modifying the program to find and display all 92.

You can also experiment by changing the constant to another value. Try changing it to 3 and find the solution for 3 queens on a 3x3 board (hint, there is none. There are only solutions for n=1 or n > 3). Try finding the solution for 20 queens on a 20x20 board. How about 30 queens? You might find that calculating the solution for that many queens will take longer than you want to wait (unless you are on a fast computer)

Another method for solving the 8 Queens puzzle

Now for some fun, here is a program that solves the 8 queen puzzle using a different method which is much faster than using recursion. It is based on the algorithm found on the wikipedia page at http://en.wikipedia.org/wiki/Eight_queens_puzzle under the heading of Constructing a Solution



Xerra(Posted 2008) [#2]
Nice post, matey. I'll have a play with this when i get home from work.