Back to Solutions

Chessboard And Queens

Explanantion

This problem can be solved using the Backtracking algorithm.

Source: CSES Book (Page: 50)

Here, we'll first try and place the first queen in all the cells in the first row, then for each queen placed in the first row we'll place the queens in the possible cells in the second row and so on. We'll break the recursion if we're unable to place a queen in any of the cells in a row.

If are able to place all the queens in the board, we'll increment the count by one.

Code

from typing import List, Tuple

board = [input() for _ in range(8)]
reserved = set()
count = 0

for i in range(8):
    for j in range(8):
        if board[i][j] == '*':
            reserved.add((i, j))


def can_place(
    curr_queens: List[Tuple[int, int]],
    queen: Tuple[int, int]
) -> bool:
    global reserved

    if queen in reserved:
        return False

    for q in curr_queens:
        if q[0] == queen[0] or q[1] == queen[1]:
            return False
        if abs(q[0] - queen[0]) == abs(q[1] - queen[1]):
            return False

    return True


def place_queens(curr_queens: List[Tuple[int, int]], row: int):
    global reserved

    for i in range(8):
        if can_place(curr_queens, (row, i)):
            curr_queens.append((row, i))
            if row == 7:
                global count
                count += 1
            else:
                place_queens(curr_queens, row + 1)
            curr_queens.pop()


place_queens([], 0)
print(count)