[informatica] Sudoku's oplossen met de computer

[op=op]

Ik ga er van uit dat de lezer bekend is met de Sudoku puzzel:
(9x9 vierkantjes, verdeeld in 9 blokken van 3x3. In elke rij, kolom en blok komen de getallen 1 t/m 9).

Een computerprogramma schrijven dat Sudoku puzzels oplost lijkt nog niet zo eenvoudig, maar is in feite eenvoudiger dan je zou denken. De oplossing is namelijk de oplossing van een matrixvergelijking Ax=b.

Nummer de vakjes van 1 t/m 81.
We stellen nu de vergelijkingen op, die we later in een matrixvergelijking omzetten.
De onbekenden hebben alle 2 indices x(.,.). (Die indices zijn een geheugensteuntje, je hoeft ze niet te programmeren).

\(x(3,5) = 1\)

als in vakje 3 een 5 staat en

\(x(3,5) = 0\)

als in vakje 3 geen 5 staat.
In elke rij komt precies één 5 voor.
Dat betekent voor de eerste rij:
x(1,5) + x(2,5) + ... + x(9,5) = 1
(algemeen: x(9k+1,p) + x(9k+2,p) + ... + x(9k+9,p) = 1 voor k=0,...,8, p=1,...,9)

In elke kolom komt een 6 voor.
Dat betekent voor de eerste kolom:
x(1,6) + x(10,6) + ... + x(72,0) = 1
(algemeen: x(k+1+0.9,p) + x(k+1+1.9,p) + x(k+1+2.9,p) + ... + x(k+1+8.9,p) = 1, k=0,...,8, p=1,...,9)

En voor de blokken
x(1+k+m,p) + x(2+k+m,p) + x(3+k+m,p) + x(10+k+m,p) + x(11+k+m,p) + x(12+k+m,p) + x(19+k+m,p) +x(20+k+m,p) + x(21+k+m,p) = 1
k=0,3,6, m=0,27,54, p=0,...,9

We moeten nog vermelden dat in elk vakje maar 1 cijfer ingevuld mag worden, d.w.z.
voor het eerste vakje:
x(1,1) + x(1,2) + ... + x(1,9) = 1.
(algemeen: x(k,1) + x(k,2) + ... + x(k,9) = 1, k=1,...,81).

Verder zijn er nog enkele vakjes bekend. B.v. in het eerste vakje staat een 3,
dan betekent dat nog een extra vergelijking x(1,3) = 1.

Alles bij elkaar een flink aantal vergelijkingen, maar een computer draait daar zijn hand niet voor om.

We hebben zo een stelsel vergelijkingen.
In matrixvorm Ax = b bestaat de b uit louter 1-en en de matrix A uit nullen en enen.
Dit is op te lossen met standaard oplosprogramma's voor het oplossen van stelsels in gehele getallen.
Lineair programmeren dus. Zit in Maple en Mathematica.

Voor wie graag puzzels oplost met de computer hier een site (met oplossingen)
http://www.chlond.demon.co.uk/academic/puzzles.html

[Safe]

Heb je hier nog meer informatie over?
Heb je zelf zo'n prg opgesteld?
Welke dimensies hebben jouw matrices?

[op=op]

De dimensie van de matrix is afhankelijk van het aantal gegevens vooraf.
De grootte van de matrix ligt tussen 324 bij 729 en 405 bij 729.
Ik heb zelf dit nooit geprogrammeerd, maar het moet werken.
Mogelijk dat ik na de vakantie een werkend javaprogramma geef.

[Safe]

Bedankt, ik puzzel verder ...

[drc.]

Ik neem aan dat je de velden als volgt hebt genummerd.

\(\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18\\ 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27\\ 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36\\ 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45\\ 46 & 47 & 48 & 49 & 50 & 51 & 52 & 53 & 54\\ 55 & 56 & 57 & 58 & 59 & 60 & 61 & 62 & 63 \\ 64 & 65 & 66 & 67 & 68 & 69 & 70 & 71 & 72 \\ 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 & 81\end{bmatrix}\)

Klopt dat?

In elke kolom komt een 6 voor.
Dat betekent voor de eerste kolom:
x(1,6) + x(10,6) + ... + x(72,0) = 1
(algemeen: x(k+1+0.9,p) + x(k+1+1.9,p) + x(k+1+2.9,p) + ... + x(k+1+8.9,p) = 1, k=0,...,8, p=1,...,9)

Ik had in je voorbeeld dan, aangenomen dat de indeling van de nummers klopt,
x(1,6) + x(10,6) + ... + x(73,6) = 1
Het veld links onderin 73, en het cijfer 6.
algemeen:
(algemeen: x(k+1+0.9,p) + x(k+1+1.9,p) + x(k+1+2.9,p) + ... + x(k+1+8.9,p) = 1, k=0,...,8, p=1,...,9)
Wat bedoel je met 0.9?

Evt. een veld beschrijven met
x(9r+k,p) met r is nummer van de rij, k=nummer van de kolom. r=0,...,8, k=1,...,9 en p=1,...,9

0.9=0*9=0?

[op=op]

Je veldnummering is correct.
Die

\(x(72,0)\)

moet inderdaad

\(x(73,6)\)

zijn. (Merkwaardige fout).
Nog merkwaardiger is de notatie 0.9. Dat moet inderdaad 0*9 zijn. Ik moet een flauwte in het hoofd gehad hebben ;-(.

[Sjoerd Job]

Je veldnummering is correct.
Die

\(x(72,0)\)

moet inderdaad

\(x(73,6)\)

zijn. (Merkwaardige fout).
Nog merkwaardiger is de notatie 0.9. Dat moet inderdaad 0*9 zijn. Ik moet een flauwte in het hoofd gehad hebben ;-(.

Waarschijnlijk bedoel eerder dat je

\(0\cdot 9\)

bedoelde, wat sommige mensen als 0.9 schrijven. Het verschil tussen x * y en x . y. Alleen met cijfers wordt dat vervelend .

Daarnaast wordt het als matrixvergelijking moeilijk. Je matrix is namelijk onder-bepaald, of over-bepaald, afhankelijk van hoe ik het moet lezen:
tussen 324 bij 729 en 405 bij 729

324 rijen bij 729 kolommen: Dat geeft aan dat je 729-324 variabelen hebt die je vrij kan kiezen, en dan krijg je de andere waarden cadeau (als die niet afhankelijk zijn, dan wordt het erger). Maar, ze moeten in {0,1} zitten, en ik verwacht dat er maar 1 oplossing is waarvoor die andere variabelen ook hieraan voldoen. Dus moet je

\(2^{405}\)

mogelijkheden proberen, of in het andere geval:

\(2^{324}\)

mogelijkheden.

729 rijen bij 324 kolommen: Je matrix is over-bepaald. Heeft hij wel een oplossing??

[op=op]

Over- en onderbepaaldheid zijn onbekende begrippen bij lineair programmeren.
Alle variabelen x voldoen aan de ongelijkheid 0 <=x <=1, en zijn gehele getallen.

[Sjoerd Job]

Over- en onderbepaaldheid zijn onbekende begrippen bij lineair programmeren.
Alle variabelen x voldoen aan de ongelijkheid 0 <=x <=1, en zijn gehele getallen.

Bij lineair programmeren, zijn dat inderdaad onbekende begrippen. Maar, zelfs dan kom je nog niet veel verder. Voor gehele getallen moet je overstappen naar integer lineair programmeren, wat computationeel veel zwaarder is.

Wat ik mij nu afvraag: Zou de ILP methode hier efficiënter zijn dan een `brute-force' solver? Ik denk namelijk dat je stelsel te groot is voor efficiëntie. Uiteraard zijn alle algoritmes `constant-time'.

Ik ben benieuwd om de implementatie van je solver te zien.

[siep]

Heb je al wat resultaten?
Noot: mocht de 3x3 solver te groot worden voor je computer kan je ook starten met een 2x2 sudoku, bijvoorbeeld deze:

Code: Selecteer alles

1 . | . .
. . | 2 .
- - + - -
. . | . .
. . | 4 2

(het gaat om het principe van de solver, en dat blijft hetzelfde als dat van de 3x3 solver).