Imagine you’re trying to solve a maze. You start walking, choosing one path, but soon realize it leads to a dead end. What do you do? You backtrack—step back to the last point where you could choose another path and try a different way. This is essentially what backtracking is about in computing.

Backtracking is a trial-and-error method used in programming and problem solving. When you try to solve a problem, you take one step at a time, choosing from available options. If you find that you’ve made a wrong choice somewhere along the line—much like hitting a dead end in a maze—you go back and try a different option from the last point where things were still working. This process continues until you find a solution or exhaust all possibilities.

Why is it Useful?

Backtracking is particularly useful for problems where the solution involves multiple steps, and each step has multiple choices. It helps you systematically search for a solution by exploring all possible options and backing up when an option leads to a dead end. Think of solving a puzzle, planning a route in a complex network, or deciding moves in a game. Each decision impacts subsequent choices, and backtracking helps manage this complexity by allowing for corrections of mistakes in decision-making.

In our everyday problem-solving toolkit, backtracking is like having an “undo” button that helps us reverse decisions, explore different choices, and find the best solution to complex problems

Understanding the N-Queens Puzzle

Imagine you have a chessboard and several chess queens. The challenge is to place a certain number of queens (N queens) on an N×N chessboard so that no two queens can attack each other. In chess, queens can move any number of squares vertically, horizontally, or diagonally. This means for the puzzle, no two queens can share the same row, column, or diagonal. The N-Queens puzzle is a classic exercise in using logic and strategy to figure out the placement of each queen.

Why is it Interesting?

The N-Queens puzzle isn’t just about chess or queens; it’s a way to exercise critical thinking and problem-solving skills. It demonstrates how a seemingly simple setup can unfold into a complex problem requiring thoughtful strategies to solve. Each move you make affects all subsequent moves, similar to real-life decisions.

How to Approach Solving It

Approaching the N-Queens puzzle can feel daunting at first, but like any complex problem, it can be broken down into smaller, manageable parts:

1. Start Small: Begin with a smaller board, like 4×4. This simplifies the problem and helps you understand the mechanics without getting overwhelmed.

2. One Step at a Time: Place one queen at a time. Start in one column, and try placing a queen in each row until you find a position where the queen is not threatened by others.

3. Check for Safety: For each position, check if placing the queen there would put her in line with any previously placed queen. This means checking all rows, columns, and both diagonals for any potential threats.

4. Backtrack if Needed: If it turns out a queen’s position is leading to a dead-end (where subsequent queens cannot be placed without conflict), backtrack. This means removing the last placed queen and trying the next possibility in the previous column.

5. Repeat: Continue this process, moving forward and backtracking as necessary until all queens are placed safely or all possibilities are exhausted.

Visualizing the Solution

Imagine a grid where you systematically test each cell: Can a queen be placed here? Is she safe? If yes, move to the next column. If no, move her to the next row. This methodical testing and moving is the essence of solving the N-Queens puzzle.

Why Use Backtracking?

Backtracking is a natural fit for N-Queens because it allows for exploring all potential placements of queens on the board without missing any possibilities. It’s a way of navigating through decisions where each choice leads to new options, and incorrect choices can be reconsidered.

Human Perspective

From a human perspective, solving the N-Queens puzzle is like navigating a complex life decision where every choice impacts all subsequent choices. It teaches patience, strategy, and the wisdom of sometimes taking a step back to move forward more effectively.

Conclusion

The N-Queens puzzle is more than just a game or a puzzle; it’s a metaphor for decision-making and problem-solving in everyday life. It provides a clear example of how complex problems can be approached systematically and solved with patience and persistence.

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

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

    # Check lower diagonal on left side
    for i, j in zip(range(row, len(board), 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    return True

def solve_n_queens(board, col):
    # If all queens are placed
    if col >= len(board):
        return True

    # Consider this column and try placing this queen in all rows one by one
    for i in range(len(board)):
        if is_safe(board, i, col):
            # Place this queen in board[i][col]
            board[i][col] = 1

            # Recur to place rest of the queens
            if solve_n_queens(board, col + 1):
                return True

            # If placing queen in board[i][col] doesn't lead to a solution
            # then remove queen from board[i][col] (backtrack)
            board[i][col] = 0

    # If the queen can not be placed in any row in this column col
    # then return false
    return False

def print_solution(board):
    for row in board:
        print(" ".join(['Q' if x else '.' for x in row]))

def main(n):
    board = [[0]*n for _ in range(n)]
    if not solve_n_queens(board, 0):
        print("Solution does not exist")
    else:
        print_solution(board)

# Example usage
n = 8
main(n)