问题描述

方格填数

如下的10个格子

思路

填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

解决思路

该题是一个填数问题，要求将0~9各个数字填入10个方格中，并且连续数字不相邻，填数的策略可以以从左到右，从上到下的顺序填入。易发现，该问题可以分解为当前还需填入多少个满足要求的数字，当该子问题规模为0时，可以得到解决，因此具有最优子结构的性质，易使用递归实现。

• 递归边界条件：当所需要填的数为0，输出填数方案
• 递归式：循环遍历能够填入的数字，选择其中一个数字填入，递归填入满足条件更多的数，当所需填入数的个数为0时，返回

代码实现

package lanqiao.seven;

public class Six {

    //define the schema numbers
    private static int count = 0;
    
    public static void main(String[] args) {
        //define numbers:0~9
        int[] a= {0,1,2,3,4,5,6,7,8,9};
        //define grid
        int[] b = new int[10];
        //initialize
        for(int i=0;i<10;i++)
            b[i] = 100;
        fill(a,b,0,a.length);
        System.out.println(count);
    }
    
    public static void fill(int a[],int b[],int k,int n) {
        //fill by order,left to right,top to bottom
        
        //check whether adjacent first
        if(k>=5&&k<=10) {
            //upper adjacent
            if(isAdjacent(b[k-1],b[k-5])) return;
        }
        if(k>=2&&k<=3||k>=5&&k<=7||k>=9&&k<=10)
            //left adjacent
            if(isAdjacent(b[k-1],b[k-2])) return;
        if(k>=6&&k<=7||k>=9&&k<=10)
            //left upper adjacent
            if(isAdjacent(b[k-1],b[k-6])) return;
        if(k>=4&&k<=6||k>=8&&k<=10)
            //right upper adjacent
            if(isAdjacent(b[k-1],b[k-4])) return;
        
        //end condition
        if(k==n) {
            count ++ ;
            // print the reasonable solution
            for(int i=0;i<b.length;i++)
                System.out.print(b[i]);
            System.out.println();
            return;
        }
        
        //add a non-repeated number
        for(int i=0;i<a.length;i++) {
            //a[i]=-1 represents that a[i] is used before
            if(a[i] == -1) continue;
            b[k] = a[i];
            a[i] = -1; //used flag
            //enter the next recursive layer
            fill(a,b,k+1,n);
            //if b[k] = a[i] does not work, change an a[i]
            a[i] = b[k];
        }
    }
    
    public static boolean isAdjacent(int n1, int n2) {
        return Math.abs(n1-n2) == 1;
    }
}