java - 如何生成一个完整的数独板？算法错误

Question

我正在尝试生成一个完整的（即，每个单元格都填充一个数字）类似数独的板。这是为了与数独无关的其他事情，所以我对达到可以解决的白色方块的数独或与数独有关的任何事情不感兴趣。不知道你知不知道我的意思。

我在java中完成了这个：

private int sudokuNumberSelector(int x, int y, int[][] sudoku) {

    
    boolean valid = true;
    String validNumbers = new String();
    int[] aValidNumbers;
    int squarexstart = 0;
    int squareystart = 0;
    int b = 0;                          // For random numbers
    Random randnum = new Random();
    randnum.setSeed(new Date().getTime());
    
    // Check numbers one by one
    for(int n = 1; n < 10; n++) {
        
        valid = true;
        
        // Check column
        for(int i = 0; i < 9; i++) {
            if(sudoku[i][y] == n) {
                valid = false;
            }
        }
        
        // Check file
        for(int j = 0; j < 9; j++) {
            if(sudoku[x][j] == n) {
                valid = false;
            }
        }
        
        // Check square
        switch (x) {
        case 0: case 1: case 2: squarexstart = 0; break;
        case 3: case 4: case 5: squarexstart = 3; break;
        case 6: case 7: case 8: squarexstart = 6; break;
        }
        
        switch (y) {
        case 0: case 1: case 2: squareystart = 0; break;
        case 3: case 4: case 5: squareystart = 3; break;
        case 6: case 7: case 8: squareystart = 6; break;
        }
        
        for(int i = squarexstart; i < (squarexstart + 3); i++ ) {
            for(int j = squareystart; j < (squareystart + 3); j++ ) {
                if(sudoku[i][j] == n) {
                    valid = false;
                }
            }
        }
        
        // If the number is valid, add it to the String
        if(valid) {
            validNumbers += n;
        }
    }
    
    if(validNumbers.length() != 0) {
                
        // String to int[]
        aValidNumbers = fromPuzzleString(validNumbers);
        
        // By this random number, return the valid number in its position
        Log.d(TAG, "NUMBERS: " + validNumbers.length()); 
        
        // Select a random number from the int[]
        b = randnum.nextInt((aValidNumbers.length));
        
            
        return aValidNumbers[b];

    } else {
        return 0;
    }
}

从这段代码调用此方法：

int[][] sudoku = new int[9][9];

for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                sudoku[i][j] = sudokuNumberSelector(i, j, sudoku);
            }
        }

但这并不像看起来那么容易！当算法生成了像这样的板的一部分，并且循环在粗体单元格上时：

|||164527389|||
|||983416257|||
|||257938416|||
|||719352648|||
|||3256791**0**0|||
|||000000000|||
|||000000000|||
|||000000000|||
|||000000000|||

这个单元格中没有数字可以输入，因为所有符合数独规则的数字都已经在列、行或方格上！

这对我来说是一场噩梦。有什么办法可以做到这一点吗？如果没有，我想我必须像在做数独游戏一样重做所有事情。

Answer 1

问题是在大多数情况下不可能使用随机数生成完整的棋盘，在无法匹配下一个单元格的情况下，您必须使用回溯。我曾经写过一个数独游戏，所以这是生成填充板的一段代码。

这是 Cell 类。

 public class SudokuCell implements Serializable {

    private int value;
    private boolean filled;
    private HashSet<Integer> tried;

    public SudokuCell() {
        filled = false;
        tried = new HashSet();
    }

    public boolean isFilled() {
        return filled;
    }

    public int get() {
        return value;
    }

    public void set(final int number) {
        filled = true;
        value = number;
        tried.add(number);
    }

    public void clear() {
        value = 0;
        filled = false;
    }

    public void reset() {
        clear();
        tried.clear();
    }

    public void show() {
        filled = true;
    }

    public void hide() {
        filled = false;
    }

    public boolean isTried(final int number) {
        return tried.contains(number);
    }

    public void tryNumber(final int number) {
        tried.add(number);
    }

    public int numberOfTried() {
        return tried.size();
    }
 }

这是 Field 类（将所有数据保存在一个对象中非常方便）。

 public class SudokuField implements Serializable {

    private final int blockSize;
    private final int fieldSize;
    private SudokuCell[][] field;

    public SudokuField(final int blocks) {
        blockSize = blocks;
        fieldSize = blockSize * blockSize;
        field = new SudokuCell[fieldSize][fieldSize];
        for (int i = 0; i < fieldSize; ++i) {
            for (int j = 0; j < fieldSize; ++j) {
                field[i][j] = new SudokuCell();
            }
        }
    }

    public int blockSize() {
        return blockSize;
    }

    public int fieldSize() {
        return fieldSize;
    }

    public int variantsPerCell() {
        return fieldSize;
    }

    public int numberOfCells() {
        return fieldSize * fieldSize;
    }

    public void clear(final int row, final int column) {
        field[row - 1][column - 1].clear();
    }

    public void clearAllCells() {
        for (int i = 0; i < fieldSize; ++i) {
            for (int j = 0; j < fieldSize; ++j) {
                field[i][j].clear();
            }
        }
    }

    public void reset(final int row, final int column) {
        field[row - 1][column - 1].reset();
    }

    public void resetAllCells() {
        for (int i = 0; i < fieldSize; ++i) {
            for (int j = 0; j < fieldSize; ++j) {
                field[i][j].reset();
            }
        }
    }

    public boolean isFilled(final int row, final int column) {
        return field[row - 1][column - 1].isFilled();
    }

    public boolean allCellsFilled() {
        for (int i = 0; i < fieldSize; ++i) {
            for (int j = 0; j < fieldSize; ++j) {
                if (!field[i][j].isFilled()) {
                    return false;
                }
            }
        }
        return true;
    }

    public int numberOfFilledCells() {
        int filled = 0;
        for (int i = 1; i <= fieldSize; ++i) {
            for (int j = 1; j <= fieldSize; ++j) {
                if (isFilled(i, j)) {
                    ++filled;
                }
            }
        }
        return filled;
    }

    public int numberOfHiddenCells() {
        return numberOfCells() - numberOfFilledCells();
    }

    public int get(final int row, final int column) {
        return field[row - 1][column - 1].get();
    }

    public void set(final int number, final int row, final int column) {
        field[row - 1][column - 1].set(number);
    }

    public void hide(final int row, final int column) {
        field[row - 1][column - 1].hide();
    }

    public void show(final int row, final int column) {
        field[row - 1][column - 1].show();
    }

    public void tryNumber(final int number, final int row, final int column) {
        field[row - 1][column - 1].tryNumber(number);
    }

    public boolean numberHasBeenTried(final int number, final int row, final int column) {
        return field[row - 1][column - 1].isTried(number);
    }

    public int numberOfTriedNumbers(final int row, final int column) {
        return field[row - 1][column - 1].numberOfTried();
    }

    public boolean checkNumberBox(final int number, final int row, final int column) {
        int r = row, c = column;
        if (r % blockSize == 0) {
            r -= blockSize - 1;
        } else {
            r = (r / blockSize) * blockSize + 1;
        }
        if (c % blockSize == 0) {
            c -= blockSize - 1;
        } else {
            c = (c / blockSize) * blockSize + 1;
        }
        for (int i = r; i < r + blockSize; ++i) {
            for (int j = c; j < c + blockSize; ++j) {
                if (field[i - 1][j - 1].isFilled() && (field[i - 1][j - 1].get() == number)) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean checkNumberRow(final int number, final int row) {
        for (int i = 0; i < fieldSize; ++i) {
            if (field[row - 1][i].isFilled() && field[row - 1][i].get() == number) {
                return false;
            }
        }
        return true;
    }

    public boolean checkNumberColumn(final int number, final int column) {
        for (int i = 0; i < fieldSize; ++i) {
            if (field[i][column - 1].isFilled() && field[i][column - 1].get() == number) {
                return false;
            }
        }
        return true;
    }

    public boolean checkNumberField(final int number, final int row, final int column) {
        return (checkNumberBox(number, row, column)
                && checkNumberRow(number, row)
                && checkNumberColumn(number, column));
    }

    public int numberOfPossibleVariants(final int row, final int column) {
        int result = 0;
        for (int i = 1; i <= fieldSize; ++i) {
            if (checkNumberField(i, row, column)) {
                ++result;
            }
        }
        return result;
    }

    public boolean isCorrect() {
        for (int i = 0; i < fieldSize; ++i) {
            for (int j = 0; j < fieldSize; ++j) {
                if (field[i][j].isFilled()) {
                    int value = field[i][j].get();
                    field[i][j].hide();
                    boolean correct = checkNumberField(value, i + 1, j + 1);
                    field[i][j].show();
                    if (!correct) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public Index nextCell(final int row, final int column) {
        int r = row, c = column;
        if (c < fieldSize) {
            ++c;
        } else {
            c = 1;
            ++r;
        }
        return new Index(r, c);
    }

    public Index cellWithMinVariants() {
        int r = 1, c = 1, min = 9;
        for (int i = 1; i <= fieldSize; ++i) {
            for (int j = 1; j <= fieldSize; ++j) {
                if (!field[i - 1][j - 1].isFilled()) {
                    if (numberOfPossibleVariants(i, j) < min) {
                        min = numberOfPossibleVariants(i, j);
                        r = i;
                        c = j;
                    }
                }
            }
        }
        return new Index(r, c);
    }

    public int getRandomIndex() {
        return (int) (Math.random() * 10) % fieldSize + 1;
    }
}

最后是填充游戏板的功能

private void generateFullField(final int row, final int column) {
    if (!field.isFilled(field.fieldSize(), field.fieldSize())) {
        while (field.numberOfTriedNumbers(row, column) < field.variantsPerCell()) {
            int candidate = 0;
            do {
                candidate = field.getRandomIndex();
            } while (field.numberHasBeenTried(candidate, row, column));
            if (field.checkNumberField(candidate, row, column)) {
                field.set(candidate, row, column);
                Index nextCell = field.nextCell(row, column);
                if (nextCell.i <= field.fieldSize()
                        && nextCell.j <= field.fieldSize()) {
                    generateFullField(nextCell.i, nextCell.j);
                }
            } else {
                field.tryNumber(candidate, row, column);
            }
        }
        if (!field.isFilled(field.fieldSize(), field.fieldSize())) {
            field.reset(row, column);
        }
    }
}

关键是您在继续之前保存您已经为每个单元格尝试过的数字。如果你不得不走到死胡同，你只需要为前一个单元格尝试另一个数字。如果不可能，请擦除该单元格并退回一个单元格。迟早你会完成的。（它实际上需要很少的时间）。

Answer 2

从解决的Sudoko开始，如下所示：

ABC DEF GHI
329 657 841 A
745 831 296 B
618 249 375 C

193 468 527 D
276 195 483 E
854 372 619 F

432 716 958 G 
587 923 164 H 
961 584 732 I

然后通过切换列和切换行来排列它。如果您只在以下组 ABC、DEF、GHI 内切换，数独仍然可以解决。

置换版本（切换列）：

BCA DFE IGH   
293 675 184 A 
457 813 629 B 
186 294 537 C 

931 486 752 D 
762 159 348 E 
548 327 961 F 

324 761 895 G 
875 932 416 H 
619 548 273 I 

经过更多排列（切换行）：

BCA DFE IGH   
293 675 184 A 
186 294 537 C 
457 813 629 B 

931 486 752 D 
548 327 961 F 
762 159 348 E 

875 932 416 H 
619 548 273 I 
324 761 895 G 

Answer 3

您的问题是您使用的是字符串。尝试使用整数的递归算法。该算法对于任何大小的数独都非常有用。虽然在每次通话中选择随机数确实有效，但需要更长的时间。如果在下一个单元格不起作用的情况下选择一组随机数进行遍历，那么您将不会再次使用相同的数字。该算法每次都会创建一个独特的谜题。

public class Sudoku {
    //box size, and game SIZE ==> e.g. size = 3, SIZE = 9
    //game will be the game
    private int size, SIZE;
    private int[][] game;

    public Sudoku(int _size) {
        size = _size;
        SIZE = size*size;
        game = generateGame();
    }

    //This will return the game
    private int[][] generateGame() {
        //Set everything to -1 so that it cannot be a value
        int[][] g = new int[SIZE][SIZE];
        for(int i = 0; i < SIZE; i++)
            for(int j = 0; j < SIZE; j++)
                g[i][j] = -1;

        if(createGame(0, 0, g))
            return g;
        return null;
    }

    //Create the game
    private boolean createGame(int x, int y, int[][] g) {
        //An array of integers
        Rand r = new Rand(SIZE);

        //for every random num in r
        for(int NUM = 0; NUM < size; NUM++) {
            int num = r.get(NUM);

            //if num is valid
            if(isValid(x, y, g, num)) {
                //next cell coordinates
                int nx = (x+1)%SIZE, ny = y;
                if(nx == 0) ny++;

                //set this cell to num
                g[x][y] = num;

                //if the next cell is valid return true
                if(createGame(nx, ny, g)) return true;

                //otherwise return false
                g[x][y] = -1;
                return false;
            }
        }
        return false;
    }

    private boolean isValid(int x, int y, int[][] g, int num) {
        //Rows&&Cols
        for(int i = 0; i < SIZE; i++)
            if(g[i][y] == num || g[x][i] == num) return false;
        //Box
        int bx = x - x%size;, by = y - y%size;
        for(int i = bx; i < bx + size; i++) {
            for(int j = by; j < by + size; j++) {
                if(g[i][j] == num)return false;
            }
        }
        return true;
    }
}

public class Rand {
    private int rSize;
    private int[] r; 
    public Rand(int _size) {
        rSize = _size;
        r = new int[size];
        for(int i = 0; i < rSize; r++)r[i] = i;
        for(int i = 0; i < rSize*5; r++) {
            int a = (int)(Math.random()*rSize);
            int b = (int)(Math.random()*rSize);
            int n = r[a];
            r[a] = r[b];
            r[b] = n;
    }
    public void get(int i) {
        if(i >= 0 && i < rSize) return r[i]; return -1;
    } 
}

Answer 4

你将不得不实现一个回溯算法。

• 对于 81 个位置中的每一个，生成集合 1 到 9。
• 重复直到解决
  • 解决一个位置。从集合中选择一个数字。
  • 从同一行、列和正方形中的所有集合中删除该数字。
  • 如果发生冲突，则回溯到已知的良好位置，并解决不同的位置。

您可能必须使用递归函数才能回溯。

Answer 5

您至少有几种方法可以做到这一点，但通常您需要重复/回溯。如果您想要真正的数独，那么拥有求解器也会很棒，只需检查部分填充的拼图是否有解决方案（以及唯一的解决方案 - 用于停止标准 - 如果您想要真正的数独）。

在执行回溯/重复时，您将需要：

• 随机选择可用的空单元格（您可以通过测量给定单元格上仍然空闲的数字，然后排序来优化此步骤）

• 随机选择该单元格中仍然可用的数字

• 您填充单元格并检查解决方案是否存在，如果是 - 继续前进，如果不存在 - 执行后退一步。

起点： - 从完全空的拼图开始 - 从部分填充的拼图开始 - 从已解决的拼图开始（有很多转换不会改变解决方案的存在，但会使拼图不同 - 即：反射，旋转，转置，段交换，列/行在段内交换、排列等）

我最近在使用 Janet Sudoku 库，它提供求解器、生成器和拼图转换方法。

珍妮特数独网站

请参考 GitHub 上提供的以下源代码

数独求解器

数独发生器

数独转换

库的使用非常简单，即：

SudokuGenerator g = new SudokuGenerator();
int[][] puzzle = g.generate();
SudokuSolver s = new SudokuSolver(puzzle);
s.solve();
int[][] solvedPuzzle = s.getSolvedBoard();

最好的祝福，

Answer 6

只需在 1 到 9 之间生成一些随机数，然后查看它是否适合给定的 cell[i][j] 它每次都会向您保证一组新的数字，因为每个单元格编号都是根据当前系统时间随机生成的。

public int sudokuNumberSelector(int i, int j, int[][] sudoku) {
    while (true) {
        int temp = (int) ((System.currentTimeMillis()) % 9) + 1;//Just getting some random number
        while (temp < 10) {
        boolean setRow = false, setColomn = false, setBlock = false;
            for (int a = 0; a < 9; a++) {
                if (sudoku[a][j] == temp) {
                    setRow = true;
                    break;
                }
            }

            for (int a = 0; a < 9; a++) {
                if (sudoku[i][a] == temp) {
                    setColomn = true;
                    break;
                }
            }
            for (int a = i - (i % 3); a < i - (i % 3)+ 3; a++) {
                for (int b = j - (j % 3); b < j - (j % 3)+3; b++) {
                    if (sudoku[a][b] == temp) {
                        setBlock = true;
                        a = 3;
                        b = 3;
                    }
                }
            }
            if(setRow | setColomn | setBlock == false){
                return temp;
            }
            temp++;
        }
    }
}