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