Sudoku [StateSolver]

Gepost door M 17 op 07-05-2010 21:28.

freakz..

Ik heb nu in allerlei talen sudoku oplossers geschreven en vandaag was PHP aan de beurt om mijn `fantastische` StateSolver in te implementeren whehehe.

Hierbij lever ik jullie 2 bestanden:
Sudoku.php - dit kun je als voorbeeld gebruiken over hoe de klasse te gebruiken, tevens kan deze de sudoku's tonen.
StateSolver.class.php - dit is dus de klasse die al het werk voor je gaat doen.

De klasse heeft (behalve de constructor) slechts twee `public` velden:
- property sudoku - get/set de puzzel
- method findSolution - start de oplosser

Uiteraard kun je ook met constructor een sudoku puzzel meegeven aan de klasse. Maar mocht je zin hebben om heel veel puzzels in 1x op te lossen, dan kun je het property gebruiken als `setter`.

Ohja, aangezien een goede sudoku slechts 1 oplossing heeft, heb ik de klasse niet uigebreidt om meerdere oplossingen te geven. Het algoritme zelf is wel in staat om alle oplossingen te vinden. Mocht je hier mee willen prutsen, zet dan de if (ready) return regels uit en waar de ready flag gezet wordt de code om extra oplossingen te verwerken (bv door ze te tonen).
Stel je geeft een lege sudoku, dan blijft het script draaien totdat alle mogelijke oplossingen zijn gevonden, ik kwam met mn C# versie tot 50 miljoen binnen 10 uur, maar ik schat dat je PHP er na 30 seconden al mee op zal houden!

Tot slot:
Doe ermee wat je wilt, het interesseert me echt geen bal. Desnoods vertel je iedereen dat jij die geweldige auteur bent en zet je je naam er boven (+ copyright natuurlijk he).

mocht mijn server online zijn, dan kun je even snel een voorbeeldje bekijken op:
http://mark.space.servehttp.com/Sudoku.php

mocht je de rest van mn sudoku crap willen zien:
http://mark.space.servehttp.com/sudoku/

Hier onder volgt een copy/paste van een document dat ik gisteren heb geschreven voor de C# versie doch met dezelfde aanpak..
Let op dat namen van methoden een beetje kunnen verschillen, ik gebruik in de php versie bv geen overload van findSolution.
Waar je ook op moet letten is dat in de C# versie gebruikt wordt gemaakt van een BitArray om de kandidaatlijsten bij te houden. In PHP maak ik gewoon gebruik van ints en heb er een paar extra methoden bij geschreven om de bitsets te bewerken.

TACTIEK
Het algoritme maakt gebruik van kandidaat lijsten die voortdurend bijgehouden worden. Er zijn 27 kandidaatlijsten, voor iedere rij, kolom en blok is er een lijst beschikbaar. Elk van deze kandidaatlijsten bevat een bitset waarbij ieder bit van rechts naar links aangeeft of het nummer wel of niet een kandidaat is.
Als een kandidaatlijst de bitset 001011001 bevat wil dit zeggen dat de getallen 1, 4, 5 en 7 als kandidaat beschikbaar zijn voor de rij, kolom of het blok.
De recursieve methode zelf probeert voor elke lege cel de eerste kandidaat en gaat vervolgens verder met de volgende lege cel. Indien hier dan geen kandidaten meer zijn, gaat het algoritme terug naar de vorige cel en probeert de volgende kandidaat. Dit gaat zo verder totdat er geen lege cellen meer zijn.

INITIALISATIE VAN HET ALGORITME
Wanneer de methode FindSolution wordt aangeroepen vindt er eerst een initialisatie plaats alvorens het recursieve gedeelte de macht overneemt:
1. alle 27 kandidaatlijsten worden gevult met TRUE zodat alle mogelijke kandidaten aan staan.
2. een iteratie langs alle 81 getallen van de puzzel
2a. is er een getal op positie x, dan wordt deze uit de corresponderende kandidaatlijsten verwijderd
2b. is er geen getal op positie x, dan wordt deze positie toegevoegd een een lijst met lege cellen
3. ready vlag wordt FALSE gezet, dit betekend dat er nog geen oplossing is gevonden
4. aanroep van de recursieve methode en start van positie 0

DE RECURSIEVE OPLOS METHODE
Als eerst wordt hier gekeken of het algoritme alle lege cellen heeft ingevult, dit is het geval wanneer de indexvariabele een hogere waarde heeft dan de lengte van de lijst met lege cellen die tijdens de initialisatie aangemaakt is. Indien het einde is bereikt, wordt de ready vlag op TRUE gezet zodat het algoritme uit de recursieve diepe kan komen door geen actie meer te ondernemen en alleen nog maar m.b.v. return de methode verlaat.
Vervolgens moeten de corresponderende kandidaatlijsten bemachtigd worden. De huidige positie in de puzzel wordt gebruikt om de indices van de kandidaatlijsten te berekenen, hierbij wordt gebruikt gemaakt van de methode GetCandidateLists.
De kern van deze methode bevat de logica die iedere kandidaat test en eventueel doorgaat met de volgende cel. Een simpele for/next lus van 1 tot 9 gaat alle mogelijke kandidaten bij langs voor de huidige cel.
Binnen deze lus wordt eerst gekeken of de waarde van de lus (1..9) voorkomt in de drie kandidaatlijsten (rij, kolom en blok). Wanneer een getal voorkomt in alle drie kandidaatlijsten, wordt deze op de huidige posititie van de puzzel gezet en uit de lijsten verwijderd. Vervolgens gaat de recursie een niveau dieper en herhaalt het algoritme zich met de volgende lege cel in de puzzel.
Mocht geen van de getallen binnen de for/next lus voorkomen in alle drie lijsten, dan valt het algoritme terug naar een hoger recursief niveau en verwijderd dan het vorige getal van de vorige cel en probeert de volgende kandidaat. Is dit ook niet mogelijk, gaat het algoritme nog verder terug.

Op deze manier worden alle mogelijke combinaties geprobeert om zo tot een oplossing te komen. Werkt iets niet, dan `backtrackt` het algoritme gewoon en probeert de volgende kandidaat.

De ready vlag wordt gebruikt om netjes de recursieve methode te verlaten zonder verder de puzzel te veranderen. Als dit uitgezet wordt gaat het algoritme door om zoveel mogelijk oplossingen te vinden, mocht het een foute sudoku zijn.

CHANGELOG
04-02 - onbelangrijke bugfix: $this->ready = false wordt $this->_ready = false
27-05 - hele domme bugfix: ik schaam me dood maar in de aanroepende logica staan 2 hele domme fouten, ik heb eigenlijk geen idee of dit een probleem zou veroorzaken maar de aanroepende DisplaySudoku() functies worden displaySudoku() met dus een kleine letter 'd'.
in java zou ik hier direct voor beboet worden..

Bestanden van dit script

index.php

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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
Sudoku.php
<?php
    // Include the class
    include 'StateSolver.class.php';

    // This is what a given sudoku should look like (solution on the right)
    $sudoku = array(
    0,2,0,4,0,9,5,0,6,  // 321   489   576
    0,4,5,0,7,0,8,0,9,  // 645   173   829
    0,7,0,0,2,6,0,0,0,  // 879   526   413
    0,0,0,0,3,0,6,0,1,  // 587   234   691
    9,0,2,0,6,0,0,0,0,  // 912   865   347
    0,0,0,7,0,1,0,5,0,  // 436   791   258
    0,0,0,3,1,0,0,0,4,  // 258   317   964
    7,0,0,0,0,0,1,0,0,  // 794   658   132
    0,0,3,9,0,2,7,8,0); // 163   942   785

    // Instantiate the solver class
    $stateSolver = new StateSolver($sudoku);

    // Display the current sudoku
    displaySudoku($sudoku);

    // Obtain start time
    $beginTime = microtime();

    // Call the solver
    $stateSolver->findSolution();

    // Obtain end time
    $endTime = microtime();

    // Calculate the total time
    $totalTime = $endTime - $beginTime;

    echo 'Elapsed time: '.$totalTime.'ms<br />';

    // Display the solved sudoku
    displaySudoku($stateSolver->sudoku);

    function displaySudoku($sudoku) {
        for ($i = 0; $i < 81; $i++) {
            echo ' ' . $sudoku[$i] . ' ';

            if (($i + 1) % 9 == 0) {
                echo '<br />';
            }
        }
    }

?>

StateSolver.class.php
<?php

    class StateSolver {

        /////////////////////////
        /// PUBLIC ATTRIBUTES ///
        /////////////////////////

        // Holds the sudoku puzzel as an array
        public $sudoku;

        //////////////////////////
        /// PRIVATE ATTRIBUTES ///
        //////////////////////////

        // Holds the 27 candidatelists as an array
        private $_candidates;

        // Holds the list of empty cells as an array
        private $_emptyCells;

        // Determines whether or not the algorithm has found a solution
        private $_ready;

        ////////////////////
        /// CONSTRUCTORS ///
        ////////////////////

        public function __construct($sudoku) {
            $this->sudoku = $sudoku;
        }

        //////////////////////
        /// PUBLIC METHODS ///
        //////////////////////

        // Initialize the solving algorithm
        public function findSolution() {
            $column = 0;
            $row = 0;
            $region = 0;
            $eIndex = 0;

            // Fill the candidatelists with all 9 bits set
            for ($i = 0; $i < 27; $i++) {
                $this->_candidates[$i] = 511;
            }

            // Exclude invalid candidates and get empty cells
            for ($i = 0; $i < 81; $i++) {
                if ($this->sudoku[$i] == 0) {
                    // Add this empty cell to the list
                    $this->_emptyCells[$eIndex++] = $i;
                } else {
                    // Exclude this number from the candidatelists
                    $this->_getCandidateLists($i, $column, $row, $region);

                    $this->_exclude($this->_candidates[$column], $this->sudoku[$i]);
                    $this->_exclude($this->_candidates[$row], $this->sudoku[$i]);
                    $this->_exclude($this->_candidates[$region], $this->sudoku[$i]);
                }
            }

            // Set the ready flag to false
            $this->_ready = false;

            // Run the recursive backtracking algorithm
            $this->_solve(0);
        }

        ///////////////////////
        /// PRIVATE METHODS ///
        ///////////////////////

        // Recursive backtracking solver
        private function _solve($eIndex) {
            $column = 0;
            $row = 0;
            $region = 0;

            // See if haven't reached the end of the pattern
            if ($eIndex < count($this->_emptyCells)) {

                // Get the corresponding candidatelists
                $this->_getCandidateLists($this->_emptyCells[$eIndex], $column, $row, $region);

                // Check if $i occurs in all three candidatelists
                for ($i = 1; $i < 10; $i++) {
                    if ($this->_isCandidate($this->_candidates[$column], $i) &&
                        $this->_isCandidate($this->_candidates[$row], $i) &&
                        $this->_isCandidate($this->_candidates[$region], $i)) {

                        // Suitable candidate found, use it!
                        $this->sudoku[$this->_emptyCells[$eIndex]] = $i;

                        // Exclude this number from the candidatelists
                        $this->_exclude($this->_candidates[$column], $i);
                        $this->_exclude($this->_candidates[$row], $i);
                        $this->_exclude($this->_candidates[$region], $i);

                        // Don't advance if a solution has been found
                        if ($this->_ready) return;

                        // Advance to the next cell
                        $this->_solve($eIndex + 1);

                        // Don't revert if a solution has been found
                        if ($this->_ready) return;

                        // Reset the cell
                        $this->sudoku[$this->_emptyCells[$eIndex]] = 0;

                        // Put the candidates back in the lists
                        $this->_include($this->_candidates[$column], $i);
                        $this->_include($this->_candidates[$row], $i);
                        $this->_include($this->_candidates[$region], $i);

                    }
                }
            } else {
                // A solution has been found, get out of recursion
                $this->_ready = true;
            }
        }

        // Obtains the corresponding candidatelist indices
        private function _getCandidateLists($position, &$column, &$row, &$region) {
            $column = $position % 9;
            $row = floor(9 + $position / 9);
            $region = floor(18 + floor($column / 3) + 3 * floor(($row - 9) / 3));
        }

        // Excludes a number from the list of candidates
        private function _exclude(&$bitSet, $bit) {
            $bitSet &= ~(1 << $bit -1);
        }

        // Includes a number into the list of candidates
        private function _include(&$bitSet, $bit) {
            $bitSet |= (1 << $bit - 1);
        }

        // Determines if number occurs in the specified list of candidates
        private function _isCandidate($bitSet, $bit) {
            return (($bitSet & (1 << $bit - 1)) == 0) ? false : true;
        }

    }

?>

Commentaar

06-02-2006 19:16

Leuk script, en leuk bedacht om het zo op te pakken.

Ik heb zelf in C een ander algoritme bedacht, dat als volgt werkt:

zolang er nog lege velden zijn
----loop van links naar rechts, en van boven naar beneden
----totdat alle velden geweest zijn
--------controleer per veld wat het aantal mogelijke getallen
--------is. Dit gebeurt door alle getallen uit de rij, de kolom
--------en het blok af te strepen
------------als het aantal = 1, dan
----------------vul het getal in
----------------herstart het algortime
------------anders
----------------ga naar volgende veld

1
2
3
Post hier de source-code van je script. Alle informatie tussen <? ... ?> en <?php ... ?> zal automatisch worden getoond in color-coding. 

Let op! Het is niet de bedoeling om hier een link naar je website te plaatsen. Post hier gewoon de code, veel simpeler, sneller en meer kans dat het blijft staan.
06-02-2006 19:41

aha, die aanpak staat bij mij bekend als `simpele eliminatie`. Dat was mijn eerste oplosser die ik in C# schreef (en eerste C# code ooit dan wel)..

De meeste gemiddelde/simpele sudoku's kunnen hiermee vrij snel opgelost worden. Maar zodra er wat minder gegeven cellen aanwezig zijn, wordt het al snel minder. Tot dat dit algoritme geen enkel getal meer kan invullen omdat overal meer dan 1 kandidaat is.

Het voordeel van eliminatie is dat het geen bruteforce cq trial/error is. Een simpel eliminatie algoritme kan met wat meer logica uitgebreidt worden tot een algoritme dat sudoku's oplost zoals mensen dat doen.. pure logica en geen gokken.

Je zou dus eigenlijk extra technieken moeten toevoegen aan de code, een hele belangrijke techniek is cross-hatching (google maar eens kijk op wikipedia). Met eliminatie + cross-hatching kun je al veeeeel meer puzzels oplossen.

Succes ermee :-)

1
2
3
<?php
   echo 'grappig, dat we beide hetzelfde wiel hebben uitgevonden';
?>
07-02-2006 09:43

Dus je moet toch een zekere tetrahydrocanabinol gehalte bevatten om de puzzel op te kunnen lossen? grapje

1
mijn complimenten..is een leuk script.
07-02-2006 09:45

Leuk script.
Ik zal vanavond als ik thuis ben eens even wat gaan experimenteren. Mijn zus is helemaal gek van sudoku dus kan ik misschien wat voor me zus in elkaar zetten.

1
2
3
4
5
<?php

 echo 'Leuk!';

?>
07-02-2006 12:08

Leuk script! Had er zelf over na zitten denken hoe je zoiets met PHP zou kunnen oplossen maar 't was er nog niet van gekomen! Ziet er goed uit :D

Voorbeeldje: http://www.jortberends.nl/Sudoku/

1
2
3
<?php
exit;
?>
09-02-2006 20:48

Hey,

Heb een beetje aan je script zitten prutsen zodat deze ook voor PHP4 toegankelijk is.

Met vriendelijke groet,
Wouter Nijland

Voorbeeld: http://home.wdwn.nl/sudoku.php

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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
sudoku.php:
<?php
    // Include the class
    include 'class.sudoku.php';

    // This is what a given sudoku should look like (solution on the right)
    if($_SERVER['REQUEST_METHOD'] == 'POST'){
      for ($i = 0; $i < 81; $i++)
       $sudoku[] = $_POST['sudoku'.$i]; 
    }
    else{
      $sudoku = array(
      0,2,0,4,0,9,5,0,6,  // 321   489   576
      0,4,5,0,7,0,8,0,9,  // 645   173   829
      0,7,0,0,2,6,0,0,0,  // 879   526   413
      0,0,0,0,3,0,6,0,1,  // 587   234   691
      9,0,2,0,6,0,0,0,0,  // 912   865   347
      0,0,0,7,0,1,0,5,0,  // 436   791   258
      0,0,0,3,1,0,0,0,4,  // 258   317   964
      7,0,0,0,0,0,1,0,0,  // 794   658   132
      0,0,3,9,0,2,7,8,0); // 163   942   785
    }

    // Instantiate the solver class
    $stateSolver = new StateSolver($sudoku);

    // Obtain start time
    $beginTime = microtime();

    // Call the solver
    $stateSolver->findSolution();

    // Obtain end time
    $endTime = microtime();

    // Calculate the total time
    $totalTime = $endTime - $beginTime;

    // Display the current sudoku
    echo '<h1 align="center">SuDoKu Solver</h1><table cellpadding="5" align="center"><tr><td valign="top" align="center">Before';
    DisplaySudoku($sudoku);

    // Display the solved sudoku
    echo '</td><td valign="top" align="center">After';
    DisplaySudoku($stateSolver->sudoku);

    // Display the sudoku form
    echo "</td></tr></table><br><center>";
    echo 'Elapsed time: '.$totalTime.' sec.<br /><br />';
    displaySudokuForm();

    function displaySudoku($sudoku) {
        echo '<table border="3" rules="all" cellpadding="5" cellspacing="0" bordercolor="#000"><tr>';
        $td = 0;
        $row = 0;
        for ($i = 0; $i < 81; $i++) {
            $td++;
            echo '<td><tt style="font-size:15pt;">' . (($sudoku[$i] == 0) ? '&nbsp;' : $sudoku[$i]) . '</tt></td>';
            //echo '<td><input value="' . (($sudoku[$i] == 0) ? '' : $sudoku[$i]) . '" style="width: 20px;" disabled /></td>';
            if ($td % 3 == 0 && $td % 9 != 0) {
                  echo '<td style="width:1px;" bgcolor="#000"></td>';
            }
            if ($td % 9 == 0) {
                $row++;
                echo '</tr>';
                if($row % 3 == 0 && $row % 9 != 0)
                    echo '<tr bgcolor="#000"><td style="height:1px;"></td>'.str_repeat('<td></td>',10).'</tr>';
                echo '<tr>';
            }
        }
        echo '</table>';
    }

    function displaySudokuForm() {
        echo '<form action="" name="sudokuForm" method="post"><table border="3" rules="all" cellpadding="5" cellspacing="0" bordercolor="#000"><tr>';
        $td = 0;
        $row = 0;
        for ($i = 0; $i < 81; $i++) {
            $td++;
            echo '<td><input name="sudoku'.$i.'" '.(isset($_POST['sudoku'.$i]) ? 'value="'.$_POST['sudoku'.$i].'"' : '') .' onKeyPress="document.sudokuForm.sudoku'.(($i==80) ? 0 : $i+1).'.select();" style="width:20px;" maxlength="1" /></td>';
            if ($td % 3 == 0 && $td % 9 != 0) {
                  echo '<td style="width:1px;" bgcolor="#000"></td>';
            }
            if ($td % 9 == 0) {
                $row++;
                echo '</tr>';
                if($row % 3 == 0 && $row % 9 != 0)
                    echo '<tr bgcolor="#000"><td style="height:1px;"></td>'.str_repeat('<td></td>',10).'</tr>';
                echo '<tr>';
            }
        }
        echo '</table><input type="submit" value="Solve SuDoKu" /></form>';
    }
?>

class.sudoku.php:
<?php

    /*  Sudoku State Solver v0.1 [04-feb-2006]
        --------------------------------------
            All code by Mark Jelsma AND Wouter Nijland (http://home.wdwn.nl/sudoku.php)
    */

    class StateSolver {

        /////////////////////////
        /// PUBLIC ATTRIBUTES ///
        /////////////////////////

        // Holds the sudoku puzzel as an array
        var $sudoku;

        //////////////////////////
        /// PRIVATE ATTRIBUTES ///
        //////////////////////////

        // Holds the 27 candidatelists as an array
        var $_candidates;

        // Holds the list of empty cells as an array
        var $_emptyCells;

        // Determines whether or not the algorithm has found a solution
        var $_ready;

        ////////////////////
        /// CONSTRUCTORS ///
        ////////////////////

        function StateSolver($sudoku) {
            $this->sudoku = $sudoku;
        }

        //////////////////////
        /// PUBLIC METHODS ///
        //////////////////////

        // Initialize the solving algorithm
        function findSolution() {
            $column = 0;
            $row = 0;
            $region = 0;
            $eIndex = 0;

            // Fill the candidatelists with all 9 bits set
            for ($i = 0; $i < 27; $i++) {
                $this->_candidates[$i] = 511;
            }

            // Exclude invalid candidates and get empty cells
            for ($i = 0; $i < 81; $i++) {
                if ($this->sudoku[$i] == 0) {
                    // Add this empty cell to the list
                    $this->_emptyCells[$eIndex++] = $i;
                } else {
                    // Exclude this number from the candidatelists
                    $this->_getCandidateLists($i, $column, $row, $region);

                    $this->_exclude($this->_candidates[$column], $this->sudoku[$i]);
                    $this->_exclude($this->_candidates[$row], $this->sudoku[$i]);
                    $this->_exclude($this->_candidates[$region], $this->sudoku[$i]);
                }
            }

            // Set the ready flag to false
            $this->_ready = false;

            // Run the recursive backtracking algorithm
            $this->_solve(0);
        }

        ///////////////////////
        /// PRIVATE METHODS ///
        ///////////////////////

        // Recursive backtracking solver
        function _solve($eIndex) {
            $column = 0;
            $row = 0;
            $region = 0;

            // See if haven't reached the end of the pattern
            if ($eIndex < count($this->_emptyCells)) {

                // Get the corresponding candidatelists
                $this->_getCandidateLists($this->_emptyCells[$eIndex], $column, $row, $region);

                // Check if $i occurs in all three candidatelists
                for ($i = 1; $i < 10; $i++) {
                    if ($this->_isCandidate($this->_candidates[$column], $i) &&
                        $this->_isCandidate($this->_candidates[$row], $i) &&
                        $this->_isCandidate($this->_candidates[$region], $i)) {

                        // Suitable candidate found, use it!
                        $this->sudoku[$this->_emptyCells[$eIndex]] = $i;

                        // Exclude this number from the candidatelists
                        $this->_exclude($this->_candidates[$column], $i);
                        $this->_exclude($this->_candidates[$row], $i);
                        $this->_exclude($this->_candidates[$region], $i);

                        // Don't advance if a solution has been found
                        if ($this->_ready) return;

                        // Advance to the next cell
                        $this->_solve($eIndex + 1);

                        // Don't revert if a solution has been found
                        if ($this->_ready) return;

                        // Reset the cell
                        $this->sudoku[$this->_emptyCells[$eIndex]] = 0;

                        // Put the candidates back in the lists
                        $this->_include($this->_candidates[$column], $i);
                        $this->_include($this->_candidates[$row], $i);
                        $this->_include($this->_candidates[$region], $i);

                    }
                }
            } else {
                // A solution has been found, get out of recursion
                $this->_ready = true;
            }
        }

        // Obtains the corresponding candidatelist indices
        function _getCandidateLists($position, &$column, &$row, &$region) {
            $column = $position % 9;
            $row = floor(9 + $position / 9);
            $region = floor(18 + floor($column / 3) + 3 * floor(($row - 9) / 3));
        }

        // Excludes a number from the list of candidates
        function _exclude(&$bitSet, $bit) {
            $bitSet &= ~(1 << $bit -1);
        }

        // Includes a number into the list of candidates
        function _include(&$bitSet, $bit) {
            $bitSet |= (1 << $bit - 1);
        }

        // Determines if number occurs in the specified list of candidates
        function _isCandidate($bitSet, $bit) {
            return (($bitSet & (1 << $bit - 1)) == 0) ? false : true;
        }

    }

?>
09-02-2006 23:15

__Niks belangrijks maar toch:__

@ Mark:
"Elapsed time: 0.0077460000000000306ms"
0.0077 miliseconde... dat is wel HEEEEL weinig ;)
Ik denk dat je '0.0077 seconde' of '7.7 miliseconde' bedoelt. Detail :)

@ Jort Berens:
"Elapsed time: -0.462805ms"
Ook dat is wel erg weinig :) Nog minder dan 0.0077 miliseconde. Lijkt me sterk, -0.46miliseconde.

groet

ps @ Jort ", dat we beide hetzelfde wiel hebben uitgevonden"
Dit wiel is al wel een aantal keer uitgevonden :) Over and over!
Je gebruikt een mooie methode echter :)
Ik ga er iets leuks mee doen
groet
Rudie

1
2
3
Post hier de source-code van je script. Alle informatie tussen <? ... ?> en <?php ... ?> zal automatisch worden getoond in color-coding. 

Let op! Het is niet de bedoeling om hier een link naar je website te plaatsen. Post hier gewoon de code, veel simpeler, sneller en meer kans dat het blijft staan.
10-02-2006 21:06

php.net/microtime
microtime -- Return current Unix timestamp with microseconds

hmm, minder dus want het zijn geen milliseconden maar microseconden.. da's nog minder..

ik heb overigens ook vreemde resultaten gehad met microtime en heb het nog niet uitgezocht hoe/wat/waarom.

allicht zijn het wel seconden maar misschien toch microseconden. ook ik heb trouwens negatieve getallen gehad.. weet nog niet precies waar dit door komt..

maar hier komt wel antwoord op zodra ik weer aan de slag ga. Ik ga nog een 0.2 versie maken die net wat meer functionaliteit biedt.

de 0.3 en 0.4 moeten nog komen.

1
2
3
Post hier de source-code van je script. Alle informatie tussen <? ... ?> en <?php ... ?> zal automatisch worden getoond in color-coding. 

Let op! Het is niet de bedoeling om hier een link naar je website te plaatsen. Post hier gewoon de code, veel simpeler, sneller en meer kans dat het blijft staan.
10-02-2006 21:18

Ha, leuk gedaan joh :)

er moet nog een fix komen voor het feit dat het algoritme met een ongeldige sudoku over de kop slaat. bij jou online versie kon ik mooi even twee 1tjes in een blok zetten en vervolgens kreeg ik de 30seconden time out (sorry dat je server voor 30seconden alle resources op at :D).

maar dus, php4 compatible he. je hebt dus slechts de `visibility keywords` verwijderd. helaas heeft dit als gevolg dat de `private methods` weer gewoon overal zichtbaar zijn, wat het oop idee een beetje teniet doet.

toch handig voor de mensen die geen php5 gebruiken :)

goed werk! ondanks weinig werk ;-)

maar ik ga er nu natuurlijk wel van uit dat je binnenkort de volgende 0.2 - 0.4 versies ook voor de php4 gebruikers gaat aan passen ;)
zoniet, dan zet ik er wel bij dat men de wijzigingen moet maken die jij hebt gedaan.

ohja, nog een vraagje he... aangezien voor zover ik weet jij de enige bent die erin heeft zitten prutsen, vraag ik me het volgende af:

vond je het overzichtelijk?
kon je snel vinden wat je zocht?
was het goed te begrijpen wat de methoden deden?
begreep je de noodzaak van de lokale variabelen?

ik ben hier nieuwsgierig naar aangezien ik graag duidelijke klassen schrijf.mijn doel is bij iedere OOP taal om het gebrui van een klasse (de public velden) zo simpel mogelijk te houden.. maar tevens ook de private onderdelen overzichtelijk te houden (met commentaar enzo).

Misschien zou ik meer commentaar toe moeten voegen?

of heb je nog ideeen?

dank

1
2
3
Post hier de source-code van je script. Alle informatie tussen <? ... ?> en <?php ... ?> zal automatisch worden getoond in color-coding. 

Let op! Het is niet de bedoeling om hier een link naar je website te plaatsen. Post hier gewoon de code, veel simpeler, sneller en meer kans dat het blijft staan.
11-02-2006 13:31

Vermeld hier alle zaken betreffende valkuilen, handige informatie, (installatie-)instructies e.d.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Oplossing voor microtime probleem

microtime geeft onder < php 5 nog altijd een string terug.

de oplossing:

<?php
function getmicrotime ()
{
   return array_sum (explode (' ', microtime ()));
}
?>

zo heb je altijd de correcte tijd.

NOG 1 ding: een geweldig script, hier was ik zelf nog niet opgekomen;)
11-02-2006 13:41

dankje voor je post... ik kwam vanochtend toevallig precies hetzelfde stukje tegen op php.net/microtime, tussen de reacties dan he ;)

maar heb na het lezen van je reactie het direct toegepast!

1
2
3
Post hier de source-code van je script. Alle informatie tussen <? ... ?> en <?php ... ?> zal automatisch worden getoond in color-coding. 

Let op! Het is niet de bedoeling om hier een link naar je website te plaatsen. Post hier gewoon de code, veel simpeler, sneller en meer kans dat het blijft staan.
28-05-2006 08:25

Vermeld hier alle zaken betreffende valkuilen, handige informatie, (installatie-)instructies e.d.

1
Je hebt geluk Mark;) In PHP zijn function/method/constant namen case-insensitive (de variabelen overigens wel;))
17-08-2006 11:59

Microtime geeft dus niet altijd een string toch en array_sum is zwaar achterhaald als je php 5 hebt

1
2
3
4
5
6
<?

// GEEN string dus, alleen PHP 5:
echo microtime( TRUE );

?>
19-08-2006 14:14

Heel leuk gedaan :) Mijn complimenten!

1
2
3
Post hier de source-code van je script. Alle informatie tussen <? ... ?> en <?php ... ?> zal automatisch worden getoond in color-coding. 

Let op! Het is niet de bedoeling om hier een link naar je website te plaatsen. Post hier gewoon de code, veel simpeler, sneller en meer kans dat het blijft staan.
19-08-2006 14:21

Thanks :P

Waarom had jij die nog niet gemaakt (functie)?

1
2
3
Post hier de source-code van je script. Alle informatie tussen <? ... ?> en <?php ... ?> zal automatisch worden getoond in color-coding. 

Let op! Het is niet de bedoeling om hier een link naar je website te plaatsen. Post hier gewoon de code, veel simpeler, sneller en meer kans dat het blijft staan.
19-08-2006 14:27

ik heb wel betere dingen te doen en heb het ontzettend druk. Programmeer 40 uur per week voor mn baas, verder in mn vrije tijd zoveel mogelijk tijd met http://cannagrow.org bezig en verder nog met freelance projecten en mn eigen framework http://jazztique.org (heel oude tekst daar trouwesn)

1
2
3
Post hier de source-code van je script. Alle informatie tussen <? ... ?> en <?php ... ?> zal automatisch worden getoond in color-coding. 

Let op! Het is niet de bedoeling om hier een link naar je website te plaatsen. Post hier gewoon de code, veel simpeler, sneller en meer kans dat het blijft staan.
19-08-2006 14:33

Dat dacht ik al :-p

1
2
3
Post hier de source-code van je script. Alle informatie tussen <? ... ?> en <?php ... ?> zal automatisch worden getoond in color-coding. 

Let op! Het is niet de bedoeling om hier een link naar je website te plaatsen. Post hier gewoon de code, veel simpeler, sneller en meer kans dat het blijft staan.
21-08-2006 12:06

Dit een bewerkte versie van mij + functie "isSudoku" om te kijken of de sudoku wel geldig is. Een voorbeeld kan je hier vinden:
http://www.leon.serverthuis.nl/veendesign/?p=sudoku
en de afbeelding voor bij het script:
http://www.leon.serverthuis.nl/veendesign/images/sudoku.jpg

Hij werkt goed en snel, thank you "/\/\ark/17 Spacepiloot"

Ik hoop dat jullie er wat aan hebben

Edit:
Je kunt hem hier downloaden:
http://www.leon.serverthuis.nl/veendesign/?p=download&id=19&d=1

Edit:
Hij is vernieuwt, een apparte afbeelding is niet meer nodig en hij kan nu ook sudoku's aan met 4² in plaats van 3²

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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
<?php
/* Most of the code is by Mark Jelsma
but the are changes by Leon van der veen. */
set_time_limit(60);

// functions
function sudoku_losop($sudoku, $count=3){    // code by Mark Jelsma
    $_emptyCells = array();
    $_candidates = array();
    $column = 0;
    $row = 0;
    $region = 0;
    $eIndex = 0;
    $_ready = false;
    
    for( $i=0; $i<pow($count, 3); $i++ ){
        $_candidates[$i] = (pow(2, pow($count, 2))-1);
    }
    for( $i=0; $i<pow($count, 4); $i++ ){
        if( $sudoku[$i]==0 ){
            $_emptyCells[$eIndex++] = $i;
        } else {
            _getCandidateLists($i, $column, $row, $region, $count);
            _exclude($_candidates[$column], $sudoku[$i]);
            _exclude($_candidates[$row], $sudoku[$i]);
            _exclude($_candidates[$region], $sudoku[$i]);
        }
    }    
    _solve(0, $sudoku, $_emptyCells, $_candidates, $_ready, $count);    
    return $sudoku;
} // sudoku(start_ar)
function isSudoku($sudoku, $count){ // code by Leon van der Veen
    $_column = array();
    $_row = array();
    $_region = array();
    $column = 0;
    $row = 0;
    $region = 0;
    $bool = true;    
    for( $i=0; $i<pow($count, 4); $i++ ){
        if( $sudoku[$i]!=0 ){
            _getCandidateLists($i, $column, $row, $region, $count);
            if( !isset($_column[$column]) ) $_column[$column] = array();
            if( !isset($_row[$row]) ) $_row[$row] = array();
            if( !isset($_region[$region]) ) $_region[$region] = array();
            if( in_array($sudoku[$i], $_column[$column]) ){ $bool = false; break; } else { $_column[$column][] = $sudoku[$i]; }
            if( in_array($sudoku[$i], $_row[$row]) ){ $bool = false; break; } else { $_row[$row][] = $sudoku[$i]; }
            if( in_array($sudoku[$i], $_region[$region]) ){ $bool = false; break; } else { $_region[$region][] = $sudoku[$i]; }            
        }
    }    
    return $bool;
} // isSudoku(sudoku)
function _solve($eIndex, &$sudoku, &$_emptyCells, &$_candidates, &$_ready, $count){ // code by Mark Jelsma
    $column = 0;
    $row = 0;
    $region = 0;    
    if( $eIndex<count($_emptyCells) ){
        _getCandidateLists($_emptyCells[$eIndex], $column, $row, $region, $count);
        for( $i=1; $i<=pow($count, 2); $i++ ){
            if(    _isCandidate($_candidates[$column], $i) &&
                _isCandidate($_candidates[$row], $i) &&
                _isCandidate($_candidates[$region], $i)
            ){
                $sudoku[$_emptyCells[$eIndex]] = $i;
                _exclude($_candidates[$column], $i);
                _exclude($_candidates[$row], $i);
                _exclude($_candidates[$region], $i);
                if( $_ready ) return;
                _solve($eIndex + 1, $sudoku, $_emptyCells, $_candidates, $_ready, $count);
                if( $_ready ) return;
                $sudoku[$_emptyCells[$eIndex]] = 0;
                _include($_candidates[$column], $i);
                _include($_candidates[$row], $i);
                _include($_candidates[$region], $i);
            }
        }
    } else {
        $_ready = true;
    }
} // _solve(eIndex, sudoku, _emptyCells, _candidates, _ready)
function _isCandidate($bitSet, $bit){ // code by Mark Jelsma
    return (($bitSet & (1 << $bit - 1)) == 0) ? false : true;
} // _isCandidate(bitSet, bit)
function _getCandidateLists($position, &$column, &$row, &$region, $count){ // code by Mark Jelsma
    $column = $position % pow($count,2);
    $row = floor(pow($count,2) + $position / pow($count,2));
    $region = floor((pow($count,2)*2) + floor($column / $count) + $count * floor(($row - pow($count,2)) / $count));
} // _getCandidateLists(position, column, row, region)
function _include(&$bitSet, $bit){ // code by Mark Jelsma
    $bitSet |= (1 << $bit - 1);
} // _include(bitSet, bit)
function _exclude(&$bitSet, $bit) { // code by Mark Jelsma
    $bitSet &= ~(1 << $bit -1);
} // _exclude(bitSet, bit)

// html
$count = (isset($_GET['m'])&&is_numeric($_GET['m'])&&($_GET['m']==3 XOR $_GET['m']==4))?$_GET['m']:3;

$body .= "<div style=\"padding:10px;\"><center><font class=\"tit3\">Sudoku oplosser</font></center><br/>";
/////////////////////////////////////////
if( isset($_GET['a']) && $_GET['a']==1 ){
    $htmlprint = false;
    header("Content-type:image/png");
    header("Cache-Control: no-cache, must-revalidate");
    header("Expires: Mon, 26 Jul 1997 05:00:00 GMT");
    //////////////////
    $w = $h = 26 * $count;
    $im = imagecreatetruecolor($w,$h);
    $white = imagecolorallocate($im, 255, 255, 255);
    imagefilledrectangle($im, 1, 1, ($w-2), ($h-2), $white);
    //////////////////
    imagepng($im);
    imagedestroy($im);
} else {
    $start_ar = array();
    $issetbool = true;
    for( $i=0; $i<pow($count, 4); $i++ ){
        if(    isset($_POST['var_'.$i]) ){
            if( is_numeric($_POST['var_'.$i]) && $_POST['var_'.$i]>=1 && $_POST['var_'.$i]<=pow($count,2) ){
                $start_ar[$i] = $_POST['var_'.$i];
            } elseif( $_POST['var_'.$i]=="?" ){
                $start_ar[$i] = 0;
            } else {
                $issetbool = false;
                break;
            }
        } else {
            $issetbool = false;
            break;
        }
    }
    if( $issetbool && isSudoku($start_ar, $count) ){
        $end_ar = sudoku_losop($start_ar, $count);
        $body .= "<table cellspacing=\"0\" cellpadding=\"0\" width=\"100%\"><tr valign=\"top\"><td width=\"". (pow($count,2)*26) ."\">".
        "<table cellspacing=\"0\" cellpadding=\"0\" width=\"". (pow($count,2)*26) ."\" height=\"". (pow($count,2)*26) .
        "\" style=\"background:top left url(".basename($_SERVER['PHP_SELF'])."?a=1&m=".$count.");\"><tr valign=\"top\" height=\"26\">";
        for( $i=0; $i<pow($count, 4); $i++ ){
            $body .= ((($i%pow($count,2))==0&&$i!=0)?"</tr><tr valign=\"top\" height=\"26\">":"") .
            "<td width=\"26\" align=\"center\" valign=\"middle\">". (($end_ar[$i]==$start_ar[$i])?"<font color=\"#FF0000\">".
            $end_ar[$i]."</font>":$end_ar[$i]) ."</td>";
        }
        $body .= "</tr></table></td><td width=\"10\"></td><td>Hier naast staat een oplossing.<br/><br/><a href=\"".
        basename($_SERVER['PHP_SELF'])."?m=".$count."\">Ga terug</a>".
        "</td></tr></table>";
    } else {
        $body .= "<form onSubmit=\"fillempty(".$count.");\" id=\"sudoku_form\" action=\"".basename($_SERVER['PHP_SELF'])."?m=".$count."\" method=\"post\">".
        "<table cellspacing=\"0\" cellpadding=\"0\" width=\"100%\"><tr valign=\"top\"><td width=\"". (pow($count,2)*26) ."\">".
        "<table cellspacing=\"0\" cellpadding=\"0\" width=\"". (pow($count,2)*26) ."\" height=\"". (pow($count,2)*26) .
        "\" style=\"background:top left url(".basename($_SERVER['PHP_SELF'])."?a=1&m=".$count.");\"><tr valign=\"top\" height=\"26\">";
        for( $i=0; $i<pow($count, 4); $i++ ){
            $body .= ((($i%pow($count,2))==0&&$i!=0)?"</tr><tr valign=\"top\" height=\"26\">":"") .
            "<td width=\"26\" align=\"center\" valign=\"middle\">".
            "<input type=\"text\" style=\"font-size:16px; width:24px; height:24px; text-align:center; color:#FF0000; border:1px solid #CCCCCC;\" ".
            "name=\"var_".$i."\" maxlength=\"". strlen(pow($count,2)) ."\" ".
            "id=\"var_".$i."\" onkeyup=\"check_num('var_".$i."');\" ".
            ((isset($_POST['var_'.$i])&&$_POST['var_'.$i]!="")?(($_POST['var_'.$i]!=0)?"value=\"".$_POST['var_'.$i]."\" ":""):"") ."/></td>";
        }
        $body .= "</tr></table><div align=\"right\"><input type=\"button\" onClick=\"clear_sudoku(".$count.");\" value=\"Reset\" />".
        "<input type=\"submit\" value=\"Los op\" />".
        "</div></td><td width=\"10\"></td><td>". ($issetbool?"<font color=\"#FF0000\">Je hebt de sudoku niet goed ingevuld.</font><br/>":"") .
        "Vul hiernaast de getallen in die je al weet.<br/>".
        "</td></tr></table></form>";
    }
}
/////////////////////////////////////////
$body .= "</div>"; 
?>
<html>
    <head>
        <title>Sudoku Oplosser</title>
        <script language="javascript" type="text/javascript">
            var numb = '0123456789';
            var lwr = 'abcdefghijklmnopqrstuvwxyz';
            var upr = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
            function is_numeric(str){ return isNum(str); }
            function isValid(parm,val){
                if( parm=="" ) return true;
                for( i=0; i<parm.length; i++ ){
                    if( val.indexOf(parm.charAt(i),0)==-1) return false;
                }
                return true;
            }
            function isNum(parm) {return isValid(parm,numb);}
            function isLower(parm) {return isValid(parm,lwr);}
            function isUpper(parm) {return isValid(parm,upr);}
            function isAlpha(parm) {return isValid(parm,lwr+upr);}
            function isAlphanum(parm) {return isValid(parm,lwr+upr+numb);}
            function fillempty(count){
                for( var i=0; i<Math.pow(count, 4); i++ ){
                    document.getElementById('var_'+i).value = ((document.getElementById('var_'+i).value=='')?'?':document.getElementById('var_'+i).value);
                }
            }
            function check_num(id){
                var obj = document.getElementById(id);
                var str = obj.value;
                if( str!="" && !is_numeric(str) ){
                    obj.value = '';
                    alert("Alleen getallen!!");
                }
            }
            function clear_sudoku(count){
                for( i=0; i<Math.pow(count, 4); i++ ){
                    document.getElementById('var_'+i).value = '';
                }
            }
        </script>
    </head>
    <body>
        <?=$body;?>
        
    </body>
</html>
11-05-2010 18:55

Wat heb je nu veranderd sinds de versie uit 2006? Je changelog is namelijk erg leeg, staat alleen iets uit februari in, maar welk jaar etc?

1
.
18-09-2010 00:04

Ik dacht al dat ik m herkende. Ik gebruik m al JAAAREN (beste die ik ooit ben tegengekomen :)) KUDO's!!

Een leuke implementatie: http://games.hotblocks.nl/136

Nieuwe Topics

Scripts

Wiki's

Vacatures

Nieuwsberichten

Software Updates

Inloggen wachtwoord vergeten? Aanmelden