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

我正在尝试生成一个完整的（即每个单元格中填充一个数字）类似Sudoku的板。 这是与sudokus无关的其他东西，所以我对达到可以解决的白色方块或与sudokus有关的任何东西都不感兴趣。 不知道你是否知道我的意思。

我在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

问题是在大多数情况下不可能使用随机数生成完整的电路板，在不可能使用下一个电池的情况下，必须使用回溯。 我曾经写过一个数独游戏，所以这里是生成填充板的代码片段。

这是Cell类。

  public class SudokuCell implements Serializable { private int value; private boolean filled; private HashSet 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; } } 

最后是填充游戏板的function

 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

从解决的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 

然后通过切换列和切换行来置换它。 如果你只在以下组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 

Answer 3

你的问题是你正在使用字符串。 尝试使用整数的递归算法。 该算法对任何大小的数独都有用。 虽然在每次通话中选择随机数确实有效，但这需要更长的时间。 如果您选择一组随机数，如果下一个单元格不起作用，那么您将不再使用相同的数字。 该算法每次都会创建一个独特的拼图。

 public class Sudoku { //box size, and game SIZE ==> eg 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; } } 

Answer 4

您将不得不实施回溯算法。

• 对于81个位置中的每个位置，生成1到9的集合。
• 重复直到解决
  • 解决一个位置。 从集合中选择一个数字。
  • 从同一行，列和方块中的所有集中删除该数字。
  • 如果发生冲突，则回溯到已知的好位置，并解决不同的位置。

您可能必须使用递归函数，以便可以回溯。

Answer 5

你至少有几种方法可以做到这一点，但通常你需要重复/回溯。 拥有解算器也很棒，只是为了检查部分填充的拼图是否有解决方案（以及唯一的 – 用于停止标准 – 如果你想要真正的数独）。

在执行回溯/重复时，您将需要：

• 随机选择可用的空单元格（您可以通过测量给定单元格上仍然空闲的数字格式，然后排序来优化此步骤）

• 随机选择该单元格中仍然可用的数字

• 你填写单元格并检查解决方案是否存在，如果是 – 进一步，如果没有 – 执行退一步。

起点： – 从完全空的拼图开始 – 从部分填充的拼图开始 – 从解决拼图开始（有很多变换不会改变解决方案的存在，但使拼图不同 – 即：reflection，旋转，换位，段交换，列/行在段内交换，排列等）

我最近使用的是Janet Sudoku库，它提供了求解器，生成器和拼图转换方法。

珍妮特数独网站

请参阅GitHub上提供的以下源代码

数独求解器

数独生成器

数独转换

库的使用非常简单，即：

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

最好的祝福，

Answer 6

只需生成一个介于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++; } } }