Source: LeetCode
Genre: Hadr
Problem:
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
Example:
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
Problem:
Let's understand the problem first! On a chase board a queen can move,
- Horizontally
- Vertically
- Diagonally
The problem says, on a nxn chase board, we've to place n queens on n different places of that chase board such that no queen can attack any other queens, horizontally, vertically as well as diagonally.
The above picture of 8x8 chase board is a perfect example of an arrangement where every queens are safe from others.
Solution:
The chase board can be represented by a binary matrix (two dimensional array) where 0 means no queen and 1 means queen. Initially, every position of the matrix will be placed by 0.
Create a two dimensional array to represent the board.
static int[][] board = null;
Initialize the board.
void init(int numberOfQueens) {
this.board = new int[numberOfQueens][numberOfQueens];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
board[i][j] = 0;
}
}
}
Check if there's already a queen in a row.
boolean checkIfTheresAQueenInARow(int row) {
for (int i = 0; i < board.length; i++) {
if (board[row][i] == 1) {
return true;
}
}
return false;
}
Check if there's already a queen in a column.
boolean checkIfTheresAQueenInAColumn(int column) {
for (int i = 0; i < board.length; i++) {
if (board[i][column] == 1) {
return true;
}
}
return false;
}
Check if there's already a queen in diagonal positions.
boolean checkIfTheresQueenDiagonally(int row, int col) {
int rowCarry = 0;
int columnCarry = 0;
boolean res = false;
while (!res) {
if ((row - rowCarry) > -1 && (col - columnCarry) > -1) {
if (board[row - rowCarry][col - columnCarry] != 0) {
res = true;
}
}
if ((row - rowCarry) > -1 && (col + columnCarry) < board.length) {
if (board[row - rowCarry][col + columnCarry] != 0) {
res = true;
}
}
if ((row + rowCarry) < board.length && (col - columnCarry) > -1) {
if (board[row + rowCarry][col - columnCarry] != 0) {
res = true;
}
}
if ((row + rowCarry) < board.length && (col + columnCarry) < board.length) {
if (board[row + rowCarry][col + columnCarry] != 0) {
res = true;
}
}
rowCarry++;
columnCarry++;
if (rowCarry > board.length - 1 && columnCarry > board.length - 1) {
break;
}
}
return res;
}
Check if a position is safe (There's no queen row wise, column wise and diagonally).
boolean checkIfAPositionIsSafe(int row, int col) {
if (checkIfTheresAQueenInARow(row)) {
return false;
}
if (checkIfTheresAQueenInAColumn(col)) {
return false;
}
if (checkIfTheresQueenDiagonally(row, col)) {
return false;
}
return true;
}
Solve the problem by backtracking.
private void solveNQueensHelper(int row) {
if (row == board.length) {
listToReturn.add(print());
} else {
for (int col = 0; col < board.length; col++) {
if (checkIfAPositionIsSafe(row, col)) {
board[row][col] = 1;
row += 1;
solveNQueensHelper(row);
row = row - 1;
board[row][col] = 0;
}
}
}
}
Full code:
class Solution {
static int[][] board = null;
List < List < String >> listToReturn = new ArrayList < List < String >> ();
public List < List < String >> solveNQueens(int n) {
init(n);
solveNQueensHelper(0);
return listToReturn;
}
private void solveNQueensHelper(int row) {
if (row == board.length) {
listToReturn.add(print());
} else {
for (int col = 0; col < board.length; col++) {
if (checkIfAPositionIsSafe(row, col)) {
board[row][col] = 1;
row += 1;
solveNQueensHelper(row);
row = row - 1;
board[row][col] = 0;
}
}
}
}
List < String > print() {
List < String > individualMatch = new ArrayList < > ();
for (int i = 0; i < board.length; i++) {
StringBuffer sb = new StringBuffer();
for (int j = 0; j < board.length; j++) {
if (board[i][j] == 1) {
sb.append("Q");
} else {
sb.append(".");
}
}
individualMatch.add(sb.toString());
}
return individualMatch;
}
void init(int numberOfQueens) {
this.board = new int[numberOfQueens][numberOfQueens];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
board[i][j] = 0;
}
}
}
boolean checkIfTheresAQueenInARow(int row) {
for (int i = 0; i < board.length; i++) {
if (board[row][i] == 1) {
return true;
}
}
return false;
}
boolean checkIfTheresAQueenInAColumn(int column) {
for (int i = 0; i < board.length; i++) {
if (board[i][column] == 1) {
return true;
}
}
return false;
}
boolean checkIfTheresQueenDiagonally(int row, int col) {
int rowCarry = 0;
int columnCarry = 0;
boolean res = false;
while (!res) {
if ((row - rowCarry) > -1 && (col - columnCarry) > -1) {
if (board[row - rowCarry][col - columnCarry] != 0) {
res = true;
}
}
if ((row - rowCarry) > -1 && (col + columnCarry) < board.length) {
if (board[row - rowCarry][col + columnCarry] != 0) {
res = true;
}
}
if ((row + rowCarry) < board.length && (col - columnCarry) > -1) {
if (board[row + rowCarry][col - columnCarry] != 0) {
res = true;
}
}
if ((row + rowCarry) < board.length && (col + columnCarry) < board.length) {
if (board[row + rowCarry][col + columnCarry] != 0) {
res = true;
}
}
rowCarry++;
columnCarry++;
if (rowCarry > board.length - 1 && columnCarry > board.length - 1) {
break;
}
}
return res;
}
boolean checkIfAPositionIsSafe(int row, int col) {
if (checkIfTheresAQueenInARow(row)) {
return false;
}
if (checkIfTheresAQueenInAColumn(col)) {
return false;
}
if (checkIfTheresQueenDiagonally(row, col)) {
return false;
}
return true;
}
}