第七届蓝桥杯个人赛省赛（Java B组）第六题

方格填空

如下的10个格子

填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

将方格横排展开为10个空间的整形数组

• 方格0和方格1， 3， 4， 5相邻
• 方格1和方格0， 2， 4， 5， 6相邻
• 方格2和方格1， 5， 6相邻

• 。。。。。

• 知道以上特性后，那我们一个一个地将输填入格子内，如果不满足题目条件就返回上一步，原理和八皇后回溯问题类似。

public class ResultFilling6 {
public static int counter = 0;

// 方格横排展开后的数组表示形式
public static int[] array = new int[10];

// 用来表示数字是否已经填过
public static boolean[] isVisit = new boolean[10];

public static void fill(int position) {
// 填入最后一个数字就结束
if (position == 10) {
            counter++;
return;
        }
for (int i = 0; i < 10; i++) {
// 判断数字是否可以填入
if (judge(i, position) && !isVisit[i]) {
array[position] = i;
                isVisit[i] = true;
// 填下一个方格
                fill(position + 1);
array[position] = -2;
                isVisit[i] = false;
            }
        }
    }

// 判断连续数字是否相邻
public static boolean judge(int num, int position) {
switch (position) {
case 0:
if (Math.abs(num - array[1]) > 1 && Math.abs(num - array[3]) > 1 && Math.abs(num - array[4]) > 1
                    && Math.abs(num - array[5]) > 1) {
return true;
            }
break;
case 1:
if (Math.abs(num - array[0]) > 1 && Math.abs(num - array[2]) > 1 && Math.abs(num - array[4]) > 1
                    && Math.abs(num - array[5]) > 1 && Math.abs(num - array[6]) > 1) {
return true;
            }
break;
case 2:
if (Math.abs(num - array[1]) > 1 && Math.abs(num - array[5]) > 1 && Math.abs(num - array[6]) > 1) {
return true;
            }
break;
case 3:
if (Math.abs(num - array[0]) > 1 && Math.abs(num - array[4]) > 1 && Math.abs(num - array[7]) > 1
                    && Math.abs(num - array[8]) > 1) {
return true;
            }
break;
case 4:
if (Math.abs(num - array[0]) > 1 && Math.abs(num - array[1]) > 1 && Math.abs(num - array[3]) > 1
                    && Math.abs(num - array[5]) > 1 && Math.abs(num - array[7]) > 1 && Math.abs(num - array[8]) > 1
                    && Math.abs(num - array[9]) > 1) {
return true;
            }
break;
case 5:
if (Math.abs(num - array[0]) > 1 && Math.abs(num - array[1]) > 1 && Math.abs(num - array[2]) > 1
                    && Math.abs(num - array[4]) > 1 && Math.abs(num - array[6]) > 1 && Math.abs(num - array[8]) > 1
                    && Math.abs(num - array[9]) > 1) {
return true;
            }
break;
case 6:
if (Math.abs(num - array[1]) > 1 && Math.abs(num - array[2]) > 1 && Math.abs(num - array[5]) > 1
                    && Math.abs(num - array[9]) > 1) {
return true;
            }
break;
case 7:
if (Math.abs(num - array[3]) > 1 && Math.abs(num - array[4]) > 1 && Math.abs(num - array[8]) > 1) {
return true;
            }
break;
case 8:
if (Math.abs(num - array[3]) > 1 && Math.abs(num - array[4]) > 1 && Math.abs(num - array[5]) > 1
                    && Math.abs(num - array[7]) > 1 && Math.abs(num - array[9]) > 1) {
return true;
            }
break;
default:
if (Math.abs(num - array[4]) > 1 && Math.abs(num - array[5]) > 1 && Math.abs(num - array[6]) > 1
                    && Math.abs(num - array[8]) > 1) {
return true;
            }
break;
        }
return false;
    }

public static void main(String[] args) {
// 初始化数组数据
for (int i = 0; i < array.length; i++) {
array[i] = -2;
            isVisit[i] = false;
        }
// 从第一个方格开始填
        fill(0);
        System.out.println(counter); // 输出结果为1580
    }
}