Uit Japan overgewaaid.
Wat is een sudoku.
Het is een puzzeltje van negen bij negen vakjes met een klein aantal reeds ingevulde enkelvoudige cijfers.
De kunst is om de overige vakjes ook in te vullen op zo’n manier dat in elke horizontale reeks en in elke verticale reeks de cijfers 1 tot en met 9 één keer voorkomen.
Bovendien is de puzzel onderverdeeld in negen blokjes van drie bij drie, die elk ook weer eenmaal de cijfers 1 tot en met 9 moeten bevatten.
Hieronder staat er eentje.
Is dit moeilijk op te lossen? Of vullen jullie de cijfers gewoon achter elkaar in?
quote:Ja.Op vrijdag 20 mei 2005 17:01 schreef Speedski het volgende:
Hehe, niets voor mij. Misschien wel als ik weet hoe je dat nou moet aanpakken.
Hoe moet je zoiets aanpakken?
Is het gewoon uitproberen, trial and error?
Of zijn er methoden?
quote:Das ook mijn vraagOp vrijdag 20 mei 2005 17:03 schreef Yosomite het volgende:
[..]
Ja.
Hoe moet je zoiets aanpakken?
Is het gewoon uitproberen, trial and error?
Of zijn er methoden?
Kom er altijd wel uit, de ene keer sneller als de andere keer.
Wat betreft de cijfers die al gegeven zijn: zijn die willekeurig gekozen, of niet? En is er gegarandeerd een oplossing voor, of zijn sommige varianten niet op te lossen?
quote:Deze komt uit The Guardian. De gegeven cijfers zijn niet willekeurig.Op vrijdag 20 mei 2005 17:12 schreef HenryHill het volgende:
Gave breinkraker.
Wat betreft de cijfers die al gegeven zijn: zijn die willekeurig gekozen, of niet? En is er gegarandeerd een oplossing voor, of zijn sommige varianten niet op te lossen?
Ze moeten in rijen en kolommen in ieder geval verschillend zijn.
Ook in de kleine vierkantjes moeten ze verschillend zijn.
Kijk naar het middelste vierkant. In de linker twee vrije vakjes mogen geen 3, geen 5 en geen 6 zitten, want die zitten al in de betreffende verticale rij.
Rechtsonder mag geen 5 zitten want in die horizontale rij zit er al een. Idem met rechtsboven. Daar mogen geen 5 en geen 3.
Conclusie, het aller middelste vakje is een 5, en rechtsonder is de enige plek waar een 3 mag. Dan is de rest van dat vlak redelijk simpel. Nu de rest nog
1. Opschrijven hoeveel er in elke rij missen
2. Op elke plek in de matrix waar er twee lijnen samen komen waar er zo min mogelijk nummers missen invullen welke mogelijkheden er op de plek zijn.
3. Zo door gaan tot je aardig wat mogelijkheden ingevuld hebt.
4. Keuzes maken en dan trail en error.
In elk vakje (met klein lettertype) invullen welke cijfers daar wél mogen. Zo kan je langzaamaan door goed kijken en redeneren steeds nummertjes wegstrepen.
quote:Combinatie van uitproberen en logisch nadenken (en tijd te veel hebbenOp vrijdag 20 mei 2005 17:03 schreef Yosomite het volgende:
[..]
Ja.
Hoe moet je zoiets aanpakken?
Is het gewoon uitproberen, trial and error?
Of zijn er methoden?
). Als je al wat cijfers hebt ingevuld, dan blijven er voor steeds meer vakjes nog maar weinig mogelijkheden over. De mogelijkheden die het meest kunnen elimineren moet je als eerste uitproberen. Het zou me niets verbazen als deze puzzel NP-compleet is overigens.
quote:Valt toch wel mee als je het voor het eerst doet. Netjes hoorOp vrijdag 20 mei 2005 17:53 schreef Litso het volgende:
Opgelost. Het heeft wel langer geduurd dan ik had gedacht. Een half uur
Wel dik 20 minuten over gedaan.
SPOILERgaat het ineens best snel eigenlijk...bijvoorbeeld linksonder in het middelste blokje
quote:Inderdaad ja. Misschien zijn er moeilijkere puzzels van dit soort.Op vrijdag 20 mei 2005 20:18 schreef Enigmatic het volgende:
Trouwens je hoeft niks te gokken, vanuit het midden beginnen en met denkwerk is die helemaal uit te schrijven.
Als het goed is heeft iedereen hier onafhankelijk van elkaar dus dezelfde configuratie bedacht.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | +------+------+------+ | . . .| 8 . .| . . 5| | . 9 8| . 5 .| 1 . .| | 5 . .| 9 . .| . . 8| +------+------+------+ | . . 3| . 7 .| 8 5 .| | . . 4| 3 . 1| . . .| | . 2 .| . 4 .| . 1 .| +------+------+------+ | 6 . .| 1 . .| . . 7| | . 8 .| . . .| 2 . .| | 2 . .| 6 . 5| . . 1| +------+------+------+ |
Ik heb hem gemaakt door vanuit een complete oplossing 2/3e van de getallen weg te halen, maar wel zodanig dat op elke rij en kolom minimaal 2 getallen staan, en in elk kwadrant iig 3.
Ik kan echter niet garanderen dat er
a) precies 1 oplossing bestaat, en
b) dat je het zonder te gokken kunt oplossen.
Oplossing:
SPOILEREdit: er is dus nog een 2e oplossing voor:4 6 2 8 1 3 9 7 5
3 9 8 7 5 2 1 4 6
5 7 1 9 6 4 3 2 8
9 1 3 2 7 6 8 5 4
7 5 4 3 8 1 6 9 2
8 2 6 5 4 9 7 1 3
6 4 9 1 2 8 5 3 7
1 8 5 4 3 7 2 6 9
2 3 7 6 9 5 4 8 1
SPOILER3 6 2 8 1 4 9 7 5
4 9 8 7 5 3 1 2 6
5 7 1 9 6 2 3 4 8
9 1 3 2 7 6 8 5 4
7 5 4 3 8 1 6 9 2
8 2 6 5 4 9 7 1 3
6 4 9 1 2 8 5 3 7
1 8 5 4 3 7 2 6 9
2 3 7 6 9 5 4 8 1
[ Bericht 5% gewijzigd door HenryHill op 21-05-2005 14:11:19 ]
SPOILER273584916
685139274
419762385
354976128
968251437
127843659
832497561
796315842
541628793
quote:* Yosomite heeft deze ook.Op vrijdag 20 mei 2005 22:14 schreef Enigmatic het volgende:
Alhier mijn antwoord op het oorspronkelijke probleem. Ben benieuwd of er mensen zijn met een andere oplossing.
En ook ongeveer een half uur.
Dat maakt het leuke puzzeltjes.
Pittig, oplosbaar, en niet te lang hoeven te worstelen, en makkelijk controleerbaar.
Ik kende ze niet, en was aangenaam verrast.
quote:Ik zou het graag willen weten of er eisen voor een unieke oplossing bestaan bij het creëren van zo'n puzzel.Op vrijdag 20 mei 2005 21:19 schreef HenryHill het volgende:
Ok jongens, een nieuwe. Deze is zelf bedacht:
[ code verwijderd ]
Ik kan echter niet garanderen dat er
a) precies 1 oplossing bestaat, en
b) dat je het zonder te gokken kunt oplossen.
bv per blokje van drie bij drie moeten 3 cijfers bekend zijn,
en in een van de blokjes moeten er vier cijfers gegeven zijn.
Of het middelste blokje moet altijd vier gegevens hebben? (Dit lijkt me geen noodzakelijke eis)
http://www.sudoku.com/
Staat wel het één en ander over de opbouw van die puzzeltjes. En je kunt een proggie downloaden om sudoku op je computer te spelen, best cool
Je kan de volgende bewerkingen uitvoeren op een complete matrix die een oplossing niet aantast:
(1) Verwisselen van twee rijen (of kolommen) mits binnen hetzelfde blok van 3.
(2) Verwisselen van 2 blok-rijen of blok-kolommen (bijv. verwisselen van rij 1 en 4, 2 en 5, en 3 en 6).
(2) hernoemen van de cijfers.
Dit levert een actie van een groep met (3!)^8 * 9! elementen. (Voor de precieze groep: Het verwisselen van rijen en blokrijen commuteert niet, dit brengt een groep voort van (3!)^4 elementen, een semidirect product van S_3 en (S_3)^3. Noem deze groep H. Dan is de totale groep G:=H^2*S_9.
Twee vragen waar ik zo het antwoord niet op weet:
(a) kan je twee willekeurige oplossingen in elkaar overvoeren mbv deze bewerkingen (m.a.w. werkt G transitief op de oplossingsruimte)?
(b) Zitten er naast het eenheidselement nog andere elementen in G die een matrix invariant laten? (zoja, dan zou je met een kleinere groep kunnen werken).
Als het antwoord op vraag (a) ja is, dan kan je misschien elementen uit G vinden met een 'eenvoudige' actie op de matrix, En dan met dit soort simpele elementen op een systematische manier een deels ingevulde matrix proberen over te voeren in een standaard-oplossing.
Geen idee of zoiets gaat werken,..
quote:Deze ga ik vanmiddag even doen als ik tijd hebOp vrijdag 20 mei 2005 21:19 schreef HenryHill het volgende:
Ok jongens, een nieuwe. Deze is zelf bedacht:
[ code verwijderd ]
Ik heb hem gemaakt door vanuit een complete oplossing 2/3e van de getallen weg te halen, maar wel zodanig dat op elke rij en kolom minimaal 2 getallen staan, en in elk kwadrant iig 3.
Ik kan echter niet garanderen dat er
a) precies 1 oplossing bestaat, en
b) dat je het zonder te gokken kunt oplossen.
En natuurlijk bijhouden hoelang ik er over doe
en is er een website waar je ze kan printen? sudoku.com kon ik ze niet vindenquote:Op sudoku.com kun je wel een programmaatje downloaden die automatisch van die puzzeltjes genereert. Die kun je dan weer uitprinten of op de computer zelf oplossen.Op maandag 23 mei 2005 20:49 schreef kanaiken het volgende:
tvp
quote:En waar ligt dit nu aan.Op vrijdag 20 mei 2005 21:19 schreef HenryHill het volgende:
Ok jongens, een nieuwe. Deze is zelf bedacht:
[ code verwijderd ]
Edit: er is dus nog een 2e oplossing voor:
Wat bepaalt of de oplossing in dit soort puzzeltjes uniek is?
(ik begin bij het oplossen van het middelste vierkant). Verder heb ik het in excel gedaan. Leuke puzzel quote:Hmm, helaas moet je dokken voor de hele versie, je hebt maar keuze uit 40 puzzels om te printen. Weet iemand ergens een plek waar ik de full versie kan downen? Is er nog een alternatief, dat ook zelf genereert?Op dinsdag 24 mei 2005 10:40 schreef Enigmatic het volgende:
[..]
Op sudoku.com kun je wel een programmaatje downloaden die automatisch van die puzzeltjes genereert. Die kun je dan weer uitprinten of op de computer zelf oplossen.
en heel vaak een nieuwe, ik ben echt verslaafd. Meestal haal ik de top10 wel, gemiddeld iets van 20 minuten
quote:Een derde vraag die je eerst zou moeten kennen is of het gestelde probleem minimaal is. Of je geen getallen kunt weglaten en nog steeds dezelfde oplossing zal bekomen.Op zaterdag 21 mei 2005 11:54 schreef kluut het volgende:
Misschien valt er een algemene efficiente methode te verzinnen met groepentheorie. Een beetja a la het het oplossen van een kubus.
Je kan de volgende bewerkingen uitvoeren op een complete matrix die een oplossing niet aantast:
(1) Verwisselen van twee rijen (of kolommen) mits binnen hetzelfde blok van 3.
(2) Verwisselen van 2 blok-rijen of blok-kolommen (bijv. verwisselen van rij 1 en 4, 2 en 5, en 3 en 6).
(2) hernoemen van de cijfers.
Dit levert een actie van een groep met (3!)^8 * 9! elementen. (Voor de precieze groep: Het verwisselen van rijen en blokrijen commuteert niet, dit brengt een groep voort van (3!)^4 elementen, een semidirect product van S_3 en (S_3)^3. Noem deze groep H. Dan is de totale groep G:=H^2*S_9.
Twee vragen waar ik zo het antwoord niet op weet:
(a) kan je twee willekeurige oplossingen in elkaar overvoeren mbv deze bewerkingen (m.a.w. werkt G transitief op de oplossingsruimte)?
(b) Zitten er naast het eenheidselement nog andere elementen in G die een matrix invariant laten? (zoja, dan zou je met een kleinere groep kunnen werken).
Als het antwoord op vraag (a) ja is, dan kan je misschien elementen uit G vinden met een 'eenvoudige' actie op de matrix, En dan met dit soort simpele elementen op een systematische manier een deels ingevulde matrix proberen over te voeren in een standaard-oplossing.
Geen idee of zoiets gaat werken,..
Sudoku 2 heb ik opgelost, en ik vond het patroon wel heel gemakkelijk herkenbaar.
Vandaag heb ik de derde puzzel in 2 minuten opgelost
Natuurlijk zijn er veel moeilijker versies te bedenken.
http://xs32.xs.to/pics/05230/Sodoku5756_CenterGuide.JPG
quote:ik kijk persoonlijk naar getallen, niet naar hokjesOp zondag 12 juni 2005 19:35 schreef Goldboy het volgende:
Voor de mensen die er niet uitkomen bij de eerste. Ik heb even snel 'n Guide gemaakt voor het middelste vierkant, succes.
http://xs32.xs.to/pics/05230/Sodoku5756_CenterGuide.JPG
dwz ik kijk welke getallen er per rij/kolom/vierkant missen en dan kijk ik waar die wel en niet kunnen zitten.
quote:Wat een onzin, ik had die rooie juist als eerste. Het kan op zoveel manieren dat je zoiets echt niet nodig hebt.Op zondag 12 juni 2005 19:35 schreef Goldboy het volgende:
Voor de mensen die er niet uitkomen bij de eerste. Ik heb even snel 'n Guide gemaakt voor het middelste vierkant, succes.
http://xs32.xs.to/pics/05230/Sodoku5756_CenterGuide.JPG
SPOILERzie je de 5-en? nou in het middelste vierkant kan de vijf laleen op de middelste rij zitten, waar maar één mogelijkheid is. dan zie je het vierkant daaronder, waar ook een 5 mist, die 5 kan dan alleen aan de rechterkant, en dan wel de middelste.
quote:Inderdaad. Daarom is het ook onzin om aan te geven welke van de vakjes je eerst moet oplossen... het ligt er maar net aan naar welke cijfers je het eerst kijkt...Op zondag 12 juni 2005 19:59 schreef JohnDDD het volgende:SPOILERzie je de 5-en? nou in het middelste vierkant kan de vijf laleen op de middelste rij zitten, waar maar één mogelijkheid is. dan zie je het vierkant daaronder, waar ook een 5 mist, die 5 kan dan alleen aan de rechterkant, en dan wel de middelste.
http://en.wikipedia.org/wiki/Sudoku
zie ook Simple Sudoku, programma voor op de pc met vele puzzels erbij
http://www.angusj.com/sudoku/
Veel plezier ermee!
Xander
[ Bericht 11% gewijzigd door xanderhagen op 04-07-2005 15:06:40 ]
Komt altijd op hetzelfde
Sorry
Uiteraard werkt dit ook met grotere getallen
Ga maar weer OT
quote:Wat ben je autist of zo?Op zaterdag 16 juli 2005 00:15 schreef MaRySe het volgende:
Leuk is dat sodoku, ik vul het gewoon achter elkaar in