java 如何生成一个完整的数独板？算法错误
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15690254/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to Generate a -complete- sudoku board? algorithm error
提问by Adelaiglesia
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.
我正在尝试生成一个完整的（即，每个单元格都填充一个数字）类似数独的棋盘。这是为了与数独无关的其他事情，所以我对达到可以解决的白色方块的数独或与数独有关的任何事情都不感兴趣。不知道你是否明白我的意思。
I've done this in java:
我已经在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;
}
}
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.
这对我来说是一场噩梦。有没有办法做到这一点？如果没有，我想我必须像制作数独游戏一样重做所有事情。
Thanks in advance.
提前致谢。
采纳答案by Danylo Fitel
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.
问题是在大多数情况下不可能使用随机数生成完整的电路板，在无法找到下一个单元格的情况下，您必须使用回溯。我曾经写过一个数独游戏，所以这是生成填充板的一段代码。
This is the Cell class.
这是 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();
}
}
Here's the Field class (it's really handy to keep all data in just one object).
这是 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;
}
}
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);
}
}
}
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).
关键是您在继续之前保存了您已经为每个单元格尝试过的数字。如果您必须到死胡同，您只需要为前一个单元格尝试另一个数字。如果都不可能，请擦除该单元格并后退一个单元格。迟早你会完成它。（它实际上需要很少的时间）。
回答by Ebbe M. Pedersen
Start out with a solved Sudokolike this:
从这样解决的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
And then permutate it by switching columns and switching rows. If you only switch within the following groups ABC, DEF, GHI, the Sudoku is still solved.
然后通过切换列和切换行来排列它。如果只在ABC、DEF、GHI这几个组内切换，数独还是可以解决的。
A permutated version (switching columns):
置换版本（切换列）：
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
And after some more permutation (switching rows):
经过更多的排列（切换行）：
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
回答by Ranga
Your problem is you are using Strings. Try a recursive algorithm using integers. This algorithm will be useful for a sudoku of any size. While choosing random numbers within each call does work, it'll take much longer. If you choose a set of random numbers to go through if the next cell doesnt work, then you will not use the same number again. This algorithm will create a unique puzzle every time.
您的问题是您使用的是字符串。尝试使用整数的递归算法。该算法对于任何大小的数独都非常有用。虽然在每次调用中选择随机数确实有效，但需要更长的时间。如果您选择一组随机数在下一个单元格不起作用时通过，那么您将不会再次使用相同的数字。该算法每次都会创建一个独特的谜题。
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;
}
}
回答by Leroy Kegan
You have at least few ways to do that, but usually you will need recurrence / backtracking. It would be great to have the solver also, just to check if partly filled puzzle has solution (and the unique one - for stoping criteria - if you want the real sudoku).
您至少有几种方法可以做到这一点，但通常您需要重复/回溯。拥有求解器也很棒，只是为了检查部分填充的拼图是否有解决方案（以及唯一的 - 用于停止标准 - 如果您想要真正的数独）。
While performing backtracking / recurrence you will need:
在执行回溯/重复时，您将需要：
to randomly select available empty cell (you can optimize this step by measuring digidts still free on the given cell, and then sorting)
to randomly select still available digit in that cell
you fill the cell and check if the solution exists, if yes - go further, if not - perform the step back.
随机选择可用的空单元格（您可以通过测量给定单元格上仍然空闲的数字来优化此步骤，然后进行排序）
随机选择该单元格中仍然可用的数字
您填写单元格并检查解决方案是否存在，如果是 - 继续，如果不是 - 执行后退。
Starting points: - starting with completely empty puzzle - starting with partially filled puzzle - starting with solved puzzle (there are a lot of transformations not changing the solution existence, but making the puzzle different - i.e.: reflection, rotation, transposition, segment swapping, columns / rows swapping within segments, permutation, etc.)
起点： - 从完全空的谜题开始 - 从部分填充的谜题开始 - 从已解决的谜题开始（有很多变换并没有改变解的存在，而是让谜题变得不同 - 即：反射、旋转、转置、段交换，列/行在段、排列等内交换）
I was recently using the Janet Sudoku library which provides solver, generator and puzzle transformation methods.
我最近在使用 Janet Sudoku 库，它提供了求解器、生成器和拼图转换方法。
Please refer to the below source codes available on the GitHub
请参考 GitHub 上提供的以下源代码
Library usage is pretty simple, ie:
库的使用非常简单，即：
SudokuGenerator g = new SudokuGenerator();
int[][] puzzle = g.generate();
SudokuSolver s = new SudokuSolver(puzzle);
s.solve();
int[][] solvedPuzzle = s.getSolvedBoard();
Best regards,
最好的祝福，
回答by Gilbert Le Blanc
You're going to have to implement a backtrackingalgorithm.
您将不得不实施回溯算法。
- For each of the 81 locations, generate the set 1 through 9.
- Repeat until solved
- Solve one location. Pick one number from the set.
- Remove that number from all the sets in the same row, column, and square.
- If a conflict arises, backtrack to a known good position, and solve a different location.
- 对于 81 个位置中的每一个，生成集合 1 到 9。
- 重复直到解决
- 解决一处。从集合中选择一个号码。
- 从同一行、列和方格中的所有集合中删除该数字。
- 如果出现冲突，则回溯到已知的良好位置，并解决不同的位置。
You will probably have to use recursive functions so that you can backtrack.
您可能必须使用递归函数才能回溯。
回答by MissingNumber
Just generate some random number between 1 to 9 and see it it fits the given cell[i][j] it promises you a new set of numbers every time as every cell number is generated randomly based on the current system time .
只需生成 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++;
}
}
}
