java - 数独求解器未正确求解
问题描述
我创建了一个程序,它接受一个测试用例未完成的数独难题,并且应该使用多线程来快速解决它。我遇到了一个问题,它只工作 1/3 次,当它“工作”时,它返回一个违反规则的谜题。例如,同一列中的两个五。我想知道线程是否动作太快并且没有通信?什么是我可以改变的或我没有看到的问题?
这是我的 SudokuSolver 课程。它包含两个方法:cellChecker 和fillPuzzle。单元格检查器检查单个单元格并在填充时返回 false,如果单元格为空(包含 0)则返回 true。它还包含多线程的代码,我怀疑问题出在哪里。
fillPuzzle 会在需要时简单地创建谜题,并使用 cellChecker 正确解决数独谜题。
public boolean cellChecker(int puzzle[][], int row, int col, int number) {
//Set the cellCheck boolean to true for a default case
cellCheck = true;
//variables that give us the start of the row and column respectively
//If it doesn't get divided by 3 and then multiplied by 3, the threads
//get an out of bounds exception and gets real mad. found this math
//from stackoverflow.
int rowStart = (row / 3) * 3;
int colStart = (col / 3) * 3;
//The threads are created to do the 9x9 grid in 3x3 sections,
//so it can get done quicker and cut down the large task at hand.
//checks via col
Thread thread1 = new Thread(new Runnable() {
public void run() {
//for loop that checks the col
for (int i = 0; i < 9; i++) {
if (puzzle[row][i] == number) {
cellCheck = false;
}
}
}
});
thread1.start();
//another thread to take on it's 3x3 part via row
Thread thread2 = new Thread(new Runnable() {
public void run() {
//for loop that checks the row
for (int i = 0; i < 9; i++) {
if (puzzle[i][col] == number) {
cellCheck = false;
}
}
}
});
thread2.start();
//another thread to take on it's 3x3 part via cell by cell
Thread thread3 = new Thread(new Runnable() {
public void run() {
//for loop that checks the specific cell
for (int rowCell = rowStart; rowCell < rowStart + 3; rowCell++) {
for (int colCell = 0; colCell < colStart + 3; colCell++) {
if (puzzle[rowCell][colCell] == number) {
cellCheck = false;
}
}
}
}
});
thread3.start();
//returns the boolean whether the box is empty or not. If it is false,
//it is filled with the number it needs. if it's true, it still needs
//a number
return cellCheck;
}
public boolean fillPuzzle(int puzzle[][], int row, int col) {
if (row < 9) {
//if the 9x9 puzzle is not created and filled with 0's, create it
if (puzzle[row][col] != 0) {
if (col < 8) {
//returns created 9x9 puzzle
return fillPuzzle(puzzle, row, col + 1);
} else if (row < 8) {
//returns created 9x9 puzzle
return fillPuzzle(puzzle, row + 1, 0);
}
//already created, return true!
return true;
} else {
//if the puzzle is created, go through and check for the number
//up until or equal to 9 because sudoku goes from 1-9
//once it finds the number that belongs in the cell, it
//puts it in that cell
for (int i = 1; i <= 9; i++) {
if (cellChecker(puzzle, row, col, i)) {
puzzle[row][col] = i;
//If at the end of col, add a row to finish the table
if (col == 8) {
if (fillPuzzle(puzzle, row + 1, 0)) {
return true;
}
} else {
//add 1 to the col if it doesn't == 8 because
//that means there's not enough cols
if (fillPuzzle(puzzle, row, col + 1)) {
return true;
}
}
//all else fails, set it to 0 and we'll check it later
puzzle[row][col] = 0;
}
}
return false;
}
}
return true;
}
这是我的菜单类,其中出现了拼图测试用例
public class Menu {
private SudokuSolver solver = new SudokuSolver();
//This is a test case sudoku puzzle I found off the internet to use as
//an example
private int sudokuPuzzle[][] = {{8, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 3, 6, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 9, 0, 2, 0, 0},
{0, 5, 0, 0, 0, 7, 0, 0, 0},
{0, 0, 0, 0, 4, 5, 7, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 3, 0},
{0, 0, 1, 0, 0, 0, 0, 6, 8},
{0, 0, 8, 5, 0, 0, 0, 1, 0},
{0, 9, 0, 0, 0, 0, 4, 0, 0}};
public void start() {
//set to the method fillPuzzle. It tries to solve the
//sudoku puzzle and if it does, it is set to true. If it doesn't
//it says no thank you.
boolean filledPuzzle = solver.fillPuzzle(sudokuPuzzle, 0, 0);
//if it filled the puzzle, it prints it out.
if (filledPuzzle) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
System.out.print(sudokuPuzzle[row][col] + " ");
}
System.out.println();
}
//if it can't, it let's the person know.
} else {
System.out.println("Solution not found");
}
}
}
最后,这听起来可能很愚蠢,但我不能 100% 确定实现 Runnable 的工作原理,但它确实在我的 sudokusolver 类中给了我一个空的 run 方法,如果我删除它会生气。我想知道是否需要放一些东西才能使其正常有效地工作?
@Override
public void run() {
}
解决方案
推荐阅读
- bukkit - 有没有办法在 player.BedSpawnLocation 中存储偏航?
- javascript - 使用 JS 抓取 HTML 文本选择的 CSS
- java - 本地java程序无法连接到本地数据库
- c# - 没有引导程序的 Blazor 材料
- css - 样式表不再起作用,确实起作用了
- windows - 如何在批量扩展重命名时删除文件
- algorithm - 点数组中两点之间的最小欧几里得距离
- spring-boot - JHipster i18n 似乎坏了
- swift - 无法将“TaskElement”类型的值转换为预期的参数类型“EnvironmentObject”
' - github - 使组织中的私有存储库对一组人可见