8 queen problem

0 0 7 minutes read

The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such that none of them attack one another (no two are in the same row, column, or diagonal). More generally, the n queens problem places n queens on an n×n chessboard. There are different solutions for the problem. Backtracking | Set 3 (N Queen Problem) Branch and Bound | Set 5 (N Queen Problem) You can find detailed solutions at http://en.literateprograms.org/Eight_queens_puzzle_(C)

Explanation:

This pseudocode uses a backtracking algorithm to find a solution to the 8 Queen problem, which consists of placing 8 queens on a chessboard in such a way that no two queens threaten each other.
The algorithm starts by placing a queen on the first column, then it proceeds to the next column and places a queen in the first safe row of that column.
If the algorithm reaches the 8th column and all queens are placed in a safe position, it prints the board and returns true.
If the algorithm is unable to place a queen in a safe position in a certain column, it backtracks to the previous column and tries a different row.
The “isSafe” function checks if it is safe to place a queen on a certain row and column by checking if there are any queens in the same row, diagonal or anti-diagonal.
It’s worth to notice that this is just a high-level pseudocode and it might need to be adapted depending on the specific implementation and language you are using.

Here is an example of pseudocode for solving the 8 Queen problem using backtracking:

C++

#include <iostream>
#include <vector>
 
using namespace std;
 
const int N = 8;
 
bool isSafe(vector<vector<int> >& board, int row, int col)
{
    for (int x = 0; x < col; x++)
        if (board[row][x] == 1)
            return false;
    for (int x = row, y = col; x >= 0 && y >= 0; x--, y--)
        if (board[x][y] == 1)
            return false;
    for (int x = row, y = col; x < N && y >= 0; x++, y--)
        if (board[x][y] == 1)
            return false;
    return true;
}
 
bool solveNQueens(vector<vector<int> >& board, int col)
{
    if (col == N) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                cout << board[i][j] << " ";
            cout << endl;
        }
        cout << endl;
        return true;
    }
    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col)) {
            board[i][col] = 1;
            if (solveNQueens(board, col + 1))
                return true;
            board[i][col] = 0;
        }
    }
    return false;
}
 
int main()
{
    vector<vector<int> > board(N, vector<int>(N, 0));
    if (!solveNQueens(board, 0))
        cout << "No solution found";
    return 0;
}

Java

import java.util.Arrays;
class GFG {
 
    static final int N = 8;
 
    // function to check if it is safe to place
    // a queen at a particular position
    static boolean isSafe(int[][] board, int row, int col)
    {
 
        // check if there is a queen in the same row to the
        // left
        for (int x = 0; x < col; x++)
            if (board[row][x] == 1)
                return false;
 
        // check if there is a queen in the upper left
        // diagonal
        for (int x = row, y = col; x >= 0 && y >= 0;
             x--, y--)
            if (board[x][y] == 1)
                return false;
 
        // check if there is a queen in the lower left
        // diagonal
        for (int x = row, y = col; x < N && y >= 0;
             x++, y--)
            if (board[x][y] == 1)
                return false;
 
        // if there is no queen in any of the above
        // positions, then it is safe to place a queen
        return true;
    }
 
    // function to solve the N-queens problem using
    // backtracking
    static boolean solveNQueens(int[][] board, int col)
    {
 
        // if all queens are placed, print the board
        if (col == N) {
            for (int[] row : board)
                System.out.println(Arrays.toString(row));
            System.out.println();
            return true;
        }
 
        // try placing a queen in each row of the current
        // column
        for (int i = 0; i < N; i++) {
            if (isSafe(board, i, col)) {
                board[i][col] = 1; // place the queen
                if (solveNQueens(board, col + 1))
                    return true;
 
                // backtrack if placing the queen doesn't
                // lead to a solution
                board[i][col] = 0;
            }
        }
 
        // if no solution is found, return false
        return false;
    }
 
    // initialize the board with zeros and call the
    // solveNQueens function to solve the problem
    public static void main(String[] args)
    {
        int[][] board = new int[N][N];
        if (!solveNQueens(board, 0))
            System.out.println("No solution found");
    }
}

Python3

N = 8 # (size of the chessboard)
 
def solveNQueens(board, col):
    if col == N:
        print(board)
        return True
    for i in range(N):
        if isSafe(board, i, col):
            board[i][col] = 1
            if solveNQueens(board, col + 1):
                return True
            board[i][col] = 0
    return False
 
def isSafe(board, row, col):
    for x in range(col):
        if board[row][x] == 1:
            return False
    for x, y in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[x][y] == 1:
            return False
    for x, y in zip(range(row, N, 1), range(col, -1, -1)):
        if board[x][y] == 1:
            return False
    return True
 
board = [[0 for x in range(N)] for y in range(N)]
if not solveNQueens(board, 0):
    print("No solution found")

C#

using System;
using System.Linq;
 
class GFG {
 
  static readonly int N = 8;
 
  // function to check if it is safe to place
  // a queen at a particular position
  static bool isSafe(int[,] board, int row, int col)
  {
 
    // check if there is a queen in the same row to the
    // left
    for (int x = 0; x < col; x++)
      if (board[row, x] == 1)
        return false;
 
    // check if there is a queen in the upper left
    // diagonal
    for (int x = row, y = col; x >= 0 && y >= 0;
         x--, y--)
      if (board[x, y] == 1)
        return false;
 
    // check if there is a queen in the lower left
    // diagonal
    for (int x = row, y = col; x < N && y >= 0;
         x++, y--)
      if (board[x, y] == 1)
        return false;
 
    // if there is no queen in any of the above
    // positions, then it is safe to place a queen
    return true;
  }
 
  // function to solve the N-queens problem using
  // backtracking
  static bool solveNQueens(int[,] board, int col)
  {
 
    // if all queens are placed, print the board
    if (col == N) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          Console.Write(board[i, j] + " ");
        }
        Console.WriteLine();
      }
      Console.WriteLine();
      return true;
    }
 
    // try placing a queen in each row of the current
    // column
    for (int i = 0; i < N; i++) {
      if (isSafe(board, i, col)) {
        board[i, col] = 1; // place the queen
        if (solveNQueens(board, col + 1))
          return true;
 
        // backtrack if placing the queen doesn't
        // lead to a solution
        board[i, col] = 0;
      }
    }
 
    // if no solution is found, return false
    return false;
  }
 
  // initialize the board with zeros and call the
  // solveNQueens function to solve the problem
  public static void Main(string[] args)
  {
    int[,] board = new int[N, N];
    if (!solveNQueens(board, 0))
      Console.WriteLine("No solution found");
  }
}

Javascript

const N = 8;
 
// function to check if it is safe to place a queen at a particular position
function isSafe(board, row, col) {
  // check if there is a queen in the same row to the left
  for (let x = 0; x < col; x++) {
    if (board[row][x] == 1) {
      return false;
    }
  }
 
  // check if there is a queen in the upper left diagonal
  for (let x = row, y = col; x >= 0 && y >= 0; x--, y--) {
    if (board[x][y] == 1) {
      return false;
    }
  }
 
  // check if there is a queen in the lower left diagonal
  for (let x = row, y = col; x < N && y >= 0; x++, y--) {
    if (board[x][y] == 1) {
      return false;
    }
  }
 
  // if there is no queen in any of the above positions, then it is safe to place a queen
  return true;
}
 
// function to solve the N-queens problem using backtracking
function solveNQueens(board, col) {
  // if all queens are placed, print the board
  if (col == N) {
    for (let i = 0; i < N; i++) {
      console.log(board[i].join(" "));
    }
    console.log("\n");
    return true;
  }
 
  // try placing a queen in each row of the current column
  for (let i = 0; i < N; i++) {
    if (isSafe(board, i, col)) {
      board[i][col] = 1; // place the queen
      if (solveNQueens(board, col + 1)) {
        return true;
      }
      board[i][col] = 0; // backtrack if placing the queen doesn't lead to a solution
    }
  }
 
  // if no solution is found, return false
  return false;
}
 
// initialize the board with zeros and call the solveNQueens function to solve the problem
let board = Array(N)
  .fill()
  .map(() => Array(N).fill(0));
 
if (!solveNQueens(board, 0)) {
  console.log("No solution found");
}

Output

[[1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1], [0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0]]

Time Complexity : O((m + q) log^2 n)
Space Complexity : O((m + q) log n)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!