N Queens Problem in DSA Go

Mental Model

Place N queens on an NxN chessboard so that no two queens attack each other. This means no two queens share the same row, column, or diagonal.

Analogy: Imagine placing N guards in a museum with N rooms arranged in a grid. Each guard watches their row, column, and diagonals. You want to place them so none can see each other.

Board 4x4 empty:
. . . .
. . . .
. . . .
. . . .

Each dot is an empty cell where a queen can be placed.

Dry Run Walkthrough

Input: board size N=4

Goal: Place 4 queens on a 4x4 board so none attack each other

Step 1: Place queen at row 0, column 1

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

Why: Start placing queen in first row at column 1 to try a safe spot

Step 2: Place queen at row 1, column 3

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

Why: Place second queen in second row at column 3, safe from first queen

Step 3: Place queen at row 2, column 0

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

Why: Column 0 safe, no diagonal conflicts with queens at (0,1) or (1,3)

Step 4: Try placing queen at row 3, column 0 - conflict found, backtrack

. Q . .
. . . Q
Q . . .
Q . . . (conflict)

Why: Column 0 conflicts with queen at (2,0)

Step 5: Try placing queen at row 3, column 1 - conflict found, backtrack

. Q . .
. . . Q
Q . . .
. Q . . (conflict)

Why: Column 1 conflicts with queen at (0,1)

Step 6: Place queen at row 3, column 2

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

Why: Column 2 safe from all previous queens, solution found

Result:

Final board:
. Q . .
. . . Q
Q . . .
. . Q .

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func isSafe(board [][]bool, row, col, n int) bool {
	// Check column for another queen
	for i := 0; i < row; i++ {
		if board[i][col] {
			return false
		}
	}

	// Check upper left diagonal
	for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if board[i][j] {
			return false
		}
	}

	// Check upper right diagonal
	for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if board[i][j] {
			return false
		}
	}

	return true
}

func solveNQueensUtil(board [][]bool, row, n int, solutions *[][]string) {
	if row == n {
		// Found a solution, convert board to string format
		var solution []string
		for i := 0; i < n; i++ {
			var rowStr string
			for j := 0; j < n; j++ {
				if board[i][j] {
					rowStr += "Q"
				} else {
					rowStr += "."
				}
			}
			solution = append(solution, rowStr)
		}
		*solutions = append(*solutions, solution)
		return
	}

	for col := 0; col < n; col++ {
		if isSafe(board, row, col, n) {
			board[row][col] = true // Place queen
			solveNQueensUtil(board, row+1, n, solutions) // Recurse for next row
			board[row][col] = false // Backtrack
		}
	}
}

func solveNQueens(n int) [][]string {
	board := make([][]bool, n)
	for i := range board {
		board[i] = make([]bool, n)
	}
	var solutions [][]string
	solveNQueensUtil(board, 0, n, &solutions)
	return solutions
}

func main() {
	n := 4
	solutions := solveNQueens(n)
	for i, sol := range solutions {
		fmt.Printf("Solution %d:\n", i+1)
		for _, row := range sol {
			fmt.Println(row)
		}
		fmt.Println()
	}
}

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

Check if any queen is placed in the same column above current row

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

Check upper left diagonal for queen conflicts

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

Check upper right diagonal for queen conflicts

if row == n { // Found a solution return }

If all rows are processed, record the current board as a solution

for col := 0; col < n; col++ { if isSafe(board, row, col, n) { board[row][col] = true solveNQueensUtil(board, row+1, n, solutions) board[row][col] = false } }

Try placing queen in each column of current row, recurse, then backtrack

Output

Solution 1:

.Q..

...Q

Q...

..Q.



Solution 2:

..Q.

Q...

...Q

.Q..

Complexity Analysis

Time: O(N!) because each row tries N columns and pruning reduces possibilities but worst case is factorial

Space: O(N^2) for the board and recursion stack up to depth N

vs Alternative: Brute force tries all N^N placements, backtracking prunes invalid branches early, greatly reducing search space

Edge Cases

N=1 (smallest board)

Returns one solution with a single queen

DSA Go

if row == n { // record solution }

N=2 or N=3 (no solutions)

Returns empty list as no valid placements exist

DSA Go

for col := 0; col < n; col++ { if isSafe(...) { ... } }

Large N (e.g., N=8)

Finds all solutions but takes longer due to combinatorial complexity

DSA Go

backtracking recursion with pruning in isSafe

When to Use This Pattern

When you see a problem asking to place items on a grid without conflicts in rows, columns, and diagonals, reach for backtracking with pruning because it systematically explores valid placements.

Common Mistakes

Mistake: Not checking diagonals for conflicts, only rows and columns
Fix: Add checks for both upper left and upper right diagonals in isSafe function

Mistake: Not backtracking (undoing) queen placement after recursive call
Fix: Set board[row][col] = false after recursion to remove queen and try other positions

Summary

Places N queens on an NxN board so no two queens attack each other.

Use it when you need to find all safe arrangements of items with mutual exclusion constraints on rows, columns, and diagonals.

The key insight is to place queens row by row, checking safety, and backtrack when stuck.

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