Uva 167 The Sultan's Successors

The Sultan's Successors

完全赤裸裸地八皇后问题，找出所有的八皇后放置的情况，然后比较每种情况得到的权重，找出最大的那个来，上星期看了刘汝佳竞赛入门书的思路，现在按照那种思路来写，推出斜线的规律，写完后不用调试就一次性过了，可以看出真的是不学就无知

如果不知道《算法竞赛入门经典》的话，那就看看下面的内容：

八皇后就希望在一个棋盘上放置八个皇后，使皇后之间不能攻击到，攻击的条件是：同在一行或一列或在同一斜线上；不能再同一行上那么就用递归的层次表示，每次找八皇后放置的位置时递归的层次就当做是行，所以每次递归（记住递归是为了找放置的位置）都是不同的行，这时已经解决了会放在同一行的情况，用一维的数组表示列数，如果这列放有皇后那么就标记为访问过，下次递归时就不能处理这一列，这时解决了会放在同一列的情况了，现在剩下斜线上的问题了，如图：

找到斜线的规律，那么判断正反斜方向上是否皇后就可以用两个一维数组表示即可，为了能让数组能够表示，应该将负数进行处理，即所有的值都加上一个值，比如说第一个图加上3，第二个图加上7。反斜线的规律是：blackslash[i][j] = j-i+(n-1)；斜线的规律是：(n-1)*2-i-j；（n表示方阵的阶数）

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define VALUE 8
 4 int chess[VALUE+1][VALUE+1];
 5 int visit[VALUE+1];
 6 int blackslash[VALUE*2], slash[VALUE*2];
 7 int value;
 8 
 9 void Traverse(int cur, int sum, int num)
10 {
11     int i, j;
12     if(cur >= VALUE)
13     {
14         if(num == VALUE && value < sum)
15             value = sum;
16         return; 
17     }
18     for(i=0; i<VALUE; ++i)
19     {
20         if(!visit[i] && !blackslash[i-cur+VALUE-1] && !slash[2*(VALUE-1)-i-cur])
21         {
22             visit[i] = blackslash[i-cur+VALUE-1] = slash[2*(VALUE-1)-i-cur] = 1;
23             Traverse(cur+1, sum+chess[cur][i], num+1);
24             visit[i] = blackslash[i-cur+VALUE-1] = slash[2*(VALUE-1)-i-cur] = 0;
25         }
26     }
27     return;
28 }
29 
30 int main()
31 {
32     #ifndef ONLINE_JUDGE
33     freopen("input.txt", "r", stdin);
34     #endif
35     int i, j, k;
36     scanf("%d", &k);
37     while(k--)
38     {
39         for(i=0; i<VALUE; ++i)
40             for(j=0; j<VALUE; ++j)
41                 scanf("%d", &chess[i][j]);
42         value = 0;
43         memset(blackslash, 0, sizeof(blackslash));
44         memset(slash, 0, sizeof(slash));        
45         memset(visit, 0, sizeof(visit));
46         Traverse(0, 0, 0);
47         printf("%5d\n", value);
48     }
49     return 0;
50 }