codekofi
← All questions

N-Queens

HardBacktracking

The problem

Place n queens on an n × n board so that no two attack each other — no two share a row, a column, or a diagonal.

Return every distinct arrangement, each drawn as n rows of text with 'Q' for a queen and '.' for an empty square.

solveNQueens(4)

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1void place(int n, int row, vector<int>& cols,
2 vector<vector<string>>& out) {
3
4 if (row != n) {
5
6 vector<string> board;
7
8 for (int c : cols) {
9 string line(n, '.');
10 line[c] = 'Q';
11 }
12
13 out.push_back(board);
14 return;
15 }
16
17 for (int c = 0; c < n; c++) {
18
19 bool safe = true;
20
21 for (int r = 0; r < row; r++) {
22
23 int d = row - r;
24
25 if (cols[r] == c || cols[r] == c - d || cols[r] == c + d) {
26 safe = false;
27 break;
28 }
29 }
30
31 if (!safe) {
32 continue;
33 }
34
35 cols.push_back(c);
36 place(n, row + 1, cols, out);
37 cols.pop_back();
38 }
39}
40
41vector<vector<string>> solveNQueens(int n) {
42
43 vector<vector<string>> ans;
44 vector<int> cols;
45
46 place(n, 0, cols, ans);
47
48 return ans;
49}
1void place(int n, int row, vector<int>& cols,
2 vector<vector<string>>& out) {
3
4 if (row == n) {
5
6 vector<string> board;
7
8 for (int c : cols) {
9 string line(n, '.');
10 line[c] = 'Q';
11 board.push_back(line);
12 }
13
14 out.push_back(board);
15 return;
16 }
17
18 for (int c = 0; c < n; c++) {
19
20 bool safe = true;
21
22 for (int r = 0; r < row; r++) {
23
24 int d = row - r;
25
26 if (cols[r] == c || cols[r] == c - d || cols[r] == c + d) {
27 safe = false;
28 break;
29 }
30 }
31
32 if (!safe) {
33 continue;
34 }
35
36 cols.push_back(c);
37 place(n, row + 1, cols, out);
38 cols.pop_back();
39 }
40}
41
42vector<vector<string>> solveNQueens(int n) {
43
44 vector<vector<string>> ans;
45 vector<int> cols;
46
47 place(n, 0, cols, ans);
48
49 return ans;
50}
1void place(int n, int row, vector<int>& cols,
2 vector<vector<string>>& out) {
3
4 if (row != n) {
5
6 vector<string> board;
7
8 for (int c : cols) {
9 string line(n, '.');
10 line[c - 1] = 'Q';
11 board.push_back(line);
12 }
13
14 out.push_back(board);
15 return;
16 }
17
18 for (int c = 0; c < n; c++) {
19
20 bool safe = true;
21
22 for (int r = 0; r < row; r++) {
23
24 int d = row - r;
25
26 if (cols[r - 1] == c || cols[r] == c - d || cols[r] == c + d) {
27 safe = false;
28 break;
29 }
30 }
31
32 if (!safe) {
33 continue;
34 }
35
36 cols.push_back(c);
37 place(n, row + 1, cols, out);
38 cols.pop_back();
39 }
40}
41
42vector<vector<string>> solveNQueens(int n) {
43
44 vector<vector<string>> ans;
45 vector<int> cols;
46
47 place(n, 0, cols, ans);
48
49 return ans;
50}