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

问题在于，在大多数情况下无法使用随机数生成完整的电路板，如果无法找到下一个单元，则必须使用回溯。我曾经写过一个数独游戏，所以这是生成填充板的代码。

这是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);        }    }}

关键是在继续 *** 作之前，您要保存已经为每个单元格尝试过的数字。如果要走到尽头，您只需要为上一个单元格尝试另一个数字即可。如果不可能，请擦除该单元格并向后退一个单元格。迟早您会完成它。（精算只需要很少的时间）。