The N-Queens problem involves placing N queens on an N×N chessboard such that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal. This program implements a backtracking algorithm to find all possible solutions to the N-Queens problem.

Program Structure

The program consists of a backtracking algorithm that recursively places queens on the board and checks for conflicts. If a valid placement is found, it proceeds to the next row. If a conflict is detected, it backtracks to try another position.

Go Code

package main

import (
    "fmt"
)

// NQueens solves the N-Queens problem using backtracking.
func NQueens(n int) [][]int {
    // board will store the column index for the queen in each row
    board := make([]int, n)
    var solutions [][]int
    solveNQueens(n, 0, board, &solutions)
    return solutions
}

// solveNQueens tries to place queens on the board
func solveNQueens(n, row int, board []int, solutions *[][]int) {
    if row == n {
        // If all rows are filled, add the solution to the results
        solution := make([]int, n)
        copy(solution, board)
        *solutions = append(*solutions, solution)
        return
    }

    // Try placing a queen in each column of the current row
    for col := 0; col < n; col++ {
        if isSafe(board, row, col) {
            board[row] = col
            solveNQueens(n, row+1, board, solutions)
        }
    }
}

// isSafe checks if placing a queen at (row, col) is safe
func isSafe(board []int, row, col int) bool {
    for i := 0; i < row; i++ {
        // Check if the queen is in the same column or diagonal
        if board[i] == col || board[i]-i == col-row || board[i]+i == col+row {
            return false
        }
    }
    return true
}

// printSolution prints a visual representation of the board with queens
func printSolution(solution []int) {
    n := len(solution)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if solution[i] == j {
                fmt.Print("Q ")
            } else {
                fmt.Print(". ")
            }
        }
        fmt.Println()
    }
}

func main() {
    n := 8 // You can change this value to solve for a different size board
    solutions := NQueens(n)
    
    fmt.Printf("Found %d solutions for %d-Queens problem\n", len(solutions), n)
    
    // Print each solution in a human-readable format
    for i, solution := range solutions {
        fmt.Printf("Solution #%d:\n", i+1)
        printSolution(solution)
        fmt.Println()
    }
}
    

Explanation of Code

This Go program is structured as follows:

• NQueens function: The main function that initializes the board and starts the backtracking process. It returns a slice of solutions, where each solution is represented by the column positions of the queens in each row.
• solveNQueens function: A recursive function that attempts to place queens row by row. It checks if placing a queen in a given position is safe (i.e., no other queens can attack it). If safe, it proceeds to the next row. If all rows are filled, it adds the solution to the results.
• isSafe function: This function checks if placing a queen at a given position (row, col) is safe from other queens placed on the board. It ensures that the queen is not in the same column or diagonal as any other queen.
• printSolution function: This function prints the board visually, representing queens as “Q” and empty spaces as “.”.
• main function: The entry point of the program. It defines the size of the chessboard (8×8 in this case), calls the NQueens function, and prints all found solutions.

Output Example

For an 8-Queens problem, the output might look like this:

Found 92 solutions for 8-Queens problem
Solution #1:
. . . . Q . . .
. . . . . Q . .
. . . Q . . . .
. . Q . . . . .
. Q . . . . . .
. . . . . . Q .
. . . . . . . Q
Q . . . . . . .

Solution #2:
. . . . . . Q .
. . . Q . . . .
. . Q . . . . .
. . . . Q . . .
Q . . . . . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .

...
    

Conclusion

The N-Queens problem is a classic example of a backtracking algorithm that explores all possible configurations of queens on the chessboard, eliminating invalid placements as it proceeds. This program efficiently solves the problem for any board size N, using backtracking and recursion to find all possible solutions.