12.10.2012 by Dario D. Müller

PHP: Sudoku Algorithmus

Algorithmus zum Lösen von Zahlen

Sudoku

Wer kennt sie nicht? Die Sudoku.

Es geht darum, auf einem Quadrat von 9 mal 9 Feldern jede der Zahlen (1 bis 9) neun mal einzutragen, jede nur einmal pro Spalte und pro Zeile, sowie einmal pro 9er Feld.

Das Spiel für Zwischendurch wird inzwischen in jedem Land und zu jeder beliebigen Zeit gespielt. Vor allem im Urlaub sieht man regelmäßig welche, die sich daran versuchen.

Warum also nicht eine Software bauen, die einem die Arbeit abnimmt? Grund genug, eine kleine Logik auszudenken, die einfache Sudoku ganz von alleine lösen kann – oder zumindest den Benutzer ein wenig unterstützt

 

Umsetzung

Was wird benötigt?

  • Logik
  • PHP-Backend
  • HTML- & CSS-Frontend
  • JS-Logik & AJAX-Request mit JSON

 

Sudoku Solution Software

 

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

<?php
/*
 * Sudoku Solution Software
 * by Dario D. Müller
 * dariodomi.de
 * 10 / 2012
 * v1.0
 */
 
 
/* Datenspeicher: Zahlen */
$tmpZahlenFest = array();
for($i = 1; $i <= 9; $i++)
        $tmpZahlenFest[$i] = array();
 
/* Input: POST */
if($_POST) {
        // $tmpZahlenFest[zahl][x][y] = '';
        $_POST['zahlen'] = trim($_POST['zahlen'], '|');
        $str = explode('|', $_POST['zahlen']);
        foreach($str as $val) {
                $str2 = explode(',', $val);
                $tmpZahlenFest[$str2[0]][$str2[1]][$str2[2]] = '';
        }
}
 
/* Datenspeicher: Koordinaten */
$zahlen = array();
foreach($tmpZahlenFest as $key => $val) {
        $zahl = $key;
        foreach($val as $key2 => $val2) {
                $x = $key2;
                foreach($val2 as $key3 => $val3) {
                        $y = $key3;
                        $zahlen[$x][$y][$zahl] = '';
                }
        }
}
 
/* Datenspeicher: Möglichkeiten */
$moeglichkeiten = array();
 
// Init
checkPossibilities();
 
// Main Function
function checkPossibilities() {
 
        // get vars
        global $tmpZahlenFest;
        global $zahlen;
        global $moeglichkeiten;
        $dreierY = 1;
        $found = false;
 
        // "endlos"-schleife
        do {
                $found = false;
 
                // Jede Zahl durchgehen
                for($zahl = 1; $zahl <= 9; $zahl++) {
                        $belegtX = array();
                        $belegtY = array();
                        $belegt3 = array();
 
                        // Jede belegte Zahl schauen, welche Reihe / Spalten diese belegt
                        foreach($tmpZahlenFest[$zahl] as $key => $val) {
                                $x = $key;
                                foreach($val as $key2 => $val2) {
                                        $y = $key2;
                                        $belegtX[$x] = '';
                                        $belegtY[$y] = '';
                                        $y3 = (int)($y-1)/3;
                                        $x3 = (int)($x-1)/3;
                                        $belegt3[$y3][$x3] = '';
                                }
                        }
 
                        // Reihen & Spalten durchgehen und jedes freie Feld highlighten
                        $moeglichkeiten3 = array();
                        for($y = 1; $y <= 9; $y++) {
 
                                for($x = 1; $x <= 9; $x++) {
                                        $y3 = (int)($y-1)/3;
                                        $x3 = (int)($x-1)/3;
                                        if(!isset($belegtY[$y]) && !isset($belegtX[$x]) && !isset($belegt3[$y3][$x3]) && !isset($zahlen[$x][$y])) {
                                                //echo 'frei: '.$y.'. Reihe / '.$x.'. Spalte<br>';
                                                $moeglichkeiten3[$x3][] = array($x, $y);
                                        }
                                }
 
                                // wenn die 3. / 6. / 9. zeile zu ende
                                if($y %3 == 0) {
                                        for($i = 0; $i <= 2; $i++) {
                                                if(isset($moeglichkeiten3[$i]) && count($moeglichkeiten3[$i]) == 1) {
 
                                                        // Sortierung neue Zahl in richtiger Reihenfolge speichern
                                                        $finalX = $moeglichkeiten3[$i][0][0];
                                                        $finalY = $moeglichkeiten3[$i][0][1];
                                                        $tmpZahlenFest[$zahl][$finalX][$finalY] = '';
                                                        $zahlen[$finalX][$finalY][$zahl] = '';
 
                                                        // Sortierung & Speicherung Ende
                                                        $found = true;
                                                }  else {
                                                        if(isset($moeglichkeiten3[$i]) && $moeglichkeiten3[$i] != null)
                                                                $moeglichkeiten[$zahl][] = $moeglichkeiten3[$i];
                                                }
                                        }
                                        $moeglichkeiten3 = array();
                                }
 
                        }
                }
 
                // Jede Zeile durchgucken
                for($y = 1; $y <= 9; $y++) {
                        $belegteZahlen = array();
                        $verfX = array();
                        $verfZahlen = array();
                        for($x = 1; $x <= 9; $x++) {
                                if(isset($zahlen[$x][$y])) {
                                        foreach($zahlen[$x][$y] as $key => $val)
                                                $zahl = $key;
                                        $belegteZahlen[$zahl] = '';
                                } else {
                                        $verfX[] = $x;
                                }
                        }
                        for($zahl = 1; $zahl <= 9; $zahl++) {
                                if(!isset($belegteZahlen[$zahl]))
                                        $verfZahlen[] = $zahl;
                        }
                        if(count($verfZahlen) == 1) {
                                $zahl = $verfZahlen[0];
                                $x = $verfX[0];
                                $tmpZahlenFest[$zahl][$x][$y] = '';
                                $zahlen[$x][$y][$zahl] = '';
                        }
 
                        // TODO: Bei mehreren Fehlenden, die einzelnen y nochmal durchgucken
                        // das Gleiche anschließend beim Spalten-Durchgucken
                }
 
                // Jede Spalte durchgucken
                for($x = 1; $x <= 9; $x++) {
                        $belegteZahlen = array();
                        $verfY = array();
                        $verfZahlen = array();
                        for($y = 1; $y <= 9; $y++) {
                                if(isset($zahlen[$x][$y])) {
                                        foreach($zahlen[$x][$y] as $key => $val)
                                                $zahl = $key;
                                        $belegteZahlen[$zahl] = '';
                                } else {
                                        $verfY[] = $y;
                                }
                        }
                        for($zahl = 1; $zahl <= 9; $zahl++) {
                                if(!isset($belegteZahlen[$zahl]))
                                        $verfZahlen[] = $zahl;
                        }
                        if(count($verfZahlen) == 1) {
                                $zahl = $verfZahlen[0];
                                $y = $verfY[0];
                                $tmpZahlenFest[$zahl][$x][$y] = '';
                                $zahlen[$x][$y][$zahl] = '';
                        }
                }
 
 
 
        } while($found);
 
        //echo json_encode(array($tmpZahlenFest, $moeglichkeiten));
        echo json_encode($tmpZahlenFest);
}
 
 
?>

 

 

ENDE : )

Tags: algorithmus, logic, PHP, software, sudoku


  • Categories

  • About me

    Dario D. Müller, living in Hamburg is Programmer for Web Development since five years. A year ago, he began studing game programming at SAE University Hamburg, Germany.

    Social

    • XING
    • GitHub
    • Google+