0
public class Solver {
public LinkedList<Sudoku> sudokus = new LinkedList<>();
public Solver() {
Sudoku current = null;
int count = 1;
try (BufferedReader br = new BufferedReader(new FileReader(new File("p096_sudoku.txt")))) {
for (String line; (line = br.readLine()) != null;) {
if (line.contains("Grid")) {
current = new Sudoku(count);
sudokus.add(current);
count++;
} else {
current.addLine(line);
}
}
} catch (IOException ex) {
Logger.getLogger(Solver.class.getName()).log(Level.SEVERE, null, ex);
}
}
/*
For debugging purposes
*/
public void SolveFirstPrint() {
int count = 0;
for (Sudoku s : sudokus) {
if (count == 0) {
s.lines = solve(s.lines);
if (s.lines != null) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(s.lines[i][j] + " ");
}
System.out.print("\n");
}
}
System.out.println();
}
count++;
}
}
public void SolveFirst() {
int count = 0;
for (Sudoku s : sudokus) {
if (count == 0) {
s.lines = solve(s.lines);
}
count++;
}
}
public void SolveAllPrint() {
for (Sudoku s : sudokus) {
s.lines = solve(s.lines);
}
for (Sudoku s : sudokus) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(s.lines[i][j] + " ");
}
System.out.print("\n");
}
System.out.println();
}
}
public void SolveAll() {
for (Sudoku s : sudokus) {
s.lines = solve(s.lines);
}
}
public static boolean check(int[] numbers) {
int[][] key = new int[2][numbers.length];
key[0] = numbers;
for (int i = 0; i < numbers.length; i++) {
key[1][i] = 0;
}
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] > 0) {
key[1][numbers[i] - 1]++;
}
}
boolean keycheck = false;
for (int i = 0; i < numbers.length; i++) {
if (key[1][i] > 1) {
keycheck = true;
break;
}
}
if (keycheck == true) {
return false;
} else {
return true;
}
}
public static boolean checkY(int[][] numbers, int y) {
int[] key = new int[numbers[y].length];
key = numbers[y];
return check(key);
}
public static boolean checkX(int[][] numbers, int x) {
int[] key = new int[numbers.length];
for (int i = 0; i < key.length; i++) {
key[i] = numbers[i][x];
}
return check(key);
}
public static boolean checkAll(int[][] numbers) {
//Check Y lijnen
for (int i = 0; i < numbers.length; i++) {
if (!checkY(numbers, i)) {
return false;
}
}
//Check X lijnen
for (int i = 0; i < numbers.length; i++) {
if (!checkX(numbers, i)) {
return false;
}
}
// Check of alle boxes nog kloppen
if (!checkSquare(numbers, 0, 2, 0, 2)) {
return false;
}
if (!checkSquare(numbers, 0, 2, 3, 5)) {
return false;
}
if (!checkSquare(numbers, 0, 2, 6, 8)) {
return false;
}
if (!checkSquare(numbers, 3, 5, 0, 2)) {
return false;
}
if (!checkSquare(numbers, 3, 5, 3, 5)) {
return false;
}
if (!checkSquare(numbers, 3, 5, 6, 8)) {
return false;
}
if (!checkSquare(numbers, 6, 8, 0, 2)) {
return false;
}
if (!checkSquare(numbers, 6, 8, 3, 5)) {
return false;
}
if (!checkSquare(numbers, 6, 8, 6, 8)) {
return false;
}
return true;
}
public static boolean checkSquare(int[][] numbers, int minX, int maxX, int minY, int maxY) {
Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
for (int j = minY; j < maxY +1; j++) {
for (int i = minX; i < maxX +1; i++) {
if (numbers[j][i] != 0) {
// Als de hashmap al dezelfde key heeft in deze box
if (myMap.containsKey(numbers[j][i])) {
// Kan het huidige nummer niet ingevoerd worden, dus false.
return false;
} else {
// Voeg nummer toe
myMap.put(numbers[j][i], 1);
}
}
}
}
return true;
}
public static boolean isValid(int[][] numbers) {
// Controlleer of er wel een grid van 9x9 is
if (numbers.length != 9 || numbers[0].length != 9) {
return false;
}
return (checkAll(numbers));
}
public static int[][] solve(int[][] numbers) {
int[] freeslot = getNext(numbers);
int f1 = freeslot[0];
int f2 = freeslot[1];
if (f1 == -1) {
return numbers;
}
numbers = recurseSolve(f1, f2, numbers);
return numbers;
}
public static int[][] recurseSolve(int yNR, int xNR, int[][] numbers) {
int[][] solved;
int[][] copy = new int[numbers.length][numbers[0].length];
for (int y = 0; y < numbers.length; y++) {
for (int z = 0; z < numbers[0].length; z++) {
copy[y][z] = numbers[y][z];
}
}
// Als t valid is doorgaan met next solven.
for (int i = 1; i < 10; i++) {
copy[yNR][xNR] = i;
boolean valide = isValid(copy);
if (valide) {
solved = solve(copy);
if (solved != null) {
return solved;
}
}
}
return null;
}
public static int[] getNext(int[][] numbers) {
int[] slot = {-1, -1};
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (numbers[i][j] == 0) {
slot[0] = i;
slot[1] = j;
return slot;
}
}
}
return slot;
}
public int EulerSum() {
int total = 0;
for (Sudoku sudoku : sudokus) {
total += sudoku.TopLeftNrs();
}
return total;
}
}
こんにちは！Java Sudokuソルバーの入力を高速化するにはどうすればよいですか？
私は上記のスドクソルバーを作ったが、問題がある。
私は下の性能試験を行った。
@Test
public void speedTest(){
solver = new Solver();
long tStart = System.currentTimeMillis();
solver.SolveFirst();
long tEnd = System.currentTimeMillis();
long tDelta = tEnd - tStart;
double elapsedSeconds = tDelta/1000.0;
System.out.println("1 Sudoku: " +elapsedSeconds);
solver = new Solver();
long tStart2 = System.currentTimeMillis();
solver.SolveAll();
long tEnd2 = System.currentTimeMillis();
long tDelta2 = tEnd2 - tStart2;
double elapsedSeconds2 = tDelta2/1000.0;
System.out.println("50 Sudokus:"+elapsedSeconds2);
}
}
そして私は、これらの結果を得る：
テストスイート：InputTest
1数独：0.014秒
50数独、してみてください0：7.314秒
1スードクはとても速いですが、1より大きいと、私は線形のパフォーマンス結果ではありません。
Int [] []以外のものを使用する必要がありますか？
ありがとうございます。
多分あなたは最初のものと幸運を得ました。 –
私は@ScottHunterが正しいと思います。バックトラックを使用すると、評価される間違ったパスの数が潜在的にかなり大きくなる可能性があるため、時間が極端に変わる可能性があります。そして、ボードをいつもコピーすれば、時間がかかり、間違った動きを取り戻すことができます。 – maraca
私はそれを見て、スマートな思考をします。 –