Queens Puzzle

Queens Puzzle

Further Reading & Original Articles
If you are interested in the original Chinese versions of this article, you can find them here:

• Queens Puzzle

If you’d like to follow more of my technical insights, feel free to visit my blog: Jed’s Software Blog 🚀

The Eight Queens problem is a classic chess puzzle where the goal is to place 8 queens on an 8×8 chessboard in such a way that none of the queens can attack each other.

Rules

• No two queens in the same row: Each queen must be placed in a different row.
• No two queens in the same column: Each queen must be placed in a different column.
• No two queens on the same diagonal: Each queen must not be placed on the same diagonal as another queen.

Example on a 4×4 board

When a queen is placed at (0,0), the following positions cannot have another queen:

• Same row: (0, y)
• Same column: (x, 0)
• Diagonals: (calculated using the formula)

The letter X indicates the positions where a queen cannot be placed due to the rules.

The perfect solution for a 4×4 board is as follows:

Ans 1.

Ans2.

Creating a 4×4 Chessboard

After understanding the rules and the solution, let’s implement it using Python. First, we will create the chessboard.

class QueensPuzzle:

    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.checkerboard = [['.' for _ in range(cols)] for _ in range(rows)]

    def print_board(self):
        for row in self.checkerboard:
            print(" ".join(row))

queens_puzzle = QueensPuzzle(4, 4)

queens_puzzle.print_board()

This will print a 4×4 chessboard.

Analysis and Implementation

Queen Placement Judgment and Implementation

Identify the positions where queens cannot be placed. When placing a queen at (0,0), it can be confirmed that the 0 row and 0 col cannot be used, which helps avoid unnecessary checks.

The diagonal values can be calculated using the formulas:

Left-to-right diagonal value:

Right-to-left diagonal value:

Once the diagonal values are calculated, we can determine all diagonal coordinates from row 0 to row 3. Starting with row 0, if the queen is placed at (0,1), we calculate the diagonal values:

Left-to-right diagonal value

• Formula: row - col = value
• Solution: 0 - 1 = -1

Right-to-left diagonal value

• Formula: row + col = value
• Solution: 0 + 1 = 1

After calculating these values, we proceed with the diagonal coordinates for row 1 by applying the formulas:

Left-to-right diagonal value: 1 - x = -1, x = 2

Right-to-left diagonal value: 1 + x = 1, x = 0

Get Jed’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The coordinates are: (1,2) and (1,0)

Next, for the diagonal coordinates of row 2, apply the formulas:

Left-to-right diagonal value: 2 - x = -1, x = 3

Right-to-left diagonal value: 2 + x = 1, x = -1 (since the chessboard does not have -1, this is omitted)

The coordinate is: (2,3)

Next, for the diagonal coordinates of row 3, apply the formulas:

Left-to-right diagonal value: 3 - x = -1, x = 4 (since 4 exceeds the chessboard range, it is omitted)

Right-to-left diagonal value: 3 + x = 1, x = -4 (since the chessboard does not have -4, it is omitted)

There are no coordinates for this row, and the result remains unchanged.

In the program implementation, three set variables are defined to store:

• occupied_columns: for columns
• occupied_left_diagonals: for the left-to-right diagonal values
• occupied_right_diagonals: for the right-to-left diagonal values

The QueensPuzzle class implements is_valid and handle as follows:

class QueensPuzzle:
        ...
        def is_valid(self, row, col, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
            if col in occupied_columns or (row - col) in occupied_left_diagonals or (row + col) in occupied_right_diagonals:
                return False
            return True

        def handle(self):
            def backtrack(row, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
                for col in range(self.cols):
                    if self.is_valid(row, col, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
                        self.checkerboard[row][col] = 'Q'
                        self.print_board()
                        print('-' * 20)
                        occupied_columns.add(col)
                        occupied_left_diagonals.add(row - col)
                        occupied_right_diagonals.add(row + col)

            backtrack(0, set(), set(), set())

queens_puzzle.handle()

After running, the output is:

But the result is not as expected. You will notice that the loop runs from left to right, but the row remains unchanged because we passed 0 from the outside.

backtrack(0, set(), set(), set())

Recursion

Therefore, recursion needs to be implemented here. Each time a queen is placed, the row should be incremented by 1 until it reaches the boundary.

backtrack(row + 1,
          occupied_columns=occupied_columns,
          occupied_left_diagonals=occupied_left_diagonals,
          occupied_right_diagonals=occupied_right_diagonals)

After running, the output is:

But another issue arises here. When printing the third board in the image, why is there a queen placed beside? This happens because, during the recursion of row 2, the queen cannot be placed anywhere on the row 2.

Therefore, the recursion for row 2 ends and returns to row 1. When row 1 reaches the coordinate (1,2), it will continue executing.

However, only the col is recorded, and the row is not. Since the diagonal values do not match, this leads to the validation of (1, 3) passing.

Backtracking Implementation

As mentioned earlier, when a Q cannot be placed, we need to backtrack the previous row's Q, remove the original (1, 2) placement and the corresponding variable values, and then search for the next valid coordinate. Therefore, the next coordinate will be (1, 3).

Backtracking Implementation

def backtrack(row, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
    for col in range(self.cols):
        if self.is_valid(row, col, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
            ....
            backtrack(row + 1,
                      occupied_columns=occupied_columns,
                      occupied_left_diagonals=occupied_left_diagonals,
                      occupied_right_diagonals=occupied_right_diagonals)
						self.checkerboard[row][col] = '.'
						occupied_columns.remove(col)
						occupied_left_diagonals.remove(row - col)
						occupied_right_diagonals.remove(row + col)

result

Q . . .
. . . .
. . . .
. . . .
--------------------
Q . . .
. . Q .
. . . .
. . . .
--------------------
Q . . .
. . . Q
. . . .
. . . .
--------------------
Q . . .
. . . Q
. Q . .
. . . .
--------------------
. Q . .
. . . .
. . . .
. . . .
--------------------
. Q . .
. . . Q
. . . .
. . . .
--------------------
. Q . .
. . . Q
Q . . .
. . . .
--------------------
. Q . .
. . . Q
Q . . .
. . Q .
--------------------
. . Q .
. . . .
. . . .
. . . .
--------------------
. . Q .
Q . . .
. . . .
. . . .
--------------------
. . Q .
Q . . .
. . . Q
. . . .
--------------------
. . Q .
Q . . .
. . . Q
. Q . .
--------------------
. . . Q
. . . .
. . . .
. . . .
--------------------
. . . Q
Q . . .
. . . .
. . . .
--------------------
. . . Q
Q . . .
. . Q .
. . . .
--------------------
. . . Q
. Q . .
. . . .
. . . .
--------------------

Process finished with exit code 0

Finally, define a list to store the solutions and check if the current col has reached the board’s boundary, which means a solution has been found. The algorithm continues to increment row + 1 until it reaches the boundary.

class QueensPuzzle:

    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.checkerboard = [['.' for _ in range(cols)] for _ in range(rows)]
        self.solutions = []  # Define list

    ...
    def handle(self):
        def backtrack(row, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
            if row == self.rows:  # Check if a solution is found
                self.solutions.append(["".join(r) for r in self.checkerboard])
                return

    # Implement a method to print solutions
    def print_solve(self):
        print(f"There are {len(self.solutions)} solutions")
        for solution in self.solutions:
            for row in solution:
                print(row)
            print()

Complete Code

class QueensPuzzle:

    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.checkerboard = [['.' for _ in range(cols)] for _ in range(rows)]
        self.solutions = []

    def is_valid(self, row, col, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
        if col in occupied_columns or (row - col) in occupied_left_diagonals or (row + col) in occupied_right_diagonals:
            return False
        return True

    def print_solve(self):
        print(f"There are {len(self.solutions)} solutions")
        for solution in self.solutions:
            for row in solution:
                print(row)
            print()

    def handle(self):
        def backtrack(row, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
            if row == self.rows:
                self.solutions.append(["".join(r) for r in self.checkerboard])
                return

            for col in range(self.cols):
                if self.is_valid(row, col, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
                    self.checkerboard[row][col] = 'Q'
                    occupied_columns.add(col)
                    occupied_left_diagonals.add(row - col)
                    occupied_right_diagonals.add(row + col)
                    backtrack(row + 1,
                              occupied_columns=occupied_columns,
                              occupied_left_diagonals=occupied_left_diagonals,
                              occupied_right_diagonals=occupied_right_diagonals)
                    self.checkerboard[row][col] = '.'
                    occupied_columns.remove(col)
                    occupied_left_diagonals.remove(row - col)
                    occupied_right_diagonals.remove(row + col)

        backtrack(0, set(), set(), set())

    def print_board(self):
        for row in self.checkerboard:
            print(" ".join(row))

queens_puzzle = QueensPuzzle(4, 4)

queens_puzzle.handle()
queens_puzzle.print_solve()

Conclusion

• Core Idea: Use the backtracking algorithm to try all possible queen placements and exclude invalid positions to improve efficiency.
• Key Points:
• Use sets to track the occupation status of columns and diagonals.
• Recursively try each position for each row, and backtrack when no valid placement is found.