Algorithm
Problem Name: 51. N-Queens
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
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 1:
Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1 Output: [["Q"]]
Constraints:
1 <= n <= 9
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#define IDX(I, J, SZ) ((I) * (SZ) + J)
void set_flags(int *buff, int i, int j, int n, int flag) {
int k, x, y;
buff[IDX(i, j, n)] = flag;
for (k = 0; k < n; k ++) { // row
if (k != j && buff[IDX(i, k, n)] != -1) {
buff[IDX(i, k, n)] += flag ? 1 : -1;
}
}
for (k = 0; k < n; k ++) { // col
if (k != i && buff[IDX(k, j, n)] != -1) {
buff[IDX(k, j, n)] += flag ? 1 : -1;
}
x = k;
y = j - i + k;
if (y >= 0 && y < n) {
if (x != i && y != j && buff[IDX(x, y, n)] != -1) {
buff[IDX(x, y, n)] += flag ? 1 : -1;
}
}
y = j + i - k;
if (y >= 0 && y < n) {
if (x != i && y != j && buff[IDX(x, y, n)] != -1) {
buff[IDX(x, y, n)] += flag ? 1 : -1;
}
}
}
}
void bt(int n, char ****pp, int *psz, int *pn, int *buff, int row) {
int i, j, col, k;
if (row == n) {
// all done
if (*psz == *pn) {
*psz *= 2;
(*pp) = realloc(*pp, *psz * sizeof(char **));
//assert(*pp);
}
(*pp)[*pn] = malloc(n * sizeof(char *));
for (i = 0; i < n; i ++) {
(*pp)[*pn][i] = malloc((n + 1) * sizeof(char));
//assert((*pp)[*pn][i]);
for (j = 0; j < n; j ++) {
(*pp)[*pn][i][j] = buff[IDX(i, j, n)] == -1 ? 'Q' : '.';
}
(*pp)[*pn][i][j] = 0;
}
(*pn) ++;
return;
}
for (col = 0; col < n; col ++) {
if (buff[IDX(row, col, n)] == 0) {
set_flags(buff, row, col, n, -1);
bt(n, pp, psz, pn, buff, row + 1);
set_flags(buff, row, col, n, 0);
}
}
}
char*** solveNQueens(int n, int* returnSize) {
char ***p;
int *buff;
int psz;
psz = 10;
p = malloc(psz * sizeof(char **));
buff = calloc(n * n, sizeof(int));
//assert(result && buff);
*returnSize = 0;
bt(n, &p, &psz, returnSize, buff, 0);
free(buff);
if (!*returnSize) {
free(p);
p = NULL;
}
return p;
}
Input
n = 4
Output
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;
class Solution {
public:
bool isValid(vector<int> &columns, int row) {
for (int i = 0; i < row; i++) {
if (columns[i] == columns[row]
|| abs(columns[i] - columns[row]) == (row - i)) {
return false;
}
}
return true;
}
void placeQueens(vector < vector<string> > &ret, vector<int> &columns, int row) {
int n = columns.size();
if (row == n) { /* found one solution! */
vector < string> solution;
/* build solution vector */
for (int i = 0; i < n; i++) {
string line(n, '.');
line[columns[i]] = 'Q';
solution.push_back(line);
}
ret.push_back(solution);
return;
}
for (int j = 0; j < n; j++) {
/* try to place a queen in this row */
columns[row] = j;
/* put another queen in next row if this row's position is valid */
if (isValid(columns, row)) {
placeQueens(ret, columns, row + 1);
}
}
}
vector < vector<string> > solveNQueens(int n) {
vector<vector<string> > ret;
vector<int> columns(n, 0);
placeQueens(ret, columns, 0);
return ret;
}
};
int main() {
Solution s;
vector < vector<string> > ret;
ret = s.solveNQueens(4);
for (int i = 0; i < ret.size(); i++) {
for (int j = 0; j < ret[0].size(); j++) {
cout << ret[i][j] << endl;
}
cout << "----" << endl;
}
ret = s.solveNQueens(5);
for (int i = 0; i < ret.size(); i++) {
for (int j = 0; j < ret[0].size(); j++) {
cout << ret[i][j] << endl;
}
cout << "-----" << endl;
}
return 0;
}
Input
n = 1
Output
[["Q"]]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List();
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(0, new HashSet < >(), new HashSet<>(), new HashSet<>(), board, result, n);
return result;
}
private void backtrack(int row, Set < Integer> diagonals, Set antiDiagonals, Set columns, char[][] board, List buildBoard(char[][] board, int n) {
List resultBoard = new ArrayList<>();
for (int row = 0; row < n; row++) {
String currentRow = new String(board[row]);
resultBoard.add(currentRow);
}
return resultBoard;
}
}
Input
n = 4
Output
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const solveNQueens = function(n) {
const res = []
const chess = Array.from({length: n}, () => new Array(n).fill('.'))
bt(res, chess, 0)
return res
}
function bt(res, chess, row) {
if(row === chess.length) {
res.push(build(chess))
return
}
for(let i = 0, num = chess[0].length; i < num; i++) {
if(valid(chess, row, i)) {
chess[row][i] = 'Q'
bt(res, chess, row + 1)
chess[row][i] = '.'
}
}
}
function valid(chess, row, col> {
for(let i = row - 1; i >= 0; i--) {
if(chess[i][col] === 'Q') return false
}
for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if(chess[i][j] === 'Q') return false
}
for(let i = row - 1, j = col + 1; i >= 0 && j < chess[0].length; i--, j++) {
if(chess[i][j] === 'Q') return false
}
return true
}
function build(chess> {
return chess.map(el => el.join(''))
}
Input
n = 1
Output
[["Q"]]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def solveNQueens(self, n):
res = []
def dfs(i, l, r, m, arr):
if i == n:
res.append(arr)
else:
l = l[1:] + [0]
r = [0] + r[:-1]
for j in range(n):
if m[j] == l[j] == r[j] == 0:
l[j] = r[j] = m[j] = 1
dfs(i + 1, l, r, m, arr + [("." * j) + "Q" + ("." * (n - j - 1))])
l[j] = r[j] = m[j] = 0
dfs(0, [0] * n, [0] * n, [0] * n, [])
return res
Input
n = 1
Output
[["Q"]]
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode
{
public class _051_NQueens
{
public IList < IList();
StringBuilder rowString;
for (int i = 0; i < n; i++)
{
rowString = new StringBuilder(CONST_RESULT, n);
rowString[queenColumns[i]] = 'Q';
result.Add(rowString.ToString());
}
results.Add(result);
return;
}
bool isValid = true;
for (int col = 0; col < n; col++)
{
isValid = true;
for (int i = 0; i < currentRow; i++)
{
if (queenColumns[i] == col || Math.Abs(col - queenColumns[i]) == Math.Abs(currentRow - i))
{
isValid = false;
break;
}
}
if (!isValid) continue;
queenColumns[currentRow] = col;
RecursiveSolver(n, currentRow + 1, queenColumns, results);
}
}
}
}
Input
n = 4
Output
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]