Hoeveel sudoku´s?

[drc.]

Hallo allemaal,

Ik wil graag bepalen hoeveel oplossingen er zijn om een sudoku in te vullen. Uitleg over een sudoku is hier: http://nl.wikipedia.org/wiki/Sudoku en hier: http://sudokunet.nl/ onder uitleg te vinden.

Voor nu wil ik bij de oplossingen ook velden die bijv gespiegeld van elkaar zijn, meetellen, en velden waar onderling bijv. alleen alle tweeën en drieën zijn omgewisseld ook allebei.

Ik heb zelf een idee hoe je dit aantal kan vinden, alleen ik weet niet zeker of die juist is. Ik ga uit van de benoeming en nummering van sudokunet.nl voor rijen, kolommen en vlakken. Ik zal de methode uitleggen aan de hand van een sudoku van 4 bij 4. Dus met vlakken van 2 bij 2. (1,2) wil zeggen: het hokje in rij 1 en kolom 2.

Een leeg veld van 4 bij 4: \begin{matrix} . & . & . & . \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \\ \end{matrix}
Om het aantal mogelijkheden wilt bepalen voor een hokje, ga ik uit van het volgende: r=het aantal cijfers dat al is ingevuld in desbetreffende rij, k=het aantal cijfers dat is ingevuld in desbetreffende kolom, en v=het aantal cijfers ingevuld in het desbetreffende vlak. Ga uit van de hoogste waarde. Als voor een hokje geldt, v=1, k=2, r=3, dan r=3 en is er dus 4-3=1, nog een mogelijkheid in dat hokje een getal in te vullen. Dat is de laagste uitkomst.

In hokje (1,1) zijn 4 mogelijkheden een getal in te vullen. Zo zijn er in (1,2) nog 3 mogelijkheden om in te vullen; v=1, r=1, k=0, kies de waarde van v of r; beiden hetzelfde, in (1,3) nog 2 en in (1,4) nog 1. Bovenste rij ingevuld.
In (2,1) zijn nog 2 mogelijkheden; in het vlak zijn al 2 cijfers ingevuld, v=2. 4-2=2.
In (2,2) is nog 1 mogelijkheid, v=3. In (2,3) zijn nog 2 mogelijkheden, en in (2,4) is dan nog een mogelijkheid. Bovenste 2 vlakken ingevuld. Ik had na rij 1 ook eerst het aantal mogelijkheden voor bijv. (2,2) kunnen bepalen, voor die rij, maar die volgorde maakt niet zoveel uit.
In (3,1) zijn nog 2 mogelijkheden, k=2 in (4,1) nog 1, k=3. Zo in (3,2) nog 2 mogelijkheden en in (4,2) nog 1. Vlak 3 ingevuld. In (3,3) zijn nog 2 mogelijkheden. In (3,4) nog 1; r=3
In (4,3) nog 1; k=3 en zo in (4,4) nog 1, v, k en r=3.

Als ik dan de matrix invul, kom ik uit op
\begin{matrix} 4 & 3 & 2 & 1 \\ 2 & 1 & 2 & 1 \\ 2 & 2 & 2 & 1 \\ 1 & 1 & 1 & 1 \end{matrix}
Dat is 1^8*2^6*3^1*4^1=2^8*3^1=768 mogelijkheden om een 4 bij 4 sudoku in te vullen.

Als ik dezelfde methode toepas op een sudoku van 9 bij 9 hokjes, kom ik uit op
\begin{matrix} 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ 6 & 5 & 4 & 6 & 5 & 4 & 3 & 2 & 1 \\ 3 & 2 & 1 & 3 & 2 & 1 & 3 & 2 & 1 \\ 6 & 6 & 3 & 6 & 5 & 3 & 3 & 2 & 1 \\ 5 & 5 & 2 & 5 & 5 & 2 & 3 & 2 & 1 \\ 4 & 4 & 1 & 4 & 4 & 1 & 3 & 2 & 1 \\ 3 & 3 & 3 & 3 & 3 & 3 & 3 & 2 & 1 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}
Dat is 1^21*2^19*3^17*4^7*5^8*6^6*7^1*8^1*9^1=2^42*3^25*5^8*7^1=
10189415229926804973158400000000 mogelijkheden om een sudoku van 9 bij 9 in te vullen. Ongeveer 1.019*10^31.

Als er nog iets onduidelijk is hoor ik het graag.

[Anoniem]

Daco,

Kijk eens op de volgende links.
Link1
Link2

RedEvil

[drc.]

Hallo RedEvil,

Dank je voor de links. Onder link 1 wordt ineens een getal neergezet van alle mogelijke sudoku's,
6.670.903.752.021.072.936.960. Alleen daar staat niet hoe dat gevonden is. De "filtermethode" die ze gebruiken begrijp ik wel, maar onder link 2 spreken ze over een grafentheorie. Dat gaat me wat ver.
Ze komen ook anders uit voor latijnse vierkanten; voor een latijs vierkant van 9 bij 9 op 5.524.751.496.156.892.842.531.225.600, ik kom uit op (met dezelfde methode als dat ik gebruikte om het aantal sudoku's te bepalen, alleen geen rekening houden met de vlakken) op 1^17*2^15*3^13*4^11*5^9*6^7*7^5*8^3*9^1. Dat is ongeveer 9,278*10^36 mogelijkheden voor een latijs vierkant van 9 bij 9. Misschien een zwak in mijn methode: ik ga ervanuit dat voor een hokje de cijfers die al in bijv. de kolom staan altijd hetzelfde zijn als in bijv. de rij, omdat dat het maximaal aantal mogelijkheden zijn. Beperking natuurlijk is dat die ook verschillend kunnen zijn en dat daarom soms minder mogelijkheden zijn voor dat hokje.

[Anoniem]

Daco,

Beide links hebben ook links naar "extra" informatie over sudoku's. Zeker de link naar 'Handout van K.P. Hart over Sudoku' en 'Sudoku Squares and Chromatic Polynomials' zijn de moeite van het lezen waard.

RedEvil

[drc.]

Hallo RedEvil,

Ik heb nu "Handout van K.P. Hart over Sudoku" gelezen, dat vind ik op zich wel te volgen, alleen "Sudoku Squares and Chromatic Polynominials" gaat diep qua stof, dat heb ik niet uit. Ik lees dat veel met brute computerkracht wordt gedaan, maar is dat, net als oplossen van sudoku´s, gedaan met invullen en kijken of het uitkomt, zeg maar "trial and error" of is daar een rekenmethode voor. Ik wil de methode zelf nog aanscherpen, als het me lukt een soort formule/algoritme (Methode om uit te rekenen, mag je dat algoritme noemen?) te schrijven, maar dat wordt een lange, miss. moeilijke formule om mee te werken.

Wordt in ieder geval nog vervolgd..

[drc.]

Ik heb nog iets voor het minimaal aantal ingevulde hokjes in een leeg veld. Tot nu wordt gezegd dat het er minstens 7 moeten zijn; als het er 7 of minder zijn, ontbreken minstens 2 unieke cijfers, bijv. 7 en 9. Die kunnen in het volledig ingevulde veld van plaats verwisseld worden.

Kleine stap verder: Het het er minstens 8 zijn. Als volgt: een blok is 3 vlakken op een rij of een kolom. Vb: vlak 1, 2 en 3 vormen een blok en vlak 2,5 en 8 vormen een blok. Er zijn 6 blokken. Als je 8 unieke - het moeten unieke cijfers zijn, anders de redenatie voor minstens 7 cijfers! - cijfers hebt, staan die in hoogstens 1 horizontaal blok en 1 vertikaal blok, anders kan je niet eens het 9^e unieke cijfer vinden. Gevolg is dat er 4 vlakken die in hetzelfde blok liggen, helemaal leeg bijven, 2 horizontale blokken en 2 verticale. Voor een unieke oplossing moeten in minstens 6 vlakken cijfers zijn ingevuld. Daardoor kunnen in die blokken De cijfers van plaatsen verwisseld worden. Geen unieke oplossing.

edit: zelfs 10; In elk blok mag maar hoogstens 1 blok leeg zijn. Om dat met 8 voor elkaar te krijgen, nog minstens 2 cijfers invullen, dus minstens 10 aan het begin