Given the dimension of a chess board (N x M), determine the minimum number of queens required to cover all the squares of the board. A queen can attack any square along its row, column or diagonals.
Examples:
Input : N = 8, M = 8
Output : 5
Layout : Q X X X X X X X
X X Q X X X X X
X X X X Q X X X
X Q X X X X X X
X X X Q X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
Input : N = 3, M = 5
Output : 2
Layout : Q X X X X
X X X X X
X X X Q X
This article attempts to solve the problem in a very simple way without much optimization.
- Step 1: Starting from any corner square of the board, find an ‘uncovered’ square (Uncovered square is a square which isn’t attacked by any of the queens already placed). If none found, goto Step 4.
- Step 2: Place a Queen on this square and increment variable ‘count’ by 1.
- Step 3: Repeat step 1.
- Step 4: Now, you’ve got a layout where every square is covered. Therefore, the value of ‘count’ can be the answer. However, you might be able to do better, as there might exist a better layout with lesser number of queens. So, store this ‘count’ as the best value till now and proceed to find a better solution.
- Step 5: Remove the last queen placed and place it in the next ‘uncovered’ cell. Step 6: Proceed recursively and try out all the possible layouts. Finally, the one with the least number of queens is the answer.
Implementation: Dry run the following code for better understanding.
C++
#include <bits/stdc++.h>using namespace std;// The chessboard is represented by a 2D array.bool board[8][8];// N x M is the dimension of the chess board.const int N = 8, M = 8;// The minimum number of queens required.// Initially, set to MAX_VAL.int minCount = INT_MAX;string layout; // Stores the best layout.// Stores the current layout in 'layout'// variable as String.void storeLayout(){ stringstream ss; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) ss << (board[i][j] ? "Q " : "X "); ss << "\n"; } layout = ss.str();}// Returns 'true' if the square (row, col) is// being attacked by at least one queen.bool isAttacked(int row, int col){ int i, j; // Check the 'col'th column for any queen. for (i = 0; i < N; ++i) if (board[i][col]) return true; // Check the 'row'th row for any queen. for (j = 0; j < M; ++j) if (board[row][j]) return true; // Check the diagonals for any queen. for (i = 0; i < min(N, M); ++i) if (row - i >= 0 && col - i >= 0 && board[row - i][col - i]) return true; else if (row - i >= 0 && col + i < M && board[row - i][col + i]) return true; else if (row + i < N && col - i >= 0 && board[row + i][col - i]) return true; else if (row + i < N && col + i < M && board[row + i][col + i]) return true; // This square is unattacked. Hence return 'false'. return false;}// Finds minimum count of queens needed and places them.void placeQueen(int countSoFar){ int i, j; if (countSoFar >= minCount) // We've already obtained a solution with lesser or // same number of queens. Hence, no need to proceed. return; bool flag = false; while (!flag) { for (i = 0; i < N; ++i) for (j = 0; j < M; ++j) { if (!isAttacked(i, j)) { i = N; flag = true; break; } } if (flag) break; // All squares all covered. Hence, this // is the best solution till now. minCount = countSoFar; storeLayout(); break; } // Checks if there exists any unattacked cells. for (i = 0; i < N; ++i) for (j = 0; j < M; ++j) { if (!isAttacked(i, j)) { // Square (i, j) is unattacked. // Therefore, place a queen here. board[i][j] = true; // Increment 'count' and proceed // recursively. placeQueen(countSoFar + 1); // Remove this queen and attempt to // find a better solution. board[i][j] = false; } }}// Driver codeint main(){ memset(board, false, sizeof(board)); placeQueen(0); cout << minCount << endl; cout << "\nLayout: \n" << layout;} |
Java
// Java program to find minimum number of queens needed// to cover a given chess board.public class Backtracking { // The chessboard is represented by a 2D array. static boolean[][] board; // N x M is the dimension of the chess board. static int N, M; // The minimum number of queens required. // Initially, set to MAX_VAL. static int minCount = Integer.MAX_VALUE; static String layout; // Stores the best layout. // Driver code public static void main(String[] args) { N = 8; M = 8; board = new boolean[N][M]; placeQueen(0); System.out.println(minCount); System.out.println("\nLayout: \n" + layout); } // Finds minimum count of queens needed and places them. static void placeQueen(int countSoFar) { int i, j; if (countSoFar >= minCount) // We've already obtained a solution with lesser // or same number of queens. Hence, no need to // proceed. return; // Checks if there exists any unattacked cells. findUnattackedCell : { for (i = 0; i < N; ++i) for (j = 0; j < M; ++j) if (!isAttacked(i, j)) // Square (i, j) is unattacked. break findUnattackedCell; // All squares all covered. Hence, this // is the best solution till now. minCount = countSoFar; storeLayout(); return; } for (i = 0; i < N; ++i) for (j = 0; j < M; ++j) { if (!isAttacked(i, j)) { // Square (i, j) is unattacked. // Therefore, place a queen here. board[i][j] = true; // Increment 'count' and proceed // recursively. placeQueen(countSoFar + 1); // Remove this queen and attempt to // find a better solution. board[i][j] = false; } } } // Returns 'true' if the square (row, col) is // being attacked by at least one queen. static boolean isAttacked(int row, int col) { int i, j; // Check the 'col'th column for any queen. for (i = 0; i < N; ++i) if (board[i][col]) return true; // Check the 'row'th row for any queen. for (j = 0; j < M; ++j) if (board[row][j]) return true; // Check the diagonals for any queen. for (i = 0; i < Math.min(N, M); ++i) if (row - i >= 0 && col - i >= 0 && board[row - i][col - i]) return true; else if (row - i >= 0 && col + i < M && board[row - i][col + i]) return true; else if (row + i < N && col - i >= 0 && board[row + i][col - i]) return true; else if (row + i < N && col + i < M && board[row + i][col + i]) return true; // This square is unattacked. Hence return 'false'. return false; } // Stores the current layout in 'layout' // variable as String. static void storeLayout() { StringBuilder sb = new StringBuilder(); for (boolean[] row : board) { for (boolean cell : row) sb.append(cell ? "Q " : "X "); sb.append("\n"); } layout = sb.toString(); }} |
C#
using System;using System.Text;class Program { // The chessboard is represented by a 2D array static bool[, ] board = new bool[8, 8]; // N * M is the dimension of the chess board const int N = 8, M = 8; // The minimum number of queens required. // Initially, set to MAX_VALUE. static int minCount = int.MaxValue; // Stores the best layout. static string layout; // Stores the current layout in 'layout' // variable as String. static void StoreLayout() { StringBuilder sb = new StringBuilder(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { sb.Append(board[i, j] ? "Q " : "X "); } sb.Append("\n"); } layout = sb.ToString(); } // Returns 'true' if the square (row, col) is // being attacked by at least one queen. static bool IsAttacked(int row, int col) { int i, j; // Check the 'col'th column for any queen. for (i = 0; i < N; ++i) { if (board[i, col]) return true; } // Check the 'row'th row for any queen. for (j = 0; j < M; ++j) { if (board[row, j]) return true; } // Check the diagonals for any queen. for (i = 0; i < Math.Min(N, M); ++i) { if (row - i >= 0 && col - i >= 0 && board[row - i, col - i]) return true; else if (row - i >= 0 && col + i < M && board[row - i, col + i]) return true; else if (row + i < N && col - i >= 0 && board[row + i, col - i]) return true; else if (row + i < N && col + i < M && board[row + i, col + i]) return true; } // This square is unattacked. Hence return 'false'. return false; } // Finds minimum count of queens needed and places them. static void PlaceQueen(int countSoFar) { int i, j; // We've already obtained a solution with lesser or // same number of queens. Hence, no need to proceed. if (countSoFar >= minCount) return; bool flag = false; while (!flag) { for (i = 0; i < N; ++i) { for (j = 0; j < M; ++j) { if (!IsAttacked(i, j)) { i = N; flag = true; break; } } if (flag) break; } if (flag) break; // All squares all covered. Hence, this // is the best solution till now. minCount = countSoFar; StoreLayout(); break; } // Checks if there exists any unattacked cells. for (i = 0; i < N; ++i) { for (j = 0; j < M; ++j) { if (!IsAttacked(i, j)) { // Square (i, j) is unattacked. // Therefore, place a queen here. board[i, j] = true; // Increment 'count' and proceed // recursively. PlaceQueen(countSoFar + 1); // Remove this queen and attempt to // find a better solution. board[i, j] = false; } } } } static void Main() { Array.Clear(board, 0, board.Length); PlaceQueen(0); Console.WriteLine(minCount); Console.WriteLine("\nLayout: \n" + layout); }} |
Javascript
// The chessboard is represented by a 2D array.const board = Array.from(Array(8), () => new Array(8).fill(false));// N x M is the dimension of the chess board.const N = 8, M = 8;// The minimum number of queens required.// Initially, set to MAX_VALUE.let minCount = Number.MAX_VALUE;let layout = ""; // Stores the best layout.// Stores the current layout in 'layout'// variable as String.function storeLayout() { let str = ""; for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if (board[i][j]) { str += "Q "; } else { str += "X "; } } str += "\n"; } layout = str;}// Returns 'true' if the square (row, col) is// being attacked by at least one queen.function isAttacked(row, col) { let i, j; // Check the 'col'th column for any queen. for (i = 0; i < N; ++i) { if (board[i][col]) { return true; } } // Check the 'row'th row for any queen. for (j = 0; j < M; ++j) { if (board[row][j]) { return true; } } // Check the diagonals for any queen. for (i = 0; i < Math.min(N, M); ++i) { if ( row - i >= 0 && col - i >= 0 && board[row - i][col - i]) { return true; } else if ( row - i >= 0 && col + i < M && board[row - i][col + i] ) { return true; } else if ( row + i < N && col - i >= 0 && board[row + i][col - i] ) { return true; } else if ( row + i < N && col + i < M && board[row + i][col + i] ) { return true; } } // This square is unattacked. Hence return 'false'. return false;}// Finds minimum count of queens needed and places them.function placeQueen(countSoFar) { let i, j; if (countSoFar >= minCount) { // We've already obtained a solution with lesser or // same number of queens. Hence, no need to proceed. return; } let flag = false; while (!flag) { for (i = 0; i < N; ++i) { for (j = 0; j < M; ++j) { if (!isAttacked(i, j)) { i = N; flag = true; break; } } if (flag) { break; } } if (flag) { break; } // All squares are covered. Hence, this // is the best solution till now. minCount = countSoFar; storeLayout(); break; } // Checks if there exists any unattacked cells. for (i = 0; i < N; ++i) { for (j = 0; j < M; ++j) { if (!isAttacked(i, j)) { // Square (i, j) is unattacked. // Therefore, place a queen here. board[i][j] = true; // Increment 'count' and proceed // recursively. placeQueen(countSoFar + 1); // Remove this queen and attempt to // find a better solution. board[i][j] = false; } } }}// Driver codeplaceQueen(0);console.log(minCount);console.log("\nLayout: \n" + layout); |
Output:
5 Layout: Q X X X X X X X X X Q X X X X X X X X X Q X X X X Q X X X X X X X X X Q X X X X X X X X X X X X X X X X X X X X X X X X X X X X
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!
