1至9数字填空与字典序

耿祥义

    本帖借助全排列解决一些数字填空问题，给出了两个例子，①九宫格填数字 ②三角形填数字。读者可以举一反三，用这里的代码解决类似的问题。

1.经典的基础算法

    ● 1-9个数字的填空问题不知道有多少，因此不同的问题可能各有各自的算法。

    ● 我们这里决定使用经典的字典序输出全排列的算法，因为这个算法可以解决各种1-9个数字的填空问题。

    ● 按照字典序从一个全排列得到下一个全排列的时间复杂度是O(1)，因此得到1至n的全部不重复的全排列时间复杂度是O(n!)。

    ★ 不管怎样填空，都是一个全排列，所以用全排列算法可以“通吃”各种数字填空问题。

    ● 我们在本公众号的帖子：基于字典序输出全排列-训练常用实用类相关知识 详细介绍了经典的字典序输出排列的算法，并给出了实现的Java代码,这里我们直接使用。

    ● 为了阅读的方便，我们把这个经典算法的代码放在本帖的最后（就当您会了），即实现下列接口的Student类放在最后。

    NextArrangement.java

    public interface NextArrangement {

        //返回全排列arrangement的下一个全排列:

        public StringBuffer nextFullArrangement(StringBuffer arrangement);

    }

2.九宫格填数字

    1至9九个数字，横竖都有3个格，使每行、每列以及两个对角线上的三数之和都等于15。

   （1）给出3种方案。

   （2）一共有多少种方案？（这里程序给出的是8种）

   （3）去掉“似乎相同”的方案，还剩多少种?(答案，1种)。

     这里解释一下第（3）条的意思。假设（2）的答案是m个。九宫格没有定义方向，那么一个人站在左上角的格子里看到的某个方案的效果，会和他站在右下角的格子里看到的某个方案的效果一样...，其它点依次类推。按照这种逻辑去掉一样的，那么应该还剩m/8种方案。即考虑旋转、镜像后相同的算同一种。

程序运行效果如图：

代码如下：

Application.java

public class Application  {

    public static void main(String args[]) {

        StringBuffer start = new StringBuffer("123456789");

        String MAX = "987654321";

        NineGrid nineGrid = new NineGrid();

        int grid[][] = null;

        NextArrangement nextArrangement = new Student();

        int count = 0;

        boolean print = false;

        grid = nineGrid.changeToIntArray(start);

        while(!new String(start).equals(MAX)) {

             if(nineGrid.isRightNineGrid(grid)){

                count++;

                print = true;

             }

             else {

                 print = false;

             }

             if(count<=3&&print) {

                 nineGrid.printNineGrid();//输出3个方案

             }

             start = nextArrangement.nextFullArrangement(start);

             grid = nineGrid.changeToIntArray(start);

        }

        System.out.println("一共有"+count+"个方案");

    }

}

NineGrid.java

import java.util.Arrays;

public class NineGrid {

    int grid[][];

    public int [][] changeToIntArray(StringBuffer str){

         int a[][] = new int[3][3];

         for(int i=0,index = 0;i<3;i++){

            for(int j=0;j<3;j++) {

                int number = Integer.parseInt(""+str.charAt(index));

                a[i][j] = number;

                index++;

            }

         }

         return a;

    }

    public boolean isRightGrid(int grid[][]) { //判断填空是否正确

        this.grid = grid; 

        int a[] = new int[8]; 

        a[0] = grid[0][0]+grid[0][1]+grid[0][2];//第1行

        a[1] = grid[1][0]+grid[1][1]+grid[1][2];

        a[2] = grid[2][0]+grid[2][1]+grid[2][2];

        a[3] = grid[0][0]+grid[1][0]+grid[2][0];//第1列

        a[4] = grid[0][1]+grid[1][1]+grid[2][1];

        a[5] = grid[0][2]+grid[1][2]+grid[2][2];

        a[6] = grid[0][0]+grid[1][1]+grid[2][2];//正对角线

        a[7] = grid[2][0]+grid[1][1]+grid[0][2];

        boolean boo = true;

        for(int i=0;i<a.length;i++){

           if(a[i]!=15) {

              boo = false;

              break;

           }

        }

        return boo;

    }

    public void printNineGrid(){

        for(int i=0;i<grid.length;i++) {

            System.out.println(Arrays.toString(grid[i]));

        } 

        System.out.println("----------------------");

    }

}

3.正三角形填数字

    1,2,3,4,5,6,7,8,9 填到直角三角形的3个边（每边上有四个数字），使得每个边上的4个数字和相等（都是17，其他数没有方案）。

例如：

---------------------

1

7  5

6     9

3  8  4  2

---------------------

   （1）给出2种方案。

   （2）一共有多少种方案？（这里程序给出的是96种）

   （3）去掉“似乎相同”的方案（剩下32种）。

     这里解释一下第（3）条的意思。假设（2）的答案是m个。三角形没有定义方向，那么一个人站在某个角的格子里看到的某个方案的效果，就会和另一个角的格子里看到的某个方案的效果一样...。按照这种逻辑去掉一样的，那么应该还剩m/3种方案。即考虑旋转、镜像后相同的算同一种。

代码如下：

ApplicationTwo.java

public class ApplicationTwo  {

    public static void main(String args[]) {

        StringBuffer start = new StringBuffer("123456789");

        String MAX = "987654321";

        TriangleGrid triangleGrid = new TriangleGrid();

        int grid[] = null;

        NextArrangement nextArrangement = new Student();

        int count = 0;

        boolean print = false;

        grid = triangleGrid.changeToIntArray(start);

        while(!new String(start).equals(MAX)) {

             if(triangleGrid.isRightGrid(grid)){

                count++;

                print = true;

             }

             else {

                 print = false;

             }           

           if(count<=2&&print) {

                  System.out.println("输出2个方案，这是第"+count+"个方案");

                  triangleGrid.printTriangleGrid();//输出2个方案

             }

             start = nextArrangement.nextFullArrangement(start);

             grid = triangleGrid.changeToIntArray(start);

        }

        System.out.println("一共有"+count+"个方案");

    }

}

TriangleGrid.java

import java.util.Arrays;

public class TriangleGrid {

    int grid [];

    public int [] changeToIntArray(StringBuffer str){

         int a[] = new int[9];

         for(int i=0,index = 0;i<9;i++){

              int number = Integer.parseInt(""+str.charAt(index));

                a[i] = number;

                index++;

         }

         return a;

    }

    public boolean isRightGrid(int grid[]) { //判断填空是否正确

        this.grid = grid; 

        int a[] = new int[3]; 

        a[0] = grid[0]+grid[1]+grid[2]+grid[3];//边1

        a[1] = grid[3]+grid[4]+grid[5]+grid[6];//边2

        a[2] = grid[6]+grid[7]+grid[8]+grid[0];//边3

        boolean boo = true;

        for(int i=0;i<a.length;i++){

           if(a[i]!=17) {

              boo = false;

              break;

           }

        }

        return boo;

    }

    public void printTriangleGrid(){

        System.out.println(""+grid[0]);

        System.out.println(""+grid[8]+"  "+grid[1]);

        System.out.println(""+grid[7]+"     "+grid[2]);

        System.out.println(""+grid[6]+"  "+grid[5]+"  "+grid[4]+"  "+grid[3]);

       System.out.println("---------------------------");

    }

}

4.给前面提供有力支持的Student

细节讲解见公众号以前的文章：基于字典序输出全排列-训练常用实用类相关知识

Student.java 

public class Student implements NextArrangement{

    public StringBuffer nextFullArrangement(StringBuffer s){ //从小到大找下一个全排列

        int k = -1;

        StringBuffer nextString = new StringBuffer();

        for(int i=0;i<s.length()-1;i++) { 

            if(s.charAt(i)<s.charAt(i+1)){

                k = i;

            }

        }

        char ch = s.charAt(k);

        char max =  s.charAt(k+1);//k+1位置的字符比ch大

        int position = -1; 

        for(int i=k+1;i<=s.length()-1;i++) {

            if(s.charAt(i)>ch&&s.charAt(i)<=max){

                position = i;

                max = s.charAt(i);

            }

        } 

        char findChar = s.charAt(position);

        s.setCharAt(position,ch);

        s.setCharAt(k,findChar); 

        StringBuffer suffix = new StringBuffer(s.substring(k+1));

        suffix = suffix.reverse();//把从k+1位置开始的字符序列反转

        nextString = nextString.append(s.substring(0,k+1));

        nextString = nextString.append(suffix);

        return nextString;

    }

}

推荐阅读：