Sudoku in Haskell < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Aufgabe | Sudoku ist ein bekanntes Zahlenrätsel. In der meistens angebotenen Variante besteht es aus einem Quadrat mit
9 x 9 Feldern. In jedes der Felder ist eine Zahl von 1 bis 9 so einzutragen, dass in jeder Zeile, jeder Spalte und
in jedem Teilquadrat der Größe 3 x 3 alle Zahlen von 1 bis 9 auftreten. Durch Vorgaben in einzelnen Feldern
wird eine eindeutige Lösung erzwungen.
Implementieren Sie eine Haskell-Funktion sudoku, die aus einer Vorgabe eine Lösung bestimmt. Die Vorgabe
erfolgt, indem die Zahlen in den Feldern einer jeden Zeile, beginnend von unten, als Liste angegeben werden.
Wenn in einem Feld keine Vorgabe erfolgt, wird eine Null in die Liste eingetragen. Insgesamt besteht also eine
Vorgabe aus einer Liste von neun Listen, die jede neun Einträge hat.
Als Lösung wird wieder eine solche Liste ausgegeben, wobei nun keine Nullen mehr auftreten dürfen.
Folgende Typen sind zu benutzen:
type Vorgaben =  Wert
type Loesung = Wert
type Wert = Int
type Sudoku = Vorgaben->Loesung
Ein Standarttestfall lautet:
v = 0,2,3,5,8,9,7,4,6],
[4,0,8,6,7,3,5,2,1],
[6,5,0,4,1,2,3,9,8],
[2,1,5,0,3,8,4,6,9],
[7,3,4,9,0,1,8,5,2],
[9,8,6,2,4,0,1,7,3],
[3,7,2,8,5,6,0,1,4],
[5,6,1,3,9,4,2,0,7],
[8,4,9,1,2,7,6,3,0
und Haskell soll die stellen, wo eine Null steht in die richtigen Zahlen umwandel, etwa so:
sudoku v ==
1,2,3,5,8,9,7,4,6],
[4,9,8,6,7,3,5,2,1],
[6,5,7,4,1,2,3,9,8],
[2,1,5,7,3,8,4,6,9],
[7,3,4,9,6,1,8,5,2],
[9,8,6,2,4,5,1,7,3],
[3,7,2,8,5,6,9,1,4],
[5,6,1,3,9,4,2,8,7],
[8,4,9,1,2,7,6,3,5
|
Hi...
Ich hab mal eine Implementierung zum Sudoku geschrieben:
type Vorgaben = Wert
type Loesung = Wert
type Sudoku = Vorgaben->Loesung
type Wert = Int
sudoku::Sudoku
sudoku a = []
x = [1,2,3,4,5,6,7,8,9]
f a1 = einfüge (fehlt x (quicksort a1)) a1 --Gibt vollstänige Liste heraus, wo vorher noch eine Zahl gefehlt hat.
quicksort [] = []
quicksort [a] = [a]
quicksort (a:l) = (quicksort l1) ++ (a:quicksort l2)
where (l1,l2) = sep a l
sep a [] = ([],[])
sep a (x:l)
| x<a = (x:l1,l2)
| otherwise = (l1, x:l2)
where (l1,l2) = sep a l
fehlt (x:y) (a:b)
| a == 0 = fehlt (x:y) b
| x == a = fehlt y b
| x /= a = x
einfüge x (t:r)
| t /= 0 = t:(einfüge x r)
| t == 0 = x:r
Damit kann man eine fehlende Zahl in einer Liste rausbekommen, das Problem, wenn zum Beispiel mehrere Fehlen in einer Reihe, dann funktioniert es nicht ganz....
Wie kann man bestimmte Elemente aus einer Liste nehmen und diese Vergleichen??? Quasi der Test für das 3x3 Feld oder die Diagonalen vergleiche.
Kann einer Helfen...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mi 02.01.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
