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)
6
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
We use a recursive complete search to simply test all boards. The search proceeds by trying to put one checker in each row. We keep track of which columns and diagonals already have checkers on them in the "col", "updiag", and "downdiag" arrays.
Since we generate solutions in increasing order, we record the first 3 in the "sol" array.
Symmetry enables us to count the first half of the solutions double and avoid calculating the second half. An exception happens when N is odd; the odd row needs to be counted once.
The N>6 lines get the program out of trouble when N==6, because at that point, the first 3 solutions include one of the symmetric answers.
Since we number rows from 0 to N-1 rather than 1 to N, we need to add 1 to each digit as we print (in "printsol").
/*
TASK: checker
LANG: C
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN 16
int n;
int nsol, nprinted;
char row[MAXN];
FILE *fout;
void
solution() {
int i;
for(i=0; i<n; i++) {
if(i != 0) fprintf(fout, " ");
fprintf(fout, "%d", row[i]+1);
}
fprintf(fout, "\n");
}
/* Keep track of whether there is a checker on each column, and diagonal. */
char col[MAXN]; /* (i, j) -> j */
char updiag[2*MAXN]; /* (i, j) -> i+j */
char downdiag[2*MAXN]; /* (i, j) -> i-j + N */
/*
* Calculate number of ways to place checkers
* on each row of the board starting at row i and going to row n.
*/
void
nway(i, lim) {
int j;
if(i == n) {
nsol++;
if (n > 6 && row[0] < n/2) nsol++;
if (nprinted++ < 3) solution();
return;
}
for(j=0; j<lim; j++){
if(!col[j] && !updiag[i+j] && !downdiag[i-j+MAXN]){
row[i] = j;
col[j]++;
updiag[i+j]++;
downdiag[i-j+MAXN]++;
nway(i+1,n);
col[j]--;
updiag[i+j]--;
downdiag[i-j+MAXN]--;
}
}
}
main(void) {
FILE *fin = fopen("checker.in", "r");
fout = fopen("checker.out", "w");
fscanf(fin, "%d", &n);
nway(0, n>6?(n+1)/2:n);
fprintf(fout, "%d\n", nsol);
exit (0);
}
Clever Michael Rybak's Solution
The Ukraine's Michael Rybak removed the 'this row is used' search (which obviously at the end of the recursion is a lot of wasted iterating) and replaced it with a list of valid rows to use (which presumably has but a single element at the end of the recursion). His program runs almost 4x faster then N==13.
Program Checker;
Var diagPLUS: Array[2..30] Of Boolean;
diagMINUS: Array[-15..15] Of Boolean;
sol: Array[1..15] Of ShortInt;
i,n,found: Longint;
stop: Boolean;
next,prev: Array[0..16] Of ShortInt;
sy: ShortInt;
Procedure Search0(y:ShortInt);
Var x,i:ShortInt;
Begin
If stop Then Exit;
If y=n+1 Then Begin
Inc(found);
If found<4 Then Begin
For i:=1 To n-1 Do
Write(sol[i],' ');
Writeln(sol[n]);
End Else
stop:=True;
Exit;
End;
If sol[y]<>0 Then Begin
Search0(y+1);
Exit;
End;
x:=next[0];
While x<=n Do Begin
If Not ((diagPLUS[x+y]) Or (diagMINUS[x-y])) Then Begin
sol[y]:=x;
diagPLUS[x+y]:=True;
diagMINUS[x-y]:=True;
next[prev[x]]:=next[x];
prev[next[x]]:=prev[x];
Search0(y+1);
diagPLUS[x+y]:=False;
diagMINUS[x-y]:=False;
next[prev[x]]:=x; prev[next[x]]:=x;
End;
x:=next[x];
End;
sol[y]:=0;
End;
Procedure Search;
Var x:ShortInt;
Begin
If sy=n+1 Then Begin
Inc(found);
Exit;
End;
If sol[sy]<>0 Then Begin
Inc(sy);
Search;
Dec(sy);
Exit;
End;
x:=next[0];
While x<=n Do Begin
If Not ((diagPLUS[x+sy]) Or (diagMINUS[x-sy])) Then Begin
sol[sy]:=x;
diagPLUS[x+sy]:=True;
diagMINUS[x-sy]:=True;
next[prev[x]]:=next[x];
prev[next[x]]:=prev[x];
Inc(sy);
Search;
Dec(sy);
diagPLUS[x+sy]:=False;
diagMINUS[x-sy]:=False;
next[prev[x]]:=x;
prev[next[x]]:=x;
End;
x:=next[x];
End;
sol[sy]:=0;
End;
Procedure Search2(miny:Longint);
Var x,y,i:ShortInt;
curf:Longint;
Begin
x:=n Div 2+1;
For y:=miny To n Div 2 Do
If Not (diagPLUS[x+y] Or diagMINUS[x-y]) Then Begin
curf:=found;
sol[y]:=x;
diagPLUS[x+y]:=True;
diagMINUS[x-y]:=True;
next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
sy:=1;
Search;
If y>miny Then
found:=found+(found-curf);
sol[y]:=0;
diagPLUS[x+y]:=False;
diagMINUS[x-y]:=False;
next[prev[x]]:=x; prev[next[x]]:=x;
End;
End;
Procedure Search1;
Var x,y,i:ShortInt;
Begin
y:=n Div 2+1;
For x:=1 To n Div 2 Do Begin
sol[y]:=x;
diagPLUS[x+y]:=True;
diagMINUS[x-y]:=True;
next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
Search2(x);
diagPLUS[x+y]:=False;
diagMINUS[x-y]:=False;
next[prev[x]]:=x; prev[next[x]]:=x;
End;
sol[y]:=0;
found:=found*4;
x:=n Div 2+1;
sol[y]:=x;
diagPLUS[x+y]:=True;
diagMINUS[x-y]:=True;
next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
sy:=1;
Search;
End;
Begin
Assign(Input,'checker.in'); Reset(Input);
Assign(Output,'checker.out'); Rewrite(Output);
Read(n);
found:=0;
FillChar(diagPLUS,SizeOf(diagPLUS),False);
FillChar(diagMINUS,SizeOf(diagMINUS),False);
FillChar(sol,SizeOf(sol),0);
For i:=0 To n+1 Do Begin
prev[i]:=i-1;
next[i]:=i+1;
End;
If n Mod 2=0 Then Begin
stop:=False;
Search0(1);
sy:=1;
found:=0;
Search;
End Else Begin
stop:=False;
Search0(1);
found:=0;
Search1;
End;
Writeln(found);
Close(Output);
End.
Clever Romanian Solution
Submitted by several from Romania, this solution uses bitmasks instead of a list to speed searching:
#include <stdio.h>
#include <stdlib.h>
#include <fstream.h>
#define MAX_BOARDSIZE 16
typedef unsigned long SOLUTIONTYPE;
#define MIN_BOARDSIZE 6
SOLUTIONTYPE g_numsolutions = 0;
void Nqueen(int board_size) {
int aQueenBitRes[MAX_BOARDSIZE]; /* results */
int aQueenBitCol[MAX_BOARDSIZE]; /* marks used columns */
int aQueenBitPosDiag[MAX_BOARDSIZE]; /* marks used "positive diagonals" */
int aQueenBitNegDiag[MAX_BOARDSIZE]; /* marks used "negative diagonals" */
int aStack[MAX_BOARDSIZE + 2]; /* a stack instead of recursion */
int *pnStack;
int numrows = 0; /* numrows redundant - could use stack */
unsigned int lsb; /* least significant bit */
unsigned int bitfield; /* set bits denote possible queen positions */
int i;
int odd = board_size & 1; /* 1 if board_size odd */
int board_m1 = board_size - 1; /* board size - 1 */
int mask = (1 << board_size) - 1; /* N bit mask of all 1's */
aStack[0] = -1; /* sentinel signifies end of stack */
for (i = 0; i < (1 + odd); ++i) {
bitfield = 0;
if (0 == i) {
int half = board_size>>1; /* divide by two */
bitfield = (1 << half) - 1;
pnStack = aStack + 1; /* stack pointer */
aQueenBitRes[0] = 0;
aQueenBitCol[0] = aQueenBitPosDiag[0] = aQueenBitNegDiag[0] = 0;
} else {
bitfield = 1 << (board_size >> 1);
numrows = 1; /* prob. already 0 */
aQueenBitRes[0] = bitfield;
aQueenBitCol[0] = aQueenBitPosDiag[0] = aQueenBitNegDiag[0] = 0;
aQueenBitCol[1] = bitfield;
aQueenBitNegDiag[1] = (bitfield >> 1);
aQueenBitPosDiag[1] = (bitfield << 1);
pnStack = aStack + 1; /* stack pointer */
*pnStack++ = 0; /* row done -- only 1 element & we've done it */
bitfield = (bitfield - 1) >> 1;
/* bitfield -1 is all 1's to the left of the single 1 */
}
for (;;) {
lsb = -((signed)bitfield) & bitfield;
/* this assumes a 2's complement architecture */
if (0 == bitfield) {
bitfield = *--pnStack; /* get prev. bitfield from stack */
if (pnStack == aStack) /* if sentinel hit.... */
break;
--numrows;
continue;
}
bitfield &= ~lsb; /* bit off -> don't try it again */
aQueenBitRes[numrows] = lsb; /* save the result */
if (numrows < board_m1) { /* more rows to process? */
int n = numrows++;
aQueenBitCol[numrows] = aQueenBitCol[n] | lsb;
aQueenBitNegDiag[numrows] = (aQueenBitNegDiag[n] | lsb) >> 1;
aQueenBitPosDiag[numrows] = (aQueenBitPosDiag[n] | lsb) << 1;
*pnStack++ = bitfield;
bitfield = mask & ~(aQueenBitCol[numrows] |
aQueenBitNegDiag[numrows] | aQueenBitPosDiag[numrows]);
continue;
} else {
++g_numsolutions;
bitfield = *--pnStack;
--numrows;
continue;
}
}
}
g_numsolutions *= 2;
}
int main(int argc, char** argv) {
ifstream f("checker.in");
ofstream g("checker.out");
long boardsize,s[20],ok,k,i,sol=0;
f>>boardsize;
Nqueen (boardsize);
k=1;
s[k]=0;
while (k>0) {
ok=0;
while(s[k]<boardsize && !ok) {
ok=1;
s[k]++;
for(i=1;i<k;i++)
if(s[i]==s[k] || abs(s[k]-s[i])==abs(k-i))
ok=0;
}
if(sol!=3)
if(!ok)
k--;
else
if(k==boardsize) {
for(i=1;i<boardsize;i++) {
for(int j=1;j<=boardsize;j++)
if(s[i]==j) g<<j<<" ";
}
for(i=1;i<=boardsize;i++)
if(s[boardsize]==i) g<<i;
g<<"\n";
sol++;
} else {
k++;
s[k]=0;
} else break;
}
g<<g_numsolutions<<"\n";
f.close();
g.close();
return 0;
}
![DB2表压缩功能[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)