Source: LeetCode.
Genre: Hard
Problem:
Genre: Hard
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,
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 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.
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;
}
}
hastaLaVista
You may follow me on LinkedIn, Github, facebook
Good job, but I think initialization the board is having a problem. this.board = new int[numberOfQueens][numberOfQueens]; Here, while initializing don't use numberOfQueen, but since you already know, a chess board forms of 8 blocks, put 8, 8.
ReplyDeleteThe code is for solving n queens, It's not aiming to solve specific blocks size.
Delete