Printing all solutions in N-Queen Problem

Introduction to the N-Queen Problem

The N-Queen problem is a classic problem in computer science and mathematics that involves placing N queens on an N x N chessboard such that no two queens can attack each other. The challenge lies in finding all the distinct solutions to this problem, where a solution is a unique configuration of the N queens on the chessboard.

The problem is significant because it not only tests the problem-solving skills of programmers but also explores the concepts of backtracking, recursion, and optimization techniques. Solving the N-Queen problem efficiently requires a deep understanding of these fundamental computer science principles.

Naive Approach: Generating all Permutations using Recursion

One of the simplest approaches to solving the N-Queen problem is to generate all possible permutations of the queen placements and then check if each permutation is a valid solution. This can be achieved using a recursive function that generates all possible permutations of the row numbers for each column.

Here‘s the implementation in various programming languages:

C++

// C++ program to find all solutions of the N-Queens problem using recursion
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Function to check if the current placement is safe
bool isSafe(vector<int>& board, int currRow, int currCol) {
    // Check all previously placed queens
    for (int i = 0; i < board.size(); ++i) {
        int placedRow = board[i];
        // Columns are 1-based
        int placedCol = i + 1;
        // Check if the queen is on the same diagonal
        if (abs(placedRow - currRow) == abs(placedCol - currCol)) {
            return false; // Not safe
        }
    }
    // Safe to place the queen
    return true;
}

// Recursive function to generate all possible permutations
void nQueenUtil(int col, int n, vector<int>& board, vector<vector<int>>& res, vector<bool>& visited) {
    // If all queens are placed, add into res
    if (col > n) {
        res.push_back(board);
        return;
    }

    // Try placing a queen in each row
    // of the current column
    for (int row = 1; row <= n; ++row) {
        // Check if the row is already used
        if (!visited[row]) {
            // Check if it‘s safe to place the queen
            if (isSafe(board, row, col)) {
                // Mark the row as used
                visited[row] = true;
                // Place the queen
                board.push_back(row);
                // Recur to place the next queen
                nQueenUtil(col + 1, n, board, res, visited);
                // Backtrack: remove the queen
                board.pop_back();
                // Unmark row
                visited[row] = false;
            }
        }
    }
}

// Main function to find all distinct
// solutions to the n-queens puzzle
vector<vector<int>> nQueen(int n) {
    vector<vector<int>> res;
    // Current board configuration
    vector<int> board;
    // Track used rows
    vector<bool> visited(n + 1, false);
    // Start solving from the first column
    nQueenUtil(1, n, board, res, visited);
    return res;
}

int main() {
    int n = 4;
    vector<vector<int>> res = nQueen(n);
    for (int i = 0; i < res.size(); i++) {
        cout << "[";
        for (int j = 0; j < n; ++j) {
            cout << res[i][j];
            if (j != n - 1)
                cout << " ";
        }
        cout << "]\n";
    }
    return 0;
}

Java

// Java program to find all solutions of the N-Queens problem using recursion
import java.util.ArrayList;

class GfG {
    // Check if placement is safe
    static boolean isSafe(ArrayList<Integer> board, int currRow, int currCol) {
        for (int i = 0; i < board.size(); i++) {
            int placedRow = board.get(i);
            int placedCol = i + 1;
            // Check diagonals
            if (Math.abs(placedRow - currRow) ==
                Math.abs(placedCol - currCol)) {
                return false; // Not safe
            }
        }
        return true; // Safe to place
    }

    // Recursive utility to solve
    static void nQueenUtil(int col, int n,
                           ArrayList<Integer> board,
                           ArrayList<ArrayList<Integer>> res,
                           boolean[] visited) {
        // If all queens placed, add to res
        if (col > n) {
            res.add(new ArrayList<>(board));
            return;
        }

        // Try each row in column
        for (int row = 1; row <= n; row++) {
            // If row not used
            if (!visited[row]) {
                // Check safety
                if (isSafe(board, row, col)) {
                    // Mark row
                    visited[row] = true;
                    // Place queen
                    board.add(row);
                    // Recur for next column
                    nQueenUtil(col + 1, n, board,
                               res, visited);
                    // Backtrack
                    board.remove(board.size()-1);
                    visited[row] = false;
                }
            }
        }
    }

    // Function to solve N-Queen
    static ArrayList<ArrayList<Integer>> nQueen(int n) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> board = new ArrayList<>();
        boolean[] visited = new boolean[n +1];
        nQueenUtil(1, n, board, res, visited);
        return res;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<ArrayList<Integer>> res = nQueen(n);
        for (ArrayList<Integer> row : res) {
            System.out.print("[");
            for (int i = 0; i < row.size(); i++) {
                System.out.print(row.get(i));
                if (i != row.size()-1)
                  System.out.print(" ");
            }
            System.out.println("]");
        }
    }
}

Python

# Python program to find all solutions of the N-Queens problem using recursion
# Function to check if placement is safe
def isSafe(board, currRow, currCol):
    # Check all previously placed queens
    for i in range(len(board)):
        placedRow = board[i]
        placedCol = i + 1
        # Check diagonals
        if abs(placedRow - currRow) == \
           abs(placedCol - currCol):
           return False # Not safe
    return True # Safe to place

# Recursive utility to solve N-Queens
def nQueenUtil(col, n, board, res, visited):
    # If all queens placed, add to res
    if col > n:
        res.append(board.copy())
        return

    # Try each row in column
    for row in range(1, n+1):
        # If row not used
        if not visited[row]:
            # Check safety
            if isSafe(board, row, col):
                # Mark row
                visited[row] = True
                # Place queen
                board.append(row)
                # Recur for next column
                nQueenUtil(col+1, n, board, res, visited)
                # Backtrack
                board.pop()
                visited[row] = False

# Main N-Queen solver
def nQueen(n):
    res = []
    board = []
    visited = [False] * (n + 1)
    nQueenUtil(1, n, board, res, visited)
    return res

if __name__ == "__main__":
    n = 4
    res = nQueen(n)
    for row in res:
        print(row)

The time complexity of this naive approach is O(n! * n), where n! is the number of possible permutations, and n is the time required to check the validity of each permutation. The space complexity is O(n) for the recursion stack and the board configuration.

While this approach is straightforward to implement, it becomes computationally expensive as the value of n increases, as it generates and checks all possible permutations. This leads us to explore more efficient approaches to solve the N-Queen problem.

Expected Approach: Backtracking with Pruning

To optimize the solution, we can use a backtracking approach with pruning. Instead of generating all possible permutations, we build the solution incrementally, ensuring that the partial solution remains valid at each step. If a conflict occurs, we backtrack immediately, avoiding unnecessary computations.