如何实现检查数独在 Java 中是否有效？

Question

我想执行检查以查看数独在 Java 中是否有效，并遇到了 (http://leetcode.tgic.me/valid-sudoku/index.html)。

我了解它是如何验证行和列的，但是对于 3x3 网格验证器：

34         for(x = 0; x < mx; x += 3){
35             for(y = 0; y < my; y += 3){
36                 
37                 HashSet<Character> block = new HashSet<Character>();
38                 
39                 for(int offset = 0; offset < 9; offset++){
40                     int ox = offset % 3;
41                     int oy = offset / 3;
42                     
43                     char c = board[x + ox][y + oy];
44                     if(c != '.'){
45                         if(block.contains(c)) return false;
46                     
47                         block.add(c);
48                     } 
49                 }
50             }
51         }

什么是 offset 以及它如何帮助检查 3x3 网格中的每个单元格？我强行尝试了 x=0, y=0、offset=0 和 offset=1，但是 offset=1 给出了 int ox = 1%3 = 1; 和 int oy = 1/3，所以 board[0 + 1][0+(1/3)] = board[1][1/3], cell [1/3] 代表什么等等？

Answer 1

当你将 n 除以 m 时，两者都是 int（文字或变量），结果也是 int，所以 1/3 -> 0 因此当偏移量 == 0 => ox=0, oy=0 偏移量 == 1 => ox=1, oy=0 偏移量 == 2 => ox=2, oy=0 偏移量 == 3 -> ox=0, oy=1 ... 因此你会很好地循环 3 行和 3 列

Answer 2

您的 HashSet 方法看起来不错，但需要稍微调整一下...

假设是：当第一个块是无重复的，并且所有块中的相同位置也是无重复的，那么数独就被解决了。

在你的外循环中，你应该只遍历第一个块的值。

您应该将当前值添加到 "first block check set" 并通过内部循环检查所有块在相同位置都有不同的编号 "check set":

First iteration
1## 2## 3##
### ### ###
### ### ###

4## 5## 5##
### ### ###
### ### ###

7## 8## 9##
### ### ###
### ### ###
firstBlock: [1]

second iteration
#2# #3# #4#
### ### ###
### ### ###

#5# #6# #7# 
### ### ###
### ### ###

#8# #9# #1# 
### ### ###
### ### ###
firstBlock: [1,2]

最大的技巧是避免 x 和 y 坐标的单独循环。

由于Java是一种面向对象的编程语言，我建议使用objects来确定坐标。我们可以将它们保存在一个数组中（设置一个书签，我通常说 "Collection" 而不是...）并用一个简单的 forech 循环迭代它...

我们还必须处理我们事先知道的固定数量的对象（有 9 个块，每个块有 9 个位置...）所以我建议像这样使用 Java enums ：所以你的逻辑应该是这样的：

public class SudokuCheck {
    enum SudokuPosition {
        p11(0, 0), p12(0, 1), p13(0, 2), 
        p21(1, 0), p22(1, 1), p23(1, 2), 
        p31(2, 0), p32(2, 1), p33(2, 2);

        private final int x;
        private final int y;
        SudokuPosition(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public int getX() {return x;}    
        public int getY() {return y;}
    }

    boolean check(int[][] sudoku) {
        Set<Integer> firstBlockUniqueNumbers = new HashSet<>();
        for (SudokuPosition inBlock : SudokuPosition.values()) {
            firstBlockUniqueNumbers.add(sudoku[inBlock.x][inBlock.y]);

            Set<Integer> samePosInOtherBlocksUniqueNumbers = new HashSet<>();
            for (SudokuPosition ofBlock : SudokuPosition.values()) {
                int sameXinAll = inBlock.x + offset(ofBlock.x);
                int sameYinAll = inBlock.y + offset(ofBlock.y);
                samePosInOtherBlocksUniqueNumbers.add(sudoku[sameXinAll][sameYinAll]);
            }
            if (9 > samePosInOtherBlocksUniqueNumbers.size())
                // numbers where not unique at current block position
                // through all the blocks
                return false;
        }
        return 9 == firstBlockUniqueNumbers.size();
    }

    private int offset(int xOrY) {
        return xOrY * 3;
    }
}

我希望展示了 Java 枚举的有用性以及好的标识符名称的重要性。

我认为可以通过两种方式改进此方法：

使用 Java 8 Stream API 可以替代 forech 循环
位置元素的名称以某种方式重复它们的构造函数值，这可能会导致严重的错误。后者可能会被通过 name() 获得的常量名称的一些巧妙计算所取代，但对于这个演示来说，它可能已经足够好了......

Answer 3

我认为最佳答案是：

public boolean isValidSudoku(char[][] board) {
    if (board == null || board.length == 0) return false;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == '.') continue;
            if (!isValid(board, i, j)) return false;
        }
    }
    return true;
}

public boolean isValid(char[][] board, int row, int col) {
    for (int i = 0; i < board.length; i++) {
        if (i == row) continue;
        if (board[i][col] == board[row][col]) return false;
    }
    for (int j = 0; j < board[0].length; j++) {
        if (j == col) continue;
        if (board[row][j] == board[row][col]) return false;
    }
    for (int i = (row / 3) * 3; i < (row / 3 + 1) * 3; i++) {
        for (int j = (col / 3) * 3; j < (col / 3 + 1) * 3; j++) {
            if (i == row && j == col) continue;
            if (board[i][j] == board[row][col]) return false;
        }
    }
    return true;
}

如何实现检查数独在 Java 中是否有效？

How to implement check if Sudoku is valid in Java?

java

algorithm

validation

sudoku

hashset