USACO 1.5 – Checker Challenge | Jack Neus
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 4https://sites.google.com/site/codetrick/checkerchallenge
HINT 1
Use recursion:
HINT 2Do everything you can to eliminate loops (searching) in the part of your program executed most frequently. Usually, the best way to do this is to 'trade memory for speed'. When checking to see if a queen can be placed in a given row, for example, store a row status list that says if a queen is already stored there or not:
Do *absolutely everything* you can to eliminate loops (searching) in the part of your program executed most frequently. Keep track not only of the rows that are legal for queen placement but also which of the two sorts of diagonals (the ones that are like a '/' and the others that are like '\' by using an array of size 2*max - 1 that records whether a diagonal is legal or not.
HINT 4
SYMMETRY. Can you eliminate half or 3/4 of the cases you test by studying rotations, reflections, or something like that? [hint: yes]
HINT 5
Still over time? If you have programmed modularly and have little subroutines to check diagonals, etc., move that code into the main execution stream. The subroutine call overhead is nontrivial.
HINT 6
Most successful Java solutions store their 'this column used' marks as bits in a word.
http://blog.csdn.net/jinmian_ay27/article/details/8856117
Use recursion:
function placequeen(column) { # place columns 0..max-1
if (column == max) { deal with answer; return; }
for (row = 0; row < max; row++) {
if (canplacequeen (row)) {
mark queen placed at column,row;
placequeen(column+1);
un-mark queen placed at column,row;
}
}
}
HINT 2Do everything you can to eliminate loops (searching) in the part of your program executed most frequently. Usually, the best way to do this is to 'trade memory for speed'. When checking to see if a queen can be placed in a given row, for example, store a row status list that says if a queen is already stored there or not:
function placequeen(column) { # place columns 0..max-1
if (column == max) { deal with answer; return; }
for (row = 0; row < max; row++) {
if (rowok[row] && canplacequeen(row,column)) {
rowok[row] = 1;
mark queen placed at column,row;
placequeen(column+1);
un-mark queen placed at column,row;
rowok[row] = 0;
}
}
}
HINT 3Do *absolutely everything* you can to eliminate loops (searching) in the part of your program executed most frequently. Keep track not only of the rows that are legal for queen placement but also which of the two sorts of diagonals (the ones that are like a '/' and the others that are like '\' by using an array of size 2*max - 1 that records whether a diagonal is legal or not.
HINT 4
SYMMETRY. Can you eliminate half or 3/4 of the cases you test by studying rotations, reflections, or something like that? [hint: yes]
HINT 5
Still over time? If you have programmed modularly and have little subroutines to check diagonals, etc., move that code into the main execution stream. The subroutine call overhead is nontrivial.
HINT 6
Most successful Java solutions store their 'this column used' marks as bits in a word.
http://blog.csdn.net/jinmian_ay27/article/details/8856117
1）只考虑一半的column结果乘以2，另一半认为是沿中心垂直对称的。如果N是奇数，则结果中数量要补上中间那条column。
2）优化对角线的判断，使之成为搜索的状态，而不是每次判断都要重新算（这里和The Clocks这一题有异曲同工）。可以发现两条对角线上的元素特征分别是i+j以及i-j+N是相同的，因此开两个2×N大小的int数组来记录占用情况。注意此处不是boolean而是int的原因是占用的影响有累积效应。
3）同理，可以优化列占用情况。（和上述八皇后不同的是，这题必须一行一行考虑）
4）小数据的情况要特别考虑，该题中N为6时，优化check是可以用的，但是由于要输出3个结果，只查找一半是不可行的，要查找全部。
该题是需要深度优化的八皇后问题，首先看一下，经典八皇后问题的一般解法：
X. 位操作
http://blog.csdn.net/baidu_23081367/article/details/43083623
http://www.matrix67.com/blog/archives/266
和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6×6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。前面说过-a相当于not a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。
http://blog.csdn.net/zzp441524586/article/details/7643574
int num,upperlim;
int N;
int q[20]; //记录每行第几个落子
void test(int row,int ld,int rd,int n)
{
int p,pos;
if (row!=upperlim)
{
pos=upperlim & ~(row|ld|rd);
while (pos!=0)
{
p=pos & -pos;
pos=pos-p;
q[n]=round(log(p)/log(2))+1; //记录当前行跳棋在哪个位置，路径存储
if (q[n]==0) q[n]=N;
test(row+p,(ld+p)<<1,(rd+p)>>1,n+1);
}
}
else
{
if (num<3)
{
for (int i=1;i<n-1;i++)
fout<<q[i]<<' ';
fout<<q[n-1]<<endl;
}
num++;
}
}
int main()
{
fin>>N;
upperlim=(1<<N)-1;
test(0,0,0,1);
fout<<num<<endl;
return 0;
}
http://www.xuebuyuan.com/2140585.html
使用了对称性，减少一半的计算量
https://sites.google.com/site/codetrick/checkerchallenge
void find(int row,int table[],int n){
int i,kn,col,flag;
if (row>n){
count++;
if (n>5 && table[0]<(n+1)/2) count++;
if (outcount++<3) output(table,n);
}
else{
if (row==0 && n>5) kn=n/2; else kn=n;
for (col=0;col<=kn;col++){
if (collist[col] || lblist[col+row] || rblist[col-row+n-1]) continue;
collist[col]=1;
lblist[col+row]=1;
rblist[col-row+n-1]=1;
table[row]=col;
find(row+1,table,n);
collist[col]=0;
lblist[col+row]=0;
rblist[col-row+n-1]=0;
}
}
}
Read full article from USACO 1.5 – Checker Challenge | Jack Neus
2）优化对角线的判断，使之成为搜索的状态，而不是每次判断都要重新算（这里和The Clocks这一题有异曲同工）。可以发现两条对角线上的元素特征分别是i+j以及i-j+N是相同的，因此开两个2×N大小的int数组来记录占用情况。注意此处不是boolean而是int的原因是占用的影响有累积效应。
3）同理，可以优化列占用情况。（和上述八皇后不同的是，这题必须一行一行考虑）
4）小数据的情况要特别考虑，该题中N为6时，优化check是可以用的，但是由于要输出3个结果，只查找一半是不可行的，要查找全部。
该题是需要深度优化的八皇后问题，首先看一下，经典八皇后问题的一般解法：
| ||
| private static int MAX; | ||
| private static BufferedReader in; | ||
| private static PrintWriter out; | ||
| //row[i] = col, row i col j | ||
| private static int[] row; | ||
| private static int cnt = 0; | ||
| private static int[] colused; | ||
| private static int[] updiagonalused; | ||
| private static int[] downdiagonalused; | ||
| public static void main(String[] args) throws Exception{ | ||
| in = new BufferedReader(new FileReader("checker.in")); | ||
| out = new PrintWriter(new BufferedWriter(new FileWriter("checker.out")),true); | ||
| MAX = Integer.parseInt(in.readLine()); | ||
| row = new int[MAX]; | ||
| colused = new int[MAX]; | ||
| updiagonalused = new int[2*MAX]; // i+j | ||
| downdiagonalused = new int[2*MAX]; // i-j+N | ||
| //6 has 4 solutions, which will not be generated by the following algorithm | ||
| if(MAX <= 6) | ||
| dfs(0); | ||
| // 7 has 40 solutions, so it's safe to do so | ||
| else{ | ||
| for(int j = 0 ; j < MAX /2; j++){ | ||
| row[0] = j; | ||
| addMarkIJ(0,j); | ||
| dfs(1); | ||
| removeMarkIJ(0,j); | ||
| } | ||
| cnt *= 2; | ||
| if(MAX % 2 != 0){ // when MAX is odd | ||
| row[0] = MAX / 2; | ||
| addMarkIJ(0,MAX / 2); | ||
| dfs(1); | ||
| removeMarkIJ(0,MAX / 2); | ||
| } | ||
| } | ||
| out.println(cnt); | ||
| System.exit(0); | ||
| } | ||
| private static void dfs(int i){ | ||
| if(i == MAX){ | ||
| cnt ++; | ||
| StringBuilder sb = new StringBuilder(); | ||
| if(cnt <=3){ | ||
| for(int col : row){ | ||
| sb.append(col+1); | ||
| sb.append(" "); | ||
| } | ||
| sb.deleteCharAt(sb.length()-1); | ||
| out.println(sb.toString()); | ||
| } | ||
| } | ||
| else | ||
| for(int j = 0; j < MAX; j ++){ | ||
| if(colused[j] == 0 && updiagonalused[i+j] == 0 | ||
| && downdiagonalused[i-j+MAX] == 0){ | ||
| row[i] = j; // [row i, col j] | ||
| addMarkIJ(i,j); | ||
| dfs(i+1); // next row | ||
| removeMarkIJ(i, j); | ||
| } | ||
| } | ||
| } | ||
| private static void removeMarkIJ(int i, int j) { | ||
| colused[j]--; | ||
| updiagonalused[i+j]--; | ||
| downdiagonalused[i-j+MAX]--; | ||
| } | ||
| private static void addMarkIJ(int i, int j){ | ||
| colused[j]++; | ||
| updiagonalused[i+j] ++; | ||
| downdiagonalused[i-j+MAX] ++; | ||
| } | ||
| } |
http://blog.csdn.net/baidu_23081367/article/details/43083623
http://www.matrix67.com/blog/archives/266
和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6×6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。前面说过-a相当于not a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。
http://blog.csdn.net/zzp441524586/article/details/7643574
int num,upperlim;
int N;
int q[20]; //记录每行第几个落子
void test(int row,int ld,int rd,int n)
{
int p,pos;
if (row!=upperlim)
{
pos=upperlim & ~(row|ld|rd);
while (pos!=0)
{
p=pos & -pos;
pos=pos-p;
q[n]=round(log(p)/log(2))+1; //记录当前行跳棋在哪个位置，路径存储
if (q[n]==0) q[n]=N;
test(row+p,(ld+p)<<1,(rd+p)>>1,n+1);
}
}
else
{
if (num<3)
{
for (int i=1;i<n-1;i++)
fout<<q[i]<<' ';
fout<<q[n-1]<<endl;
}
num++;
}
}
int main()
{
fin>>N;
upperlim=(1<<N)-1;
test(0,0,0,1);
fout<<num<<endl;
return 0;
}
http://www.xuebuyuan.com/2140585.html
int n, ans[3][50], lim, tot;
void dfs(int row, int ld, int rd) {
if(row == lim) {//找到一个可行解
tot++;
return ;
}
int pos = (~(row|ld|rd)) & lim;//取反之后空位置变为1（超出棋盘的0也变成1），再进行与，得到空位置
while(pos) {
int p = pos & -pos;//取最右边的1
if(tot < 3) {
int tmp = row, index = 0;
for(int i = 0; i < n; i++) {
if(tmp & 1)
index++;
tmp >>= 1;
}//统计1的个数做下标
ans[tot][index] = (int)(log2((float)p)) + 1;//根据p的值对应出位置
}
dfs(row|p, (ld|p)<<1, (rd|p)>>1);//ld、rd代表对角线，因为只关心当前行的合法位置，所以相当于前一行的row进行左移和右移
pos -= p;//因为是最右边的1，所以可以直接减去，代表放置了一个皇后
}
}
int main(){
freopen("checker.in", "r", stdin);
freopen("checker.out", "w", stdout);
scanf("%d", &n);
lim = (1 << n) - 1;
tot = 0;
dfs(0, 0, 0);
for(int i = 0; i < (tot < 3 ? tot : 3); i++) {
for(int j = 0; j < n-1; j++) {
if(ans[i][j] == 0)
ans[i][j] = ans[i-1][j];
printf("%d ", ans[i][j]);
}
printf("%d\n", ans[i][n-1]);
}
printf("%d\n", tot);
fclose(stdin);
fclose(stdout);
return 0;
}
http://lsharemy.com/wordpress/index.php/csit/usaco-prob-checker-challenge/使用了对称性，减少一半的计算量
nway(0, n>6?(n+1)/2: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. */voidnway(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]--; } }}void find(int row,int table[],int n){
int i,kn,col,flag;
if (row>n){
count++;
if (n>5 && table[0]<(n+1)/2) count++;
if (outcount++<3) output(table,n);
}
else{
if (row==0 && n>5) kn=n/2; else kn=n;
for (col=0;col<=kn;col++){
if (collist[col] || lblist[col+row] || rblist[col-row+n-1]) continue;
collist[col]=1;
lblist[col+row]=1;
rblist[col-row+n-1]=1;
table[row]=col;
find(row+1,table,n);
collist[col]=0;
lblist[col+row]=0;
rblist[col-row+n-1]=0;
}
}
}
Read full article from USACO 1.5 – Checker Challenge | Jack Neus
