方格填数
如下的10个格子
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：
这道题和n皇后问题很像，最开始的思路就是模仿n皇后，采用逐行摆放的方法，写完代码以后发现跑不出来，
仔细想想这道题目还是和n皇有些区别的，n皇一行只需要放一个，不需要考虑这行后面的摆放问题，而且每行只需摆
放一个，这里每个位置都需要也必须放一个，所以改变策略，一个一个放。听起来好像没什么区别，前方按行放不也
是一个一个的放啊，注意这里区别体现在代码中的循环结构和临界语句，临界语句也就是完成一次摆放，即得到一种
填数方案。
接下来要考虑的就是判断位置是否可放，注意这里的相邻只需要考虑上下左右隔着一个即可，不需要考虑
长线上对角线或者行列是否相邻。由于放入的值都是具体的数字，所以相邻只需要做减法取绝对值即可。因为摆放是
具有顺序性的，这样判断的时候只需要判断之前已经摆放好的数字和当前数组是否相邻即可，这点和n皇又很相似。
我们使用一个二维数组用来记录填数方案，个人习惯于二维数组初始值设置为-1，这里不可以，所以改为有点奇怪的
20，假设在放第一个数字的时候，放0，此时与[0][0]（这个位置不能放数字）做差取绝对值得到1，判断为相邻，但
是其实第一个位置是可以取0的，这样就会使结果方案数量减少。
当到达临界条件时，下述代码中做了一个验证，判断是否存入的0-9每个数字，其实没有必要，但为了保留这种判断
思路，代码中没有删掉，读者可自行选择删减。之所以没有必要，是因为在循环中，每放置一个数字，它的可选值
都是从0-9，它总会也必须选择一个合适的值放进去。
总结一下，也就是下面三点
1.采用二维数字记录，设置初始值便于判断当前位置是否可用
2.去掉两个不可放位置，首尾
3.通过当前位置要放的数字与临近已放数字做差取绝对值，判断是否可放
还有很重要的一点，前面提到思路为一个一个放，在代码实现中，很容易会想到用循环来放置，但其实有个简单快速
的办法，我们放第一个数时，记N=1，此时N/4=0,N%4=1，发现这里的N/4，N%4就是第一个数的行列，这样放10个
数，一直到N=10，所以临界条件也就是N=11。如果把放第一个数记为N=0，就没有这种效果了。
JAVA代码：
package Seven;
public class Test6 {
private static int result = 0;
private static int[][] box;
private static int[] flag = new int[10];
public static void main(String[] args) {
box = new int[3][4];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
box[i][j] = 20;//初始值，随便取，只要是不会造成冲突的值即可，比如-1就不可行
}
}
for (int i = 0; i < flag.length; i++) {
flag[i] = -1;
}
put(1);
System.out.println(result);
}
private static void put(int n) {
if (n == 11) {
//判断是否存够了所要求的的9个数
for (int i = 0; i <= 9; i++) {
if (flag[i] == -1) {
return;
}
}
result++;
return;
}
for (int k = 0; k <= 9; k++) {
if ((flag[k] == -1 && box[n / 4][n % 4] == 20) && check(n / 4, n % 4, k)) {
box[n / 4][n % 4] = k;
flag[k] = 1;
put(n + 1);
box[n / 4][n % 4] = 20;//回溯
flag[k] = -1;
}
}
}
private static boolean check(int n, int i, int k) {
if ((n == 0 && i == 0) || n == 2 && i == 3) {
return false;
} else {
// 行
if (i - 1 >= 0 && Math.abs(box[n][i - 1] - k) == 1) {
return false;
}
// 列
if (n - 1 >= 0 && Math.abs(box[n - 1][i] - k) == 1) {
return false;
}
// 对角线
if (n - 1 >= 0 && i + 1 <= 3 && Math.abs(box[n - 1][i + 1] - k) == 1) {
return false;
}
if (n - 1 >= 0 && i - 1 >= 0 && Math.abs(box[n - 1][i - 1] - k) == 1) {
return false;
}
}
return true;
}
}
答案：1580
| 
转播
