N Queens Problem in DSA Rust - Execution Trace

Concept Flow - N Queens Problem

Start with empty board

↓

Place queen in row 0, col 0

↓

Check conflicts

↓

Place next queen

↓

Repeat for all rows

↓

If all queens placed

↓

Record solution

↓

Backtrack to previous row

↓

Try next column

↓

Repeat until all solutions found or all options exhausted

The algorithm tries to place queens row by row, checking conflicts. If conflict occurs, it tries next column. When all queens are placed, it records the solution and backtracks to find others.

Execution Sample

DSA Rust

fn solve_n_queens(n: usize) -> Vec<Vec<String>> {
    fn backtrack(row: usize, cols: &mut Vec<usize>, n: usize, solutions: &mut Vec<Vec<String>>) {
        if row == n {
            solutions.push(draw_board(cols, n));
            return;
        }
        for col in 0..n {
            if is_safe(row, col, cols) {
                cols.push(col);
                backtrack(row + 1, cols, n, solutions);
                cols.pop();
            }
        }
    }
    let mut solutions = vec![];
    backtrack(0, &mut vec![], n, &mut solutions);
    solutions
}

This code tries to place queens row by row, checking if each position is safe, and backtracks to find all solutions.

Execution Table

Step	Operation	Row	Column Tried	Cols Vector (Queens placed)	Conflict Check Result	Action	Visual State
1	Start	-	-	[]	-	Begin with empty board	[ ]
2	Try place queen	0	0	[]	No conflict	Place queen at (0,0)	[Q . . .]
3	Try place queen	1	0	[0]	Conflict (same column)	Try next column	[Q . . .] [. . . .]
4	Try place queen	1	1	[0]	Conflict (diagonal)	Try next column	[Q . . .] [. . . .]
5	Try place queen	1	2	[0]	No conflict	Place queen at (1,2)	[Q . . .] [. . Q .]
6	Try place queen	2	0	[0,2]	Conflict (same column)	Try next column	[Q . . .] [. . Q .] [. . . .]
7	Try place queen	2	1	[0,2]	Conflict (diagonal)	Try next column	[Q . . .] [. . Q .] [. . . .]
8	Try place queen	2	3	[0,2]	No conflict	Place queen at (2,3)	[Q . . .] [. . Q .] [. . . Q]
9	Try place queen	3	0	[0,2,3]	Conflict (same column)	Try next column	[Q . . .] [. . Q .] [. . . Q] [. . . .]
10	Try place queen	3	1	[0,2,3]	Conflict (diagonal)	Try next column	[Q . . .] [. . Q .] [. . . Q] [. . . .]
11	Try place queen	3	2	[0,2,3]	Conflict (diagonal)	Try next column	[Q . . .] [. . Q .] [. . . Q] [. . . .]
12	Try place queen	3	3	[0,2,3]	Conflict (same column)	No more columns, backtrack	[Q . . .] [. . Q .] [. . . Q]
13	Backtrack	3	-	[0,2]	-	Remove queen from row 3	[Q . . .] [. . Q .] [. . . .]
14	Backtrack	2	-	[0]	-	Remove queen from row 2	[Q . . .] [. . . .]
15	Try place queen	2	3	[0]	No conflict	Place queen at (2,3)	[Q . . .] [. . . .] [. . . Q]
16	Try place queen	3	1	[0,3]	No conflict	Place queen at (3,1)	[Q . . .] [. . . .] [. . . Q] [. Q . .]
17	All queens placed	4	-	[0,3,1]	-	Record solution	[Q . . .] [. . . .] [. . . Q] [. Q . .]
18	Backtrack	3	-	[0,3]	-	Remove queen from row 3	[Q . . .] [. . . .] [. . . Q]
19	Backtrack	2	-	[0]	-	Remove queen from row 2	[Q . . .] [. . . .]
20	Try place queen	2	1	[0]	Conflict (diagonal)	Try next column	[Q . . .] [. . . .]
21	Try place queen	2	2	[0]	Conflict (same column)	Try next column	[Q . . .] [. . . .]
22	Try place queen	2	3	[0]	No conflict	Place queen at (2,3)	[Q . . .] [. . . .] [. . . Q]
23	Try place queen	3	0	[0,3]	Conflict (same column)	Try next column	[Q . . .] [. . . .] [. . . Q] [. . . .]
24	Try place queen	3	1	[0,3]	No conflict	Place queen at (3,1)	[Q . . .] [. . . .] [. . . Q] [. Q . .]
25	All queens placed	4	-	[0,3,1]	-	Record solution	[Q . . .] [. . . .] [. . . Q] [. Q . .]
26	Backtrack	3	-	[0,3]	-	Remove queen from row 3	[Q . . .] [. . . .] [. . . Q]
27	Backtrack	2	-	[0]	-	Remove queen from row 2	[Q . . .] [. . . .]
28	Try place queen	1	3	[0]	Conflict (diagonal)	Try next column	[Q . . .] [. . . .]
29	No more columns in row 1	[Backtrack]	-	[ ]	-	Remove queen from row 0	[. . . .]
30	Try place queen	0	1	[]	No conflict	Place queen at (0,1)	[. Q . .]
31	Try place queen	1	0	[1]	Conflict (diagonal)	Try next column	[. Q . .] [. . . .]
32	Try place queen	1	1	[1]	Conflict (same column)	Try next column	[. Q . .] [. . . .]
33	Try place queen	1	2	[1]	No conflict	Place queen at (1,2)	[. Q . .] [. . Q .]
34	Try place queen	2	0	[1,2]	No conflict	Place queen at (2,0)	[. Q . .] [. . Q .] [Q . . .]
35	Try place queen	3	0	[1,2,0]	Conflict (same column)	Try next column	[. Q . .] [. . Q .] [Q . . .] [. . . .]
36	Try place queen	3	1	[1,2,0]	Conflict (same column)	Try next column	[. Q . .] [. . Q .] [Q . . .] [. . . .]
37	Try place queen	3	2	[1,2,0]	Conflict (diagonal)	Try next column	[. Q . .] [. . Q .] [Q . . .] [. . . .]
38	Try place queen	3	3	[1,2,0]	No conflict	Place queen at (3,3)	[. Q . .] [. . Q .] [Q . . .] [. . . Q]
39	All queens placed	4	-	[1,2,0,3]	-	Record solution	[. Q . .] [. . Q .] [Q . . .] [. . . Q]
40	Backtrack	3	-	[1,2,0]	-	Remove queen from row 3	[. Q . .] [. . Q .] [Q . . .]
41	Backtrack	2	-	[1,2]	-	Remove queen from row 2	[. Q . .] [. . Q .]
42	Try place queen	2	1	[1]	Conflict (same column)	Try next column	[. Q . .] [. . Q .]
43	Try place queen	2	2	[1]	Conflict (diagonal)	Try next column	[. Q . .] [. . Q .]
44	Try place queen	2	3	[1]	No conflict	Place queen at (2,3)	[. Q . .] [. . Q .] [. . . Q]
45	Try place queen	3	0	[1,3]	Conflict (diagonal)	Try next column	[. Q . .] [. . Q .] [. . . Q] [. . . .]
46	Try place queen	3	1	[1,3]	Conflict (same column)	Try next column	[. Q . .] [. . Q .] [. . . Q] [. . . .]
47	Try place queen	3	2	[1,3]	No conflict	Place queen at (3,2)	[. Q . .] [. . Q .] [. . . Q] [. . Q .]
48	All queens placed	4	-	[1,3,2]	-	Record solution	[. Q . .] [. . Q .] [. . . Q] [. . Q .]
49	Backtrack	3	-	[1,3]	-	Remove queen from row 3	[. Q . .] [. . Q .] [. . . Q]
50	Backtrack	2	-	[1]	-	Remove queen from row 2	[. Q . .] [. . Q .]
51	Backtrack	1	-	[]	-	Remove queen from row 1	[. Q . .]
52	Try place queen	0	2	[]	No conflict	Place queen at (0,2)	[. . Q .]
53	Try place queen	1	0	[2]	No conflict	Place queen at (1,0)	[. . Q .] [Q . . .]
54	Try place queen	2	1	[2,0]	No conflict	Place queen at (2,1)	[. . Q .] [Q . . .] [. Q . .]
55	Try place queen	3	0	[2,0,1]	Conflict (same column)	Try next column	[. . Q .] [Q . . .] [. Q . .] [. . . .]
56	Try place queen	3	2	[2,0,1]	Conflict (same column)	Try next column	[. . Q .] [Q . . .] [. Q . .] [. . . .]
57	Try place queen	3	3	[2,0,1]	No conflict	Place queen at (3,3)	[. . Q .] [Q . . .] [. Q . .] [. . . Q]
58	All queens placed	4	-	[2,0,1,3]	-	Record solution	[. . Q .] [Q . . .] [. Q . .] [. . . Q]
59	Backtrack	3	-	[2,0,1]	-	Remove queen from row 3	[. . Q .] [Q . . .] [. Q . .]
60	Backtrack	2	-	[2,0]	-	Remove queen from row 2	[. . Q .] [Q . . .]
61	Try place queen	2	2	[2,0]	Conflict (same column)	Try next column	[. . Q .] [Q . . .]
62	Try place queen	2	3	[2,0]	No conflict	Place queen at (2,3)	[. . Q .] [Q . . .] [. . . Q]
63	Try place queen	3	0	[2,0,3]	Conflict (same column)	Try next column	[. . Q .] [Q . . .] [. . . Q] [. . . .]
64	Try place queen	3	1	[2,0,3]	No conflict	Place queen at (3,1)	[. . Q .] [Q . . .] [. . . Q] [. Q . .]
65	All queens placed	4	-	[2,0,3,1]	-	Record solution	[. . Q .] [Q . . .] [. . . Q] [. Q . .]
66	Backtrack	3	-	[2,0,3]	-	Remove queen from row 3	[. . Q .] [Q . . .] [. . . Q]
67	Backtrack	2	-	[2,0]	-	Remove queen from row 2	[. . Q .] [Q . . .]
68	Backtrack	1	-	[2]	-	Remove queen from row 1	[. . Q .]
69	Try place queen	1	1	[2]	Conflict (diagonal)	Try next column	[. . Q .]
70	Try place queen	1	2	[2]	Conflict (same column)	Try next column	[. . Q .]
71	Try place queen	1	3	[2]	No conflict	Place queen at (1,3)	[. . Q .] [. . . Q]
72	Try place queen	2	0	[2,3]	No conflict	Place queen at (2,0)	[. . Q .] [. . . Q] [Q . . .]
73	Try place queen	3	0	[2,3,0]	Conflict (same column)	Try next column	[. . Q .] [. . . Q] [Q . . .] [. . . .]
74	Try place queen	3	1	[2,3,0]	No conflict	Place queen at (3,1)	[. . Q .] [. . . Q] [Q . . .] [. Q . .]
75	All queens placed	4	-	[2,3,0,1]	-	Record solution	[. . Q .] [. . . Q] [Q . . .] [. Q . .]
76	Backtrack	3	-	[2,3,0]	-	Remove queen from row 3	[. . Q .] [. . . Q] [Q . . .]
77	Backtrack	2	-	[2,3]	-	Remove queen from row 2	[. . Q .] [. . . Q]
78	Backtrack	1	-	[2]	-	Remove queen from row 1	[. . Q .]
79	Backtrack	0	-	[]	-	Remove queen from row 0	[. . . .]
80	Try place queen	0	3	[]	No conflict	Place queen at (0,3)	[. . . Q]
81	Try place queen	1	0	[3]	No conflict	Place queen at (1,0)	[. . . Q] [Q . . .]
82	Try place queen	2	1	[3,0]	No conflict	Place queen at (2,1)	[. . . Q] [Q . . .] [. Q . .]
83	Try place queen	3	0	[3,0,1]	Conflict (same column)	Try next column	[. . . Q] [Q . . .] [. Q . .] [. . . .]
84	Try place queen	3	2	[3,0,1]	No conflict	Place queen at (3,2)	[. . . Q] [Q . . .] [. Q . .] [. . Q .]
85	All queens placed	4	-	[3,0,1,2]	-	Record solution	[. . . Q] [Q . . .] [. Q . .] [. . Q .]
86	Backtrack	3	-	[3,0,1]	-	Remove queen from row 3	[. . . Q] [Q . . .] [. Q . .]
87	Backtrack	2	-	[3,0]	-	Remove queen from row 2	[. . . Q] [Q . . .]
88	Try place queen	2	2	[3,0]	Conflict (diagonal)	Try next column	[. . . Q] [Q . . .]
89	Try place queen	2	3	[3,0]	Conflict (same column)	No more columns, backtrack	[. . . Q] [Q . . .]
90	Backtrack	1	-	[3]	-	Remove queen from row 1	[. . . Q]
91	Try place queen	1	1	[3]	No conflict	Place queen at (1,1)	[. . . Q] [. Q . .]
92	Try place queen	2	0	[3,1]	Conflict (same column)	Try next column	[. . . Q] [. Q . .] [. . . .]
93	Try place queen	2	1	[3,1]	Conflict (same column)	Try next column	[. . . Q] [. Q . .] [. . . .]
94	Try place queen	2	2	[3,1]	No conflict	Place queen at (2,2)	[. . . Q] [. Q . .] [. . Q .]
95	Try place queen	3	0	[3,1,2]	Conflict (diagonal)	Try next column	[. . . Q] [. Q . .] [. . Q .] [. . . .]
96	Try place queen	3	1	[3,1,2]	Conflict (same column)	Try next column	[. . . Q] [. Q . .] [. . Q .] [. . . .]
97	Try place queen	3	2	[3,1,2]	Conflict (same column)	Try next column	[. . . Q] [. Q . .] [. . Q .] [. . . .]
98	Try place queen	3	3	[3,1,2]	Conflict (same column)	No more columns, backtrack	[. . . Q] [. Q . .] [. . Q .]
99	Backtrack	3	-	[3,1]	-	Remove queen from row 3	[. . . Q] [. Q . .] [. . . .]
100	Backtrack	2	-	[3,1]	-	Remove queen from row 2	[. . . Q] [. Q . .]
101	Try place queen	2	3	[3,1]	Conflict (diagonal)	No more columns, backtrack	[. . . Q] [. Q . .]
102	Backtrack	1	-	[3]	-	Remove queen from row 1	[. . . Q]
103	Try place queen	1	2	[3]	No conflict	Place queen at (1,2)	[. . . Q] [. . Q .]
104	Try place queen	2	0	[3,2]	No conflict	Place queen at (2,0)	[. . . Q] [. . Q .] [Q . . .]
105	Try place queen	3	0	[3,2,0]	Conflict (same column)	Try next column	[. . . Q] [. . Q .] [Q . . .] [. . . .]
106	Try place queen	3	1	[3,2,0]	No conflict	Place queen at (3,1)	[. . . Q] [. . Q .] [Q . . .] [. Q . .]
107	All queens placed	4	-	[3,2,0,1]	-	Record solution	[. . . Q] [. . Q .] [Q . . .] [. Q . .]
108	Backtrack	3	-	[3,2,0]	-	Remove queen from row 3	[. . . Q] [. . Q .] [Q . . .]
109	Backtrack	2	-	[3,2]	-	Remove queen from row 2	[. . . Q] [. . Q .]
110	Try place queen	2	1	[3]	Conflict (diagonal)	Try next column	[. . . Q] [. . Q .]
111	Try place queen	2	2	[3]	Conflict (same column)	Try next column	[. . . Q] [. . Q .]
112	Try place queen	2	3	[3]	Conflict (same column)	No more columns, backtrack	[. . . Q] [. . Q .]
113	Backtrack	1	-	[3]	-	Remove queen from row 1	[. . . Q]
114	Backtrack	0	-	[]	-	Remove queen from row 0	[. . . .]
115	No more columns in row 0	-	-	-	-	All solutions found or exhausted	[. . . .]

💡 All columns tried in row 0, no more positions left, all solutions found or exhausted

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 17	After Step 29	After Step 30	After Step 39	After Step 79	After Step 85	Final
row	0	1	2	3	4	Back to 0	1	3	0	3	End
cols	[]	[0]	[0,2]	[0,2,3]	[0,3,1,2]	[]	[1]	[1,3,2,0]	[]	[3,0,1,2]	[]
solutions_count	0	0	0	0	1	1	1	2	2	3	4

Key Moments - 3 Insights

Why do we backtrack after trying all columns in a row?

Because if no column in the current row is safe (conflict detected), we must remove the queen from the previous row and try a different column there. This is shown in execution_table rows 12 and 29 where backtracking happens after all columns fail.

How do we know when a solution is found?

When the row number equals n (the board size), it means queens are placed in all rows safely. This is shown in execution_table row 17 where row=4 for n=4, and the solution is recorded.

Why do we keep track of columns in a vector?

The vector 'cols' stores the column index of the queen placed in each row. This helps quickly check conflicts and reconstruct the board. For example, after step 8, cols = [0,2,3] means queens at (0,0), (1,2), (2,3).

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the state of the board?

A Queens at (0,0), (1,2), (2,3)

B Queens at (0,0), (1,1), (2,3)

C Queens at (0,1), (1,2), (2,3)

D Queens at (0,0), (1,2), (2,2)

💡 Hint

Check the 'Cols Vector' and 'Visual State' columns at step 8 in execution_table

At which step does the algorithm first record a complete solution?

A Step 12

B Step 17

C Step 29

D Step 39

💡 Hint

Look for 'Record solution' action in execution_table

If the board size n was increased, how would the 'cols' vector change during execution?

A It would store more column indices, one per row

B It would store fewer column indices

C It would store row indices instead of columns

D It would remain empty

💡 Hint

Refer to variable_tracker showing 'cols' vector length matching current row

Concept Snapshot

N Queens Problem:
- Place N queens on NxN board so no two attack each other.
- Use backtracking: place queen row by row.
- Check conflicts: columns and diagonals.
- If conflict, try next column.
- If all rows placed, record solution.
- Backtrack to find all solutions.

Full Transcript

The N Queens Problem places N queens on an NxN chessboard so that no two queens threaten each other. The algorithm tries to place queens one row at a time, checking if the position is safe by ensuring no other queen is in the same column or diagonal. If a conflict is found, it tries the next column in the same row. When all queens are placed safely, it records the solution. If no column works in a row, it backtracks to the previous row to try a different column. This process continues until all solutions are found or all options are exhausted. The 'cols' vector tracks the column positions of queens placed so far, helping to check conflicts and reconstruct the board visually.

Practice

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

easy

A. Place queens only on the diagonal cells

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

C. Move queens to the center of the board

D. Count the total number of queens on a 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

   Only Place N queens on an NxN chessboard so that no two queens attack each other correctly states this goal, while others describe unrelated tasks.

3. Final Answer:

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

4. Quick Check:

   N Queens Problem = Place queens safely [OK]

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

Common Mistakes:

• Thinking queens can attack if placed on same diagonal only
• Confusing the problem with counting queens
• Assuming queens can share rows or columns

2. Which Rust syntax correctly declares a 2D vector to represent an NxN chessboard initialized with zeros?

easy

A. let board = vec![vec![0; n]; n];

B. let board = vec![0; n][vec![0; n]];

C. let board = vec![vec![n; 0]; n];

D. let board = vec![vec![0, n]; n];

Solution

1. Step 1: Understand Rust vector initialization

   To create a 2D vector with n rows and n columns filled with 0, use vec![vec![0; n]; n].

2. Step 2: Check each option

   let board = vec![vec![0; n]; n]; matches correct syntax; others have syntax errors or wrong order.

3. Final Answer:

   let board = vec![vec![0; n]; n]; -> Option A

4. Quick Check:

   2D vector init = vec![vec![0; n]; n] [OK]

Hint: Use vec![vec![value; cols]; rows] for 2D vectors [OK]

Common Mistakes:

• Using incorrect order of brackets
• Mixing values and sizes in vec! macro
• Trying to initialize with vec![0; n][vec![0; n]] which is invalid

3. What will be the output of the following Rust code snippet for n = 4?

fn is_safe(board: &Vec, row: usize, col: usize, n: usize) -> bool {
    for i in 0..col {
        if board[row][i] == 1 {
            return false;
        }
    }
    let mut i = row as i32;
    let mut j = col as i32;
    while i >= 0 && j >= 0 {
        if board[i as usize][j as usize] == 1 {
            return false;
        }
        i -= 1;
        j -= 1;
    }
    let mut i = row as i32;
    let mut j = col as i32;
    while i < n as i32 && j >= 0 {
        if board[i as usize][j as usize] == 1 {
            return false;
        }
        i += 1;
        j -= 1;
    }
    true
}

fn main() {
    let n = 4;
    let mut board = vec![vec![0; n]; n];
    board[1][0] = 1;
    println!("{}", is_safe(&board, 2, 1, n));
}

medium

A. true

B. Compilation error

C. Runtime panic

D. false

Solution

1. Step 1: Analyze the board and is_safe call

   Board has a queen at (1,0). We check if placing at (2,1) is safe.

2. Step 2: Check row, upper diagonal, and lower diagonal

   Row check: no queen in row 2 before col 1. Upper diagonal: (1,0) has queen, so is_safe returns false.

3. Final Answer:

   false -> Option D

4. Quick Check:

   Queen attacks on upper diagonal = false [OK]

Hint: Check all three directions: row, upper and lower diagonals [OK]

Common Mistakes:

• Ignoring diagonal checks
• Confusing row and column indices
• Assuming safe when queen is on diagonal

4. Identify the bug in this Rust function snippet for placing queens and suggest the fix:

fn solve_n_queens(board: &mut Vec, col: usize, n: usize) -> bool {
    if col >= n {
        return true;
    }
    for i in 0..n {
        if is_safe(board, i, col, n) {
            board[i][col] = 1;
            if solve_n_queens(board, col + 1, n) {
                return true;
            }
            board[i][col] = 0;
        }
    }
    false
}

medium

A. No bug; function is correct

B. Backtracking step resets board[i][col] incorrectly

C. Function should return false instead of true when col >= n

D. Missing base case for col == n

Solution

1. Step 1: Check base case correctness

   Base case returns true when col >= n, meaning all queens placed successfully.

2. Step 2: Verify backtracking logic

   Backtracking resets board[i][col] to 0 if deeper call fails, which is correct.

3. Final Answer:

   No bug; function is correct -> Option A

4. Quick Check:

   Backtracking logic and base case are correct [OK]

Hint: Backtracking resets state after failed recursive call [OK]

Common Mistakes:

• Removing or changing base case incorrectly
• Not resetting board cell during backtracking
• Returning wrong boolean values

5. Given the partial Rust code below, which modification will correctly print all distinct solutions for the N Queens Problem for n = 4?

fn solve_all(board: &mut Vec, col: usize, n: usize, solutions: &mut Vec>) {
    if col == n {
        solutions.push(board.clone());
        return;
    }
    for i in 0..n {
        if is_safe(board, i, col, n) {
            board[i][col] = 1;
            solve_all(board, col + 1, n, solutions);
            board[i][col] = 0;
        }
    }
}

fn main() {
    let n = 4;
    let mut board = vec![vec![0; n]; n];
    let mut solutions = Vec::new();
    solve_all(&mut board, 0, n, &mut solutions);
    // Which code snippet below correctly prints all solutions?
}

hard

A. for sol in solutions { println!("{}", sol); }

B. println!("{:?}", solutions);

C. for sol in &solutions { for row in sol { println!("{:?}", row); } println!("---"); }

D. for sol in &solutions { println!("{}", sol); }

Solution

1. Step 1: Understand solutions data structure

   solutions is a vector of boards, each board is Vec representing queen positions.

2. Step 2: Choose correct printing method

   for sol in &solutions { for row in sol { println!("{:?}", row); } println!("---"); } iterates over each solution and each row, printing rows clearly. Others print entire vectors directly or incorrectly.

3. Final Answer:

   for sol in &solutions { for row in sol { println!("{:?}", row); } println!("---"); } -> Option C

4. Quick Check:

   Iterate solutions and rows for clear output [OK]

Hint: Print each row of each solution separately for clarity [OK]

Common Mistakes:

• Printing entire vector at once causing unreadable output
• Not iterating by reference causing ownership errors
• Using {} instead of {:?} for vectors