8 queens

eight_queens.py

N = 8

def neighbors(board):
    occupied = set(board)
    for r in range(N):
        for c in range(N):
            if (r, c) not in occupied:
                yield board + ((r, c),)

def solve_8q_one():
    """Return one solution (tuple of 8 (r,c) positions), or None if none."""
    def dfs(board):
        if not check_legal(board):
            return None
        if len(board) == N:
            return board
        for nb in neighbors(board):
            ans = dfs(nb)
            if ans is not None:
                return ans
        return None
    return dfs(tuple())

def solve_8q_all():
    """Return a list of all solutions via recursive DFS."""
    sols = []
    def dfs(board):
        if not check_legal(board):
            return
        if len(board) == N:
            sols.append(board)
            return
        for nb in neighbors(board):
            dfs(nb)
    dfs(tuple())
    return sols

def check_legal(board):
    occupied_rows = set()
    occupied_cols = set()
    occupied_pos_diags = set()  # r + c
    occupied_neg_diags = set()  # r - c
    for r, c in board:
        if r in occupied_rows or c in occupied_cols or (r + c) in occupied_pos_diags or (r - c) in occupied_neg_diags:
            return False
        occupied_rows.add(r)
        occupied_cols.add(c)
        occupied_pos_diags.add(r + c)
        occupied_neg_diags.add(r - c)
    return True

if __name__ == "__main__":
    print("One solution:", solve_8q_one())
    import matplotlib.pyplot as plt
    board = solve_8q_one()
    if board is not None:
        plt.scatter([c for r, c in board], [N - 1 - r for r, c in board], s=200, marker='X')
        plt.xlim(-1, N)
        plt.ylim(-1, N)
        plt.xticks(range(N))
        plt.yticks(range(N))
        plt.grid()
        plt.gca().set_aspect('equal', adjustable='box')
        plt.show()
    assert 0
    print("All solutions ({}):".format(len(solve_8q_all())))
    for sol in solve_8q_all():
        print(sol)
    print("Total number of solutions:", len(solve_8q_all()))