Sudoku

dinsdag 14 februari 2006 @ 19:36:46 #76

JohnDDD

nou ik vraag me dus in feite af...kijk je kunt een sudoku vakje voor vakje invullen...maar als je nou heel intelligent bent, dan kun je alles in feite doorrekenen. dan hoef je dus niets in te vullen maar dan bekijk je dus elke mogelijke gok. stel dat je dan zou zeggen: wat als ik hier een 3 invul? dan komt daar een 4, en dan daar een 3, en daar een 7 en 8. en dan daar een 9 en daar ook een 9 en een 1. en dan heb je dat hele ding in je hoofd, en dan kom je tot de conclusie dat het niet kan.

dus dan vul je geen drie in. is dat dan gokken?

ik neem aan van wel dus, en dat het erom gaat om eigenlijk helemaal geen theorieën te vormen en op basis van uitsluiting te werken. maar toch is ook uitsluiting een theorie; je zegt namelijk "kan de 3 hier? nee. kan ie hier? nee. dan moet ie dus hier."

zelf gebruik ik wel graag, wat ik probeerde uit te leggen, manieren om sneller dingen in te kunnen vullen. een beetje kris-kras kijken door de sudoku heen.

ik gebruik mijn pen ook alleen om cijfers in te vullen die ik zeker weet. ik schrijf geen mogelijkheden op. behalve bij moeilijke.

Gaat voor de BHFH-award 2005!
Humanitas est in bestias bonitas.
I am the hole I can't get out of.

dinsdag 14 februari 2006 @ 19:42:58 #77

DionysuZ

Respect my authority!

dat is niet gokken

dat is beredeneren. Gokken is gewoon 'iene miene mutte' die vul ik in.

ik schrijf overigens ook geen mogelijkheden op. Ik schrijf wel cijfertjes naast de sudoku die ik al overal heb gehad. Als in alle vakken een 6 zit dan schrijf ik die dus op, dan hoef ik die niet meer te bekijken

□ Reality is merely an illusion,albeit a very persistent one-A.Einstein
■ Of ik ben gek of de rest van de wereld.Ik denk zelf de rest van de wereld-Rudeonline
□ The war is not meant to be won.It is meant to be continuous-G.Orwell

dinsdag 14 februari 2006 @ 19:46:14 #78

JohnDDD

dat is wel handig ja

Gaat voor de BHFH-award 2005!
Humanitas est in bestias bonitas.
I am the hole I can't get out of.

dinsdag 14 februari 2006 @ 19:46:50 #79

-J-D-

tvp

I asked God for a bike, but I know God doesn't work that way.
So I stole a bike and asked for forgiveness.

dinsdag 14 februari 2006 @ 20:17:01 #80

marq

Mr. Psychonaut

quote:
Op maandag 13 februari 2006 21:25 schreef McCarthy het volgende:

[..]

wat gebruikte je eerst dan?

talen bedoel je?
*kuch*
VB6.0, MSXBASIC, Z80 ASM, Java, PHP, C, Javascript

ik houd niet zo van VB6.0 en van Javascript

Sigmoid: f(x) = 1 / (1 + 2.718281828458# ^ -x)

dinsdag 14 februari 2006 @ 20:21:41 #81

marq

Mr. Psychonaut

mwah, dan willen jullie vast ook wel de PHP versie van mn StateSolver dacht ik zo...

voorbeeld - 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

<?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 />';
            }
        }
    }

?>

de klasse zelf

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

<?php

    /*  Sudoku State Solver v0.1 [04-feb-2006]
        --------------------------------------
            All code by Mark Jelsma
    */

    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;
        }

    }

?>

zoek het maar uit!

uitleg:
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.

deze uitleg hoort eigenlijk bij de C# versie ergens boven deze post maar is ook van toepassing op de PHP versie..

naja, snel verder met coden want er is meer te doen:)

Sigmoid: f(x) = 1 / (1 + 2.718281828458# ^ -x)

woensdag 1 maart 2006 @ 21:26:33 #82