Sudoku-Problem < Matlab < Mathe-Software < Mathe < Vorhilfe
|
| Aufgabe | 2. Aufgabe Computerspiele (4 Punkte)
Schreiben Sie ein matlab-Skript zur L¨osung des folgenden Sudokus durch ausprobieren:
0 0 0 0 0 0 0 1 0
2 0 0 1 0 3 0 0 0
0 3 6 7 0 0 4 0 5
0 0 1 0 7 0 8 0 2
0 4 0 0 6 0 5 3 0
3 0 0 0 8 0 0 0 7
0 0 3 0 0 7 0 5 8
0 5 0 8 0 0 1 0 0
0 1 2 5 4 0 0 0 0
Zur Erinnerung: Ein Sudoku muss folgende Bedingungen erf¨ullen:
a) Es d¨urfen nur die Ziffern 1-9 vorkommen.
b) Jede Ziffer muss in jeder Zeile genau einmal vorkommen.
c) Jede Ziffer muss in jeder Spalte genau einmal vorkommen.
d) Jede Ziffer muss in jedem der 9 Unter-Quadrate genau einmal vorkommen. |
Ich habe folgende Funktionen schon fertig:
function [exist_zeile] = check_zeile(zeile,x,A)
if (sum(sum(A(zeile,:)==x)))==1
exist_zeile=1;
else
exist_zeile=0;
end
function [exist_spalte] = check_spalte(spalte,y,A)
%für A im Input A' einsetzen um Spalten zu betrachten
if (sum(sum(A(spalte,:)==y)))==1
exist_spalte=1;
else
exist_spalte=0;
end
function [exist_kasten] = check_kasten(kasten,z)
if (sum(sum(kasten==z)))==1
exist_kasten=1;
else
exist_kasten=0;
end
function [zeilen_ok] = check_alle_zeilen(A)
for z=1:9
for zahl=1:9
if check_zeile(z,zahl,A)==0
zeilen_ok=0;
break
end
end
end
zeilen_ok=1;
function [spalten_ok] = check_alle_spalten(A)
for s=1:9
for zahl=1:9
if check_spalte(s,zahl,A')==0
spalten_ok=0;
break
end
end
end
spalten_ok=1;
function [kasten_ok] = check_alle_kasten(A)
k1=A(1:3,1:3);
k2=A(1:3,4:6);
k3=A(1:3,7:9);
k4=A(4:6,1:3);
k5=A(4:6,4:6);
k6=A(4:6,7:9);
k7=A(7:9,1:3);
k8=A(7:9,4:6);
k9=A(7:9,7:9);
for z=1:9
if check_kasten(k1,z)==0
kasten_ok=0;
break
elseif check_kasten(k2,z)==0
kasten_ok=0;
break
elseif check_kasten(k3,z)==0
kasten_ok=0;
break
elseif check_kasten(k4,z)==0
kasten_ok=0;
break
elseif check_kasten(k5,z)==0
kasten_ok=0;
break
elseif check_kasten(k6,z)==0
kasten_ok=0;
break
elseif check_kasten(k7,z)==0
kasten_ok=0;
break
elseif check_kasten(k8,z)==0
kasten_ok=0;
break
elseif check_kasten(k9,z)==0
kasten_ok=0;
break
else
kasten_ok=1
end
end
kasten_ok=1;
Ich vermute, da noch Fehler drinne zu haben.
Aber wie mache ich dann weiter?
Mein Ansatz:
function [sudoku_ok] = check_sudoku(A)
sudoku_ok=0
while sudoku_ok=0
%hier muss die Matrix verändert werden...
check_alle_spalten(A)
check_alle_zeilen(A)
check_alle_kasten(A)
if spalten_ok==1 && zeilen_ok==1 && kasten_ok==1
sudoku_ok=1
A
end
end
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:21 So 02.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Ich habe gehört, dass das mit Backtracking gehen soll. Wie mache ich das den am besten. Ich muss ja schließlich auch drauf eingehen ob ich einen Zeilen- oder Spalten- oder Kaststenkonflikt habe, oder?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:13 Di 04.11.2008 | | Autor: | dormant |
Hi!
Ich wüsste nicht wie es mit Backtracking geht, da ich den Algorithmus nicht kenne, aber für Sudoku bietet sich die Formulierung als Lineares Problem an und die Lösung mittels Simplex-Verfahren. Die Lösung kriegt man in ca. 10 Sekunden.
Gruß,
dormant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Do 06.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
