1

我有一个课堂作业（已经过去了），我必须写一个数独求解器。我能够创建一种可以解决每个缺失数字的方法。但是我无法创建一种方法来查找我需要解决的单元格。我应该采用二维数组并填写缺失的数字（由 0 表示）。我把我的一些代码放在下面，但不是全部（即使任务已经通过，我尊重教授的意愿）。

public class SolveSudoku {

    private static int[][] grid = new int[9][9];

    public static int[][] getSolution(int[][] grid) {
        for (int i = 0; i < 9; i++) {
            System.arraycopy(grid[i], 0, SolveSudoku.grid[i], 0, 9);
        }
        int n = getZero();
        return getSolution(n);
    }

    private static int[][] getSolution(int n) {
        if (n == 0) {
            return grid;
        }
        Cell cell = getZero();
        int row = cell.row;
        int column = cell.column;
        for (int number = 1; number <= 9; number++) {
            //checks cell using another method
            //I have booleans that return true if the number works
        }
        return null;
    }

    private static int getZero() {
        return 0;
    }

    private static class Cell {
        int cell = 0;
        int row = 0;
        int column = 0;
        int number;
    }
}

我有 getZero 方法，它必须在网格中找到每个零（0 代表一个缺失的数字），这样我就可以解决它。我应该在 getZero 中做什么来找到我需要更换的单元格？

4

2 回答 2

1

您不检查数字是否在同一个 3x3 正方形中重复（仅行和列）。

我不明白“找零”是什么意思。其实是没有意义的，从第一行或者最后一行解数独对解法没有影响。我将解释我为同样的麻烦做了什么。

  1. 一个单元格不是一个 int，是一个对象。在对象中，我存储了一个值（如果找到则为数字，否则为 0）和一个布尔值 [9]。False 表示 (index + 1) 被丢弃，因为它在同一行/列/正方形中，true 表示尚未确定。此外，3 个列表（向量、集合等）。
  2. 81 个单元的列表（如果您愿意，可以将其设为二维数组）。
  3. 9 个 Lists/Vectors/Sets 代表行，9 个代表列，9 个代表正方形。81 个单元格中的每一个都分配给它的行/列/正方形。在每个单元格中，您存储对其所属列表的引用。
  4. 现在是执行部分。在第一次迭代中，每次您找到一个非零（数独中固定的数字）时，您都会遍历该单元格所属的列表。对于这些列表中的每个单元格，您将分配给该数字的布尔值标记为 false。
  5. 您循环遍历单元格，每次找到 0 时，您都会检查单元格中有多少布尔值是真实的。如果为 1（所有其他 8 个可能的值已被丢弃），则为单元格的值。你设置它，然后像 4) 一样，你得到它所属的列表，并在每个单元格中将该数字标记为 false。循环直到你得到一个解决方案，或者一个你不能设置任何数字的迭代（没有直接可用的解决方案，必须从回溯或类似开始）。

请记住，在使用键盘之前，要清楚地了解问题是什么，以及在没有计算机的情况下如何解决问题。如果您不知道自己想做什么，计算机将无济于事（除非您在 stackoverflow 中发帖）-

于 2011-03-07T22:47:27.160 回答
0

据我所知，您想在grid. 我将首先定义为最低含零行中的第一个含零列。

这可以使用简单的搜索来完成：

private Cell getZeroCell(){
    int rz = -1;
    int cz = -1;
    outer: for(int row = 0; row < grid.length; row++){
        for(int col = 0; col < grid[row].length; col++){
            if(grid[row][col] == 0){
               rz = row;
               cz = col;
               break outer;
            }
        }
    }
    if(rz == -1 || cz == -1){
       // no zeros found
       return null;
    }else{
       // first zero found at row `rz` and column `cz`
       Cell cell = new Cell();
       cell.row = rz;
       cell.column = cz;
       return cell;
    }
}

获取第一个包含零的单元格的“数字”（从左到右，然后从上到下，从 0 开始计数）：

private int getZeroInt(){
    int rz = -1;
    int cz = -1;
    outer: for(int row = 0; row < grid.length; row++){
        for(int col = 0; col < grid[row].length; col++){
            if(grid[row][col] == 0){
               rz = row;
               cz = col;
               break outer;
            }
        }
    }
    if(rz == -1 || cz == -1){
       // no zeros found
       return -1;
    }else{
       return rz * grid[0].length + cz;
    }
}

获取包含零的单元格数：

private int getNumZeros(){
    int count = 0;
    for(int row = 0; row < grid.length; row++){
        for(int col = 0; col < grid[row].length; col++){
            if(grid[row][col] == 0){
              count++;
            }
        }
    }
    return count;
}
于 2011-03-07T21:41:17.863 回答