N-Queens II

發表於   |   分類於

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

N-QueensII

N皇后问题，回溯可解。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
int getState(int n, int* board, int r, int c)
{
	return board[r * n + c];
}

void setState(int n, int* board, int r, int c, int state)
{
	board[r * n + c] = state;
}

void printBoard(int* board, int n)
{
	printf("***************\n\n");
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			printf("%d ", getState(n, board, i, j));
		}
		printf("\n");
	}
}

bool palced(int n, int* board, int r, int c)
{
	for (int i = 0; i < n; ++i)
	{
		if (getState(n, board, r, i))
			return false;
	}
	for (int i = 0; i < n; ++i)
	{
		if (getState(n, board, i, c))
			return false;
	}
	int ir = r + 1;
	int ic = c + 1;
	// 斜线为0
	while (ir < n && ic < n)
	{
		if (getState(n, board, ir, ic))
			return false;
		++ir;
		++ic;
	}
	ir = r - 1;
	ic = c - 1;
	while (ir >= 0 && ic >= 0)
	{
		if (getState(n, board, ir, ic))
			return false;
		--ir;
		--ic;
	}
	ir = r - 1;
	ic = c + 1;
	while (ir >= 0 && ic < n)
	{
		if (getState(n, board, ir, ic))
			return false;
		--ir;
		++ic;
	}
	ir = r + 1;
	ic = c - 1;
	while (ir < n && ic >= 0)
	{
		if (getState(n, board, ir, ic))
			return false;
		++ir;
		--ic;
	}
}

void queens(int n, int* board, int* nums, int r, int c)
{
	if ((r >= 0 && r < n) && ((c >= 0 && c < n)))
	{
		if (r == n - 1)
		{
			for (int i = 0; i < n; ++i)
			{
				if (palced(n, board, r, i))
				{
					//setState(n, board, r, i, 1);
					++(* nums);
					//printBoard(board, n); //可以打印棋盘
					//setState(n, board, r, i, 0);
				}
			}
		}
		else
		{
			for (int i = 0; i < n; ++i)
			{
				if (palced(n,board,r,i))
				{
					setState(n, board, r, i, 1);//放置一个皇后
					queens(n, board, nums, r + 1, 0);//对剩下的棋盘进行摆放
					setState(n, board, r, i, 0);//恢复棋盘
				}
			}
		}
	}
}

int totalNQueens(int n) {
    if (n ==0)
    {
        return 1;
    }
    int* board = (int*)malloc(sizeof(int) * n * n);
    for (int i = 0; i < n*n; ++i)
    {
        board[i] = 0;
    }
    int result = 0;

    queens(n, board, &result, 0, 0);

    return result;
}