[informatica] Sudoku's oplossen met de computer
Geplaatst: 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
(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