source: Java_Quellcode_SOOP_Vorlesung/arrays/SudokuSolver.java @ 435

Last change on this file since 435 was 435, checked in by tr, 5 years ago

Sudoku: Kleinigkeiten

File size: 6.9 KB
Line 
1package eu.hsrw.tr.prog.vl.arrays;
2
3/**
4 * Löst 9x9 Sudokus mittels Brute Force und Backtracking: Durchprobieren von
5 * oben links nach unten rechts
6 *
7 * @author Thomas Richter
8 *
9 */
10public class SudokuSolver {
11
12    /**
13     * Testet, ob die Zahl bereits in der angegebenen Zeile des Sudokus vorkommt
14     *
15     * @param a
16     *            9x9 Array mit dem Sudoku
17     * @param zeile
18     *            zu prüfende Zeile
19     * @param kandidat
20     *            zu prüfende Zahl
21     * @return false, falls die Zahl vorkommt, sonst true
22     */
23    public static boolean zeileOK(int[][] a, int zeile, int kandidat) {
24        for (int i = 0; i < a.length; i++) {
25            if (Math.abs(a[zeile][i]) == kandidat) {
26                return false;
27            }
28        }
29        return true;
30    }
31
32    /**
33     * Testet, ob die Zahl bereits in der angegebenen Spalte des Sudokus
34     * vorkommt
35     *
36     * @param a
37     *            9x9 Array mit dem Sudoku
38     * @param spalte
39     *            zu prüfende Spalte
40     * @param kandidat
41     *            zu prüfende Zahl
42     * @return false, falls die Zahl vorkommt, sonst true
43     */
44    public static boolean spalteOK(int[][] a, int spalte, int kandidat) {
45        for (int i = 0; i < a.length; i++) {
46            if (Math.abs(a[i][spalte]) == kandidat) {
47                return false;
48            }
49        }
50        return true;
51    }
52
53    /**
54     * Testet, ob die Zahl bereits in dem 3x3 Block vorkommt, in dem das durch
55     * zeile und spalte festgelegte Feld liegt
56     *
57     * @param a
58     *            9x9 Array mit dem Sudoku
59     * @param zeile
60     *            Zeile des Elements, dessen 3x3 Block getestet werden soll
61     * @param spalte
62     *            Spalte des Elements, dessen 3x3 Block getestet werden soll
63     * @param kandidat
64     *            zu prüfende Zahl
65     * @return false, falls die Zahl vorkommt, sonst true
66     */
67    public static boolean blockOK(int[][] a, int zeile, int spalte, int kandidat) {
68        // Feststellen in welchem Block wir eigentlich sind -> wir benötigen die
69        // kleinste Zeile und die kleinste Spalte dieses Blocks
70        int startZeile = zeile - zeile % 3;
71        int startSpalte = spalte - spalte % 3;
72
73        for (int i = startZeile; i < startZeile + 3; i++) {
74            for (int j = startSpalte; j < startSpalte + 3; j++) {
75                if (Math.abs(a[i][j]) == kandidat) {
76                    return false;
77                }
78            }
79        }
80        return true;
81    }
82
83    /**
84     * Löst das übergebene 9x9 Sudoku mittels Brute Force und Backtracking: Es
85     * wird mit dem Feld oben links begonnen und dann spalten- und zeilenweise
86     * nach rechts unten gearbeitet. Als erster Wert wird die 1 versucht. Falls
87     * der Versuch einen Konflikt auslöst, wird die Zahl immer weiter erhöht,
88     * bis entweder kein Konflikt mehr auftritt oder die Zahl 10 erreicht wurde.
89     * Falls 10 erreicht wurde konnte kein passender Eintrag gefunden werden,
90     * das Problem muss also schon weiter vorn liegen. Es wird um ein Feld
91     * zurückgegangen und dort die nächsthöhere Zahl versucht. Ggf. sind sehr
92     * viele Rücksprünge erforderlich, da viele Kombinationen durchprobiert
93     * werden müssen.
94     *
95     * @param a
96     *            zu lösendes Sudoku als 9x9 Array
97     */
98    public static void solve(int[][] a) {
99        // wir beginnen oben links und gehen nach unten rechts durch
100        // Nummer des Feldes: 0..80
101        int position = 0;
102        // zähle die Rücksprünge (nur zu Informationszwecken)
103        int rueckspruenge = 0;
104
105        while (position < 81) {
106            // Zeile und Spalte aus der Nummer des Feldes bestimmen
107            int zeile = position / 9;
108            int spalte = position % 9;
109
110            // Es werden nur Felder bearbeitet, die nicht negativ sind.
111            // negative Zahlen sind die Startbelegung -> überspringen
112            if (a[zeile][spalte] < 0) {
113                // Zahl war negativ -> weiterrücken
114                position++;
115           
116            } else {
117                // Versuche, eine Zahl im Feld a[zeile][spalte] einzubauen
118                // Beginne mit der aktuellen Zahl + 1: anfangs 0 + 1
119                int kandidat = a[zeile][spalte] + 1;
120
121                // testen, ob die Zahl einen Sudoku-Fehler verursacht
122                // bei Fehler: Zahl erhöhen
123                while (!zeileOK(a, zeile, kandidat) ||
124                       !spalteOK(a, spalte, kandidat) ||
125                       !blockOK(a, zeile, spalte, kandidat)) {
126                    kandidat++;
127                }
128
129                // Warum sind wir aus der Schleife rausgekommen?
130                if (kandidat < 10) {
131                    // zahl < 10 hat keinen Fehler verursacht -> eintragen
132                    a[zeile][spalte] = kandidat;
133                    // weiterrücken zum nächsten Feld
134                    position++;
135
136                } else {
137                    // zahl == 10 -> keine passende Zahl gefunden -> zurückgehen
138                    // Feld auf 0 zurücksetzen damit spätere Einträge nicht verfälscht
139                    // werden
140                    a[zeile][spalte] = 0;
141
142                    // Wir dürfen nicht auf ein Feld mit negativem Eintrag
143                    // zurückspringen, da die negativen Zahlen die Startbelegung
144                    // kennzeichnen -> Zurück bis Inhalt nicht mehr negativ
145                    do {
146                        position--;
147                        rueckspruenge++;
148                    } while (a[position / 9][position % 9] < 0);
149                }
150            }
151        }
152        System.out.println("Rücksprünge: " + rueckspruenge);
153    }
154
155    /**
156     * Gibt ein Sudoku auf der Konsole aus
157     *
158     * @param a
159     *            zweidimensionales Array mit dem Sudoku
160     */
161    public static void printSudoku(int[][] a) {
162        System.out.println("\n----------------------");
163
164        for (int i = 0; i < a.length; i++) {
165            System.out.print("|");
166            for (int j = 0; j < a[i].length; j++) {
167                System.out.print(Math.abs(a[i][j]) + " ");
168                if (j % 3 == 2) {
169                    System.out.print("|");
170                }
171            }
172            if (i % 3 == 2) {
173                System.out.print("\n----------------------");
174            }
175            System.out.println();
176        }
177    }
178
179    public static void main(String[] args) {
180
181        // Beispiele für schnell und langsam zu lösende Sudokus
182        int[][] sudokuLeer = new int[9][9];
183
184        int[][] sudokuSchnell = {
185                { 0,  0, -5,  0,  0,  0,  0, -6,  0},
186                { 0,  0, -8, -7,  0,  0,  0,  0,  0},
187                { 0,  0,  0,  0, -3,  0,  0,  0, -9},
188                { 0,  0,  0,  0,  0, -6,  0,  0,  0},
189                { 0,  0, -3,  0,  0,  0,  0,  0, -7},
190                { 0,  0,  0, -5,  0,  0,  0, -4,  0},
191                { 0, -9,  0,  0,  0, -1,  0,  0,  0},
192                { 0, -6,  0,  0,  0,  0, -7,  0,  0},
193                { 0,  0,  0,  0,  0, -5,  0,  0, -8}
194        };
195
196        int[][] sudokuLangsam = {
197                {  0,  0,  0,  0,  0,  0,  0,  0,  0},
198                {  0,  0,  0,  0,  0,  0, -9, -6,  0},
199                { -5, -8,  0,  0, -3,  0,  0,  0,  0},
200                {  0, -7,  0,  0,  0, -5,  0,  0,  0},
201                {  0,  0, -3,  0,  0,  0,  0,  0,  0},
202                {  0,  0,  0, -6,  0,  0, -1,  0, -5},
203                {  0,  0,  0,  0,  0,  0,  0, -7,  0},
204                { -6,  0,  0,  0,  0, -4,  0,  0,  0},
205                {  0,  0, -9,  0, -7,  0,  0,  0, -8}
206        };
207
208        int[][] sError = {
209            {-4, -7, 0, 3, 0, -2, 0, -6, 0},
210            {0, 0, -9, 0, 0, 0, -2, 0, 0},
211            {0, -8, 0, 0, 0, 0, -7, 0, 0},
212            {0, -5, 0, 0, -1, -9, 0, 0, 0},
213            {0, 0, 0, -6, 0, -5, 0, 0, 0},
214            {0, 0, 0, -2, -8, 0, 0, -5, 0},
215            {0, 0, -3, 0, 0, 0, 0, -9, 0},
216            {0, 0, -2, 0, 0, 0, -8, 0, 0},
217            {0, -4, 0, -8, 0, -6, 0, -7, -2},
218        };
219/*
220[4, 7, 1, 3, 2, 2, 5, 6, 9]
221[3, 6, 9, 4, 5, 7, 2, 1, 8]
222[2, 8, 5, 9, 6, 1, 7, 4, 3]
223[6, 5, 8, 7, 1, 9, 3, 2, 4]
224[1, 2, 4, 6, 3, 5, 9, 8, 7]
225[9, 3, 7, 2, 8, 4, 6, 5, 1]
226[8, 1, 3, 5, 7, 6, 4, 9, 2]
227[5, 9, 2, 1, 4, 3, 8, 7, 6]
228[7, 4, 6, 8, 9, 6, 1, 7, 2]
229 */
230       
231        int[][] sudoku;
232        sudoku = sudokuSchnell;
233        sudoku = sudokuLangsam;
234        sudoku = sError;
235        // sudoku = sudokuLeer;
236
237        printSudoku(sudoku);
238
239        solve(sudoku);
240
241        printSudoku(sudoku);
242    }
243}
Note: See TracBrowser for help on using the repository browser.