[informatica] Sudoku's oplossen met de computer
[informatica] Sudoku's oplossen met de computer
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).
als in vakje 3 een 5 staat en 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
(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).
als in vakje 3 een 5 staat en 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
Re: [informatica] Sudoku's oplossen met de computer
Heb je hier nog meer informatie over?
Heb je zelf zo'n prg opgesteld?
Welke dimensies hebben jouw matrices?
Heb je zelf zo'n prg opgesteld?
Welke dimensies hebben jouw matrices?
Re: [informatica] Sudoku's oplossen met de computer
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.
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.
Re: [informatica] Sudoku's oplossen met de computer
Bedankt, ik puzzel verder ...
Re: [informatica] Sudoku's oplossen met de computer
Ik neem aan dat je de velden als volgt hebt genummerd.
Klopt dat?
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?
Klopt dat?
Ik had in je voorbeeld dan, aangenomen dat de indeling van de nummers klopt,op=op schreef: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)
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?
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)
(Raffiek Torreman)
Re: [informatica] Sudoku's oplossen met de computer
Je veldnummering is correct.
Die moet inderdaad 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 ;-(.
Die moet inderdaad 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 ;-(.
-
- Vergevorderde
- Berichten: 1144
- Lid geworden op: 21 jan 2006, 15:09
- Locatie: Krimpen aan den IJssel
Re: [informatica] Sudoku's oplossen met de computer
Waarschijnlijk bedoel eerder dat je bedoelde, wat sommige mensen als 0.9 schrijven. Het verschil tussen x * y en x . y. Alleen met cijfers wordt dat vervelend .op=op schreef:Je veldnummering is correct.
Die moet inderdaad 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 ;-(.
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 mogelijkheden proberen, of in het andere geval: mogelijkheden.
729 rijen bij 324 kolommen: Je matrix is over-bepaald. Heeft hij wel een oplossing??
``Life is complex. It has real and imaginary parts.''
Re: [informatica] Sudoku's oplossen met de computer
Over- en onderbepaaldheid zijn onbekende begrippen bij lineair programmeren.
Alle variabelen x voldoen aan de ongelijkheid 0 <=x <=1, en zijn gehele getallen.
Alle variabelen x voldoen aan de ongelijkheid 0 <=x <=1, en zijn gehele getallen.
-
- Vergevorderde
- Berichten: 1144
- Lid geworden op: 21 jan 2006, 15:09
- Locatie: Krimpen aan den IJssel
Re: [informatica] Sudoku's oplossen met de computer
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.op=op schreef:Over- en onderbepaaldheid zijn onbekende begrippen bij lineair programmeren.
Alle variabelen x voldoen aan de ongelijkheid 0 <=x <=1, en zijn gehele getallen.
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.
``Life is complex. It has real and imaginary parts.''
Re: [informatica] Sudoku's oplossen met de computer
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:
(het gaat om het principe van de solver, en dat blijft hetzelfde als dat van de 3x3 solver).
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