[informatica] Sudoku's oplossen met de computer

Heb je een leuke tutorial, een duidelijke uitleg van een bepaald onderwerp, een interessante minicursus of heb je een leuk trucje gevonden, post het hier.
Plaats reactie
Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1096
Lid geworden op: 23 apr 2010, 18:11

[informatica] Sudoku's oplossen met de computer

Bericht door op=op » 07 mei 2010, 10:08

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

SafeX
Moderator
Moderator
Berichten: 14223
Lid geworden op: 29 dec 2005, 11:53

Re: [informatica] Sudoku's oplossen met de computer

Bericht door SafeX » 30 jun 2010, 13:14

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

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1096
Lid geworden op: 23 apr 2010, 18:11

Re: [informatica] Sudoku's oplossen met de computer

Bericht door op=op » 30 jun 2010, 17:21

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.

SafeX
Moderator
Moderator
Berichten: 14223
Lid geworden op: 29 dec 2005, 11:53

Re: [informatica] Sudoku's oplossen met de computer

Bericht door SafeX » 30 jun 2010, 17:43

Bedankt, ik puzzel verder ...

David
Moderator
Moderator
Berichten: 4935
Lid geworden op: 14 mei 2009, 16:22

Re: [informatica] Sudoku's oplossen met de computer

Bericht door David » 30 jun 2010, 21:42

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



Klopt dat?
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)
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?
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1096
Lid geworden op: 23 apr 2010, 18:11

Re: [informatica] Sudoku's oplossen met de computer

Bericht door op=op » 01 jul 2010, 08:29

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 ;-(.

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1148
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Re: [informatica] Sudoku's oplossen met de computer

Bericht door Sjoerd Job » 01 jul 2010, 10:40

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 ;-(.
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 ;).

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.''

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1096
Lid geworden op: 23 apr 2010, 18:11

Re: [informatica] Sudoku's oplossen met de computer

Bericht door op=op » 01 jul 2010, 15:58

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
Vergevorderde
Vergevorderde
Berichten: 1148
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Re: [informatica] Sudoku's oplossen met de computer

Bericht door Sjoerd Job » 02 jul 2010, 07:32

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.
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.
``Life is complex. It has real and imaginary parts.''

arie
Moderator
Moderator
Berichten: 3051
Lid geworden op: 09 mei 2008, 09:19

Re: [informatica] Sudoku's oplossen met de computer

Bericht door arie » 29 jul 2010, 11:00

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

Plaats reactie