1. Runtime Distribution

2. Submission Details

3. Description

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.

4. Example

There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]

6. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

char ** board;
int* row;
int* col;
int** diagonal;

void Marking(int i, int j, int n, int mark) {
	row[i] += mark;
	col[j] += mark;

	for (int x = i, y = j; x >= 0 && y < n; x--, y++)
	{
		diagonal[x][y] += mark;
	}

	for (int x = i + 1, y = j - 1; x < n && y >= 0; x++, y--)
	{
		diagonal[x][y] += mark;
	}

	for (int x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--)
	{
		diagonal[x][y] += mark;
	}

	for (int x = i + 1, y = j + 1; x < n && y < n; x++, y++)
	{
		diagonal[x][y] += mark;
	}
}

void findNextOne(char*** ret, int* returnSize, int i, int j, int n)
{
	if (i == n)
	{
		ret[*returnSize] = (char **)malloc(sizeof(void *) * n);

		for (int a = 0; a < n; a++)
		{
			ret[*returnSize][a] = (char *)malloc(sizeof(char) * (n + 1));
		}

		for (int a = 0; a < n; a++)
		{
			for (int b = 0; b < n; b++)
			{
				ret[*returnSize][a][b] = board[a][b];
			}
			ret[*returnSize][a][n] = '\0';
		}

		(*returnSize)++;

		return;
	}

	for (int y = j; y < n; y++)
	{
		if (row[i] == 0 && col[y] == 0 && diagonal[i][y] == 0)
		{
			board[i][y] = 'Q';
			Marking(i, y, n, 1);
			findNextOne(ret, returnSize, i + 1, 0, n);
			Marking(i, y, n, -1);
			board[i][y] = '.';
		}
	}
}

char*** solveNQueens(int n, int* returnSize) {

	*returnSize = 0;
	char*** ret = (char***)malloc(sizeof(char **) * 512);

	board = (char **)malloc(sizeof(char*) * n);
	for (int i = 0; i< n; i++)
	{
		board[i] = (char *)malloc(sizeof(char) * n);
	}

	row = (int *)malloc(sizeof(int) * n);
	col = (int *)malloc(sizeof(int) * n);
	diagonal = (int **)malloc(sizeof(int *) * n);

	for (int i = 0; i< n; i++)
	{
		diagonal[i] = (int *)malloc(sizeof(int) * n);
	}

	for (int i = 0; i < n; i++)
	{
		row[i] = 0; col[i] = 0;
		for (int j = 0; j< n; j++)
		{
			board[i][j] = '.';
			diagonal[i][j] = 0;
		}
	}

	findNextOne(ret, returnSize, 0, 0, n);
	return ret;
}

[/restab]
[restab title="C++"]

vector> solveNQueens(int n) {

	vector row(n);
	vector col(n);

	vector > diagonal(n);

	vector > board(n);
	for (auto i = 0; i < n; i++)
	{
		diagonal[i].resize(n);
		board[i].resize(n);
	}

	for(auto i = 0; i< n; i++)
	{
		for(auto j = 0; j < n; j++)
		{
			board[i][j] = '.';
		}
	}

	vector > res;

	findNextOne(res, board, row, col, diagonal, 0, 0, n);

	return res;

}

static void findNextOne(vector > &res, vector > &board,
	vector row, vector col, vector > diagonal, int i, int j, int n)
{
	if (i == n)
	{
		vector solution;
		for (auto a = 0; a < n; a++)
		{
			string line(board[a].begin(), board[a].end());
			solution.push_back(line);
		}

		res.push_back(solution);

		return;
	}

	for (int y = j; y < n; y++)
	{
		if (row[i] == 0 && col[y] == 0 && diagonal[i][y] == 0)
		{
			board[i][y] = 'Q';
			Marking(row, col, diagonal, i, y, n, 1);
			findNextOne(res, board, row, col, diagonal, i + 1, 0, n);
			Marking(row, col, diagonal, i, y, n, -1);
			board[i][y] = '.';
		}
	}
}

static void Marking(vector &row, vector &col, vector > &diagonal, int i, int j, int n, int mark) {

	row[i] += mark;
	col[j] += mark;

	for (int x = i, y = j; x >= 0 && y < n; x--, y++)
	{
		diagonal[x][y] += mark;
	}

	for (int x = i + 1, y = j - 1; x < n && y >= 0; x++, y--)
	{
		diagonal[x][y] += mark;
	}

	for (int x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--)
	{
		diagonal[x][y] += mark;
	}

	for (int x = i + 1, y = j + 1; x < n && y < n; x++, y++)
	{
		diagonal[x][y] += mark;
	}
}

[/restab]
[/restabs]

7.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

#include 
#include 

char ** board;
int* row;
int* col;
int** diagonal;

void Marking(int i, int j, int n, int mark) {
	row[i] += mark;
	col[j] += mark;

	for (int x = i, y = j; x >= 0 && y < n; x--, y++)
	{
		diagonal[x][y] += mark;
	}

	for (int x = i + 1, y = j - 1; x < n && y >= 0; x++, y--)
	{
		diagonal[x][y] += mark;
	}

	for (int x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--)
	{
		diagonal[x][y] += mark;
	}

	for (int x = i + 1, y = j + 1; x < n && y < n; x++, y++)
	{
		diagonal[x][y] += mark;
	}
}

void findNextOne(char*** ret, int* returnSize, int i, int j, int n)
{
	if (i == n)
	{
		ret[*returnSize] = (char **)malloc(sizeof(void *) * n);

		for (int a = 0; a < n; a++)
		{
			ret[*returnSize][a] = (char *)malloc(sizeof(char) * (n + 1));
		}

		for (int a = 0; a < n; a++)
		{
			for (int b = 0; b < n; b++)
			{
				ret[*returnSize][a][b] = board[a][b];
			}
			ret[*returnSize][a][n] = '\0';
		}

		(*returnSize)++;

		return;
	}

	for (int y = j; y < n; y++)
	{
		if (row[i] == 0 && col[y] == 0 && diagonal[i][y] == 0)
		{
			board[i][y] = 'Q';
			Marking(i, y, n, 1);
			findNextOne(ret, returnSize, i + 1, 0, n);
			Marking(i, y, n, -1);
			board[i][y] = '.';
		}
	}
}

char*** solveNQueens(int n, int* returnSize) {

	*returnSize = 0;
	char*** ret = (char***)malloc(sizeof(char **) * 512);

	board = (char **)malloc(sizeof(char*) * n);
	for (int i = 0; i< n; i++)
	{
		board[i] = (char *)malloc(sizeof(char) * n);
	}

	row = (int *)malloc(sizeof(int) * n);
	col = (int *)malloc(sizeof(int) * n);
	diagonal = (int **)malloc(sizeof(int *) * n);

	for (int i = 0; i< n; i++)
	{
		diagonal[i] = (int *)malloc(sizeof(int) * n);
	}

	for (int i = 0; i < n; i++)
	{
		row[i] = 0; col[i] = 0;
		for (int j = 0; j< n; j++)
		{
			board[i][j] = '.';
			diagonal[i][j] = 0;
		}
	}

	findNextOne(ret, returnSize, 0, 0, n);
	return ret;
}

int main()
{
	int n = 8;
	int returnSize = 0;
	char*** res = solveNQueens(n, &returnSize);
	printf("size = %d\n", returnSize);

	for (int i = 0; i < returnSize; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				printf("%c ", res[i][j][k]);
			}
			printf("\n");
			free(res[i][j]);
		}
		printf("\n");
		free(res[i]);
	}

	free(res);
	system("pause");
	return 0;
}

[/restab]
[restab title="C++"]

#include 
#include 
#include 

using namespace std;

class LeetCode0051 {
public:
	vector> solveNQueens(int n) {

		vector row(n);
		vector col(n);

		vector > diagonal(n);

		vector > board(n);
		for (auto i = 0; i < n; i++)
		{
			diagonal[i].resize(n);
			board[i].resize(n);
		}

		for(auto i = 0; i< n; i++)
		{
			for(auto j = 0; j < n; j++)
			{
				board[i][j] = '.';
			}
		}

		vector > res;

		findNextOne(res, board, row, col, diagonal, 0, 0, n);

		return res;

	}

	static void findNextOne(vector > &res, vector > &board,
		vector row, vector col, vector > diagonal, int i, int j, int n)
	{
		if (i == n)
		{
			vector solution;
			for (auto a = 0; a < n; a++)
			{
				string line(board[a].begin(), board[a].end());
				solution.push_back(line);
			}

			res.push_back(solution);

			return;
		}

		for (int y = j; y < n; y++)
		{
			if (row[i] == 0 && col[y] == 0 && diagonal[i][y] == 0)
			{
				board[i][y] = 'Q';
				Marking(row, col, diagonal, i, y, n, 1);
				findNextOne(res, board, row, col, diagonal, i + 1, 0, n);
				Marking(row, col, diagonal, i, y, n, -1);
				board[i][y] = '.';
			}
		}
	}

	static void Marking(vector &row, vector &col, vector > &diagonal, int i, int j, int n, int mark) {

		row[i] += mark;
		col[j] += mark;

		for (int x = i, y = j; x >= 0 && y < n; x--, y++)
		{
			diagonal[x][y] += mark;
		}

		for (int x = i + 1, y = j - 1; x < n && y >= 0; x++, y--)
		{
			diagonal[x][y] += mark;
		}

		for (int x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--)
		{
			diagonal[x][y] += mark;
		}

		for (int x = i + 1, y = j + 1; x < n && y < n; x++, y++)
		{
			diagonal[x][y] += mark;
		}
	}

};

int main() {
	LeetCode0051 leetCode0051;
	vector > ret = leetCode0051.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;
	}
	return 0;
}

[/restab]
[/restabs]

7、Appendix

Belowing is the num of queens of different n

1           1
2            0
3            0
4            2
5            10
6            4
7            40
8            92
9            352
10          724
11          2680
12          14200
13          73712
14          365596
15          2279184
16          14772512
17          95815104
18          666090624
19          4968057848
20          39029188884
21          314666222712
22          2691008701644
23          24233937684440
24          227514171973736
25          2207893435808352