N Queens Problem in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the chessboard with empty cells represented by '.'

DSA Go

board := make([][]byte, n)
for i := 0; i < n; i++ {
    board[i] = make([]byte, n)
    for j := 0; j < n; j++ {
        board[i][j] = [1]
    }
}

Drag options to blanks, or click blank then click option'

A'Q'

B'.'

C'X'

D'O'

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'Q' instead of '.' which represents a queen, not an empty cell.

Using characters like 'X' or 'O' which are not standard for empty cells.

The chessboard cells are initialized with '.' to represent empty spaces where queens can be placed later.

2fill in blank

medium

Complete the code to check if placing a queen at (row, col) is safe by checking the column above.

DSA Go

for i := 0; i < row; i++ {
    if board[i][[1]] == 'Q' {
        return false
    }
}

Drag options to blanks, or click blank then click option'

Acol

B0

Ci

Drow

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'row' instead of 'col' which checks the wrong column.

Using 'i' which is the row index, not the column.

We check the same column 'col' in all rows above the current 'row' to ensure no queen is placed there.

3fill in blank

hard

Fix the error in the diagonal check to ensure no queen is placed on the upper left diagonal.

DSA Go

for i, j := row, col; i >= 0 && j >= 0; i, j = i-1, [1] {
    if board[i][j] == 'Q' {
        return false
    }
}

Drag options to blanks, or click blank then click option'

Aj+1

Bj

Cj-1

Dj-2

Attempts:

3 left

💡 Hint

Common Mistakes

Incrementing j instead of decrementing causes checking the wrong diagonal.

Not changing j causes an infinite loop or wrong checks.

To move diagonally up-left, both row and column indices decrease by 1 each step.

4fill in blank

hard

Fill both blanks to check the upper right diagonal for queens.

DSA Go

for i, j := row, col; i >= 0 && j < n; i, j = i-1, [1] {
    if board[i][j] == 'Q' {
        return false
    }
}

board[row][col] = [2]

Drag options to blanks, or click blank then click option'

Aj+1

Bj-1

C'Q'

D'.'

Attempts:

3 left

💡 Hint

Common Mistakes

Using j-1 instead of j+1 for the diagonal movement.

Placing '.' instead of 'Q' when setting the queen.

To check upper right diagonal, column index j increases by 1 while row decreases by 1. Then place a queen 'Q' at the position.

5fill in blank

hard

Fill all three blanks to complete the recursive backtracking function that tries to place queens row by row.

DSA Go

func solve(row int, board [][]byte, n int, solutions *[][]string) {
    if row == n {
        var copyBoard []string
        for _, r := range board {
            copyBoard = append(copyBoard, string(r))
        }
        *solutions = append(*solutions, copyBoard)
        return
    }

    for col := 0; col < n; col++ {
        if isSafe(board, row, col, n) {
            board[row][col] = [1]
            solve(row+[2], board, n, solutions)
            board[row][col] = [3]
        }
    }
}

Drag options to blanks, or click blank then click option'

A'Q'

B1

C'.'

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Not backtracking by resetting the cell to '.' causes wrong solutions.

Incrementing row by wrong value or not incrementing at all.

Place a queen 'Q' at the current cell, move to the next row by adding 1, and backtrack by resetting the cell to '.' after recursion.

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