#!/usr/bin/python3
"""Simple brute-force N-queens recursive solver.

In interpreted Python this runs in 55 milliseconds for N=8, the same
speed as just loading Python.  It starts to take human-detectable time
to find new solutions around N=18 and be annoyingly slow around N=22.

In retrospect using dictionaries for this was a dumb idea.  I should
have just used a list of integers.

Here’s the first solution it finds for 32 queens.

32
♛ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . ♛ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . ♛ . . . . . . . . . . . . . . . . . . . . . . . . . . .
. ♛ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . ♛ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . ♛ . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . ♛ . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . ♛ . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . ♛ . . . . . . . . . . . . . . . . .
. . . . . ♛ . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . ♛ . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . ♛ . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . ♛ . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ♛ . .
. . . . . . . . . . . . . . . . . . . . . . . . ♛ . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ♛ .
. . . . . . . . . . . . . . . . . . . . . . . . . . . ♛ . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ♛
. . . . . . . . . . . . . . . . . . . . . . . . . . ♛ . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . ♛ . . .
. . . . . . . . . . . . . . . ♛ . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . ♛ . . . . . . . . . . . . .
. . . . . . . . . ♛ . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . ♛ . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . ♛ . . . . . . . . . . . . . . .
. . . . . . . . . . . ♛ . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . ♛ . . . . . . . . . . .
. . . . . . ♛ . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . ♛ . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . ♛ . . . . . . . . .
. . . . . . . . . . . . . . . . . . . ♛ . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . ♛ . . . . . . . . . .

"""
import sys


def queens(n, m):
    """Yield solutions for the first *n* rows of an *m*-queens puzzle.

    We can observe that in a valid solution at most one queen can be
    in any row, and since there are as many queens as rows, every row
    must contain exactly one queen, so it’s nice to use a
    representation that restricts solutions thus by construction.

    A solution maps each row to the column in which the queen for that
    row is sitting.  So for example {0: 0, 1: 2, 2: 4, 3: 6, 4: 1, 5:
    3, 6: 5, 7: 7} is this invalid solution:

    0 1 2 3 4 5 6 7
    ♛ . . . . . . . 0: 0
    . . ♛ . . . . . 1: 2
    . . . . ♛ . . . 2: 4
    . . . . . . ♛ . 3: 6
    . ♛ . . . . . . 4: 1
    . . . ♛ . . . . 5: 3
    . . . . . ♛ . . 6: 5
    . . . . . . . ♛ 7: 7

    This is not a valid solution because (0, 0) and (7, 7) are
    attacking one another.

    """
    if n == 0:
        yield {}
        return

    for solution in queens(n-1, m):
        # Pick where to put the queen in row n-1.
        for p in range(m):
            if not any(col == p or col+row == p+n-1 or col-row == p-(n-1)
                       for row, col in solution.items()):
                nsol = solution.copy()
                nsol[n-1] = p
                yield nsol

def print_board(b):
    size = max(b.keys()) + 1
    for row in range(size):
        print(' '.join('♛' if b[row] == col else '.' for col in range(size)))

if __name__ == '__main__':
    if len(sys.argv) == 1:
        N = 1
        while True:
            print(N)
            for solution in queens(N, N):
                print_board(solution)
                print()
                break
            N += 1

    else:
        N = int(sys.argv[1])
        for solution in queens(N, N):
            print_board(solution)
            print()