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 Falsedef 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 Trueboard = [[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 positionfunction 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 backtrackingfunction 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 problemlet 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)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
