Eight Queens Puzzle

What is the eight queens puzzle?

Put eight queens on a chessboard so that no two attack each other. A queen attacks along its row, its column and both diagonals, so no two queens may share any of those. It was first set in 1848 and has been a favourite of mathematicians and programmers ever since, because it is easy to state, awkward to do by hand, and a perfect first example of searching with backtracking. The same question can be asked of any board, n queens on an n by n.

How many solutions are there?

Ninety-two on an ordinary board. Many of those are the same arrangement turned or flipped, and once those are counted together there are twelve genuinely different answers. The All the solutions tab steps through every one of them, and the tick box narrows it to the twelve.

Boards of two and three have no answer at all, and the 6 by 6 has fewer than the 5 by 5, just four against ten. Every figure here was counted by this page's own search, and they match the published sequence.

The 8 queens problem using backtracking

Go down the board one row at a time. On each row, try the columns from left to right and put a queen on the first square no earlier queen attacks. Then move down. If a row has no safe square left, the problem is the queen above: take it off, move it to its next safe column, and carry on from there. That retreat is the backtrack, and it is the whole idea.

Because a whole branch is abandoned the moment it fails, the search never looks at most of the 16,777,216 ways of putting one queen in each row. On this page it reaches its first answer in 982 steps, and Watch it search replays every one of them: each queen placed, each square rejected, each retreat.

The eight queens problem in Python

The same backtracking, keeping sets of the columns and the two diagonal directions already taken, so checking a square is instant. Run it and it prints 92.

def solve(n):
    solutions, cols = [], []

    def place(row, used, diag1, diag2):
        if row == n:
            solutions.append(cols[:])
            return
        for c in range(n):
            if c in used or row + c in diag1 or row - c in diag2:
                continue
            cols.append(c)
            place(row + 1, used | {c}, diag1 | {row + c}, diag2 | {row - c})
            cols.pop()

    place(0, set(), set(), set())
    return solutions


print(len(solve(8)))   # 92

Chess puzzles you solve with your hands

The eight queens is a chess puzzle with no game in it. So are the puzzles Sherzod Khaydarbekov designs for us, except that his are solid boards where the pieces move by the ordinary chess rules: Swapping Castles asks you to swap four rooks with four others, and Queen's Attack has the queen missing and asks the rest of the pieces to clear the pawns. More on the idea is in chess puzzles you solve with your hands, and there are more solvers on the puzzle tools page.