Checker Challenge 跳棋的挑战
描述
检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
0 1 2 3 4 5 6 ------------------------- 1 | | O | | | | | ------------------------- 2 | | | | O | | | ------------------------- 3 | | | | | | O | ------------------------- 4 | O | | | | | | ------------------------- 5 | | | O | | | | ------------------------- 6 | | | | | O | | -------------------------
上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6 列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式），这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号删除并且不能参加USACO的任何竞赛。我警告过你了！
格式
测试时间: 1s
程序名: checker
输入格式:
(checker.in)
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
输出格式:
(checker.out)
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
SAMPLE INPUT
6
SAMPLE OUTPUT
2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
[编辑]Hint1
使用递归：
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; } } }
[编辑]Hint2
尽量减少频繁搜索的次数。通常最好的方法是以空间换时间。当检测某个皇后能否放在某一行时，存一个数组表示是否有皇后已经被放在那儿：
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; } } }
Hint3
使用“让一切绝对化（absolutely everything）” (在搜索中)您能避免程序中频繁的重复。不仅要记录下合法的皇后所在的那一行，还要标记所在的两条对角线(也就是象‘/’和‘\’的两条）使用大小为2*max - 1的布尔数组来判断其他皇后所在的对角线是否合法。
Hint4
对称： 您能否通过利用旋转、对称来削减一半或3/4的枚举量 ？ [提示：能]
Hint5
还是超时吗？如果你已经编好各个模块并且有检查对角线的子程序或者还有别的，把它们的代码移动到主过程中，调用子程序的消耗很重要。
Hint6 位运算的搜索
n皇后问题位运算版
n皇后问题是啥我就不说了吧，学编程的肯定都见过。下面的十多行代码是n皇后问题的一个高效位运算程序，看到过的人都夸它牛。初始时，upperlim:=(1 shl n)-1。主程序调用test(0,0,0)后sum的值就是n皇后总的解数。拿这个去交USACO，0.3s，暴爽。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;
乍一看似乎完全摸不着头脑，实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟，实在没研究出来再看下面的解说。
和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6x6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。前面说过-a相当于not
a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。。。
自己的代码：（加上了路径储存）
/*
ID: 138_3531
LANG: C++
TASK: checker
*/
#include<fstream>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
ifstream fin("checker.in");
ofstream fout("checker.out");
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;
}