# Look ma, no modules!

# bottlenecks around 12, when the problem size starts to mushroom
board_size = 11

solutions = []
queens = []
occupied = board_size*[0,]



def explore(depth):
    # base case
    if(depth==board_size):
        # stringify/serialize the solution
        solutions.append("%s"%(queens))
        return

    else:
        attacked = 2*board_size*[0,]
        for i in range(0,len(queens)):
            ix1 = queens[i] + depth - i
            attacked[ix1] = 1

            ix2 = queens[i] - depth + i
            attacked[ix2] = 1

        for row in range(0,board_size):
            if(occupied[row] or attacked[row]):
                continue

            # make a choice
            queens.append(row)
            occupied[row] = 1

            # explore the consequences
            explore(depth+1)

            # unmake the choice
            queens.pop()
            occupied[row] = 0



explore(0)
print "Found %d solutions"%(len(solutions))
#print solutions