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

[informatica] Sudoku's oplossen met de computer

Berichtdoor 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
Gebruikers-avatar
op=op
Vergevorderde
Vergevorderde
 
Berichten: 1096
Geregistreerd: 23 Apr 2010, 18:11

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

Berichtdoor 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?
SafeX
Moderator
Moderator
 
Berichten: 14161
Geregistreerd: 29 Dec 2005, 11:53

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

Berichtdoor 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.
Gebruikers-avatar
op=op
Vergevorderde
Vergevorderde
 
Berichten: 1096
Geregistreerd: 23 Apr 2010, 18:11

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

Berichtdoor SafeX » 30 Jun 2010, 17:43

Bedankt, ik puzzel verder ...
SafeX
Moderator
Moderator
 
Berichten: 14161
Geregistreerd: 29 Dec 2005, 11:53

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

Berichtdoor 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)
David
Moderator
Moderator
 
Berichten: 4935
Geregistreerd: 14 Mei 2009, 16:22

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

Berichtdoor 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 ;-(.
Gebruikers-avatar
op=op
Vergevorderde
Vergevorderde
 
Berichten: 1096
Geregistreerd: 23 Apr 2010, 18:11

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

Berichtdoor 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.''
Sjoerd Job
Admin
Admin
 
Berichten: 1148
Geregistreerd: 21 Jan 2006, 15:09
Woonplaats: Krimpen aan den IJssel

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

Berichtdoor 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.
Gebruikers-avatar
op=op
Vergevorderde
Vergevorderde
 
Berichten: 1096
Geregistreerd: 23 Apr 2010, 18:11

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

Berichtdoor 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.''
Sjoerd Job
Admin
Admin
 
Berichten: 1148
Geregistreerd: 21 Jan 2006, 15:09
Woonplaats: Krimpen aan den IJssel

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

Berichtdoor 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: Alles selecteren
1 . | . .
. . | 2 .
- - + - -
. . | . .
. . | 4 2

(het gaat om het principe van de solver, en dat blijft hetzelfde als dat van de 3x3 solver).
arie
Moderator
Moderator
 
Berichten: 2962
Geregistreerd: 09 Mei 2008, 09:19


Terug naar Tutorials en Minicursussen

Wie is er online?

Gebruikers in dit forum: Geen geregistreerde gebruikers en 2 gasten

cron

Wie is er online?

Er zijn in totaal 2 gebruikers online :: 0 geregistreerd, 0 verborgen en 2 gasten (Gebaseerd op de gebruikers die actief waren gedurende 5 minuten)
De meeste gebruikers ooit tegelijkertijd online was 649 op 31 Okt 2014, 18:45

Gebruikers in dit forum: Geen geregistreerde gebruikers en 2 gasten
Copyright © 2009 Afterburner - Free GPL Template. All Rights Reserved.