Sudoku Programm ist fertig
-
Wie Versprochen setze ich meinen Quellcode ins Netz vielleicht hat einer ja lust da mal durchzusteigen wenn nicht und ihr das einfach so mit ins Programm implementieren wollt dann braucht ihr die paar Zeilen, die gleich folgen.
//- In Form1.cpp leitet man das so ein ganz oben wenn möglich #include "algo.h" //- Die Class muss bereit gestellt werden sudokux sudo_algo; //- Sudoku Array erstellen; int sudoku[9][9]; int type = 1; //- Bestimmt den Schwierigkeitsgrad 1=leicht, 2=normal und 3=schwer sudo_algo.Create_SudokuField_Numbers(sudoku, type); //- Sudoku Array lösen int sudoku_finish[9][9]; ... //- Das Array wird hier mit Zahlen gefüllt die gegeben sind falls keine Zahl da ist wird eine Null reingeschrieben. if(sudo_algo.Finish_SudokuField_Numbers(sudoku_finish)) { ... //- Das ist eine bool Funktion und gibt ein true or false zurück. True wenn das Rätsel gelöst wurde beim durchlauf, false //- wenn sich noch keine Lösung eingestellt hat. Dann sollte man das Programm solange durchlaufen lassen bis eine Lösung gefunden wurde. }Die Class findet ihr hier: http://eyewatch.selfip.net/down/algo.h
Habt viel Spaß damit
-
warum heißt lösen finish und nicht solve
zu den gotos sag ich mal nichts
-
kann ich auch noch umbenennen ist ir wurst
naja man kann doch mal mit goto arbeiten weiß nicht ist doch lustig mal ein wenig spaghetti-code... na gut bin eh noch ein wenig am pfeilen da fällt das goto auch noch weg 
-
viel zu viele magic numbers
-
@Denfius: Findest Du nicht, dass Du da'n bischen viel Code zum Lösen des Sudokus brauchst?
Wie lange braucht Dein Algorithmus für ein durchschnittliches Sudoku? ...zum Beispiel für das da:
003006040
100950760
006100000
390000400
010000020
008000097
000008900
045039008
020700500(0 steht für ein leeres Feld.)
-
also ich habe es mal durchlaufen lassen und er braucht nicht mal ne sec...
Und messen will ich das nicht
Jo ist ziemlich viel Code aber den brauch ich wenn ich mehrere Arten von Sudokus lösen will
Hmm haste mal nen Code der kleiner ist? würde den zugerne mal sehen
-
Denfius schrieb:
also ich habe es mal durchlaufen lassen und er braucht nicht mal ne sec...
Und messen will ich das nichtJo ist ziemlich viel Code aber den brauch ich wenn ich mehrere Arten von Sudokus lösen will
Hmm haste mal nen Code der kleiner ist? würde den zugerne mal sehenWelche Arten von Sudokus denn noch? Meinst Du so 4*4-Sudokus und so?
...mein Code ist zugegebenermaßen nur auf das Lösen von 3*3-Sudokus ausgelegt. Dürfte aber nicht sooo schwer sein, den entsprechend flexibler zu machen. ...kannst Dir den ja mal angucken. Das Programm erwartet als Parameter den Namen einer Textdatei, in der ein Sudoku wie das da oben enthalten ist.
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; } }
-
Hallo,
Hatte noch ein paar Links zum Thema in meinen Bookmarks, dachte mir, dass Euch davon uU auch manches interessieren könnte:
- relativ simpler CommonLisp-Sudoku-Solver, <60 LOC, braucht für Gregors Beispiel-Sudoku auf meinem Athlon XP 2400+ unter 0.05 Sekunden.
- nochmal CommonLisp, etwas ausführlicher
- Prolog-Progrämmchen eines Kollegen (clever und kurz)
- verbessertes Prolog-Progrämmchen eines Kollegen (sehr clever, nicht ganz so kurz)
- Oh, und wenn Ihr herausfinden wollt, wer den längstenWWdas kürzeste hat, dann schaut Euch mal das und das hier an.
Vielleicht ist ja was für Euch dabei.
-
Gregor schrieb:
Mein Soduko ist viel länger als deiner!11
-
übersetzer schrieb:
Gregor schrieb:
Mein Soduko ist viel länger als deiner!11
Nene... Du irrst Dich. Mein aktuelles Maß für virtuelle Längenvergleiche ist CP/q bei JBB.