如何生成-complete-数独板？算法错误 [英] How to Generate a -complete- sudoku board? algorithm error
问题描述
我想生成一个完整的（即，洋溢着数每个单元）数独样板。这对于有无关，与数独游戏别的东西，所以我没兴趣达到了用白色方块就能解决的，或任何有做数独游戏数独。不知道你知道我的意思。
I'm trying to generate a complete (ie, each cell filled with a number) Sudoku-like board. It's for something else that has nothing to do with sudokus, so I am not interested in reaching a sudoku with white squares that can be solved, or anything that has to do with sudokus. Don't know if you know what I mean.
我在Java中做到了这一点：
I've done this in 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;
}
}
此方法从这块code名为：
This method is called from this piece of code:
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);
}
}
但它并不容易，因为它看起来！当算法已生成的板一个像这样的一个部分，并且所述环是上粗体细胞上：
But it is not as easy as it seemed! When the algorithm has generated a part of the board like this one, and the loop is on the cell on bold:
|||164527389|||
|||983416257|||
|||257938416|||
|||719352648|||
|||3256791**0**0|||
|||000000000|||
|||000000000|||
|||000000000|||
|||000000000|||
有没有编号，以把在这个小区，因为所有根据数独的规则的数量已经在列，行或正方形！
There are no numbers to put in this cell, because all the numbers according to the rules of sudoku are already on the column, row or square!
这是一场噩梦我。有什么办法来这工作吗？如果不是这样，我想我必须重做一切，如果我是做一个数独游戏。
It is a nightmare for me. Is there any way to this to work? If not, i guess I have to redo everything as if I were making a Sudoku game.
在此先感谢。
推荐答案
的问题是，它是不可能的，在大多数情况下，使用随机数生成一个完整的板，已使用回溯在情况下，当它不possibe到Fi技术的下一个单元格。 我曾经写了一个数独游戏，所以这里的一块code，其产生填充板。
The problem is that it is not possible to generate a complete board using random numbers in most cases, you have to use backtracking in cases when it is not possibe to fi the next cell. I have once written a sudoku game, so here's the piece of code that generates filled board.
这是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类（这是非常方便的将所有的数据在短短的一个对象）。
Here's the Field class (it's really handy to keep all data in just one object).
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;
}
}
最后，填补了游戏板的功能
And finally the function that fills the game board
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);
}
}
}
的一点是，你在移动之前保存你已经尝试过的每一个细胞的数量。如果你有到穷途末路，你只需要尝试另一个号码为previous细胞。如果没有这样的可能，擦除单元，并加强一个细胞回。迟早你会完成它。 （这actuay所花费的时间很少量）。
The point is that you save the numbers you've already tried for each cell before moving on. If you have to the dead end, you simply need to try another number for the previous cell. If none are possible, erase that cell and step one cell back. Sooner or later you will get it done. (It actuay takes tiny amount of time).
这篇关于如何生成-complete-数独板？算法错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
