Backtracking

"""
Backtracking is a systematic way of trying out different sequences of decisions until we find one that "works." It's often used for solving problems related to constraints, such as puzzles (like Sudoku), combinatorial problems, and pathfinding in mazes.

A classic example of a problem solved using backtracking is the N-Queens puzzle. The challenge is to place N queens on an N×N chessboard so that no two queens threaten each other. This means no two queens can be in the same row, column, or diagonal.

Here's a simple Python solution using backtracking. This solution focuses on placing one queen in each row, starting from the first row and moving downwards. If a valid position is found, the algorithm proceeds to the next row; if not, it backtracks.

The code below defines a chessboard as a 2D list, where '.' represents an empty square and 'Q' represents a queen. The solve_n_queens function tries to place queens on the board in a way that no two queens attack each other. The is_safe function checks if a queen can be placed at the specified row and column considering the current state of the board. The solve function attempts to place a queen in every row of a particular column before moving on to the next column, and it backtracks if no safe position is found.

For an n of 4, this will generate all the possible solutions where the queens don't attack each other.

Pseudocode:

backtracking:
    # define empty results obj
    # initialize cache-like object to track global state
    # start recursive function at one end of the object looking for solutions
    # return results

    # recursive function:
        # check edge cases / add solution to results
        # if the current position is OK to proceed down based on what you've seen so far, update global state, recurse from here, then update global state to undo your change.


Note that the code for checking the diagonals is trickier/fancier than it may first look:
1) it depends on the behavior of the zip() function in which it will stop creating new pairs once one of the input ranges runs out of indices, thereby preventing an out-of-bounds error.
2) The fact that it is iterating "backwards" starting from the row/col and then moving left towards the left edge of the board, rather than iterating from the left edge of the board to the right, is actually by design; it's necessary to do it that way to ensure you're looking along the correct diagonals. I once tried to do the iteration from the left and it turned out that I was actually just iterating from the top-left / bottom-left corners every time.
"""


def backtracking(n):
    board = [['.' for _ in range(n)] for _ in range(n)]
    results = []

    def is_safe(row, col):
        # Check this row on left side
        for c in range(col):
            if board[row][c] == 'Q':
                return False

        # Check upper diagonal on left side
        for r, c in zip(range(row, -1, -1), range(col, -1, -1)):
            if board[r][c] == 'Q':
                return False

        # Check lower diagonal on left side
        for r, c in zip(range(row, n), range(col, -1, -1)):
            if board[r][c] == 'Q':
                return False

        return True

    def solve(col):
        # If all queens are placed
        if col >= n:
            results.append([''.join(row) for row in board])
            return

        # Consider this column and try placing this queen in all rows one by one
        for row in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'
                solve(col + 1)  # Recurse to place rest of the queens
                board[row][col] = '.'  # Remove the queen to check for other possible solutions

    solve(0)
    return results

# Example usage
n = 4
for solution in backtracking(n):
    for row in solution:
        print(row)
    print()