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);
}
}
을 그리고이 결과에서 얻을 :
있는 TestSuite :
1 스도쿠
InputTest : 0.014 초50 스도쿠를 시도 0 : 7.314 초
1 스도쿠가 너무 빠르지 만 1 이상은 선형 성능 결과가 아닐 수 있습니까?
Int [] [] 이외의 다른 것을 사용해야합니까?
미리 감사드립니다.
어쩌면 당신은 첫 번째 행운을 얻었을 것입니다. –
@ SkottHunter가 맞다고 생각합니다. 역 추적을 사용하면 평가 된 잘못된 경로의 수가 잠재적으로 상당히 커질 수 있기 때문에 시간이 크게 달라질 수 있습니다. 그리고 보드를 항상 복사하는 경우 시간이 오래 걸리며 잘못된 동작을 취소하는 것이 더 빠릅니다. – maraca
나는 그것을 똑똑한 사고로 들여다 보겠습니다. –