回溯法小结（leetcode37）解决数独问题

数独题如下，求出解答

数独

题目给定的数据是：
["5","3",".",".","7",".",".",".","."]
["6",".",".","1","9","5",".",".","."]
[".","9","8",".",".",".",".","6","."]
["8",".",".",".","6",".",".",".","3"]
["4",".",".","8",".","3",".",".","1"]
["7",".",".",".","2",".",".",".","6"]
[".","6",".",".",".",".","2","8","."]
[".",".",".","4","1","9",".",".","5"]
[".",".",".",".","8",".",".","7","9"]
‘.’代表空出的部分
题目给的方法是：

class Solution {
    public void solveSudoku(char[][] board) {   
    }

本题可以用回溯法来解决。

第一步
首先解决辅助部分的函数

1. 查看放入的数据是否有效
2. 用list记录空格的位置，这样我们就不用每次遍历整个表来填空格，而是直接定位空格，这样就可以用少量空间换出时间。
   实现
   1

    private boolean isValid(int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.' && board[i][col] == c)
                return false; // 检查行
            if (board[row][i] != '.' && board[row][i] == c)
                return false; // 检查列
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.'
                    && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
                return false; // 检查3x3小方格
        }
        return true;
    }

2 此处注意num=9*i+j的模式，可以反编译为i = num/9，j = num%9

记录空格的位置
    public void CountEmptyCell() {
        list = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.') {
                    list.add(9 * i + j);
                }
        }

    }

dfs函数用回溯法

递归树 image.png

    public boolean dfs(int cur) {
        if (cur == list.size()) {
            return true;
        }

        int decode = list.get(cur);
        int row = decode / 9;
        int col = decode % 9;
        for (char i = '1'; i <= '9'; i++) {
            if (isValid(row, col, i)) {
                board[row][col] = i;
                if (dfs(cur + 1))
                    return true;
                else
                    board[row][col] = '.';//一定要记得状态回滚
            }
        }
        return false;
    }

注意此处的dfs方法我用的是boolean返回类型，就是能够让其找到了答案后不会继续的递归，而是及时的中断返回（由于正解只有一个，所以我们不必继续遍历把所有的解都找出来，如果不这样做，那么在查找下一个解的时候，会把状态给返回到默认的没有填写数字的状态，如果之后一直没有找到解，那么最后的答案就会是初始状态，这是因为没有找到解，就会把状态还原）

以下是没考虑的错误写法

image.png

    public void dfs(int cur) { // 他也可以打印出结果，但是由于是全体枚举，即使找到了答案，还是会一直枚举之后的结果，看之后的结果是不是对的，但是这样的话就会冲掉我们的正确答案，因为只有一个解，其他的全是错误的！这样就会一直把我们填好的答案还原为'.'
        if (cur == list.size()) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
            return;
        }

        int decode = list.get(cur);
        int row = decode / 9;
        int col = decode % 9;
        for (char i = '1'; i <= '9'; i++) {
            if (isValid(row, col, i)) {
                board[row][col] = i;
                dfs(cur + 1);
                board[row][col] = '.';
            }
        }

    }

这样，输出结果在输出第一个解后，继续遍历，然后后面又找不到解了，整个函数就会把结果，也就是我们的board[][]还原为初始状态。
[图片上传中...(image.png-c68388-1547468691246-0)]

错误的输出结果为

package com.leetcode;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

import javax.print.attribute.IntegerSyntax;

public class leet37 {

    char[][] board;
    ArrayList<Integer> list;

    public char[][] solveSudoku(char[][] board) {
        this.board = board;
        CountEmptyCell();
        dfs(0);
        return board;

    }

/*  public boolean dfs(int cur) {
        if (cur == list.size()) {
            return true;

        }

        int decode = list.get(cur);
        int row = decode / 9;
        int col = decode % 9;
        for (char i = '1'; i <= '9'; i++) {
            if (isValid(row, col, i)) {
                board[row][col] = i;
                if (dfs(cur + 1))
                    return true;
                else
                    board[row][col] = '.';
            }
        }
        return false;

    }*/

    
      public void dfs(int cur) {//他也可以打印出结果，但是由于是全体枚举，即使找到了答案，还是会一直枚举之后的结果，看之后的结果是不是对的，但是这样的话就会冲掉我们的正确答案， 因为只有一个解，其他的全是错误的！这样就会一直把我们填好的答案还原为'.' 
          if (cur == list.size()) { 
              for (int i =0; i < 9; i++) { 
                  for (int j = 0; j < 9; j++) { 
                      System.out.print(board[i][j]+" ");
                     } 
                  System.out.println(); 
                  } 
              return;
      }
      
      int decode = list.get(cur); 
      int row = decode / 9; 
      int col = decode % 9; 
      for(char i = '1'; i <= '9'; i++) { 
          if (isValid(row, col, i)) { 
              board[row][col] =i; 
              dfs(cur + 1); 
              board[row][col] = '.'; 
              } 
          }
      
      }
     


    public void CountEmptyCell() {
        list = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.') {
                    list.add(9 * i + j);
                }
        }

    }

    private boolean isValid(int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.' && board[i][col] == c)
                return false; // check row
            if (board[row][i] != '.' && board[row][i] == c)
                return false; // check column
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.'
                    && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
                return false; // check 3*3 block
        }
        return true;
    }

    public static void main(String[] args) throws FileNotFoundException {
        leet37 test = new leet37();
        File file = new File("C:\\Users\\yihon\\Desktop\\123.txt");
        Scanner sc = new Scanner(file);
        char[][] c = new char[9][9];
        int i = 0;
        while (sc.hasNextLine()) {
            String in = sc.nextLine();
            in = in.replace("[", "");
            in = in.replace("]", "");
            in = in.replaceAll("\"", "");
            String[] t = in.split(",");

            for (int j = 0; j < 9; j++)
                c[i][j] = t[j].charAt(0);

            i++;
        }
        for (i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(c[i][j] + " ");

            }
            System.out.println();
        }

        test.solveSudoku(c);

        for (i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(c[i][j] + " ");

            }
            System.out.println();
        }

    }

}

输入
5 3 . . 7 . . . . 
6 . . 1 9 5 . . . 
. 9 8 . . . . 6 . 
8 . . . 6 . . . 3 
4 . . 8 . 3 . . 1 
7 . . . 2 . . . 6 
. 6 . . . . 2 8 . 
. . . 4 1 9 . . 5 
. . . . 8 . . 7 9 
输出：
这次输出是由于我在dfs函数没cur==list.size()的情况下输出的结果，然后继续遍历
5 3 4 6 7 8 9 1 2 
6 7 2 1 9 5 3 4 8 
1 9 8 3 4 2 5 6 7 
8 5 9 7 6 1 4 2 3 
4 2 6 8 5 3 7 9 1 
7 1 3 9 2 4 8 5 6 
9 6 1 5 3 7 2 8 4 
2 8 7 4 1 9 6 3 5 
3 4 5 2 8 6 1 7 9 
main函数输出结果：（由于没有及时停止，继续遍历后没找到解，从而冲掉了原解）
5 3 . . 7 . . . . 
6 . . 1 9 5 . . . 
. 9 8 . . . . 6 . 
8 . . . 6 . . . 3 
4 . . 8 . 3 . . 1 
7 . . . 2 . . . 6 
. 6 . . . . 2 8 . 
. . . 4 1 9 . . 5 
. . . . 8 . . 7 9 

然后以下是正确解法的源代码：（这里我把给定函数的void，换成了char[][]，主要是方便我本地输入测试用）

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

import javax.print.attribute.IntegerSyntax;

public class leet37 {

    char[][] board;
    ArrayList<Integer> list;

    public char[][] solveSudoku(char[][] board) {
        this.board = board;
        CountEmptyCell();
        dfs(0);
        return board;

    }

    public boolean dfs(int cur) {
        if (cur == list.size()) {
            return true;

        }

        int decode = list.get(cur);
        int row = decode / 9;
        int col = decode % 9;
        for (char i = '1'; i <= '9'; i++) {
            if (isValid(row, col, i)) {
                board[row][col] = i;
                if (dfs(cur + 1))
                    return true;
                else
                    board[row][col] = '.';
            }
        }
        return false;

    }

    
    /*  public void dfs(int cur) {//他也可以打印出结果，但是由于是全体枚举，即使找到了答案，还是会一直枚举之后的结果，看之后的结果是不是对的，但是这样的话就会冲掉我们的正确答案， 因为只有一个解，其他的全是错误的！这样就会一直把我们填好的答案还原为'.' 
          if (cur == list.size()) { 
              for (int i =0; i < 9; i++) { 
                  for (int j = 0; j < 9; j++) { 
                      System.out.print(board[i][j]+" ");
                     } 
                  System.out.println(); 
                  } 
              return;
      }
      
      int decode = list.get(cur); 
      int row = decode / 9; 
      int col = decode % 9; 
      for(char i = '1'; i <= '9'; i++) { 
          if (isValid(row, col, i)) { 
              board[row][col] =i; 
              dfs(cur + 1); 
              board[row][col] = '.'; 
              } 
          }
      
      }*/
     


    public void CountEmptyCell() {
        list = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.') {
                    list.add(9 * i + j);
                }
        }

    }

    private boolean isValid(int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.' && board[i][col] == c)
                return false; // check row
            if (board[row][i] != '.' && board[row][i] == c)
                return false; // check column
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.'
                    && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
                return false; // check 3*3 block
        }
        return true;
    }

    public static void main(String[] args) throws FileNotFoundException {
        leet37 test = new leet37();
        File file = new File("C:\\Users\\yihon\\Desktop\\123.txt");
        Scanner sc = new Scanner(file);
        char[][] c = new char[9][9];
        int i = 0;
        while (sc.hasNextLine()) {
            String in = sc.nextLine();
            in = in.replace("[", "");
            in = in.replace("]", "");
            in = in.replaceAll("\"", "");
            String[] t = in.split(",");

            for (int j = 0; j < 9; j++)
                c[i][j] = t[j].charAt(0);

            i++;
        }
        for (i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(c[i][j] + " ");

            }
            System.out.println();
        }

        test.solveSudoku(c);

        for (i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(c[i][j] + " ");

            }
            System.out.println();
        }

    }

}

运行结果

输入
["5","3",".",".","7",".",".",".","."]
["6",".",".","1","9","5",".",".","."]
[".","9","8",".",".",".",".","6","."]
["8",".",".",".","6",".",".",".","3"]
["4",".",".","8",".","3",".",".","1"]
["7",".",".",".","2",".",".",".","6"]
[".","6",".",".",".",".","2","8","."]
[".",".",".","4","1","9",".",".","5"]
[".",".",".",".","8",".",".","7","9"]
输出
5 3 4 6 7 8 9 1 2 
6 7 2 1 9 5 3 4 8 
1 9 8 3 4 2 5 6 7 
8 5 9 7 6 1 4 2 3 
4 2 6 8 5 3 7 9 1 
7 1 3 9 2 4 8 5 6 
9 6 1 5 3 7 2 8 4 
2 8 7 4 1 9 6 3 5 
3 4 5 2 8 6 1 7 9