Solving the 8 Queens puzzle using recursion

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:

SuperStrict
Const n:Int = 8
Global Board:Int[n,n]


Function Test:Int(Row:Int)
 Local col:Int = 0 'initialize to the first column
 
 While col < n 'keep looping until all columns are checked
  Local Capture:Int = False 'initialize the capture flag to False
  If Row > 0 'First row doesn't need to check for capture
   'test column
   For Local r:Int = 0 To Row - 1
    If Board[r,col] 'Queen here?
     Capture = True
     Exit
    End If
   Next
   '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
  '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
  'if we are here, that means a capture has been detected or succeeding rows could not be completed
  Board[Row,col] = False 'remove queen
  col :+ 1 'try next column
 Wend
 'if we are here, all columns have been tried and failed.  So we return false
 Return False
End Function


Local Result:Int = test(0) 'Start the whole thing off


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


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 athttp://en.wikipedia.org/wiki/Eight_queens_puzzle under the heading of Constructing a Solution

SuperStrict
Const n:Int = 100


If n = 0 Or n = 2 Or n = 3
 Print "No solution found"
 End
End If


Local Board:Int[n,n]
Local list:TList = CreateList()
Type TPosition
 Field i:Int
 
 Function Create:TPosition(i:Int)
  Local Position:TPosition = New TPosition
  Position.i = i
  Return Position
 End Function
End Type


'   1. Divide n by 12. Remember the remainder (n is 8 For the eight queens puzzle).
Local r:Int = n Mod 12


'   2. Write a list of the even numbers from 2 To n in order.
For Local j:Int = 2 To n Step 2
 list.Addlast(TPosition.Create(j))
Next


'   3. If the remainder is 3 Or 9, move 2 To the End of the list.
If r = 3 Or r = 9
 list.remove(list.First())
 list.addlast(TPosition.Create(2))
End If


'   4. Append the odd numbers from 1 To n in order, but, If the remainder is 8, switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
Local PairSwap:Int = False
Local Temp:TPosition
For Local j:Int = 1 To n Step 2
 If r = 8
  If Not PairSwap
   Temp = TPosition.Create(j)
   PairSwap = True
  Else
   PairSwap = False
   List.AddLast(TPosition.Create(j))
   List.Addlast(Temp)
  End If
 Else
  List.AddLast(TPosition.Create(j))
 End If
Next


'   5. If the remainder is 2, switch the places of 1 And 3, Then move 5 To the End of the list.
If r = 2
 For Local Position:TPosition = EachIn List
  Select Position.i
   Case 1
    Position.i = 3
   Case 3
    Position.i = 1
   Case 5
    List.Remove(Position)
  End Select
 Next
 List.AddLast(TPosition.Create(5))
End If


'   6. If the remainder is 3 Or 9, move 1 And 3 To the End of the list.
If r = 3 Or r = 9
 For Local position:Tposition = EachIn List
  If Position.i = 1 Or position.i = 3
   List.Remove(Position)
  End If
 Next
 List.AddLast(TPosition.Create(1))
 List.AddLast(TPosition.Create(3))
End If
'   7. Place the first-column queen in the row with the first number in the list, place the second-column queen in the row with the second number in the list, etc.


Local q:Int = 1
For Local Position:TPosition = EachIn List
 Board[Position.i-1,q-1] = True
 q :+ 1
Next


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