N Queens Problem in DSA Go - Build from Scratch

N Queens Problem

📖 Scenario: You are helping a chess club find all the ways to place n queens on an n x n chessboard so that no two queens attack each other. Queens can attack horizontally, vertically, and diagonally. Your task is to write a program that finds all valid arrangements.

🎯 Goal: Build a Go program that solves the N Queens problem for a given n. The program will find all possible ways to place n queens on the board so that none attack each other, and print each solution as a list of queen positions.

📋 What You'll Learn

Create a variable n for the board size

Create a slice board to represent queen positions by row

Write a function isSafe to check if a queen can be placed safely

Write a recursive function solveNQueens to find all solutions

Print all solutions found

💡 Why This Matters

🌍 Real World

Solving the N Queens problem helps understand backtracking algorithms used in puzzles, scheduling, and constraint satisfaction problems.

💼 Career

Backtracking and recursion are common in technical interviews and real-world software problems involving search and optimization.

1

Set up board size and initial board

Create an integer variable n and set it to 4. Then create a slice of integers called board with length n, initialized with zeros.

DSA Go

n := 4
board := make([]int, n) // Your code here

Hint

Use make([]int, n) to create a slice of length n.

2

Write the isSafe function

Write a function isSafe that takes board []int, row int, and col int as parameters and returns a bool. It should return true if placing a queen at board[row] = col does not conflict with queens in previous rows. Check for column and diagonal conflicts.

DSA Go

package main

import "fmt"

func main() {
    n := 4
    board := make([]int, n)
}

// Write isSafe(board []int, row int, col int) bool function below
// Your code here

Hint

Check if any previous queen is in the same column or diagonal by comparing positions.

3

Write the solveNQueens recursive function

Write a recursive function solveNQueens that takes board []int, row int, n int, and a pointer to a slice of slices of int called solutions *[][]int. It should try placing a queen in each column of the current row, check safety with isSafe, and recurse to the next row. When row == n, append a copy of board to *solutions.

DSA Go

package main

import "fmt"

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

// Write solveNQueens(board []int, row int, n int, solutions *[][]int) function below
// Your code here

func main() {
    n := 4
    board := make([]int, n)
}

Hint

Use recursion to place queens row by row. When all rows are placed, save the solution.

4

Print all solutions found

In main, create a variable solutions as a slice of slices of int. Call solveNQueens(board, 0, n, &solutions). Then use a for loop with variables i and solution to iterate over solutions and print each solution with fmt.Printf("Solution %d: %v\n", i+1, solution).

DSA Go

package main

import "fmt"

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

func solveNQueens(board []int, row int, n int, solutions *[][]int) {
    if row == n {
        solution := make([]int, n)
        copy(solution, board)
        *solutions = append(*solutions, solution)
        return
    }
    for col := 0; col < n; col++ {
        if isSafe(board, row, col) {
            board[row] = col
            solveNQueens(board, row+1, n, solutions)
        }
    }
}

func main() {
    n := 4
    board := make([]int, n)
    // Your code here
}

Hint

Use a slice of slices to store all solutions and print them with their index.

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