Witajcie!
Chciałem sobie napisać własny sudoku solver.
I tu na początku ważna uwaga - nie chcę korzystać z gotowych rozwiązań. Nie zrozumcie mnie źle, po prostu chciałbym trochę podszkolić z wprowadzania algorytmów w życie.
Korzystam z Wikipediowego algorytmu backtrack
Initialize 2D array with 81 empty grids (nx = 9, ny = 9)
Fill in some empty grid with the known values
Make an original copy of the array
Start from top left grid (nx = 0, ny = 0), check if grid is empty
if (grid is empty) {
assign the empty grid with values (i)
if (no numbers exists in same rows & same columns same as (i) & 3x3 square (i) is currently in)
fill in the number
if (numbers exists in same rows | same columns same as (i) | 3x3 square (i) is currently in)
discard (i) and repick other values (i++)
}
else {
while (nx < 9) {
Proceed to next row grid(nx++, ny)
if (nx equals 9) {
reset nx = 1
proceed to next column grid(nx,ny++)
if (ny equals 9) {
print solution
}
}
}
}
Pisząc kod staram się zrozumieć jak działa owy algorytm. Oto kod mojej klasy:
package com.burdzi0.solver.sudoku;
public class Solve {
int sudoku[][] = new int[9][9];
int current[][] = sudoku;
// Example for debugging
void fill() {
sudoku[0][0] = 5;
sudoku[0][1] = 3;
sudoku[0][4] = 7;
sudoku[1][0] = 6;
sudoku[1][3] = 1;
sudoku[1][4] = 9;
sudoku[1][5] = 5;
sudoku[2][1] = 9;
sudoku[2][2] = 8;
sudoku[2][7] = 6;
sudoku[2][7] = 6;
sudoku[3][0] = 8;
sudoku[3][4] = 6;
sudoku[3][8] = 3;
sudoku[4][0] = 4;
sudoku[4][3] = 8;
sudoku[4][5] = 3;
sudoku[4][8] = 1;
sudoku[5][0] = 7;
sudoku[5][4] = 2;
sudoku[5][8] = 6;
sudoku[6][1] = 6;
sudoku[6][6] = 2;
sudoku[6][7] = 8;
sudoku[7][3] = 4;
sudoku[7][4] = 1;
sudoku[7][5] = 9;
sudoku[7][8] = 5;
sudoku[8][4] = 8;
sudoku[8][7] = 7;
sudoku[8][8] = 9;
}
// Checks if the number is already used in the given row
boolean checkIfNumberIsInRow(int number, int rowIndex) {
for (int i = 0; i < 9; i++) {
if (current[rowIndex][i] == number) return true;
}
return false;
}
// Checks if the number is already used in the given column
boolean checkIfNumberIsInColumn(int number, int j) {
for (int i = 0; i < 9; i++) {
if (current[i][j] == number) return true;
}
return false;
}
// Defines the square that is needed to be searched in
boolean checkSquare(int number, int rowIndex, int columnIndex) {
int x,y;
if (rowIndex < 2) {
x = 0;
} else if (rowIndex < 5) {
x = 1;
} else {
x = 2;
}
if (columnIndex < 2) {
y = 0;
} else if (columnIndex < 5) {
y = 1;
} else {
y = 2;
}
for (byte i = 0; i < 3; i++) {
for (byte j = 0; j < 3; j++) {
if (current[3*x + i][3*y + j] == number) return true;
}
}
return false;
}
void printTable() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(sudoku[i][j] + " ");
}
System.out.println();
}
}
void mainSearch(int row, int column, int number) {
if (current[row][column] == 0) {
if (!checkIfNumberIsInRow(number, row) && !checkIfNumberIsInColumn(number, column) && !checkSquare(number, row, column)) {
current[row][column] = number;
} else {
mainSearch(row, column, number + 1);
}
} else {
while (row < 9) {
mainSearch(row, column, number);
if (row == 8) {
row = 0;
mainSearch(row, column++, number);
if (column == 8) {
printTable();
}
}
}
}
}
}
Widziałem już ten temat i wiele linków w necie, lecz uparłem się żeby zrobić to bez korzystania z gotowego kodu, więc zapytam na forum.
Gdzie w mojej metodzie mainSearch popełniłem błąd (stawiam, że stąd pojawia się StackOverflowError)?
Jak powinna wyglądać i dlaczego?
Moglibyście mnie nakierunkować, proszę?