N Queens Problem in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of N Queens Board Representation

What is the printed board state after placing 4 queens in a valid solution for the 4-Queens problem?

DSA Go

package main
import "fmt"
func printBoard(board [][]int) {
    for _, row := range board {
        for _, val := range row {
            if val == 1 {
                fmt.Print("Q ")
            } else {
                fmt.Print(". ")
            }
        }
        fmt.Println()
    }
}
func main() {
    board := [][]int{
        {0, 1, 0, 0},
        {0, 0, 0, 1},
        {1, 0, 0, 0},
        {0, 0, 1, 0},
    }
    printBoard(board)
}

A

Q . . . 
. . Q . 
. . . Q 
. Q . . 

B

. . Q . 
Q . . . 
. . . Q 
. Q . . 

C

. Q . . 
. . . Q 
Q . . . 
. . Q . 

D

. . . Q 
Q . . . 
. Q . . 
. . Q . 

💡 Hint

Look carefully at the positions of 1s in the board array and match them to Q positions.

The board array has 1s at positions (0,1), (1,3), (2,0), and (3,2). This matches option C's printed board.

🧠 Conceptual

intermediate

Understanding Diagonal Attacks in N Queens

Which of the following conditions correctly checks if two queens at positions (r1, c1) and (r2, c2) are attacking each other diagonally?

A r1 - c1 == r2 - c2

B r1 + c1 == r2 + c2

C r1 == r2 || c1 == c2

D abs(r1 - r2) == abs(c1 - c2)

💡 Hint

Diagonal attack means difference in rows equals difference in columns.

Two queens attack diagonally if the absolute difference of their row indices equals the absolute difference of their column indices.

🔧 Debug

advanced

Identify the error in the backtracking function

What error will occur when running this backtracking function snippet for N Queens?

DSA Go

func solveNQueens(row int, board [][]int, n int) bool {
    if row == n {
        return true
    }
    for col := 0; col < n; col++ {
        if isSafe(row, col, board, n) {
            board[row][col] = 1
            if solveNQueens(row+1, board, n) {
                return true
            }
            board[row][col] = 0
        }
    }
    return false
}

// isSafe function omitted for brevity

A Logical error: function returns after first solution, missing others

B Stack overflow due to infinite recursion

C No error, function works correctly

D Index out of range error accessing board

💡 Hint

Check what happens after finding the first solution.

The function returns true immediately after finding the first solution, so it does not explore all possible solutions.

🚀 Application

advanced

Number of solutions for 5-Queens problem

How many distinct solutions exist for the 5-Queens problem?

A 10

B 8

C 5

D 2

💡 Hint

Recall the known counts of solutions for small N.

The 5-Queens problem has exactly 10 distinct solutions.

❓ Predict Output

expert

Output of partial board after placing queens

Given this partial board state after placing queens in a 6x6 board, what is the printed output?

DSA Go

package main
import "fmt"
func printBoard(board [][]int) {
    for _, row := range board {
        for _, val := range row {
            if val == 1 {
                fmt.Print("Q ")
            } else {
                fmt.Print(". ")
            }
        }
        fmt.Println()
    }
}
func main() {
    board := [][]int{
        {0, 0, 1, 0, 0, 0},
        {1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0},
        {0, 1, 0, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 1},
    }
    printBoard(board)
}

A

. Q . . . . 
. . . Q . . 
Q . . . . . 
. . Q . . . 
. . . . Q . 
. . . . . Q 

B

. . Q . . . 
Q . . . . . 
. . . . Q . 
. Q . . . . 
. . . Q . . 
. . . . . Q 

C

Q . . . . . 
. . Q . . . 
. . . . . Q 
. Q . . . . 
. . . Q . . 
. . . . Q . 

D

. . Q . . . 
. Q . . . . 
Q . . . . . 
. . . Q . . 
. . . . Q . 
. . . . . Q 

💡 Hint

Match the 1s in the board array to Q positions in each row.

The board has queens at (0,2), (1,0), (2,4), (3,1), (4,3), (5,5), matching option B's output.

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