请问一个算法题，关于填格子的。

[stefanzweig]

大家好。非常冒昧到这里来问一道算法题。

我有一个棋盘，10×10大小的。现在我要依次在格子内放棋子，棋子有编号的，1 到 100。

要求是：
1. 编号为1的棋子只能放在最左上角的格子里。接下里一次放相应编号的棋子。
2. 接下来的棋子可以水平相隔两个格子或者竖直相隔两个格子放入。或者……
3. 接下来的棋子可以在对角线的线路上放，和上次的棋子相隔一个格子。
4. 目的是100个棋子都能放进棋盘。

问题是按照这个规则能有多少种结果。用程序怎么实现呢？

我自己简化过问题到5×5，包括可以重复的组合一共有500+种结果。但是同样的程序跑6×6已经一个多小时出不来结果了。我想知道在算法上应该选择什么样的策略。谢谢。

[laskuma]

要求有点没看懂 2 3条件是任何时刻选一个满足？还是说只能交替满足？另外3有点没看懂

[laskuma]

我算法不好…问了@abccb1 表示用DFS或者直接数学方法解

[fanzeyi]

感觉可能是动态规划，目测不在能力范围内

大概想了下状态 f[i][j] 表示 (i,j) 格子（左上为 (0,0)）的结果..

=== 以上删除 ===

尝试写动态转移方程的时候发现，还可以竖直放，也就是说第 (i,j) 格子可以从 (i+1,j)个格子放过来…… 所以不满足动态规划的无后效性……

或者是比较高级的动态规划…… 不会呢

（其他同学继续想吧…… ）

[qiukun]

将起点和终点连接起来。就是寻找汉密尔顿回路的问题。http://zh.wikipedia.org/zh/%E5%93%88%E5%AF%86%E9%A1%BF%E5%9B%BE
baidu之下，木有求总数的算法（实际上只能构造出特定的回路的样子）。