Sudoku

[Math]

In Excel gemaakte hulpmiddel voor het overzicht van de mogelijkheden per vakje is te vinden op:

http://members.home.nl/palkema

Vul de gegeven waarden in onder het tabblad "origineel"

Oplossen kan onder het tabblad "invul"

Onder in elk vakje invullen.

Uhm, tegen betaling?

Nee, dan beter deze: http://www.angusj.com/sudoku/

[Anonymous]

Na veel geprogrammeer heb ik eindelijk een sudoku generator af die een goede puzzel geeft.

Je heb wel een keer dat ie 650 invulpogingen doet om de juiste te vinden maar ja.

Soms vindt ie hem al na 32 pogingen.

Ik heb er eentje gemaakt waarbij je plaatjes moet ontdekken.

Je moet zelf eerst op ontdekkingstoch gaan en dan kun je zelf de sudoku gaan proberen in te vullen.

Ontdekken kost -1 punt, goed raden is 2 punten en een mislukte poging kost zelf -4 punten.

Is de kunst om zo veel mogelijk punten te scoren.

In ieder geval werkt de randomgenerator als volgt:

Je begint met de 1 en je plaatst die op plek 1 t/m 9 in box 1.

Dan haal je alle plekken weg in de gehele puzzel waar geen 1 kan komen te staan.

En dan ga je naar de volgende box.

Je kiest daar random een vrije plekje uit (die kan) en plaatst daar het cijfer.

Etc.

En zo loopt je de cijfers 1 t/m 9 af.

Bij het 1e cijfer heb je het volgende:

Dus eerst heb je kans 1 op 9.

Dan heb je kans op 1 op 6.

Dan heb je kans op 1 op 3.

Dan heb je kans op 1 op 6.

Dan heb je kans op 1 op 4.

Dan heb je kans op 1 op 2.

Dan heb je kans op 1 op 3.

Dan heb je kans op 1 op 2.

Dan heb je kans 1 op 1.



Bij het 2e cijfer gaat het verder als:

Dan heb je kans van 1 op 8.

Dan heb je kans van 1 op (6-random_range(0,1))

Random_range geeft een toeval vanaf het eerste getal tot en met het tweede getal.

Dan heb je kans op 1 op (3-random_range(0,1))

etc.

De plekken raken steeds meer bezet waardoor de kans op plaatsing afneemt.

Bij 3 cijfers heeft men al de kans dat er een niet invulbaarheid ontstaat waardoor de sudoku niet kan.

[Dragonfighter]

Op de vraag hoeveel mogelijke puzzels er te maken zijn heb ik niet zo snel een antwoord. Om er een boek van te maken lijkt me een goed idee, alleen het aanhangsel met oplossingen bevat 6670903752021072936960 sudoku's . 48 Sudoku's op 1 bladzijde vormt een boek van 14,7 lichtjaar of 138977161500439 km dik (80 grams papier is ongeveer 80 µm dik)

Begin alvast maar boompjes te planten

Uitvoeriger op

http://web.inf.tu-dresden.de/~bf3/sudoku/sudoku.pdf

Om er puzzels van te maken kunnen er om te beginnen 3 willekeurige getallen uitgeveegt worden zonder dat er een 'bad puzzel' kan ontstaan (bij 4 getallen bestaat de mogelijkheid deze te verwisselen) er kunnen dus nu 6670903752021072936960*81*80*79=3414969048734627657888563200

puzzels worden gemaakt.Ik begin alvast aan deze te puzzelen die andere miljarden laat ik aan anderen over......

[Anonymous]

Ik heb vandaag het voor elkaar gekregen, zo tussendoor hoor, om een dubbele puzzel te genereren van 3 bij 3 en een van 3 bij 3 waarbij 1 blokje bij beide tegelijk toegepast wordt.

Dus er zijn 17 blokjes.

De software voor de random invulling voor het 2e blok is dezelfde als voor het eerste alleen heb ik voor het 2e blok een blok gekopieerd vanuit de eerste en de rijen en kolommen bijgehouden.

De rest werkt zoals bij de eerste.

En nu hebben we nog meer mogelijkheden...

[ZonnTroLL]

Iets van een 50000 mogelijkheden staat hier op mijn gekregen sudokucomputerke

De puzzels zijn in levels ingedeeld en ik moet zeggen:

Level 4 en 5 zijn precies onmogelijk.. (1/2 cijfer per vierkant)

[Brownie]

Level 4 en 5 zijn precies onmogelijk.. (1/2 cijfer per vierkant)

Maar is daar dan maar 1 unieke oplossing?

[Tom Poes]

In de zaterdag-bijlage van de Volkskrant staat een interessant artikel over de sudoku.

Er bestaan (ik hoop het goed over te tikken) 6670903752021072936960 mogelijkheden van invullen. Rekening houdend met symmetrieën loopt het aantal terug tot 5472730538 roosters. Als je er elke seconde eentje uitschrijft, ben je 180 jaar bezig.

Gebleken is dat makers van deze puzzels zich er met een jantje-van-leiden vanaf maken. Door cijfers te wisselen en roosters te kantelen en te spiegelen, kun je van een correcte puzzel een heleboel nieuwe correcte puzzels maken.

[A.Square]

Rekening houdend met symmetrieën

nb: Die symmetrieen zijn de volgende:

-Spiegelen in kolom 5

-Spiegelen in rij 5

-Diagonaal spiegelen (2x)

-Verwisselen van rij 1, 2 of 3 ; 4, 5 of 6 ; 7, 8 of 9

-Verwisselen van kolom 1, 2 of 3 ; 4, 5 of 6 ; 7, 8 of 9

-Verwisselen van de cijfers

Zo loopt het aantal unieke sudoku's van 6670903752021072936960 ([ongeveer]6,*10^21) terug naar 5472730538 ([ongeveer]5,5*10^9)

[Raspoetin]

Zo loopt het aantal unieke sudoku's van 6670903752021072936960 ([ongeveer]6,*10^21) terug naar 5472730538 ([ongeveer]5,5*10^9)

Gelukkig, ik dacht al. Heb ik ze toch voor vrijdag allemaal opgelost.

[Micheltje]

Level 4 en 5 zijn precies onmogelijk.. (1/2 cijfer per vierkant)

Maar is daar dan maar 1 unieke oplossing?

Ik denk zelf van niet. Ik ben zelf bezig geweest met een algoritme die sudoku's probeert op te lossen door enkel logisch te beredeneren met de gegeven regels. Dit werkt prima voor niveau 2 en 3. Bij niveau 4 en 5 ( en hoger ) zul je denk ik trail-and-error moeten gebruiken en vanuit een bepaalde positie verschilende oplossingen gaan proberen en vanuit die positie weer de eenvoudige wegstreepfuncties te gebruiken en kijken of hij vervolgens wel oplosbaar is tot 1 unieke oplossing.

Erg leuk om te doen maar wel best lastig om zoiets snel en netjes te houden. Ga hem denk ik binnenkort overnieuw schrijven en proberen nieuwe strategien te verzinnen.

Overigens zijn niveau 4 puzzels in de boekjes erg goed op te lossen, zit vaak 1 of 2 x een 'probleemmuur' in. 5 is al lastiger.

"Hoever / hoe dichtbij is dit eigenlijk bij kunstmatige intelligentie?"  

Oneindig ver volgens mij. Het denkwerk wordt door de mens gedaan, het algoritme is niets intelligenter dan een horloge. Het algoritme leert en bedenkt niets.  

Ben ik met je eens. Oneindig ver wil ik niet zeggen want de ontkrachtig van vrije wil is ook gebasseerd op het feit dat de mens zou handelen naar de natuurwetten en daarmee dus vast ligt. Maargoed, dat is een geheel andere discussie

Wat ik me wel net bedacht dat dit type puzzel eigenlijk heel elementair is. Misschien spelen ze aan de andere kant van het universum ook wel sudoku?

Hangt er natuurlijk erg vanaf. De logica van die soort (configuratie van aardig hoopje elementaire deeltjes ofzo) kan wezenlijk verschillen van die

van ons. Ook hoeft die soort geen herkenning te hebben voor figuren ( cijfers, bolletjes, rasters, etc ) zoals wij en daarmee niet eens iets met die puzzel te kunnen doen. Daarbij nog veel meer dingen.

Maargoed, je blijft altijd een kans hebben. Herinner mij dat in "Godel, Esher , Bach" boek een onderwerp over het vraagstuk ging of wiskunde universeel is in he heelal.

Maargoed, back on-topic:)

[pultjuh]

een stukje terug wordt er beweerdt dat er alleen met de symetrische sudoku's wordt gewerkt,

maar een sudoku boekje wat ik heb heeft geen symetrische puzels

op deze manier heb je dus weer 6670903752021072936960 mogelijkheden

[Tom Poes]

een stukje terug wordt er beweerdt dat er alleen met de symetrische sudoku's wordt gewerkt,

maar een sudoku boekje wat ik heb heeft geen symetrische puzels

op deze manier heb je dus weer 6670903752021072936960 mogelijkheden

Dit heeft niemand beweert...

[Frenchipen]

Hey,

Sinds dit jaar moeten wij in het zesde middelbaar een eindwerk maken. Ik doe it over sudoku's. Ben wel blij dat ik eindelijk een nederlands forum heb gevonden hierover.

Ik vroeg me eigenlijk ook een aantal dingen af:

° als je een sudoku hebt met een symmetrische vorm, is deze dan makkelijker of moeilijker op te lossen?

(die met 17 cijfers gegeven zijn steeds onsymmetrisch, wat me doet denken dat een symmetrische met 17 cijfers onmogelijk is en dus moeilijker. toch vind ik sudoku's met veel gegeven cijfers die symmetrisch staan precies makkelijker dat met veel gegeven die niet symmtrisch staan. Of vergis ik mij)

° Ik las dat hier enkele bezig waren met programmeren. Ik had oorspronkelijk ook het doel om sudoku's met de computer te laten maken en oplossen maar het lukt me niet (computerprogrammeerkennis is te laag). Kan iemand me hierbij helpen

Ik zou dit voor de gemakkelijkheid doen met vierkanten van 4 op 4

° Over het aantal sudoku's heb ik ook al veel informatie gevonden, maar ik snap de berekening niet helemaal. Als iemand me ook hierbij kan helpen

Alvast bedankt

Als iemand nog vragen heeft, let me know, want ondertussen weet ik er toch al wat van af.

greetz

Fran

btw: sudoku's verminderen de achteruitgang van de hersencapaciteit dus: puzzelen maar!!

[Nieuwsgierig]

Hallo,

ik wil graag iets meer over de wiskunde in sudoku weten..

is er mischien een bepaald algortime of formule waarin je de cijfers die gegevn zijn kan invullen, zodat het goede antwoord eruit rolt?

(dit klinkt wel raar, maar moet tog mogelijk zijn, want dit is puur wiskunde, een cijfer word pas ingevult als men er 100% zeker van is dat die daar goed staat)

alvast bedankt

[Schwartz]

Omdat de sudoku 9 symbolen heeft en wel 1 2 3 4 5 6 7 8 9 kan men ook indianensymbolen nemen of letters zoals: A B C D E F G H I

Men vindt in een sudoku puzzel altijd minimaal 8 symbolen aan het begin omdat bij 7 symbolen men niet weet of een symbool dan dat specifieke symbool is.

dus als 1 t/m 7 bekend is kan 8 en 9 net zo goed andersom ingevuld worden;

zonder afbreuk te doen aan de puzzel.

Dus het verwisselen van alle 9 symbolen met andere symbolen is ook een symmetrie.

Mijn computerprogramma heeft soms 200 tryouts nodig om een unieke sudoku te maken.

Ik werk met een randomgeneratie zodat men geen symmetrie sudokus bekomt.

Deze zijn te doorzichtig voor de puzzelaar.

Omdat mijn sudoku een ander soort sudoku spel is; men kan een getal openzetten wat 1 punt kost, goed raden levert 2 punten op en een fout kost 2 punten of meer; heb ik niet de startpuzzel hoeven te programmeren.