Lua - Backtracking - Sudoku
-
Hallo liebes Forum,
ich bin hier am verzweifeln. Ich moechte fuer WoW ein Add On schreiben welches Sudokus generiert, die man dann Ingame loesen kann. Aber das soll im Moment auch egal sein. Ich haenge an dem Algorithmus zum erstellen mit Backtracking. Ich habe folgenden Ansatz:- Ich erstelle ein Funktion die mit ein Array mit den Zahlen 1 - 9 an zufaelligen Positionen erstellt
- dieses Array uebergebe ich an die Funktion die mir das Sudoku rekursiv mit Backtracking erstellen soll. In dieser Funktion laufe ich das Array ab von 1 - 9 und pruefe fuer jede Zahl ob die Zahl ins SUdoku eingefuegt werden kann. Wenn es keine der 9 Zahlen ist ruft er sich selbst auf mit Koordinaten um 1 Verschoben, sollte eine passe ruft er sich auch selbst auf und Koordinaten um 1 nach vorn logischer weise verschoben auf.. der ganze queltext ist vllt etwas lang deswegen poste ich nur mal die funktion zum generieren und erklaer das allesfunction generate(x,y,rndarray) // wird mit koordinaten 1,1 initialisiert
for i=1,9 do
b = tb(x,y,rndarray[i]) // die 3 Funktionsaufrufe pruefen ob eine zahl
v = tv(x,y,rndarray[i]) // zulaessig ist fuer die stelle im Sudoku
h = th(x,y,rndarray[i])
if h and b and v then
sudoku[x][y] = rndarray[i]
ral() // funktion zum leeren des arrays
if x == 9 then // aufpassen das man nicht ueber den index rennt
generate(1,y+1,rndarray)
else
generate(x+1,y,rndarray)
end
end
end
ral()
if x == 9 and y == 9 then
return sudoku // dann isser fertig
else
if x == 1 then // um nicht ueber den index zu rennen
generate(9,y-1,rndarray)
else
generate(9,y-1,rndarray)
end
end
end.Mein Problem hierbei.... er Backtrackt nicht!!! ka warum 0,0 help plz
-
benutz mal bitte Code-Tags achja sieht ja aus wie Basic dann wirst wohl nicht drumrum kommen die Schlüsselwörter haendisch per [b]-Tag fett zu machen.
Die Krönung wäre noch gewesen Du hättest deinen Beitrag komplett in eine
Zeile geschrieben
-
Bei der Rekursion ist es wichtig vorher 2 Bedingungen zu definieren
Eine Bedingung wenn Rekursion beendet ist
Zweite Bedingung wenn wieder Rekursive aufgerufen werden muss
Die Dinger muessen Korrekt sein vor allem die Bedingung wenn Rekursion beendet ist sonst droht ein brüschtigter stack overflow
-
Exavier schrieb:
Backtracking erstellen soll. In dieser Funktion laufe ich das Array ab von 1 - 9 und pruefe fuer jede Zahl ob die Zahl ins SUdoku eingefuegt werden kann. Wenn es keine der 9 Zahlen ist ruft er sich selbst auf mit Koordinaten um 1 Verschoben, sollte eine passe ruft er sich auch selbst auf und Koordinaten um 1 nach vorn logischer weise verschoben auf.. der ganze queltext ist vllt etwas lang deswegen poste ich nur mal die funktion zum generieren und erklaer das alles
Ich tippe auf Stackoverflow oder Indexoverflow
Du solltest es so machen das du bei der einzelnen Zahl guckst ob sich die verwenden lässt ist das nicht der Fall rufst du nur auf diesen einen Index
im Array ne neue Zufallsgenerierung auf
und dabei immer überprüfen vorher ob der letzte Index schon erreicht ist
-
solltest es mal schrittweise Debugen fuer eine kleine Matrix
dabei den Inhalt der Matrix beobachten und die Indexvariablen auch
-
Im übrigen wenn die Matrixdimension und Grösse wird ja nicht unbedingt
gross varieren 9x9 verwendest Du doch bestimmt fest oder?Dann wuerde ich Rekursion raushauen das kann man auch rein iterative
machen sind ja bloss 81 Elemente dann in der Matrix dafuer schon Rekursion ist mit Kanonen auf Spatzen. Zum anderen lässt sich die Sache dann auch besser
debugen.
-
Exavier schrieb:
Ich moechte fuer WoW ein Add On schreiben welches Sudokus generiert
Ich hätte nur passenden Code zum Lösen des Sudokus anzubieten.
import java.io.*; public class SudokuSolver { public static void main(String[] args) { if(args.length != 1) { System.out.println("Wrong number of parameters."); System.exit(1); } int[][] sudoku = null; try { sudoku = loadSudoku(args[0]); } catch(IOException e) { System.out.println(e); } if (sudoku == null) { System.out.println("Could not load Sudoku!"); System.exit(1); } System.out.println("Eingelesenes Sudoku:"); System.out.println(); printSudoku(sudoku); System.out.println(); long time = System.currentTimeMillis(); int[][] outSudoku = solveSudoku(sudoku); time = System.currentTimeMillis() - time; System.out.println("Gelöstes Sudoku:"); System.out.println(); if (sudoku == null) System.out.println("Sudoku konnte nicht gelöst werden!"); else printSudoku(outSudoku); System.out.println(); System.out.println("Benötigte Zeit in (ms):"); System.out.println(time); } public static int[][] loadSudoku(String filename) throws IOException { String[] lines = new String[9]; BufferedReader reader = new BufferedReader(new FileReader(filename)); for (int i = 0 ; i < 9 ; ++i) { if(reader.ready()) { lines[i] = reader.readLine(); if(lines[i].length() != 9) return null; } else return null; } int[][] sudoku = new int[9][9]; for(int y = 0 ; y < 9 ; ++y) { for (int x = 0 ; x < 9 ; ++x) { final char currentChar = lines[y].charAt(x); if ((currentChar <= '9') && (currentChar >= '1')) { sudoku[x][y] = 1 + (int)(currentChar - '1'); } } } return sudoku; } public static void printSudoku(int[][] sudoku) { for(int y = 0 ; y < 9 ; ++y) { if (y % 3 == 0) { System.out.println(" XXXXXXXXXXXXXXXXXXX"); } for (int x = 0 ; x < 9 ; ++x) { if (x % 3 == 0) System.out.print(" X "); if (sudoku[x][y] == 0) System.out.print("_"); else System.out.print(sudoku[x][y]); } System.out.println(" X"); } System.out.println(" XXXXXXXXXXXXXXXXXXX"); } public static int[][] solveSudoku(int[][] sudoku) { boolean[][][] possibleSudoku = new boolean[9][9][]; for (int x = 0 ; x < 9 ; ++x) { for(int y = 0 ; y < 9 ; ++y) { if (sudoku[x][y] != 0) { possibleSudoku[x][y] = null; continue; } possibleSudoku[x][y] = getPossibleNumbers(sudoku, x, y); } } int minCount = 11; int minX = -1; int minY = -1; for (int x = 0 ; x < 9 ; ++x) { for(int y = 0 ; y < 9 ; ++y) { if (possibleSudoku[x][y] == null) continue; int freeNumbers = getFreeNumberCount(possibleSudoku[x][y]); if (freeNumbers == 0) return null; if (freeNumbers < minCount) { minCount = freeNumbers; minX = x; minY = y; } } } if (minX == -1) return sudoku; //System.out.println("minCount : " + minCount); for (int i = 1 ; i < 10 ; ++i) { if (!possibleSudoku[minX][minY][i]) continue; sudoku[minX][minY] = i; int[][] outSudoku = solveSudoku(sudoku); if(outSudoku != null) return outSudoku; sudoku[minX][minY] = 0; } return null; } public static int getFreeNumberCount (boolean[] possibleNumbers) { int count = 0; for(int i = 1 ; i < possibleNumbers.length ; ++i) { if(possibleNumbers[i]) ++count; } return count; } public static boolean[] getPossibleNumbers(int[][] sudoku, int x, int y) { if (sudoku[x][y] != 0) return null; boolean[] possibleNumbers = new boolean[10]; for (int i = 0 ; i < 10 ; ++i) { possibleNumbers[i] = true; } for (int i = 0 ; i < 9 ; ++i) { possibleNumbers[sudoku[x][i]] = false; possibleNumbers[sudoku[i][y]] = false; } int boxX = x / 3; int boxY = y / 3; for(int i = 0 ; i < 3 ; ++i) { for(int j = 0 ; j < 3 ; ++j) { possibleNumbers[sudoku[3*boxX+i][3*boxY+j]] = false; } } return possibleNumbers; } }...wobei das natürlich reichlich zusammengefrickelt ist.
