N Queens Problem in DSA Go - Execution Trace

Concept Flow - N Queens Problem

Start with empty board

↓

Place queen in row 0, col 0

↓

Check if safe

↓

Place queen

↓

Move to next row

↓

Repeat placement

↓

If no safe place in row

↓

Backtrack to previous row

↓

Try next column

↓

Continue until all queens placed or no solution

The algorithm tries to place queens row by row, checking safety. If stuck, it backtracks to try other columns.

Execution Sample

DSA Go

func solveNQueens(n int) [][]string {
  // recursive backtracking to place queens
}

This code tries to place N queens on an N×N board so no two queens attack each other.

Execution Table

Step	Operation	Row	Column Tried	Safe?	Action	Board State
1	Place queen	0	0	Yes	Place queen at (0,0)	Q . . . . . . . . . . . . . . .
2	Place queen	1	0	No	Try next column	Q . . . . . . . . . . . . . . .
3	Place queen	1	1	No	Try next column	Q . . . . . . . . . . . . . . .
4	Place queen	1	2	Yes	Place queen at (1,2)	Q . . . . . Q . . . . . . . . .
5	Place queen	2	0	No	Try next column	Q . . . . . Q . . . . . . . . .
6	Place queen	2	1	No	Try next column	Q . . . . . Q . . . . . . . . .
7	Place queen	2	2	No	Try next column	Q . . . . . Q . . . . . . . . .
8	Place queen	2	3	No	No safe place, backtrack	Q . . . . . Q . . . . . . . . .
9	Backtrack	1	2	-	Remove queen	Q . . . . . . . . . . . . . . .
10	Place queen	1	3	Yes	Place queen at (1,3)	Q . . . . . . Q . . . . . . . .
11	Place queen	2	0	No	Try next column	Q . . . . . . Q . . . . . . . .
12	Place queen	2	1	Yes	Place queen at (2,1)	Q . . . . . . Q . Q . . . . . .
13	Place queen	3	0	No	Try next column	Q . . . . . . Q . Q . . . . . .
14	Place queen	3	1	No	Try next column	Q . . . . . . Q . Q . . . . . .
15	Place queen	3	2	No	Try next column	Q . . . . . . Q . Q . . . . . .
16	Place queen	3	3	No	No safe place, backtrack	Q . . . . . . Q . Q . . . . . .
17	Backtrack	2	1	-	Remove queen	Q . . . . . . Q . . . . . . . .
18	Place queen	2	2	No	Try next column	Q . . . . . . Q . . . . . . . .
19	Place queen	2	3	Yes	Place queen at (2,3)	Q . . . . . . Q . . . Q . . . .
20	Place queen	3	0	No	Try next column	Q . . . . . . Q . . . Q . . . .
21	Place queen	3	1	Yes	Place queen at (3,1)	Q . . . . . . Q . . . Q . Q . .
22	All queens placed	-	-	-	Solution found	Q . . . . . . Q . . . Q . Q . .

💡 All queens placed safely on the board, solution found.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 9	After Step 10	After Step 12	After Step 17	After Step 19	After Step 21	Final
row	0	1	2	1	2	3	2	3	4	4
column	-	0	2	2	3	1	1	3	1	-
board	empty	Q . . . . . . . . . . . . . . .	Q . . . . . Q . . . . . . . . .	Q . . . . . . . . . . . . . . .	Q . . . . . . Q . . . . . . . .	Q . . . . . . Q . Q . . . . . .	Q . . . . . . Q . . . . . . . .	Q . . . . . . Q . . . Q . . . .	Q . . . . . . Q . . . Q . Q . .	Q . . . . . . Q . . . Q . Q . .

Key Moments - 3 Insights

Why do we backtrack when no safe column is found in a row?

Because placing a queen in the previous row's column led to no safe options in the current row, so we remove that queen and try a different column (see steps 8-9 and 16-17 in execution_table).

How do we check if a position is safe for a queen?

We check columns, and both diagonals for existing queens. If none found, it's safe (see 'Safe?' column in execution_table).

Why do we move row by row instead of placing all queens randomly?

Row-wise placement simplifies checking and ensures one queen per row, reducing complexity (visible in the 'Row' column progression).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the board state?

A Q . . . . . Q . . . . . . . . .

B Q . . . . . . . . . . . . . . .

C . Q . . . . . . . . . . . . . .

D Q . . . . . . Q . . . . . . . .

💡 Hint

Check the 'Board State' column at step 4 in execution_table.

At which step does the algorithm backtrack for the first time?

A Step 8

B Step 5

C Step 12

D Step 16

💡 Hint

Look for 'No safe place, backtrack' in the 'Action' column.

If we change the board size to 3, what would happen to the execution_table?

A It would find a solution quickly.

B It would backtrack more and find no solution.

C It would place queens in all columns without backtracking.

D It would place queens only in the first row.

💡 Hint

Recall that 3x3 board has no solution; backtracking will exhaust all options.

Concept Snapshot

N Queens Problem:
- Place N queens on N×N board
- One queen per row
- Check columns and diagonals for safety
- Use backtracking to try columns
- Backtrack if no safe column
- Continue until all queens placed

Full Transcript

The N Queens Problem places N queens on an N×N chessboard so that no two queens attack each other. The algorithm tries to place queens row by row, checking if each position is safe by verifying columns and diagonals. If no safe position is found in a row, it backtracks to the previous row to try a different column. This process continues until all queens are placed safely or no solution exists. The execution table shows step-by-step queen placements, safety checks, backtracking, and board states. Key moments include understanding backtracking necessity, safety checks, and row-wise placement benefits. The visual quiz tests understanding of board states, backtracking steps, and behavior on smaller boards.

Practice

1. What is the main goal of the N Queens Problem?

easy

A. Place N queens on an NxN chessboard so that no two queens attack each other

B. Count the total number of queens on a chessboard

C. Find the shortest path for a queen to move across the board

D. Arrange queens in a single row on the chessboard

Solution

1. Step 1: Understand the problem statement

   The N Queens Problem requires placing N queens on an NxN board so that no two queens threaten each other.

2. Step 2: Identify the correct goal

   This means no two queens share the same row, column, or diagonal.

3. Final Answer:

   Place N queens on an NxN chessboard so that no two queens attack each other -> Option A

4. Quick Check:

   Goal = Place queens safely [OK]

Hint: Remember: no two queens can share row, column, or diagonal [OK]

Common Mistakes:

• Thinking queens can be in the same row or column
• Confusing the problem with counting queens
• Ignoring diagonal attacks

2. Which of the following Go function signatures is correct for solving the N Queens Problem recursively?

easy

A. func solveNQueens(board []int, row int) bool

B. func solveNQueens(board []int, row string) int

C. func solveNQueens(board [][]int, col int) string

D. func solveNQueens(board [][]int, row int) bool

Solution

1. Step 1: Understand typical parameters

   Usually, the board is represented as a 1D slice of ints where index is row and value is column, and row is int.

2. Step 2: Match correct signature

   func solveNQueens(board []int, row int) bool uses a 1D slice and int row, returning bool to indicate success, which is common in backtracking.

3. Final Answer:

   func solveNQueens(board []int, row int) bool -> Option A

4. Quick Check:

   Correct signature uses []int and int row [OK]

Hint: Use 1D slice for board and int for row in recursive function [OK]

Common Mistakes:

• Using 2D slice which is less efficient
• Using wrong parameter types like string for row
• Returning wrong type instead of bool

3. What will be the output of the following Go code snippet for N=4?

func main() {
    solutions := solveNQueens(4)
    fmt.Println(len(solutions))
}

func solveNQueens(n int) [][]string {
    var res [][]string
    board := make([]int, n)
    backtrack(0, n, board, &res)
    return res
}

func backtrack(row, n int, board []int, res *[][]string) {
    if row == n {
        *res = append(*res, generateBoard(board, n))
        return
    }
    for col := 0; col < n; col++ {
        if isValid(row, col, board) {
            board[row] = col
            backtrack(row+1, n, board, res)
        }
    }
}

func isValid(row, col int, board []int) bool {
    for i := 0; i < row; i++ {
        if board[i] == col || abs(board[i]-col) == row-i {
            return false
        }
    }
    return true
}

func generateBoard(board []int, n int) []string {
    var res []string
    for i := 0; i < n; i++ {
        row := make([]byte, n)
        for j := 0; j < n; j++ {
            if board[i] == j {
                row[j] = 'Q'
            } else {
                row[j] = '.'
            }
        }
        res = append(res, string(row))
    }
    return res
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

medium

A. 4

B. 2

C. 1

D. 0

Solution

1. Step 1: Understand the code logic

   The code uses backtracking to find all solutions for 4 queens on a 4x4 board.

2. Step 2: Recall known result for 4 queens

   It is a classic result that there are 2 distinct solutions for 4 queens.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Number of solutions for N=4 = 2 [OK]

Hint: Remember classic N=4 has exactly 2 solutions [OK]

Common Mistakes:

• Assuming only 1 solution
• Confusing number of solutions with board size
• Ignoring diagonal checks

4. Identify the bug in this Go backtracking function for N Queens:

func backtrack(row, n int, board []int, res *[][]string) {
    if row == n {
        *res = append(*res, generateBoard(board, n))
        return
    }
    for col := 0; col < n; col++ {
        if isValid(row, col, board) {
            board[row] = col
            backtrack(row+1, n, board, res)
            board[row] = -1
        }
    }
}

medium

A. The function should return an int, not void

B. The base case condition should be row > n

C. The loop should start from col = 1 instead of 0

D. Missing resetting board[row] after recursion causes wrong results

Solution

1. Step 1: Analyze backtracking state reset

   After recursive call, board[row] must be reset to -1 to undo the choice.

2. Step 2: Check if resetting is done correctly

   Resetting board[row] = -1 is done inside the loop after recursion, which is correct to backtrack.

3. Step 3: Identify the bug

   If resetting is missing or incorrect, it causes wrong results because previous choices remain.

4. Final Answer:

   Missing resetting board[row] after recursion causes wrong results -> Option D

5. Quick Check:

   Backtracking needs state reset [OK]

Hint: Always undo your move after recursion in backtracking [OK]

Common Mistakes:

• Not resetting board state after recursion
• Wrong base case condition
• Incorrect loop start index

5. How can you optimize the N Queens solution to handle large N efficiently in Go?

hard

A. Use nested loops without recursion for all placements

B. Store the entire board as a 2D slice of strings

C. Use bitmasks to track columns and diagonals instead of arrays

D. Check only rows for conflicts, ignore columns and diagonals

Solution

1. Step 1: Understand performance bottlenecks

   Checking conflicts using arrays for columns and diagonals is slower for large N.

2. Step 2: Use bitmasks for fast conflict checks

   Bitmasks allow O(1) checks and updates for columns and diagonals, improving speed and memory.

3. Step 3: Compare options

   Use bitmasks to track columns and diagonals instead of arrays uses bitmasks, which is a known optimization. Others increase complexity or ignore constraints.

4. Final Answer:

   Use bitmasks to track columns and diagonals instead of arrays -> Option C

5. Quick Check:

   Bitmask optimization = faster large N [OK]

Hint: Use bitmasks for columns and diagonals to speed up checks [OK]

Common Mistakes:

• Using 2D board increases memory and slows down
• Ignoring diagonal checks causes wrong solutions
• Trying nested loops without pruning is inefficient