Java 数独游戏求解，dfs

dfs深度优先解决数独游戏问题

今天做到了一道题目是关于解决数独游戏的问题，这也是我第一次用dfs深度优先来解决问题很开心，能解决这种看起来非常难的问题。

---

数独游戏

---

玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个同色九宫内的数字均含1-9，不重复。

输入包含9x9的已知数字，空位用0补齐，中间用空格隔开。（输入数独题目确保正确）

输出为输入数独题目的解。

样例输入：

8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0

样例输出：

8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2

深度优先在数独游戏中怎么体现的呢，众所周知深度优先自然是一条道走到黑，有不符合要求的回到上一个点走另一条道路，以此类推，自然我们没法知道要循环多少次所以，我们要用递归法来解决这个问题。

回到这个题目我们都是知道的数独游戏是竖着横着都有1-9的数，不能重复不能少，并且在其九宫格内也是1-9不可以重复，所以我们可以用dfs来一步一步的看，

。。。。。。。。。。。。。。。。。。。不知怎么说了，看代码吧！

import java.util.Scanner;

/**
 * @Author Robin Wang
 * @Date 2020/3/8 12:49
 */
public class 数独游戏 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char a[][] = new char[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                a[i][j] = sc.next().charAt(0);
            }
        }
        dfs(a,0,0);
    }

    private static void dfs(char[][] a, int x, int y) {
        if(x==9){//x==9的时候自然就都走完了，可以输出了
            print(a);
            System.exit(0);
        }
        if(a[x][y]=='0'){    //判断当这个数是零的时候就是没有数自然可以进行填数。
            for (int i = 1; i <= 9 ; i++) {
                boolean res = check(a,x,y,i);//循环1-9 check（）函数判断是否能用 。
                if(res){
                    a[x][y] = (char) ('0'+i);//能用这个数的话 就填给它
                    dfs(a,x+(y+1)/9,(y+1)%9);//继续往下走（先横着走，在竖着走）。

                }
            }
            a[x][y] = '0';//回溯归零。

        }else{
            dfs(a,x+(y+1)/9,(y+1)%9);//不是空白继续往下走就可以了。
        }
    }

    private static void print(char[][] a) {//一个输出的函数
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(a[i][j]+" ");
            }
            System.out.println();
        }
    }

    private static boolean check(char[][] a, int x, int y, int i) {

        for (int j = 0; j < 9; j++) {
            if(a[x][j]=='0'+i) return false;//横着检查
            if (a[j][y]=='0'+i) return false;//竖着检查
        }
        for (int j = (x/3)*3; j < (x/3+1)*3; j++) {
            for (int k = (y/3)*3; k < (y/3+1)*3; k++) {
                if(a[j][k]=='0'+i) return  false;//九宫格内
            }

        }
        return true;
    }
}

希望明天更加精彩！！！！！