如何生成-complete- sudoku板卡？算法错误

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

问题是，在大多数情况下，不可能使用随机数生成完整的电路板，在不可能对下一个单元进行fi的情况下，您必须使用回溯。我曾经写过一个数独游戏，下面是生成填充棋盘的代码。

这是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

使用如下所示的已解决的数独开始：

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中切换，仍然可以解决数独问题。

A置换版本(切换列)：

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;
    } 
}