logo标签列表

如何生成一个“完整”的数独板？算法错误。

javaalgorithmsudoku
8
我正在尝试生成一个完整的（即每个单元格都填有数字的）类数独棋盘。这是为了其他事情而不是数独，所以我不感兴趣达成一个可以解决的白色方块数独或任何与数独有关的东西。不知道你是否明白我的意思。
我已经用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|||

这个单元格中没有可填写的数字，因为根据数独规则，该列、行或宫已经有所有数字了！

这对我来说是一场噩梦。有没有办法让它工作？如果没有，我想我必须重新制作数独游戏。

你可能可以使用自己的代码：（1）修改调用sudokuNumberSelector的例程，使其在棋盘未填满且下一个单元格没有有效选择时终止。(2)添加另一个例程，递归调用您的数独制作例程以针对每个单元格（已完成的数字）生成多个棋盘，但仅返回完成的棋盘。 - גלעד ברקן
6个回答
8
问题在于，大多数情况下无法使用随机数生成完整的数独棋盘，在无法填充下一个单元格时必须使用回溯。 我曾经编写过一个数独游戏，这里是生成填充棋盘的代码片段。
这是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);
        }
    }
}

重点是在移动到下一个单元格之前，您需要保存已经尝试过的每个单元格的数字。如果您到达了死路，那么您只需要为上一个单元格尝试另一个数字。如果没有可能的数字，则擦除该单元格并向后移动一个单元格。迟早您将完成它。(实际上只需要很少的时间)。

谢谢，我也是这么认为的。我对算法的经验不足，无法确定是否可能。 - Adelaiglesia
一段时间前我也遇到了同样的问题。 - Danylo Fitel
3

从解决了的数独开始：

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
这种技术将为您提供广泛的合法棋盘，但它无法涵盖所有可能的合法棋盘（因为它们中的一些以不同的方式连接）。总的来说，它很可能能够满足大多数需求。 - Charles Ofria
2

你的问题在于使用了字符串。尝试使用整数编写递归算法。这个算法对于任何大小的数独都有用。虽然在每次调用中选择随机数字确实有效，但会花费更长时间。如果您选择一组随机数字来遍历，如果下一个单元格不起作用，则不会再次使用相同的数字。这个算法每次都会创建一个唯一的谜题。

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;
    } 
}
1
你至少有几种方法可以实现这个，但通常你需要使用递归/回溯。最好还有一个求解器，用于检查部分填充的谜题是否有解（并且唯一解-作为停止标准-如果你想要真正的数独）。
在执行回溯/递归时，你需要：
- 随机选择可用的空单元格（你可以通过测量给定单元格上仍然空闲的数字来优化此步骤，然后进行排序） - 随机选择该单元格中仍可用的数字 - 填写单元格并检查解决方案是否存在，如果是，则继续前进，如果不是，则执行回退步骤。
起始点： - 从完全空白的谜题开始 - 从部分填充的谜题开始 - 从已解决的谜题开始（有很多变换不改变解决方案的存在性，但使谜题不同-例如：反射、旋转、转置、段交换、列/行在段内交换、排列等）
我最近使用了Janet Sudoku库，它提供了求解器、生成器和谜题转换方法。 Janet Sudoku website 请参考GitHub上提供的以下源代码：

数独求解器

数独生成器

数独变换

库的使用非常简单，例如：

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

最好的问候，
1

你需要实现一个回溯算法。

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

你可能需要使用递归函数，以便进行回溯。

0
只需生成1到9之间的一些随机数，然后查看它是否适合给定的单元格[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++;
        }
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接