#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int n;
char **board;
bool *cols, *diag1, *diag2;
char ***rows;
int size;
int cap;
} State;
static void save(State *st) {
if (st->size == st->cap) {
st->cap = st->cap ? 2 * st->cap : 16;
st->rows = realloc(st->rows, st->cap * sizeof(char **));
}
char **copy = malloc(st->n * sizeof(char *));
for (int r = 0; r < st->n; r++)
copy[r] = strdup(st->board[r]);
st->rows[st->size++] = copy;
}
static void backtrack(State *st, int row) {
int n = st->n;
if (row == n) {
save(st);
return;
}
for (int col = 0; col < n; col++) {
int d1 = row + col; // "/" diagonal
int d2 = row - col + n - 1; // "\" diagonal, shifted
if (st->cols[col] || st->diag1[d1] || st->diag2[d2])
continue;
st->board[row][col] = 'Q';
st->cols[col] = st->diag1[d1] = st->diag2[d2] = true;
backtrack(st, row + 1);
st->board[row][col] = '.';
st->cols[col] = st->diag1[d1] = st->diag2[d2] = false;
}
}
char ***solveNQueens(int n, int *returnSize, int **returnColumnSizes) {
State st = {.n = n};
st.board = malloc(n * sizeof(char *));
for (int r = 0; r < n; r++) {
st.board[r] = malloc(n + 1);
memset(st.board[r], '.', n);
st.board[r][n] = '\0';
}
st.cols = calloc(n, sizeof(bool));
st.diag1 = calloc(2 * n - 1, sizeof(bool));
st.diag2 = calloc(2 * n - 1, sizeof(bool));
backtrack(&st, 0);
for (int r = 0; r < n; r++)
free(st.board[r]);
free(st.board);
free(st.cols);
free(st.diag1);
free(st.diag2);
*returnSize = st.size;
*returnColumnSizes = malloc((st.size ? st.size : 1) * sizeof(int));
for (int i = 0; i < st.size; i++)
(*returnColumnSizes)[i] = n;
return st.rows;
}
#include <string>
#include <vector>
using namespace std;
class Solution {
vector<bool> cols, diag1, diag2;
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<string> board(n, string(n, '.'));
cols.assign(n, false);
diag1.assign(2 * n - 1, false);
diag2.assign(2 * n - 1, false);
backtrack(n, 0, board, result);
return result;
}
private:
void backtrack(int n, int row, vector<string> &board,
vector<vector<string>> &result) {
if (row == n) {
result.push_back(board);
return;
}
for (int col = 0; col < n; col++) {
int d1 = row + col; // "/" diagonal
int d2 = row - col + n - 1; // "\" diagonal, shifted
if (cols[col] || diag1[d1] || diag2[d2])
continue;
board[row][col] = 'Q';
cols[col] = diag1[d1] = diag2[d2] = true;
backtrack(n, row + 1, board, result);
board[row][col] = '.';
cols[col] = diag1[d1] = diag2[d2] = false;
}
}
};
package backtracking
import "strings"
func solveNQueens(n int) [][]string {
var result [][]string
board := make([][]byte, n)
for r := range board {
board[r] = []byte(strings.Repeat(".", n))
}
cols := make([]bool, n)
diag1 := make([]bool, 2*n-1)
diag2 := make([]bool, 2*n-1)
var backtrack func(row int)
backtrack = func(row int) {
if row == n {
snapshot := make([]string, n)
for r := range board {
snapshot[r] = string(board[r])
}
result = append(result, snapshot)
return
}
for col := 0; col < n; col++ {
d1 := row + col // "/" diagonal
d2 := row - col + n - 1 // "\" diagonal, shifted
if cols[col] || diag1[d1] || diag2[d2] {
continue
}
board[row][col] = 'Q'
cols[col], diag1[d1], diag2[d2] = true, true, true
backtrack(row + 1)
board[row][col] = '.'
cols[col], diag1[d1], diag2[d2] = false, false, false
}
}
backtrack(0)
return result
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
private boolean[] cols, diag1, diag2;
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
cols = new boolean[n];
diag1 = new boolean[2 * n - 1];
diag2 = new boolean[2 * n - 1];
backtrack(n, 0, board, result);
return result;
}
private void backtrack(int n, int row, char[][] board, List<List<String>> result) {
if (row == n) {
List<String> snapshot = new ArrayList<>(n);
for (char[] r : board) {
snapshot.add(new String(r));
}
result.add(snapshot);
return;
}
for (int col = 0; col < n; col++) {
int d1 = row + col; // "/" diagonal
int d2 = row - col + n - 1; // "\" diagonal, shifted
if (cols[col] || diag1[d1] || diag2[d2]) {
continue;
}
board[row][col] = 'Q';
cols[col] = diag1[d1] = diag2[d2] = true;
backtrack(n, row + 1, board, result);
board[row][col] = '.';
cols[col] = diag1[d1] = diag2[d2] = false;
}
}
}
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function (n) {
const result = [];
const board = Array.from({ length: n }, () => Array(n).fill("."));
const cols = Array(n).fill(false);
const diag1 = Array(2 * n - 1).fill(false);
const diag2 = Array(2 * n - 1).fill(false);
const backtrack = (row) => {
if (row === n) {
result.push(board.map((r) => r.join("")));
return;
}
for (let col = 0; col < n; col++) {
const d1 = row + col; // "/" diagonal
const d2 = row - col + n - 1; // "\" diagonal, shifted
if (cols[col] || diag1[d1] || diag2[d2]) continue;
board[row][col] = "Q";
cols[col] = diag1[d1] = diag2[d2] = true;
backtrack(row + 1);
board[row][col] = ".";
cols[col] = diag1[d1] = diag2[d2] = false;
}
};
backtrack(0);
return result;
};
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
result: List[List[str]] = []
board = [["."] * n for _ in range(n)]
cols = [False] * n
diag1 = [False] * (2 * n - 1)
diag2 = [False] * (2 * n - 1)
def backtrack(row: int) -> None:
if row == n:
result.append(["".join(r) for r in board])
return
for col in range(n):
d1 = row + col # "/" diagonal
d2 = row - col + n - 1 # "\" diagonal, shifted
if cols[col] or diag1[d1] or diag2[d2]:
continue
board[row][col] = "Q"
cols[col] = diag1[d1] = diag2[d2] = True
backtrack(row + 1)
board[row][col] = "."
cols[col] = diag1[d1] = diag2[d2] = False
backtrack(0)
return result
struct State {
n: usize,
board: Vec<Vec<u8>>,
cols: Vec<bool>,
diag1: Vec<bool>,
diag2: Vec<bool>,
result: Vec<Vec<String>>,
}
impl State {
fn backtrack(&mut self, row: usize) {
let n = self.n;
if row == n {
let snapshot = self
.board
.iter()
.map(|r| String::from_utf8(r.clone()).unwrap())
.collect();
self.result.push(snapshot);
return;
}
for col in 0..n {
let d1 = row + col; // "/" diagonal
let d2 = row + n - 1 - col; // "\" diagonal, shifted
if self.cols[col] || self.diag1[d1] || self.diag2[d2] {
continue;
}
self.board[row][col] = b'Q';
self.cols[col] = true;
self.diag1[d1] = true;
self.diag2[d2] = true;
self.backtrack(row + 1);
self.board[row][col] = b'.';
self.cols[col] = false;
self.diag1[d1] = false;
self.diag2[d2] = false;
}
}
}
impl Solution {
pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
let n = n as usize;
let mut st = State {
n,
board: vec![vec![b'.'; n]; n],
cols: vec![false; n],
diag1: vec![false; 2 * n - 1],
diag2: vec![false; 2 * n - 1],
result: Vec::new(),
};
st.backtrack(0);
st.result
}
}