回溯法解数独

孟君

发布于 2019-08-26 17:52:49

1.8K0

发布于 2019-08-26 17:52:49

数独，是源自18世纪瑞士的一种数学游戏，是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。这是一种老少皆宜的游戏，想必很多读者都玩过吧。

数独盘面是个九宫，每一宫又分为九个小格。
在这八十一格中给出一定的已知数字和解题条件，
利用逻辑和推理，在其他的空格上填入1-9的数字。
使1-9每个数字在每一行、每一列和每一宫中都只出现一次，
所以又称“九宫格”。

在开始下文之前，我们先来回忆一下自己是如何解答数独难题的？是不是尝试着放一个数，然后判断该数放上去是否符合规则。如果符合规则，继续放其它的数字；如果不符合规则，就在该位置上放置其它的数字进行尝试。这种试探性的操作，其实就是回溯法。其定义如下：

## https://baike.baidu.com/item/%E5%9B%9E%E6%BA%AF%E6%B3%95
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，
按选优条件向前搜索，以达到目标。但当探索到某一步时，
发现原先选择并不优或达不到目标，就退回一步重新选择，
这种走不通就退回再走的技术为回溯法，
而满足回溯条件的某个状态的点称为“回溯点”。

本文的目标是：

对于一个给定的“残缺”的9 X 9棋盘，使用回溯法去给出一个解，如有解则打印出一个解；如果没有解，则输出没有找到相应的解法。

如，给定一个“残缺”的棋盘：

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

求得一个结果，如：

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

接下来，我们就对回溯法如何去做进行思考，思路和解法如下：

思路

1、如何存储数独？

使用二维数组存储一个9 X 9的数独信息。
其中，值为0表示该位置未放数值 (1-9)。

2、处理方向？

从二维数组(int[][])的(0,0)坐标开始，先处理行数据，
到该行最后时，从下一行的第一列开始处理下一行的数据。
依此类推。

3、冲突如何判断？

一个9 X9的数独有如下规则：

每一行数字不能重复，1到9。
每一列数字不能重复，1到9。
每个宫(3X3)的块，数字不能重复，1到9。

所以，我们尝试去填值的时候，需要判断是否符合规则，也即没有与其它数值冲突。

  /**
   * 在指定位置是否可以放置数据
   */
  private boolean isSafe(int[][] grids, int row, int column, int value) {
    return this.isColumnSafe(grids, column, value)
        && this.isRowSafe(grids, row, value)
        && this.isSmallBoxSafe(grids, row, column, value);
  }
  
  /**
   * 某一行放置数据是否有冲突
   */
  private boolean isRowSafe(int[][] grids, int row, int value) {
    for (int i = 0; i < 9; i++) {
      if (grids[row][i] == value) {
        return false;
      }
    }
    return true;
  }

  /**
   * 某一列放置数据是否有冲突
   */
  private boolean isColumnSafe(int[][] grids, int column, int value) {
    for (int i = 0; i < 9; i++) {
      if (grids[i][column] == value) {
        return false;
      }
    }
    return true;
  }

  /**
   * 每个区域是 3 X 3 的子块，是否可以可以放置数据
   */
  private boolean isSmallBoxSafe(int[][] grids, int row, int column, int value) {
    int rowOffset = (row / 3) * 3;
    int columnOffset = (column / 3) * 3;
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        if (grids[rowOffset + i][columnOffset + j] == value) {
          return false;
        }
      }
    }
    return true;
  }

4、结束条件？

一个数独的解法，其每个位置的数值，都符合上述安全的规则。
所以，最简单的方法是循环遍历二维数组中的数值，
然后判断每个数值是否都是安全的，且没有不为0的数值。

如果有多次这样的判断调用，那判断的成本太大了。我们可以使用更加简单的方法判断。

因为，我们的做法是先处理行，然后处理列。如果某行某列的值为0，则填充一个合适的值之后，处理下一列；或者某行某列的数值不为0，直接处理下一列。所以，如果找到一种解法，最后的条件可以根据最终行和列的值来判断，row为8，column为9。

结束条件如下：

  /**
   * 解数独
   */
  private boolean solve(int[][] grids, int row, int column) {

    /**
     * 结束条件
     */
    if (row == 8 && column == 9) {
      return true;
    }
        //省略其它
   }

有了上述的思路，就很容易写出代码来了。如：

/**
 * 
 * @author wangmengjun
 *
 */
public class SudokuPuzzleSolver {

  /**
   * 解数独，并打印结果
   */
  public void solve(int[][] grids) {
    printArray(grids);
    System.out.println();

    if (this.solve(grids, 0, 0)) {
      printArray(grids);
    } else {
      System.out.println("没有找到相应的解法");
    }
  }

  /**
   * 解数独
   */
  private boolean solve(int[][] grids, int row, int column) {

    /**
     * 结束条件
     */
    if (row == 8 && column == 9) {
      return true;
    }

    /**
     * 如果column == 9, 那么需要换行，也就需要更新column和row的值.
     */
    if (column == 9) {
      column = 0;
      row++;
    }
    /**
     * 如果当前位置上grids[row][column]的值不为0，则处理下一个
     */
    if (grids[row][column] != 0) {
      return solve(grids, row, column + 1);
    }

    /**
     * 如果当前位置上grids[row][column]的值为0, 尝试在1~9的数字中选择合适的数字
     */
    for (int num = 1; num <= 9; num++) {
      if (isSafe(grids, row, column, num)) {
        grids[row][column] = num;
        if (solve(grids, row, column + 1)) {
          return true;
        }

      }
    }
    /**
     * 回溯重置
     */
    grids[row][column] = 0;
    return false;
  }

  /**
   * 某一行放置数据是否有冲突
   */
  private boolean isRowSafe(int[][] grids, int row, int value) {
    for (int i = 0; i < 9; i++) {
      if (grids[row][i] == value) {
        return false;
      }
    }
    return true;
  }

  /**
   * 某一列放置数据是否有冲突
   */
  private boolean isColumnSafe(int[][] grids, int column, int value) {
    for (int i = 0; i < 9; i++) {
      if (grids[i][column] == value) {
        return false;
      }
    }
    return true;
  }

  /**
   * 每个区域是 3 X 3 的子块，是否可以可以放置数据
   */
  private boolean isSmallBoxSafe(int[][] grids, int row, int column, int value) {
    int rowOffset = (row / 3) * 3;
    int columnOffset = (column / 3) * 3;
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        if (grids[rowOffset + i][columnOffset + j] == value) {
          return false;
        }
      }
    }
    return true;
  }

  /**
   * 在指定位置是否可以放置数据
   */
  private boolean isSafe(int[][] grids, int row, int column, int value) {
    return this.isColumnSafe(grids, column, value)
        && this.isRowSafe(grids, row, value)
        && this.isSmallBoxSafe(grids, row, column, value);
  }

  /**
   * 打印二维数组到控制台
   */
  private void printArray(int[][] grids) {
    for (int i = 0; i < 9; i++) {
      if (i % 3 == 0) {
        System.out.println(" -----------------------");
      }
      for (int j = 0; j < 9; j++) {
        if (j % 3 == 0) {
          System.out.print("| ");
        }
        System.out.print(grids[i][j] == 0 ? " " : grids[i][j]);
        System.out.print(" ");
      }
      System.out.println("|");
    }
    System.out.println(" -----------------------");
  }
}

接下来，我们使用上述程序对不同的场景做些验证，以求出某个解。

测试

1、完全空白的数独

测试代码和输出如下：

import java.util.Random;

public class Main {

  public static void main(String[] args) {
    SudokuPuzzleSolver example = new SudokuPuzzleSolver();
    int[][] grids = new int[9][9];
    example.solve(grids);
  }
}

 -----------------------
|       |       |       |
|       |       |       |
|       |       |       |
 -----------------------
|       |       |       |
|       |       |       |
|       |       |       |
 -----------------------
|       |       |       |
|       |       |       |
|       |       |       |
 -----------------------

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

2、部分残缺的数独

如果是完全空白的场景，那么结果只会有一种（第一行是123456789，是基于我们编写的代码决定的）。如果想让产生的数独有随机性，我们可以随机初始化第一行的数据，如：

import java.util.Random;

public class Main {

  public static void main(String[] args) {
    SudokuPuzzleSolver example = new SudokuPuzzleSolver();
    int[][] grids = initGrids();
    example.solve(grids);
  }

  public static int[][] initGrids() {
    int[][] grids = new int[9][9];
    int[] firstRow = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    Random rand = new Random();
    for (int i = 0; i < 10; i++) {
      int randIndex = rand.nextInt(8) + 1;
      int temp = firstRow[0];
      firstRow[0] = firstRow[randIndex];
      firstRow[randIndex] = temp;
    }
    grids[0] = firstRow;
    return grids;
  }
}

某次运行的结果如下

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

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

3、解决指定数独难题

如果已经有一个数独难题，想给出一个解法，则可以使用如下方式：

public class Main {

  public static void main(String[] args) {
    SudokuPuzzleSolver example = new SudokuPuzzleSolver();
    int[][] grids = initGrids();
    example.solve(grids);
  }

  public static int[][] initGrids() {
    int[][] grids = { { 3, 0, 0, 0, 1, 7, 0, 2, 8 },
        { 5, 0, 0, 0, 2, 0, 0, 9, 4 }, { 6, 2, 0, 0, 9, 0, 0, 1, 7 },
        { 0, 3, 0, 4, 0, 1, 0, 0, 6 }, { 4, 7, 0, 0, 0, 0, 0, 3, 5 },
        { 2, 0, 0, 0, 3, 0, 0, 0, 1 }, { 1, 0, 0, 7, 0, 9, 0, 0, 2 },
        { 0, 0, 9, 8, 0, 2, 0, 4, 0 }, { 8, 0, 0, 0, 0, 3, 7, 0, 0 } };
    return grids;
  }
}

运行结果如下：

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

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

小结

通过阅读本文，大家可以掌握使用回溯法解数独的方法。其实，使用回溯法可以去解决较多的问题，比如：比较典型的是八皇后问题。

有兴趣的读者可以尝试编写一下。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-08-13，如有侵权请联系 cloudcommunity@tencent.com 删除

游戏

本文分享自孟君的编程札记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

游戏

登录后参与评论

0 条评论

热度