Python Backtracking (queens checkboard)

Question

Ok so finally after hours and hours of struggling with my head I finally understood how backtracking works. Though I still think there are secrets left to be understood. Anyways, I'm trying to create the 4-queens problem on the checkboard. Practically I'm giving myself a blank checkboard (it's 4x4 actually) and I need to find 4 places where those queens won't attack themselves. A queen attacks the row, column and diagonal it belongs too. here is what I've done so far (The valid func isn't complete yet, but it doesn't really matter. I just need the backtrack function to work).

def findNextCell(grid,i,j):

    for index in range(i,4):
        for jindex in range(j,4):
            return index, jindex

    for index in range(0,4):
        for jindex in range(0,4):
            if grid[index][jindex] == 0:
                return index, jindex

    return -1,-1


def isValid(grid, index, jindex, queen):

    rowOk = all([queen != grid[index][x] for x in range(4)])
    if rowOk:
        columnOk = all([queen != grid[x][jindex] for x in range(4)])
        if columnOk:
            return True
    return False

def queenSolve(grid, i=0, j=0, num_queens = 0):

    i, j = findNextCell(grid, i, j)
    print grid
    if num_queens == 4:
        return True
    if isValid(grid, i, j, 1):
        grid[i][j]=1
        num_queens += 1
        if (queenSolve(grid, i, j, num_queens)):
            return True
        grid[i][j]=0
    return False

input = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]

print queenSolve(input)

Answer 1

The first problem I see is the initial nested loops in this routine:

def findNextCell(grid,i,j):

    for index in range(i,4):
        for jindex in range(j,4):
            return index, jindex

    for index in range(0,4):
        for jindex in range(0,4):
            if grid[index][jindex] == 0:
                return index, jindex

    return -1,-1

This appears to be some early test code that never got cleared out:

    for index in range(i,4):
        for jindex in range(j,4):
            return index, jindex

But unfortunately, it causes findNextCell() to always return the i and j it was passed, nothing more:

>>> findNextCell(0, 1, 2)
(1, 2)
>>> findNextCell(0, 3, 2)
(3, 2)
>>> findNextCell(0, 1, 1)
(1, 1)
>>> 

The next problem I see is this pair of lines:

num_queens += 1
if (queenSolve(grid, i, j, num_queens)):

This is augmenting the number of queens, succeed or fail! Instead you probably want just one line:

if (queenSolve(grid, i, j, num_queens + 1)):

That is increase the number of queens on recursion but don't affect current number in case this fails.

The third problem I see is that this isn't a loop:

i, j = findNextCell(grid, i, j)
...
if isValid(grid, i, j, 1):
    grid[i][j]=1
    num_queens += 1
    if (queenSolve(grid, i, j, num_queens)):
        return True
    grid[i][j]=0

You should be trying to place the current queen in all valid spaces until you run out of valid spaces, findNextCell() returns negative, or until the recursion succeeds. You try one location for the current queen and then give up. This problem is iterative on the current queen and recursive on the subsequent ones.