USACO1.5.4Checker Challenge

Checker Challenge

Examine the 6x6 checkerboard below and note that the six checkers are arranged on the board so that one and only one is placed in each row and each column, and there is never more than one in any diagonal. (Diagonals run from southeast to northwest and southwest to northeast and include all diagonals, not just the major two.)

          Column
    1   2   3   4   5   6
  -------------------------
1 |   | O |   |   |   |   |
  -------------------------
2 |   |   |   | O |   |   |
  -------------------------
3 |   |   |   |   |   | O |
  -------------------------
4 | O |   |   |   |   |   |
  -------------------------
5 |   |   | O |   |   |   |
  -------------------------
6 |   |   |   |   | O |   |
  -------------------------

The solution shown above is described by the sequence 2 4 6 1 3 5, which gives the column positions of the checkers for each row from 1 to 6:

ROW	1	2	3	4	5	6
COLUMN	2	4	6	1	3	5

This is one solution to the checker challenge. Write a program that finds all unique solution sequences to the Checker Challenge (with ever growing values of N). Print the solutions using the column notation described above. Print the the first three solutions in numerical order, as if the checker positions form the digits of a large number, and then a line with the total number of solutions.

Special note: the larger values of N require your program to be especially efficient. Do not precalculate the value and print it (or even find a formula for it); that's cheating. Work on your program until it can solve the problem properly. If you insist on cheating, your login to the USACO training pages will be removed and you will be disqualified from all USACO competitions. YOU HAVE BEEN WARNED.

TIME LIMIT: 1 CPU second

PROGRAM NAME: checker

INPUT FORMAT

A single line that contains a single integer N (6 <= N <= 13) that is the dimension of the N x N checkerboard.

SAMPLE INPUT (file checker.in)

OUTPUT FORMAT

The first three lines show the first three solutions found, presented as N numbers with a single space between them. The fourth line shows the total number of solutions found.

SAMPLE OUTPUT (file checker.out)

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
题解：只知道最朴素的方法，然后觉得13估计会超时。所以就去看了下题解的标准方法，上面说要位运算。。。所以就去看了下位运算讲稿。。。但是，还是木有明白怎么算N皇后的总解数的，智商拙计啊。Matrix64大神的位运算讲稿里的方法的代码是这样的

procedure test(row,ld,rd:longint);
var
pos,p:longint;
begin
{ 1} if row<>upperlim then
{ 2} begin
{ 3} pos:=upperlim and not (row or ld or rd);
{ 4} while pos<>0 do
{ 5} begin
{ 6} p:=pos and -pos;
{ 7} pos:=pos-p;
{ 8} test(row+p,(ld+p)shl 1,(rd+p)shr 1);
{ 9} end;
{10} end
{11} else inc(sum);
end;

我用的是最朴素的方法，DFS，判断当前行，列，和对角线是否符合要求，如果符合就继续搜，直到达到N。N=13用了0.7S。

View Code

 1 /*
 2 ID:spcjv51
 3 PROG:checker
 4 LANG:C
 5 */
 6 #include<stdio.h>
 7 #include<stdlib.h>
 8 #include<math.h>
 9 long row[15],Diagonal1[30],Diagonal2[30],path[15];
10 long n,ans;
11 void DFS(long i)
12 {
13     long j,k;
14     if(i>n)
15     {
16         ans++;
17         if(ans<=3)
18         {
19             for(k=1; k<n; k++)
20                 printf("%ld ",path[k]);
21             printf("%ld\n",path[n]);
22         }
23         return;
24     }
25     for(j=1; j<=n; j++)
26         if(row[j]==0&&Diagonal1[i+j]==0&&Diagonal2[i-j+n]==0)
27         {
28             path[i]=j;
29             row[j]=1;
30             Diagonal1[i+j]=1;
31             Diagonal2[i-j+n]=1;
32             DFS(i+1);
33             row[j]=0;
34             Diagonal1[i+j]=0;
35             Diagonal2[i-j+n]=0;
36         }
37 }
38 int main(void)
39 {
40     freopen("checker.in","r",stdin);
41     freopen("checker.out","w",stdout);
42     scanf("%ld",&n);
43     memset(row,0,sizeof(row));
44     memset(Diagonal1,0,sizeof(Diagonal1));
45     memset(Diagonal2,0,sizeof(Diagonal2));
46     ans=0;
47     DFS(1);
48     printf("%ld\n",ans);
49     return 0;
50 }