Goed. Wat je nu doet als je zo'n sudoku probeert op te lossen is in elk vakje alle cijfers opschrijven die daar nog mogelijk zouden kunnen staan en dan doormiddel van logisch denkwerk steeds meer van die mogelijkheden doorstrepen. Laten we de mogelijkheden voor een vakje v noteren met a(v).
Okee, ik heb nu 2 basisregels bedacht die je kunt gebruiken om cijfers door te strepen.
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.
Regel 2. Beschouw de volgende situatie, bestaande uit een rij of kolom en een blok:
| 1 2 3 | CCC CCC |
In dit plaatje mag de rij best in het midden staan of een kolom zijn. De regel is nu: als een bepaald cijfer niet meer in B voor kan komen, dan moet het in A voorkomen en kan het dus niet in C voorkomen. Hetzelfde met B en C omgewisseld.
De vraag is nu: zijn deze twee regels voldoende om elke sudoku op te lossen (ervan uitgaande dat we met een sudoku te maken hebben die een eenduidige oplossing heeft)?
Met de hand deze regels toepassen is erg omslachtig. Het lukt mij in elk geval niet. Ik ben te langzaam en te slordig daarvoor. Een computer is echter snel en precies dus ik heb een computerprogrammaatje geschreven dat herhaaldelijk op alle mogelijke manieren de regels 1 en 2 toepast totdat het de sudoku heeft opgelost. Het mooie is: elke sudoku die ik erin heb gestopt heeft het weten op te lossen.
Ik heb ook nog geen bewijs gewonden dat het waar is. Niet eens geprobeerd omdat ik nog niet overtuigd genoeg ben. Zijn hier sudoku-beoefenaars die er meer van weten? Zijn er sudoku's waarbij je echt cijfertjes moet uitproberen anders kun je er niet uitkomen?
Ik heb 't geprobeerd maar ik ben blond. Dus hou ik er maar mee op :-D :-D
quote:Laat ik deze regel even toelichten aan de hand van een paar voorbeelden.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.
Stel in een rij/kolom/blok weten we ergens dat het cijfer 7 staat. Als we deze regel dan toepassen met S=7 dan kunnen we in de andere vakjes daar de 7 doorstrepen.
Ander voorbeeld. Stel we hebben een rij/kolom/blok met de volgende mogelijkheden:
12, 23, 31, 14567, 2789, 3456, 12789, 6789, 4579.
Als we dan S=123 toepassen zien we dat de cijfers 1,2 en 3 wel verdeeld moeten zijn over de eerste 3 vakjes en kunnen we ze bij de andere vakjes wegstrepen tot
12, 23, 31, 4567, 789, 456, 789, 6789, 4579.
Derde voorbeeld. Stel we hebben de volgende mogelijkheden in een rij/kolom/blok:
123456, 2345, 3456, 4567, 6789, 2356, 347, 679, 289.
We zien dat alleen in het eerste vakje nog een 1 kan staan. Dat vakje moet dus wel een 1 zijn. De rest van de cijfers krijgen we dan ook weggestreept door S=23456789 toe te passen en zo krijgen we
1, 2345, 3456, 4567, 6789, 2356, 347, 679, 289.
quote:Heb je hier ook een bron van?Op woensdag 28 december 2005 22:03 schreef -jos- het volgende:
Ehm, ik vind het wel een leuk idee maar volgens mij kun je elke sudoku gewoon met een simpel excel file-tje oplossen, heb ik gelezen ergens
quote:Jij bent grappig, maar inderdaad een beetje simpel als je niet eens een beetje kan Sudoku'en.Op woensdag 28 december 2005 21:57 schreef tass het volgende:
Ik ben gek op rekenspelletjes, maar van het hele sudoku of zo, snap ik echt geen ene bal!!!
Ik heb 't geprobeerd maar ik ben blond. Dus hou ik er maar mee op :-D :-D
quote:Het stond enkele weken terug in een computerblad dat een oud-leraar van me op het perron stond te lezen.
quote:Ik denk dat hij een of ander computerblad bedoelde, daar stond schijnbaar in hoe random Sudoku's kon laten maken doormiddel van een excel sheet. Maar opzich is het niet heel moeilijk om op te lossen doormiddel van een programmatje te schrijven voor je rekenmachine, iig een maat van hem deed dat nog vrij rap
quote:ff op google gezocht ( op excel sudoku oplosser )
http://www.gewoongertjan.nl/archives/34
http://members.home.nl/f.petry/Downloads.htm
Zijn jouw regels ook voldoende voor die Sudoku?
quote:Hmm, nee. Niet voor die. Er moeten dus nog regels bij. Vooral regel 2 moet algemener.Op woensdag 28 december 2005 22:29 schreef Zap het volgende:
Klik hier: http://www.stolaf.edu/people/hansonr/sudoku eens op Hardest (rechtsboven).
Zijn jouw regels ook voldoende voor die Sudoku?
quote:Als je per vakje zou bijhouden welke getallen er niet meer in zouden kunnen staan, vind je vanzelf vakjes waarvoor alle mogelijkheden uitgeput zijn. Bij een moeilijke soduko ontkom je er denk ik echter niet aan om eerst puur op de gok bijv. drie vakjes in te vullen. Je hebt dan 1000 mogelijkheden, en bij een van de mogelijkheden kom je met de andere regel tot een oplossing.Op woensdag 28 december 2005 23:05 schreef thabit het volgende:
De beginsituatie is al een probleem.
De vraag is natuurlijk weer of het toevoegen van dat patroon genoeg is, en of je wel elke soduko kunt oplossen met 3 vakjes (bij elkaar of random?) proberen in te vullen..
Het lijkt me een goed startpunt voor een algoritme om die Sudokupuzzels te kunnen oplossen.
quote:Ik was altijd onder de indruk dat je er met "simpel" wegstrepen wel kon komen, als je moet gaan gokken is het toch niet echt een leuk spel meer, lijkt me. Je moet er toch rekenkundig uit kunnen komen.Op donderdag 29 december 2005 08:10 schreef Alicey het volgende:
[..]
Bij een moeilijke soduko ontkom je er denk ik echter niet aan om eerst puur op de gok bijv. drie vakjes in te vullen.
Meestal is dat echter niet nodig.
quote:Zelfs de allermoeilijkste soduku's kunnen zonder gokwerk opgelost worden.Op donderdag 29 december 2005 08:10 schreef Alicey het volgende:
[..]
Als je per vakje zou bijhouden welke getallen er niet meer in zouden kunnen staan, vind je vanzelf vakjes waarvoor alle mogelijkheden uitgeput zijn. Bij een moeilijke soduko ontkom je er denk ik echter niet aan om eerst puur op de gok bijv. drie vakjes in te vullen. Je hebt dan 1000 mogelijkheden, en bij een van de mogelijkheden kom je met de andere regel tot een oplossing.
De vraag is natuurlijk weer of het toevoegen van dat patroon genoeg is, en of je wel elke soduko kunt oplossen met 3 vakjes (bij elkaar of random?) proberen in te vullen..
quote:Dat is een feit?Op donderdag 29 december 2005 15:15 schreef DionysuZ het volgende:
[..]
Zelfs de allermoeilijkste soduku's kunnen zonder gokwerk opgelost worden.
quote:Anders is het geen Sudoku.
quote:Bij het maken van een opgave moet het computerprogramma eerst een oplossing in mekaar knutselen d.m.v. random-verdelingen van de 9 cijfers en toetsing van de rij-kolom-blok-compatibiliteit. Zodra een nieuwe oplossing is gevonden moet ze omgezet worden naar een opgave door er (eveneens random) een aantal cijfers van vrij te geven. Het computerprogramma moet dan nagaan of de vrijgegeven cijfers toelaten de puzzel op te lossen. Is dat niet het geval dan kan een bijkomend cijfer vrijgegeven worden (en telkens weer een volgend) tot de puzzel zonder gokken oplosbaar is.
quote:Het lijkt me wel logisch, op zich. Als je moet gaan gokken, is er toch niks uitdagends meer aan? Het is juist de truc om het met flink zoeken op te lossen, niet met mazzel.
quote:Brengt je wel op de vraag wanneer een sudoku als gokken wel was toegestaan makkelijker gaat worden naarmate je meer symbolen weglaat. Je krijgt dan, heb ik het idee, nl meer mogelijkheden op een gegeven moment. Zo is een geheel lege sodoku vast makkelijker als eentje met een heel stel cijfers al fixed erin.
quote:Bekijk de source van bestaande sudoku solvers zou ik zeggenOp 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.
quote:ik doe het altijd zo in mijn hoofd, en tot nu toe ben ik nog nooit 1 tegengekomen waarmee ik er niet uitkwam, en echt moest gaan gokkenOp woensdag 28 december 2005 21:38 schreef thabit het volgende:Met de hand deze regels toepassen is erg omslachtig. Het lukt mij in elk geval niet. Ik ben te langzaam en te slordig daarvoor. Een computer is echter snel en precies dus ik heb een computerprogrammaatje geschreven dat herhaaldelijk op alle mogelijke manieren de regels 1 en 2 toepast totdat het de sudoku heeft opgelost. Het mooie is: elke sudoku die ik erin heb gestopt heeft het weten op te lossen.
Zijn hier sudoku-beoefenaars die er meer van weten? Zijn er sudoku's waarbij je echt cijfertjes moet uitproberen anders kun je er niet uitkomen?
quote:Mooi, dan gaat het dus puur om logica toepassen.
*neuriet Alle Menschen werden Brüder*
. Je kunt het dus gewoon over gelijkheid hebben.quote:Ik neem aan dat met "zonder gokwerk" bedoeld wordt dat de oplossing eenduidig is.Op donderdag 29 december 2005 15:15 schreef DionysuZ het volgende:
[..]
Zelfs de allermoeilijkste soduku's kunnen zonder gokwerk opgelost worden.
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.
quote:Nee, afzonderlijk werken ze niet. Maar een generalisatie die beide omvat zou inderdaad wel interessant zijn.Op donderdag 29 december 2005 15:46 schreef Koekepan het volgende:
Werkt regel 1 of 2 ook afzonderlijk al? En is er misschien een generalisatie te verzinnen die beide regels omvat?
quote:Helaas, de puzzels die daar op het moeilijkste niveau staan kunnen gewoon met de in de OP beschreven regels worden opgelost.Op donderdag 29 december 2005 20:39 schreef Rewimo het volgende:
Online spelen in diverse moeilijkheidsgraden
quote:In het geval van de sudoku klopt dat aardig.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.
quote:In dat geval is dom blijven dus een slimmere keuzeOp donderdag 29 december 2005 20:51 schreef Koekepan het volgende:
[..]
In het geval van de sudoku klopt dat aardig.
quote:Dat is nou een sudoku....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.
Het moeilijke zit hem er voor een menselijke speler in het allemaal te onthouden...
quote:Begrijp me niet verkeerd, ik vind het erg knap dat je een verzameling regels hebt gevonden die zeer waarschijnlijk werkt. Maar het zélf maken van sudoku's gaat natuurlijk wel vrij snel vervelen (precies omdat je zelf te werk gaat volgens een beperkte verzameling regels).Op donderdag 29 december 2005 20:57 schreef thabit het volgende:
Ach ja, als je op sudoku bent uitgekeken kun je natuurlijk altijd aan het de Riemannhypothese gaan werken.
quote:Dacht dat die al opgelost was.Op donderdag 29 december 2005 20:57 schreef thabit het volgende:
Ach ja, als je op sudoku bent uitgekeken kun je natuurlijk altijd aan het de Riemannhypothese gaan werken.
maar volgens mij ben je idd wel een paar jaartjes zoet die oplossing te begrijpen.
quote:Als je dit topic had doorgelezen had je gezien dat mijn verzameling regels niet werkt.Op donderdag 29 december 2005 21:00 schreef Koekepan het volgende:
[..]
Begrijp me niet verkeerd, ik vind het erg knap dat je een verzameling regels hebt gevonden die zeer waarschijnlijk werkt. Maar het zélf maken van sudoku's gaat natuurlijk wel vrij snel vervelen (precies omdat je zelf te werk gaat volgens een beperkte verzameling regels).
Wat als je regel 2 nou eens abstracter formuleert, als: "zijn U en V verzamelingen sudokuvakjes waarvan bekend is welke getallen erin moeten staan, streep dan in U \ V door wat al in V \ U staat en andersom."
O trouwens, dat is onbruikbaar omdat er te veel van zulke verzamelingen zijn. Streep maar door. Je zou mogelijke verzamelingen U en V kunnen beperken tot deelverzamelingen van blokken, kolommen en rijen.
quote:Iemand die beweert die oplossing te begrijpen heeft sowieso ongelijk.Op donderdag 29 december 2005 21:01 schreef soulsurvivor het volgende:
[..]
Dacht dat die al opgelost was.
maar volgens mij ben je idd wel een paar jaartjes zoet die oplossing te begrijpen.
dus
| 1 2 3 | BBBEEEEEE CCC |
Jammer dat dit sowieso niet echt gaat leiden tot wat de mooiste regels zouden zijn...
quote:Wat wordt de regel dan precies?Op donderdag 29 december 2005 21:16 schreef ThE_ED het volgende:
Werkt het niet als je regel 2 wat ruimer neemt met 1e rij/kolom erbij?
dus
[ code verwijderd ]
Jammer dat dit sowieso niet echt gaat leiden tot wat de mooiste regels zouden zijn...
quote: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 | 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 ]
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.
quote:hihi, heb je t over mij??Op woensdag 28 december 2005 23:28 schreef gexxz het volgende:
Een vriend van me heeft er een programmaatje voor geschreven
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.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 ]
quote: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.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.
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.
quote:er is geen `simpele formule` om dit op te lossen. want met formules reken je, en met sudoku's niet.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.
quote:Hoe moet je dit compileren?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/
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..
. 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.
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
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
.quote:Staat hier niet gewoon ieder getal mag maar één keer voorkomen in elke rij, kolom en blok maar dan onduidelijker?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.
quote:Nee, het is een generalisatie van die regel.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?
quote: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*quote:PC-ActiveOp 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.
* JapyDooge heeft
maar het was niet 'simpel'
quote:ik dacht dat er sudoku's waren met meerdere oplossingen.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.
Je moet trouwens prolog gebruiken. Kan je vrij makkelijk dit soort backtracking problemen mee solven (denk ik). Zal eens kijken wat ik kan.
quote:wat gebruikte je eerst dan?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
quote:Natuurlijk. Bijvoorbeeld de sudoku waar in het begin nog niets ingevuld is.Op maandag 13 februari 2006 21:22 schreef McCarthy het volgende:
[..]
ik dacht dat er sudoku's waren met meerdere oplossingen.
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.
quote:dat ben ik nog nooit tegen gekomen in een sudoku.Op maandag 13 februari 2006 22:06 schreef Schonedal het volgende:Het komt een enkele keer voor dat je moet gokken.
als je moet gokken heb je iets over het hoofd gezien
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
quote:ik snap geen hol van je hele postOp 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
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)
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.
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
quote:talen bedoel je?
*kuch*
VB6.0, MSXBASIC, Z80 ASM, Java, PHP, C, Javascript
ik houd niet zo van VB6.0 en van Javascript
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 | // 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 | /* 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:)
quote:idd, en nu je ouwe avatar terug aub