Ik zie hier enkele keren de vraag terugkomen van mensen die op zoek zijn naar iets dat een Sudoku op een correcte manier oplost.

Dit is, wat dat betreft een prachtige site denk ik:

[url=http://www.sudokusolver.co.uk/]http://www.sudokusolver.co.uk/[/url]

Hier vul je in de (kleine) sudoku de cijfers in die gegeven zijn, het programma gaat eventjes rekenen en in het tekstveld eronder zie je precies wat het programma heeft gedaan en in welke stappen.

Eerst bijvoorbeeld de cijfers die meteen al duidelijk zijn (1 mogelijkheid), vervolgens kijken naar welke cijfers enkel bij bepaalde hokjes kunnen, enz, totdat het bij de stap komt dat enkel 'trial and error' nog mogelijk is. Dit krijg je dan ook netjes aangegeven, met de mededeling erbij dat er misschien meerdere oplossingen zijn.

Succes voor de mensen die dat kunnen gebruiken!

Regel C wordt weer minder mogelijkheden

per vakje blijven er daar altijd nog maar 3 cijfers over die in 6 verschillende volgorden gezet kunnen worden. Dus daar 6^3 =216 mogelijheden.

dit moet weer vermenigvuldigd worden met het aantal mogelijkheden in regel B die zeker niet hoger is dan 1.728.000 (6*5*4= 120^3 waar een heleboel foute bijzitten). Bij regel D zij er weer meer mogelijkheden omdat daar weer 3 nieuwe kleine vakjes beginnen.6 mogelijkheden op D1.

Regel E is ongeveer gelijk aan regel C , met het verschil dat daar al weer minder mogelijkheden zijn omdat alles op de kolom daarboven ook af valt.

Hoe verder je naar beneden komt , dan vult de puzzel zichzelf in en krijg je steeds minder goede mogelijkheden.

Op regel I is nog maar één mogelijkheid.

Ik had het even fout het is 9*8*>>>>2*1

en dat is 362880 invullingen van eigenlijk de zelfde puzzel.

Dus moet dan ook zijn 9 faculteit.

voor het aantal basispuzzels begin je dan met op regel A1 tot A9 de getallen 1 t/m 9.

Op B1 zijn 6 mogelijkheden, B2-5 ,B3-4,B5 echter wordt weer ingewikkelder, daar mogen de A1 tot A3 cijfers weer mee doen maar vallen de in B1 tot B3 al ingevulde cijfers weer af en A4 tot A6 kunnen daar ook weer niet.

Dus het wordt een ingewikkelde puzzel om alle geldige mogelijkheden op te tellen, maar zeker met een Excell achtig programma met de nodige controlevoorwaarden te doen.

Ik schat in dat er dan maar een paar honderdduizend geldige basis-mogelijkheden zijn.

Heb zelf op basischool van mijn kinders sudoku-oriëntatie cursus gegeven , waarbij ik de 6 kinderen in de groep verschillende puzzel had laten maken, die na omzetten van cijfers naar letters achteraf dezelfde basispuzzel bleken te zijn. Gewoon door bij een puzzel uit boekje steeds cijfers om te wisselen of door te schuiven. Dus bijvoorbeeld een 1 in origineel werd een 3 in de ene puzzel en een 5 in de andere puzzel.

Bij één groepje kwamen ze er door afkijken en elkaar helpen pas iets te vroeg zelf achter.

[quote]Dat is 9+8>>>+2+1 ( hoe heet dat nou ook alweer, faculteit?).[/quote]

Faculteit is met vermenig vuldigen..

Natuurlijk moeten ook nog het aantal mogelijke symbolen worden behandeld..

Maar de grootste vraag blijft wat wij een puzzel noemen eentje met 1 vakje weg of met maar 1 vakje al ingevuld is nauwelijks een puzzel te noemen..

Gr. F.

PS.

Nogmaals bij 9! * 9! houden we geen rekening met het beperken (ivm de regels van een sudoku) van het aantal mogelijkheden voor het nieuwe vakje.

Als je op de eerste regel 1 tot en met negen invult en daarmee verder gaat combineren in de volgende regels , ook rekening houdend met dat er in de kleine vakjes niet hetzelfde mag staan, dan kom je op een aantal basismogelijkheden, waar iedere andere combinatie van de 9 cijfers op die bovenste regel naar terug te voeren is.

De combinatie mogelijkheden op de bovenste regel is eenvoudiger uit te rekenen.

Dat is 9+8>>>+2+1 ( hoe heet dat nou ook alweer, faculteit?).

Daarmee heb je het aantal mogelijkheden al aanzienlijk terug gebracht( met een factor 45)

Kun je later ook letters, kleuren, symbolen naar deze basismogelijkheden terugvoeren.

[quote='jcjlf' post='513409' date='4 May 2009, 11:00']Ik ben geen wiskundige en pas laat ingestapt op de sudoku-rage (Ik dacht eerst ik heb wel wat beters te doen, maar je raakt toch een tijdje verslaafd.)

Nu mijn idee over het aantal mogelijke roosterinvullingen en goede oplossingen en de vraag klopt dat zo?

Aantal mogelijke roosterinvullingen: 9! x 9! = 1,3168... ^11

Als ik nu uitga van één goede oplossing dan is het aantal varianten hiervan door rijen of kolmmen te verschuiven, te roteren en de symbolen te variëren, in volgorde berekend:

6! x 6! x 4 x 9 = 18.662.400 mogelijkheden.

Maar heb ik dan alles? Het lijkt mij te simpel om waar te zijn. ;) [/quote]

Nee sorry, dit kan niet, er vinden berperkingen plaats door de keuze van het eerste vakje uit 9! mogelijkheden.

Dit is ik erover denk.. Corrigeer mij a.u.b. wanneer ik er naast zit

[list]Vakje 1 wordt niet beperkt[indent=1]Geeft 9! mogelijkheden[/indent]

Vakje 2 door 1[indent=1]Geeft 9! * 2/3[/indent]

Vakje 3 door 1 en 2[indent=1]Geeft 9! * 2/3 * 2/3[/indent]

Vakje 4 door 1[indent=1]Geeft 9! * 2/3[/indent]

Vakje 5 door 4 en 2[indent=1]Geeft 9! * 2/3 * 2/3[/indent]

Vakje 6 door 4, 5 en 3[indent=1]Geeft 9! * 2/3 * 2/3 * 2/3[/indent]

Vakje 7 door 1 en 4[indent=1]Geeft 9! * 2/3 * 2/3[/indent]

Vakje 8 door 7, 2 en 5[indent=1]Geeft 9! * 2/3 * 2/3 * 2/3[/indent]

Vakje 9 door 7, 8, 3 en 6[indent=1]Geeft 9! * 2/3 * 2/3 * 2/3 * 2/3[/indent]

[/list]

Van deze antwoorden het gemiddelde (is het gemiddelde aantal oplossingen per vakje) en dit vermenigvuldigen met 9!

Dan geeft dit 65208729600 mogelijkheden. Dit is het aantal [b]oplossingen[/b]. Als je het aantal puzzel wilt weten, moet je eerst nagaan bij welk patroon/aantal missende vakjes we spreken over een [b]puzzel[/b].

Gr. F.

[quote]Maar is daar dan maar 1 unieke oplossing?[/quote]

Ik ben geen wiskundige en pas laat ingestapt op de sudoku-rage (Ik dacht eerst ik heb wel wat beters te doen, maar je raakt toch een tijdje verslaafd.)

Nu mijn idee over het aantal mogelijke roosterinvullingen en goede oplossingen en de vraag klopt dat zo?

Aantal mogelijke roosterinvullingen: 9! x 9! = 1,3168... ^11

Als ik nu uitga van één goede oplossing dan is het aantal varianten hiervan door rijen of kolmmen te verschuiven, te roteren en de symbolen te variëren, in volgorde berekend:

6! x 6! x 4 x 9 = 18.662.400 mogelijkheden.

Maar heb ik dan alles? Het lijkt mij te simpel om waar te zijn. =D>

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.

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? :D

(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

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.

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

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

Alvast bedankt

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

greetz

Fran

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

[quote='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[/quote]



Dit heeft niemand beweert... :wink:

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

[quote='Brownie'][quote='ZonnTroLL']

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

Maar is daar dan maar 1 unieke oplossing?[/quote]

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.

[quote]"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.  [/quote]

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

[quote]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?[/quote]

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

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



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

[quote]Rekening houdend met symmetrieën[/quote]

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)