Sudoku

donderdag 29 december 2005 @ 21:22:34 #51

ThE_ED

engu twiekur

quote:
Op donderdag 29 december 2005 21:16 schreef thabit het volgende:

[..]

Wat wordt de regel dan precies?

Hmm, nee wacht, slaat niet echt ergens op

Is eigenlijk gewoon de volgende iteratie van jouw idee zoasl ik het nu omschreven heb.
Ik snap eigenlijk nog niet echt hoe jouw idee fout zou kunnen gaan want dit zijn toch gewoon de sudokuregels zou je zeggen. Ik denk dat je meer blokken aan elkaar moet relateren toch, maar ik heb het nu teveel proberen te versimpelen zie ik al.

_{gaat weer terug naar het wiskundeklas :S}

edit; Ik zit nu nog even te denken hoe ik een sudoku maak (die twee keer dat ik dat gedaan heb) dan doe ik iig altijd;

1
2
3

AAABBBBBB
CCCDDDDDD
EEEFFFFFF

Als een getal in A zit dan zit ie iig ook in de D rij/kolom en in de F rij/kolom

[ Bericht 4% gewijzigd door ThE_ED op 29-12-2005 21:29:41 ]

[KNE]-Mod

vrijdag 30 december 2005 @ 11:43:03 #52

JohnDDD

Hallo. Ik heb niet het hele topic gelezen, maar ik wilde even zeggen;
persoonlijk doe ik de makkelijke en gemiddelde sudoku's altijd zonder het maken van extra notities, dwz, ik struin gewoon alle kolommen, rijen en blokjes af en kom zo tot de oplossing.

ik heb ook de moeilijkste sudoku's gedaan van The Daily Mirror
daar zitten echt heel erg pittige tussen

daar moet je haast wel gaan noteren.

dan vind je dus op een gegeven moment wel een rij, kolom of blok waarbij de situatie zo is, dat er óf maar 1 bepaald getal is dat in een bepaald vakje past, of dat er maar 1 bepaald vakje is waar een bepaald getal in past.

maar soms werkt dat ook niet helemaal lekker.

er zijn ook moeilijker oplossingen mogelijk.

een goed voorbeeld is bijvoorbeeld, dat je erachter komt dat de 7 in het blokje rechtsboven helemaal bovenaan moet zitten, maar je weet niet waar. je komt erachter dat de 7 in het blokje linksboven helemaal onderaan moet zitten, maar je weet niet waar. dan weet je dus dat in het middelste blokje bovenaan de 7 ergens in het midden zit.

zo moet je soms dingen combineren en dan was dit nog een vrij simpel voorbeeld.

het kan ook heel fijn zijn om bijv. te zien dat in het blok linksboven nog 1, 2 en 4 missen. als je er dan achterkomt dat die alleen maar helemaal links kunnen zitten, weet je dat de overige zes vakjes van de linker kolom níet de cijfers 1, 2 en 4 bevatten maar dus 3, 5, 6, 7, 8 en 9.

vaak kun je dan ook al cijfers invullen.

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

woensdag 1 februari 2006 @ 16:15:41 #53

marq

Mr. Psychonaut

quote:
Op woensdag 28 december 2005 23:28 schreef gexxz het volgende:
Een vriend van me heeft er een programmaatje voor geschreven

hihi, heb je t over mij??

ik heb zojuist de mn 4e algoritme voor het laatst geoptimaliseerd en het is nu met extreem moeilijke sudoku's nog steeds retesnel. de standaard sudoku's worden sowieso binnen 0.01 seconden opgelost als je computer > 1500MHz is.

om mn talenkennis te verbreden heb ik ervoor gekozen om het dit keer in C# te doen mbv mono onder linux.

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

using System;
using System.Collections;

namespace StateSolvingTest {

    class StateSolvingTest {
        /// Private attributes ///

        // Holds the list of empty cells
        private int[] emptyCells = new int[81];

        // Holds the 27 candidate lists 1..9
        private BitArray[] candidates = new BitArray[27];

        // Holds the sudoku as a linear array
        private int[] pattern = new int[81];

        // True when a solution has been found
        private bool ready;

        /// Properties ///

        public int[] Pattern {
            get {
                return pattern;
            }

            set {
                pattern = value;
            }
        }

        /// Constructors ///

        public StateSolvingTest() {
            // Instantiate the candidatelists
            for (int i = 0; i < 27; i++) {
                candidates[i] = new BitArray(10);
            }
        }

        /// Public methods ///

        public void FindSolution() {
            // Holds the indices of the candidatelists
            int column = 0;
            int row = 0;
            int region = 0;

            // Temporary store all empty cells
            ArrayList tempList = new ArrayList();

            // Fill the candidate lists with all 9 bits set
            for (int i = 0; i < 27; i++) {
                candidates[i].SetAll(true);
            }

            // Exclude invalid candidates from the lists and get empty cells
            for (int i = 0; i < 81; i++) {
                if (pattern[i] != 0) {
                    // Check which arraylists to remove from
                    GetCandidateLists(i, ref column, ref row, ref region);

                    candidates[column].Set(pattern[i], false);
                    candidates[row].Set(pattern[i], false);
                    candidates[region].Set(pattern[i], false);
                } else {
                    tempList.Add

;
                }
            }

            // Copy the list into an int[]
            emptyCells = new int[tempList.Count];
            tempList.CopyTo(emptyCells);

            // Set the ready flag to false
            ready = false;

            // Run the backtracking method from position 0
            FindSolution(0);
        }

        // Recursive backtracking algorithm
        private void FindSolution(int eIndex) {
            // Holds the indices of the candidatelists
            int column = 0;
            int row = 0;
            int region = 0;

            // Check if we are before the end of the pattern
            if (eIndex < emptyCells.Length) {

                // Get the corresponding candidatelists
                GetCandidateLists(emptyCells[eIndex], ref column, ref row, ref region);

                // Testing 1..9
                for (int i = 1; i < 10; i++) {
                    // Check if the candidate exists in the corresponding lists
                    if (candidates[column].Get

&& candidates[row].Get

&& candidates[region].Get

) {
                        // Add the number to the pattern
                        pattern[emptyCells[eIndex]] = i;

                        // Exclude this number from the corresponding candidatelists
                        candidates[column].Set(i, false);
                        candidates[row].Set(i, false);
                        candidates[region].Set(i, false);

                        // Don't advance if a solution has been found
                        if (ready) return;

                        // Advance to the next cell
                        FindSolution(eIndex + 1);

                        // Don't revert if a solution has been found
                        if (ready) return;

                        // Reset the cell
                        pattern[emptyCells[eIndex]] = 0;

                        // Put the tested number back into the candidatelists
                        candidates[column].Set(i, true);
                        candidates[row].Set(i, true);
                        candidates[region].Set(i, true);
                    }
                }
            } else {
                // A solution has been found, get out of recursion
            ready = true;
            }
        }

        // Obtain the corresponding candidatelists
        private void GetCandidateLists(int position, ref int column, ref int row, ref int region) {
            column = position % 9;
            row = 9 + position / 9;
            region = 18 + column / 3 + 3 * ((row - 9) / 3);
        }

        public void DisplayPattern() {
            for (int i = 0; i < 81; i++) {
                if (i % 9 == 0) {
                    Console.Write("\n\t");
                }
                Console.Write(pattern[i]);
            }

            Console.WriteLine();
        }

        public static void Main(String[] args) {
            Console.WriteLine("StateSolvingTest v0.1");
            Console.WriteLine("Code by Markus\n");

            StateSolvingTest sst = new StateSolvingTest();

            int[] pattern = {   0,7,0,0,0,3,2,0,0,
                                0,0,5,6,9,0,0,0,0,
                                0,0,0,0,0,0,0,0,0,
                                0,0,0,0,8,0,7,0,3,
                                0,0,4,0,0,0,8,0,0,
                                9,0,1,0,2,0,0,0,0,
                                0,0,0,0,0,0,0,0,0,
                                0,0,0,0,5,8,4,0,0,
                                0,0,6,4,0,0,0,1,0};

            sst.Pattern = pattern;

            DateTime startTime = DateTime.Now;

            sst.FindSolution();

            TimeSpan elapsed = DateTime.Now - startTime;
            Console.WriteLine("\tExecution time: {0}s", elapsed.TotalSeconds.ToString());

            sst.DisplayPattern();
        }

    }

}

mocht iemand dit willen gebruiken..
dit is een console applicatie.. strip de Main en de ShowPattern en je houdt de klasse over die al het werk voor je doet. In de Main kun je zien hoe de klasse te benaderen..

voor andere rommel

http://mark.space.servehttp.com/sudoku/

EDIT
overal waar dat domme blauwe ietje staat moet ( i ) staan (zonder spaties als t een beetje kan

[ Bericht 0% gewijzigd door marq op 01-02-2006 16:28:36 ]

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

woensdag 1 februari 2006 @ 16:21:34 #54

marq

Mr. Psychonaut

quote:
Op donderdag 29 december 2005 15:18 schreef ThE_ED het volgende:
Ik vraag me af wat nou (voor een computer) de snelste manier van oplossen is (als we even een database met alle mogelijkheden niet meerekenen.) zelf zou ik het zo aanpakken als TS denk ik. Zo ver kom ik nog wel met mijn beperkte wiskundige vermogens, maar blijkbaar is dat nog niet helemaal sluitend.

Er zijn enorm veel verschillende methodes om ze op te lossen.. BruteForce (recursief backtracken) is de meest voorkomende manier, maar de een backtrackt heel anders dan de andere. Ik heb bv verschillende backtrackers geschreven maar mn 3e manier van aanpak is dan weer vele malen efficienter.

de meest snelle manier is nog altijd Donald Knuth's Dancing Links!

http://mark.space.serveht(...)ncingLinks-paper.pdf

let wel op dat het echt geen flikker met rekenen heeft uit te maken. het is PUUR logica. vergelijken van getallen, elimineren van kandidaten.. niks rekenen of wiskunde.

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

woensdag 1 februari 2006 @ 16:24:28 #55

marq

Mr. Psychonaut

quote:
Op donderdag 29 december 2005 20:42 schreef soulsurvivor het volgende:
Als je dit spel kan kraken met simpele formules is er volgens mij gelijk geen reet meer an.

er is geen `simpele formule` om dit op te lossen. want met formules reken je, en met sudoku's niet.

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

woensdag 1 februari 2006 @ 16:28:47 #56

thabit

quote:
Op woensdag 1 februari 2006 16:15 schreef marq het volgende:

[..]

hihi, heb je t over mij??

ik heb zojuist de mn 4e algoritme voor het laatst geoptimaliseerd en het is nu met extreem moeilijke sudoku's nog steeds retesnel. de standaard sudoku's worden sowieso binnen 0.01 seconden opgelost als je computer > 1500MHz is.

om mn talenkennis te verbreden heb ik ervoor gekozen om het dit keer in C# te doen mbv mono onder linux.
[ code verwijderd ]

mocht iemand dit willen gebruiken..
dit is een console applicatie.. strip de Main en de ShowPattern en je houdt de klasse over die al het werk voor je doet. In de Main kun je zien hoe de klasse te benaderen..

voor andere rommel

http://mark.space.servehttp.com/sudoku/

Hoe moet je dit compileren?

woensdag 1 februari 2006 @ 16:35:19 #57

marq

Mr. Psychonaut

ik gebruik mono
compile : mcs StateSolvingTest.cs
run : mono StateSolvingTest.exe

hoewel ik geen windows gebruik is dit wel gewoon met de .NET compiler te doen die je bij Visual Studio .NET krijgt.

als je de Main eruit stript kan ie iig niet meer compileren als exe want dan heeft ie geen `entrance`

eventueel kun je mono voor windows gaan installeren of visual studio .NEt gebruiken, maar daar heb ik nog nooit mee gewerkt

het is eigenlijk bedoeld als klasse binnen een sudoku programma met interface enzo..

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

woensdag 1 februari 2006 @ 16:41:47 #58

thabit

Ik heb ook geen windows, dus dat komt goed uit.

. Interfaces interesseren me ook geen donder, dus ook dat komt goed uit.

Ik zou trouwens een algoritme dat recursief backtrackt wel rekenen willen noemen. Rekenen doe je niet alleen maar met getallen of formules.

woensdag 1 februari 2006 @ 16:46:05 #59

marq

Mr. Psychonaut

naja, dan moet je mono zeker installeren.. geef 't ding een naam en met mcs kun je hem echt in 1x compileren.

maar het enige echte rekenwerk in bovnestaande code is het bereken van de corresponderende kandidaat lijsten.. misschien hebben we beide een andere definitie voor rekenen aangezien ik dit neit als berekenen bestempel

http://www.vandale.nl/opzoeken/woordenboek/?zoekwoord=rekenen

re·ke·nen1 (onov.ww.)
1 met getallen, cijfers werken, volgens de regels hoeveelheden, aantallen benoemen, samenstellen en ontbinden => cijferen

vandale is het wel een beetje met jou eens

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

woensdag 1 februari 2006 @ 16:53:40 #60

thabit

Je zou je implementatie denk ik zelfs nog iets sneller kunnen maken door bitrepresentaties te gebruiken voor je kandidatenlijstje. Dan hoef je niet alle kandidaten af te gaan, maar verzamel je gewoon met een or-operator alles wat je al hebt en dan elimineer je dat met and(not) in de cel waarmee je bezig bent.

woensdag 1 februari 2006 @ 17:01:29 #61

marq

Mr. Psychonaut

die implementatie gebruik ik in mijn MSX versie. AND om te controleren of de bit TRUE is, bitshift, inversie en AND/OR om ze te setten/unsetten.

hier gebruik ik de BitArray om dit te doen, de C# library voorziet hier in en is vele malen sneller dan conventionele lijsten (ArrayList). Dus wat je zegt, is al reeds geimplementeerd

in een eerdere versie van deze 3e aanpak had ik nog wel gewoon ArrayLists maar toen was ie ook een stuk trager

mocht ik dit nog niet weten, dan zou ik je post als enorm waardevol beschouwen

hihihi

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

woensdag 1 februari 2006 @ 17:05:59 #62

thabit

Ah, okee. Ik ken C# niet.

.

woensdag 1 februari 2006 @ 17:09:09 #63

Invictus_

Religieuze Minderheid

quote:
Op woensdag 28 december 2005 21:38 schreef thabit het volgende:
Regel 1. Stel je hebt een verzameling cijfers S en een rij/kolom/blok waarvoor geldt dat het aantal vakjes v met a(v) deelverzameling van S minstens gelijk is aan het aantal elementen van S, dan mag je in alle andere vakjes van je rij/kolom/blok de cijfers van S wegstrepen.

Staat hier niet gewoon ieder getal mag maar één keer voorkomen in elke rij, kolom en blok maar dan onduidelijker?

Now I'm walking on the sunnyside of the street

woensdag 1 februari 2006 @ 17:11:46 #64

thabit

quote:
Op woensdag 1 februari 2006 17:09 schreef Invictus_ het volgende:

[..]

Staat hier niet gewoon ieder getal mag maar één keer voorkomen in elke rij, kolom en blok maar dan onduidelijker?

Nee, het is een generalisatie van die regel.

woensdag 1 februari 2006 @ 17:12:11 #65

marq

Mr. Psychonaut

quote:
Op woensdag 1 februari 2006 17:05 schreef thabit het volgende:
Ah, okee. Ik ken C# niet. .

dat maakt niet uit. je ontbeert het inzicht kennelijk niet anders had je me die tip nooit gegeven

C# is de `java` van microsoft. niet echt geweldig aangezien de heren van het mono project gedwongen zijn de boel te `reverse engineren`.

maar ja, een beetje programmeur verbreedt zijn talenkennis

*kuch*

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

woensdag 1 februari 2006 @ 17:13:33 #66

JapyDooge

NoxiousPluK

quote:
Op woensdag 28 december 2005 22:10 schreef Angel_of_Dth het volgende:

[..]

Het stond enkele weken terug in een computerblad dat een oud-leraar van me op het perron stond te lezen.

PC-Active

* JapyDooge heeft

maar het was niet 'simpel'

EVE Online: CEO van Jovian Legacy, alliance executor van Jovian Empire. Join 'JOVLEG Public' ingame. Blink spelen? http://cogdev.net/blink/ gebruik referalcode 'jovianblink' voor gratis startcredits. IRC

woensdag 1 februari 2006 @ 17:15:01 #67

nubie

http://www.sudokusolver.co.uk/

maandag 13 februari 2006 @ 21:22:23 #68

McCarthy

communistenjager

quote:
Op donderdag 29 december 2005 19:19 schreef thabit het volgende:

[..]

Ik neem aan dat met "zonder gokwerk" bedoeld wordt dat de oplossing eenduidig is.

ik dacht dat er sudoku's waren met meerdere oplossingen.

Je moet trouwens prolog gebruiken. Kan je vrij makkelijk dit soort backtracking problemen mee solven (denk ik). Zal eens kijken wat ik kan.

Het nationaal product is hetzelfde als een taart waar uiteraard iedereen recht op heeft, als overheden met geld smijten heet het investeren en als bedrijven investeren heet het een sprinkhanenplaag. McCarthy

maandag 13 februari 2006 @ 21:25:58 #69

McCarthy

communistenjager

quote:
Op woensdag 1 februari 2006 16:15 schreef marq het volgende:

[..]

hihi, heb je t over mij??

ik heb zojuist de mn 4e algoritme voor het laatst geoptimaliseerd en het is nu met extreem moeilijke sudoku's nog steeds retesnel. de standaard sudoku's worden sowieso binnen 0.01 seconden opgelost als je computer > 1500MHz is.

om mn talenkennis te verbreden heb ik ervoor gekozen om het dit keer in C# te doen mbv mono onder linux.
[ code verwijderd ]

mocht iemand dit willen gebruiken..
dit is een console applicatie.. strip de Main en de ShowPattern en je houdt de klasse over die al het werk voor je doet. In de Main kun je zien hoe de klasse te benaderen..

voor andere rommel

http://mark.space.servehttp.com/sudoku/

EDIT
overal waar dat domme blauwe ietje staat moet ( i ) staan (zonder spaties als t een beetje kan

wat gebruikte je eerst dan?

Het nationaal product is hetzelfde als een taart waar uiteraard iedereen recht op heeft, als overheden met geld smijten heet het investeren en als bedrijven investeren heet het een sprinkhanenplaag. McCarthy

maandag 13 februari 2006 @ 21:33:30 #70

thabit

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

[..]

ik dacht dat er sudoku's waren met meerdere oplossingen.

Natuurlijk. Bijvoorbeeld de sudoku waar in het begin nog niets ingevuld is.

maandag 13 februari 2006 @ 22:06:58 #71

Schonedal

De makkelijkste manier om sudoku`s op te lossen is als volgt:
Je hebt alleen een pen en de opgave zelf nodig.
Maak gebruik van punten.
Elk punt stelt een cijfer voor, links boven 1, midden boven 2, rechtsboven 3, links midden 4, midden midden 5, enzovoort net zo als de toetsen van je mobieltje.
Staat er dus ergens een 1, maak dan punten links boven in alle hokjes die daar op betrekking hebben.
Maak echter ook een puntje in het hokje van de gegeven 1 zelf, dan weet je waar je gebleven bent als je even naar de wc moet.
doe dat met alle gegevens.
Ga dan na of er hokjes met 8 ingevulde punten zijn, het ontbrekende puntje geeft aan welk cijfer je in moet vullen.
Vul bij elk gevonden cijfer meteen alle punten in, in de hokjes die daar weer betrekking op hebben.
Houdt het dan op om op deze wijze cijfers te vinden ga dan "vissen".
Dit houdt in dat je in elke regel, kolom of vierkant 3x3 nagaat of van de cijfers 1 tem 9 er een puntje ontbreekt.
Het komt een enkele keer voor dat je moet gokken.
Dit houdt in dat je in een hokje waar 2 punten ontbreken een van de twee mogelijke getallen invult.
Doe dat met potlood want blijkt dat je het verkeerde hebt gekozen dan kun je het weer uitgummen.
Probeer dan de andere mogelijkheid.
Eigenlijk vindt ik sudoku`soplossen niks meer aan.
De enige reden waarom ik dagelijks de sudoku uit de krant oplos is om mijn nauwkeurigheid scherp te houden.

maandag 13 februari 2006 @ 23:55:38 #72

P8

quote:
Op maandag 13 februari 2006 22:06 schreef Schonedal het volgende:Het komt een enkele keer voor dat je moet gokken.

dat ben ik nog nooit tegen gekomen in een sudoku.
als je moet gokken heb je iets over het hoofd gezien

Extremistisch gematigd.

dinsdag 14 februari 2006 @ 00:00:23 #73

DionysuZ

Respect my authority!

inderdaad. Iedere sudoku is zo opgebouwd dat hij op te lossen is zonder gokwerk.

□ 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 @ 09:10:37 #74

JohnDDD

ik vraag me wel af wat men nog onder gokken verstaat
kijk als je op een gegeven moment drie posities hebt in een rij waarin een drie kan komen te staan en je volgt dan logischerwijs voor elk van die mogelijkheden de gevolgen van het plaatsen van een 3 en je komt tot de conclusie dat ie maar in één van de vakjes kan staan, is dat dan gokken?

dan hangt "gokken" blijkbaar af van je genialiteit, dwz je vermogen tot het "uitrekenen" van de gevolgen van een bepaalde "zet", zoals een schaakcomputer ook kan bijv.

er zijn bijv. mogelijkheden bij het invullen van een sudoku om te zien dat bijv. een 7 alleen links kan zitten in een vierkantje
als je dan van het vierkant daar twee boven weet dat de 7 alleen rechts kan zitten, zit ie bij de driehoek daartussenin dus in het midden. dan kun je naar rechts kijken en als daar de 7 bovenaan moet komen (wat je ook nog eens kunt bepalen door twee andere vierkanten), weet je dat ie bij het vierkant daar weer rechts van in het midden of onderaan moet komen, en links ook.

nou ja zo kun je doorgaan

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 @ 15:26:46 #75

P8

quote:
Op dinsdag 14 februari 2006 09:10 schreef JohnDDD het volgende:
ik vraag me wel af wat men nog onder gokken verstaat
kijk als je op een gegeven moment drie posities hebt in een rij waarin een drie kan komen te staan en je volgt dan logischerwijs voor elk van die mogelijkheden de gevolgen van het plaatsen van een 3 en je komt tot de conclusie dat ie maar in één van de vakjes kan staan, is dat dan gokken?

dan hangt "gokken" blijkbaar af van je genialiteit, dwz je vermogen tot het "uitrekenen" van de gevolgen van een bepaalde "zet", zoals een schaakcomputer ook kan bijv.

er zijn bijv. mogelijkheden bij het invullen van een sudoku om te zien dat bijv. een 7 alleen links kan zitten in een vierkantje
als je dan van het vierkant daar twee boven weet dat de 7 alleen rechts kan zitten, zit ie bij de driehoek daartussenin dus in het midden. dan kun je naar rechts kijken en als daar de 7 bovenaan moet komen (wat je ook nog eens kunt bepalen door twee andere vierkanten), weet je dat ie bij het vierkant daar weer rechts van in het midden of onderaan moet komen, en links ook.

nou ja zo kun je doorgaan

ik snap geen hol van je hele post

maar gokken is als je een cijfer moet invullen terwijl je nog niet weet of die wel of niet op die plek hoort. Als je moet gokken betekent dat dat iets buiten je beredeneerskillz ligt, of dat je iets over het hoofd hebt gezien.
en volgens mij hoef je nooit verder te kijken dan "1 zet verder" als je de keuze hebt uit 2 vakjes voor 1 cijfer. Maar ook nu ik dit schrijf vraag ik me dit hard af, omdat zulke situaties ook van de andere kant bekeken kunnen worden (--> uitsluiten dat een cijfer niet in een hokje past)

Extremistisch gematigd.

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