Monthly Archives: April 2013

Back to the N-Queens with Backtracking:

Throughout this semester I have been thoroughly enjoying my artificial intelligence class. While the probability stuff can be a bit much for me at times, I absolutely love learning various searching algorithms. For our first project I implemented a genetic algorithm to find a solution for the Traveling Salesperson Problem — in a language I’d never used, Python. While I did have my ups and downs, I learned to love the cleanliness of the language and the welcoming community it has built up. Naturally, I chose Python for my second project.

The N-Queens problem is rather straightforward; how can we place N number of queens on a NxN board such that no queen can directly attack another? This is rather simple, albeit monotonous, to do by hand on small board i.e.: 4 or 5 queens. But, what about when we have 8, 10, or even 20 queens? Things get a bit more tricky. For simplicity, I chose to solve the problem with a backtracking algorithm.

Here’s a summary of how it works:

  1. Starting from the first column, check every row for a threat from queens above, below, left, right, or diagonal to it. Once you find a safe row for a given column, place a queen there.
  2. Recurs incrementing one column until you have either placed a queen in every column or you are unable to safely place a queen in a column. If latter occurs, you must backtrack to the last known good solution.
  3. Annotate the location of the last queen’s row, remove the queen, and recurs calling on the previous column beginning one row passed where the last queen was.

Before starting to code, I drew out a simple, 4-Queen problem on a white board, step by step, and really thought about what was going on, how I wanted to attack the problem, and tricky cases which would need special care. Doing so greatly reduced the amount of headaches I could have had by going straight to the old code and fix  model. Now, only if the entry level C.S. students in my lab would do the same.

Now, down to the good stuff. This is what I came up with:

import sys
import numpy as np

# override default recursion limit
sys.setrecursionlimit(1000000000)


class NQueens:

    def __init__(self, size_of_board):
        self.size = size_of_board
        self.columns = [] * self.size
        self.num_of_places = 0
        self.num_of_backtracks = 0

    def place(self, startRow=0):
        """ Backtracking algorithm to recursively place queens on the board
            args:
                startRow: the row which it attempts to begin placing the queen
            returns:
                list representing a solution
        """
        # if every column has a queen, we have a solution
        if len(self.columns) == self.size:
            print('Solution found! The board size was: ' + str(self.size))
            print(str(self.num_of_places) + ' total places were made.')
            print(str(self.num_of_backtracks) + ' total backtracks were executed.')
            print(self.columns)
            return self.columns

        # otherwise search for a safe queen location
        else:
            for row in range(startRow, self.size):
                # if a safe location in this column exists
                if self.isSafe(len(self.columns), row) is True:
                    # place a queen at the location
                    self.columns.append(row)
                    self.num_of_places += 1
                    # recursively call place() on the next column
                    return self.place()

                # if not possible, reset to last state and try to place queen
            else:
                # grab the last row to backtrack from
                lastRow = self.columns.pop()
                self.num_of_backtracks += 1
                # recursively call place() from the last known good position, incrementing to the next row
                return self.place(startRow=lastRow + 1)

    def isSafe(self, col, row):
        """Determines if a move is safe.
        args:
            col: column of desired placement
            row: row of desired placement
            self.columns: list of queens presently on the board
        returns:
            True if safe, False otherwise
        """
        # check for threats from each queen currently on board
        for threatRow in self.columns:
            # for readability
            threatCol = self.columns.index(threatRow)
            # check for horizontal/vertical threats
            if row == threatRow or col == self.columns.index(threatRow):
                return False
            # check for diagonal threats
            elif threatRow + threatCol == row + col or threatRow - threatCol == row - col:
                return False
        # if we got here, no threats are present and it's safe to place the queen at the (col, row)
        return True

# set the size of the board
n = 17
# instantiate the board and call the backtracking algorithm
queens = NQueens(n)
queens.place(0)

# convert board to numpy array for pretty printing
board = np.array([[' '] * n] * n)
for queen in queens.columns:
    board[queens.columns.index(queen), queen] = 'Q'

print board

And here is a sample output for a 17-Queen solution:

Solution found! The board size was: 17
5374 total places were made.
5357 total backtracks were executed.
[0, 2, 4, 1, 7, 10, 14, 6, 15, 13, 16, 3, 5, 8, 11, 9, 12]
[['Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q']
 [' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ']]

Now, you may have noticed these lines:

# override default recursion limit
sys.setrecursionlimit(1000000000)

After developing a working solution I started receiving: “RuntimeError: maximum recursion depth exceeded in cmp” on boards with more than 13 queens. I found this surprising and did some research. After some digging, I discovered Python has a rather conservative default recursion limit to help avoid infinite recursive calls. My resolution was rather hackish but allowed me to bump the solvable board size to 17 queens by manually setting the recursion limit. This was more than good enough for my class project.

If time permits, I would like to go back and mimic the recursive nature of this with a stack and see how large of a solution would be able to solve. If time permits.

More to follow … maybe?

“To understand recursion, you must understand recursion.”

-H.

Tagged , , , , , ,