C
#include <stdio.h>
#define MAXSIZE 20
char graph[MAXSIZE][MAXSIZE];
int n, column[MAXSIZE], pd[MAXSIZE], sd[MAXSIZE]; // primary/secondary diagonal
void tag(int r, int c) {
column[c] = 1;
pd[r+c] = 1;
sd[n-c+r-1] = 1;
}
void untag(int r, int c) {
column[c] = 0;
pd[r+c] = 0;
sd[n-c+r-1] = 0;
}
void dfs(int row) {
if (row == n) {
for (int i = 0; i < n; ++i) {
puts(graph[i]);
}
printf("\n");
return;
}
for (int col = 0; col < n; ++col) {
if (column[col] || pd[row+col] || sd[n-col+row-1]) {
continue;
}
graph[row][col] = 'Q';
tag(row, col);
dfs(row + 1);
untag(row, col);
graph[row][col] = '.';
}
}
void init() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
graph[i][j] = '.';
}
}
}
int main() {
scanf("%d", &n);
init();
dfs(0);
return 0;
}
Go
package main
import "fmt"
var (
n int
graph [][]byte
column []bool
pd []bool
sd []bool
)
func tag(row, col int) {
column[col], pd[row+col], sd[n-col+row-1] = true, true, true
}
func untag(row, col int) {
column[col], pd[row+col], sd[n-col+row-1] = false, false, false
}
func dfs(row int) {
if row == n {
for i := 0; i < n; i++ {
fmt.Printf("%s\n", graph[i])
}
fmt.Println()
return
}
for col := 0; col < n; col++ {
if column[col] || pd[row+col] || sd[n-col+row-1] {
continue
}
graph[row][col] = 'Q'
tag(row, col)
dfs(row + 1)
untag(row, col)
graph[row][col] = '.'
}
}
func init() {
fmt.Scan(&n)
graph = make([][]byte, n)
for i := 0; i < n; i++ {
graph[i] = make([]byte, n)
for j := 0; j < n; j++ {
graph[i][j] = '.'
}
}
column, pd, sd = make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1)
}
func main() {
dfs(0)
}