WFL Wetenschap, Filosofie, Levensbeschouwing
Discussieer hier over alle aspecten van de wetenschap, filosofische problemen en zaken van levensbeschouwelijke aard.
Sudoku, iedereen kent het tegenwoordig wel. Het spel dat uit Japan hiernaartoe is over komen waaien. Je hebt een 9x9 vlak, onderverdeeld ook weer in 3 blokken van 3x3. In elk vakje moet een cijfer uit de verzameling 123456789 (we noteren verzamelingen cijfers hier voor het gemak met zo'n reeks, dus zonder accolades en komma's) komen zodanig dat voor elke rij, elke kolom en elk blok geldt dat elk cijfer er precies eenmaal in voorkomt.
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:
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?
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 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
Ik heb 't geprobeerd maar ik ben blond. Dus hou ik er maar mee op :-D :-D
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
WEB / [HaxBall #64] Jos is God
Arguing on the Internet is like running in the Special Olympics.
Arguing on the Internet is like running in the Special Olympics.
Laat ik deze regel even toelichten aan de hand van een paar voorbeelden.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.
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.
Heb je hier ook een bron van?quote: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
Jij bent grappig, maar inderdaad een beetje simpel als je niet eens een beetje kan Sudoku'en.quote: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
Het stond enkele weken terug in een computerblad dat een oud-leraar van me op het perron stond te lezen.quote:
Vows are spoken to be broken
Feelings are intense, words are trivial
Pleasures remain, so does the pain
Words are meaningless and forgettable
Feelings are intense, words are trivial
Pleasures remain, so does the pain
Words are meaningless and forgettable
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 rapquote:
ff op google gezocht ( op excel sudoku oplosser )quote:
http://www.gewoongertjan.nl/archives/34
http://members.home.nl/f.petry/Downloads.htm
WEB / [HaxBall #64] Jos is God
Arguing on the Internet is like running in the Special Olympics.
Arguing on the Internet is like running in the Special Olympics.
Goed, op zich ben ik niet geinteresseerd in een programma dat sudoku's kan oplossen, maar vooral in welke afleidingsregels voldoende zijn.
Klik hier: http://www.stolaf.edu/people/hansonr/sudoku eens op Hardest (rechtsboven).
Zijn jouw regels ook voldoende voor die Sudoku?
Zijn jouw regels ook voldoende voor die Sudoku?
darwin's rollin' over in his coffin
the fittest are surviving much less often
the fittest are surviving much less often
Hmm, nee. Niet voor die. Er moeten dus nog regels bij. Vooral regel 2 moet algemener.quote: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?
Is bij deze puzzel de beginsituatie al een probleem of kom je pas na een aantal iteraties vast te zitten? Kan je in het laatste geval de situatie die overblijft posten?
darwin's rollin' over in his coffin
the fittest are surviving much less often
the fittest are surviving much less often
Een vriend van me heeft er een programmaatje voor geschreven
And as a finishing touch, God created the Dutch
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.quote: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..
Voor zover bekend heb je minstens 17 cijfertjes in je Sudoku nodig om 'm uniek op te kunnen lossen, d.w.z. uniek-oplosbare Sudoku's met 16 cijfers zijn nog niet gevonden. Een overzicht staat hier.
Het lijkt me een goed startpunt voor een algoritme om die Sudokupuzzels te kunnen oplossen.
Het lijkt me een goed startpunt voor een algoritme om die Sudokupuzzels te kunnen oplossen.
Het is tijd voor wat anders.
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.quote: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.
[KNE]-Mod
Ik vind rekenkundig in de trant van: "Dit is een één of een twee, stel het is een twee, dan moet dat wel een zes zijn, etc." met een beperkt aantal stapjes totdat je op een inconsistentie uitkomt nog wel acceptabel; dat vind ik nog geen gokken.
Meestal is dat echter niet nodig.
Meestal is dat echter niet nodig.
Het is tijd voor wat anders.
Zelfs de allermoeilijkste soduku's kunnen zonder gokwerk opgelost worden.quote: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..
□ 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
■ 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
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.
[KNE]-Mod
Dat is een feit?quote:Op donderdag 29 december 2005 15:15 schreef DionysuZ het volgende:
[..]
Zelfs de allermoeilijkste soduku's kunnen zonder gokwerk opgelost worden.
Anders is het geen Sudoku.quote:
□ 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
■ 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
http://nl.wikipedia.org/wiki/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.
□ 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
■ 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
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:
Vows are spoken to be broken
Feelings are intense, words are trivial
Pleasures remain, so does the pain
Words are meaningless and forgettable
Feelings are intense, words are trivial
Pleasures remain, so does the pain
Words are meaningless and forgettable
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:
[KNE]-Mod
Bekijk de source van bestaande sudoku solvers zou ik zeggenquote: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.
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 gokkenquote:Op 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?
Extremistisch gematigd.
Ze zijn uit Japan komen overwaaien, maar komen oorspronkelijk uit Europa. De Japanners hebben ze gewoon van ons afgekeken.
*neuriet Alle Menschen werden Brüder*
*neuriet Alle Menschen werden Brüder*
Wittgenstein
Werkt regel 1 of 2 ook afzonderlijk al? En is er misschien een generalisatie te verzinnen die beide regels omvat?
Wittgenstein
Regel 1 kun je nog iets preciezer maken. Als dat aantal vakjes strict groter is dan |S|, dan is er namelijk geen oplossing . Je kunt het dus gewoon over gelijkheid hebben.
Ik neem aan dat met "zonder gokwerk" bedoeld wordt dat de oplossing eenduidig is.quote: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.
□ 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
■ 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
Nee, afzonderlijk werken ze niet. Maar een generalisatie die beide omvat zou inderdaad wel interessant zijn.quote: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?
Had je dit al gezien overigens? http://www.stolaf.edu/people/hansonr/sudoku/12rules.htm
darwin's rollin' over in his coffin
the fittest are surviving much less often
the fittest are surviving much less often
Rewimo
Nederduitse/Mevrouw qltel
Most people don't listen with the intention to understand, they listen with the intention to reply.
<a href="http://bijenzonderzorgen.nl/" target="_blank" rel="nofollow">http://bijenzonderzorgen.nl/</a> beslist geen BIJ-zaak!
<a href="http://bijenzonderzorgen.nl/" target="_blank" rel="nofollow">http://bijenzonderzorgen.nl/</a> beslist geen BIJ-zaak!
Als je dit spel kan kraken met simpele formules is er volgens mij gelijk geen reet meer an.
gelijk
"Word bokser, dan heb je meer kans op slagen"
"Mensen die nooit wat geven, daar krijg ik wat van"
"Word bokser, dan heb je meer kans op slagen"
"Mensen die nooit wat geven, daar krijg ik wat van"
Helaas, de puzzels die daar op het moeilijkste niveau staan kunnen gewoon met de in de OP beschreven regels worden opgelost.quote:Op donderdag 29 december 2005 20:39 schreef Rewimo het volgende:
Online spelen in diverse moeilijkheidsgraden
In het geval van de sudoku klopt dat aardig.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.
Wittgenstein
In dat geval is dom blijven dus een slimmere keuzequote:Op donderdag 29 december 2005 20:51 schreef Koekepan het volgende:
[..]
In het geval van de sudoku klopt dat aardig.
gelijk
"Word bokser, dan heb je meer kans op slagen"
"Mensen die nooit wat geven, daar krijg ik wat van"
"Word bokser, dan heb je meer kans op slagen"
"Mensen die nooit wat geven, daar krijg ik wat van"
Ach ja, als je op sudoku bent uitgekeken kun je natuurlijk altijd aan de Riemannhypothese gaan werken.
Dat is nou een sudoku....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.
Het moeilijke zit hem er voor een menselijke speler in het allemaal te onthouden...
[KNE]-Mod
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).quote: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.
Wittgenstein
Dacht dat die al opgelost was.quote: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.
gelijk
"Word bokser, dan heb je meer kans op slagen"
"Mensen die nooit wat geven, daar krijg ik wat van"
"Word bokser, dan heb je meer kans op slagen"
"Mensen die nooit wat geven, daar krijg ik wat van"
Als je dit topic had doorgelezen had je gezien dat mijn verzameling regels niet werkt.quote: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).
O jee, wat suf. *thumbs-down*.
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.
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.
Wittgenstein
Iemand die beweert die oplossing te begrijpen heeft sowieso ongelijk.quote: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.
Werkt het niet als je regel 2 wat ruimer neemt met 1e rij/kolom erbij?
dus
Jammer dat dit sowieso niet echt gaat leiden tot wat de mooiste regels zouden zijn...
dus
| 1 2 3 | BBBEEEEEE CCC |
Jammer dat dit sowieso niet echt gaat leiden tot wat de mooiste regels zouden zijn...
[KNE]-Mod
Wat wordt de regel dan precies?quote: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...
Hmm, nee wacht, slaat niet echt ergens opquote:
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 ]
[KNE]-Mod
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.
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.
Humanitas est in bestias bonitas.
I am the hole I can't get out of.
hihi, heb je t over mij??quote: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 ]
Sigmoid: f(x) = 1 / (1 + 2.718281828458# ^ -x)
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.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.
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)
er is geen `simpele formule` om dit op te lossen. want met formules reken je, en met sudoku's niet.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.
Sigmoid: f(x) = 1 / (1 + 2.718281828458# ^ -x)
Hoe moet je dit compileren?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/
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..
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)
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.
Ik zou trouwens een algoritme dat recursief backtrackt wel rekenen willen noemen. Rekenen doe je niet alleen maar met getallen of formules.
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
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)
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.
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
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)
.
Staat hier niet gewoon ieder getal mag maar één keer voorkomen in elke rij, kolom en blok maar dan onduidelijker?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.
Now I'm walking on the sunnyside of the street
Nee, het is een generalisatie van die regel.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?
dat maakt niet uit. je ontbeert het inzicht kennelijk niet anders had je me die tip nooit gegevenquote:Op woensdag 1 februari 2006 17:05 schreef thabit het volgende:
Ah, okee. Ik ken C# niet. .
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)
PC-Activequote: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.
* 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
ik dacht dat er sudoku's waren met meerdere oplossingen.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.
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
wat gebruikte je eerst dan?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
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
Natuurlijk. Bijvoorbeeld de sudoku waar in het begin nog niets ingevuld is.quote:Op maandag 13 februari 2006 21:22 schreef McCarthy het volgende:
[..]
ik dacht dat er sudoku's waren met meerdere oplossingen.
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.
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.
dat ben ik nog nooit tegen gekomen in een sudoku.quote: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
Extremistisch gematigd.
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
■ 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
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
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.
Humanitas est in bestias bonitas.
I am the hole I can't get out of.
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.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
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.
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.
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.
Humanitas est in bestias bonitas.
I am the hole I can't get out of.
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
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
■ 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
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.
Humanitas est in bestias bonitas.
I am the hole I can't get out of.
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.
So I stole a bike and asked for forgiveness.
talen bedoel je?quote:
*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)
mwah, dan willen jullie vast ook wel de PHP versie van mn StateSolver dacht ik zo...
voorbeeld - sudoku.php
de klasse zelf
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:)
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:)
Sigmoid: f(x) = 1 / (1 + 2.718281828458# ^ -x)
idd, en nu je ouwe avatar terug aubquote:Op woensdag 1 maart 2006 21:26 schreef gexxz het volgende:
Ik had het over jou ja
Sigmoid: f(x) = 1 / (1 + 2.718281828458# ^ -x)
|
|
