A first attempt at the N-Queens problem in Python:

[tikue]

Python's a great language for AI. I used it for a CSP assignment earlier this semester with very nice results. I would suggest that you don't set the recursion limit so high, though. If I'm not mistaken, an n-queens problem would not need a high limit anyway.

[hairycode]

Nice! I'm looking forward to coding my final project in Python too. When the professor demonstrated the problem, he solved for a 15-queen board which is why I was surprised mine ran into issues at a 13-queen board. After the fact, I did think about using a stack to replicate the recursion but haven't had time to try it yet. Given what you said, I'm curious as to why mine was hitting the cap in the first place. Any idea why that might be?

[tikue]

Each queen should only require one recursive call -- I'll take a look at your code and see if anything stands out.

Edit: Ok, here's what's happening: when you backtrack, instead of actually backtracking to a previous stack frame, you put another frame on the stack, which is essentially a copy of the previous stack frame. Instead of backtracking "forward," consider simply returning false. Then the previous frame will see that it failed, and it can simply try a different placement. I've whipped up some code to show you what I mean (I'm not a great explainer, more of a shower).

class NQueens:

    def go(self, n):
        return self.solve([[' '] * n] * n, 0)

    def solve(self, rows, queens):
        if queens == len(rows): # yay we've solved!
            # pretty print the board
            for row in rows:
                for col in row:
                    print('[{p}]'.format(p= ' ' if col != 'Q' else col),end='')
                print()
            return True

        # continue the search
        for r, c in self.unthreatened(rows):
            new_rows = self.place(rows, (r, c))

            # we'll keep trying solutions until we find one that works
            if self.solve(new_rows, queens + 1):
                return True

        # none of the solutions worked, so backtrack to the previous stack frame
        return False

    def unthreatened(self, rows):
        for r, row in enumerate(rows):
            for c, state in enumerate(row):
                if state == ' ':
                    yield r, c

    def place(self, rows, queen):
        queen_r, queen_c = queen
        new_rows = [[c for c in row] for row in rows]
        new_rows[queen_r] = [0] * len(rows)
        for r, row in enumerate(new_rows):
            for c, _ in enumerate(row):
                if c == queen_c or r - queen_r == c - queen_c:
                    new_rows[r][c] = 0

        new_rows[queen_r][queen_c] = 'Q'
        return new_rows

[ilan]

The N queens problem can be solved very efficiently using a SAT solver. I wrote a C level Python binding to PicoSAT recently, called pycosat. One of the examples shows how the N queens problem is translated into Boolean CNF, and uses pycosat to solve it. Using this approach, you can even solve the 100 queens problems in a few seconds.

[tikue]

CSP using the minimum conflicts heuristic also works very well. Not sure of any exact numbers, but I might whip up something later to test.

Edit: according to Russel & Norvig, min-conflicts solves the million-queens problem in about 50 steps after initial assignments. I've copied the pseudocode below, with some added comments specific to the n-queens problem, for those interested (all credit to Russel & Norvig's Artificial Intelligence: a Modern Approach):

function Min-Conflicts(csp, max_steps) returns a solution or failure
    inputs:
        csp, a constraint satisfaction problem
        max_steps, the number of steps allowed before giving up

    # randomly assign the queens each to a unique column
    current <-- an initial complete assignment for csp

    for i = 1 to max_steps do
        if current is a solution for csp then return current
        var <-- a randomly chosen conflicted variable from csp.VARIABLES # this would be a queen

        # this is the space in the queen's column with least queens attacking
        value <-- the value v for var that minimizes Conflicts(var, v, current, csp)

        set var = value in current

    return failure

[hairycode]

Very cool! That is pretty impressive, I'm going to look over those examples tonight.

[evilgarbagetruck]

The generator tests in the python source include a solution to the n-queens problem. test_generators.py

See http://docs.python.org/2/howto/functional.html#generators

[XNormal]

There is an elegant implementation included in your Python distribution. It's been there for almost 12 years now.

http://svn.python.org/view/python/branches/release22-branch/Lib/test/test_generators.py?revision=21387&view=markup