Semester-Projekt - Sudoku

Prof. Dr. Jürgen Cleve

1 Das Spiel

Ein aus Japan stammendes Spiel ist SUDOKU. Gegeben ist eine Matrix (9x9). In diese müssen die Zahlen 1 ...9 mit folgenden Restriktionen eingegeben werden:

• In jeder Zeile muss exakt einmal jede Ziffer vorkommen.
• In jeder Spalte muss exakt einmal jede Ziffer vorkommen.
• In jedem der 9 Quadranten (3x) muss jede Ziffer einmal vorkommen.

Gegeben sind einige Zahlen.

Man beachte, dass die Matrix nochmal in Quadranten unterteilt ist. Auch in diesen muss jede Ziffer exakt einaml vorkommen.

Und wie sollen wir hier die Matrix EINDEUTIG auffüllen?

Nun, in jeder Spalte MUSS jede Zahl vorkommen. Wo können wir die 4 in der 2. Spalte platzieren? Nur noch im 1. Quadranten, da die 4 ja schon in den beiden unteren Quadranten enthalten ist. Also kann die 4 nur auf der Position (2,2) platziert werden.

Und so vervollständigt man nach und nach die Matirx.

2 Die Aufgabe

Entwickeln Sie in PROLOG ein Programm, welches eine vorgegebene Matrix entsprechend der obigen Regeln auffüllt.

Bitte nutzen Sie SWI-Prolog.

3 Worauf dürfen Sie aufbauen?

Ich habe eine Datei mit einigen vordefinierten Prädikaten bereitgestellt.

Folgende Schnittstellen / Konventionen halten Sie bitte UNBEDINGT ein.

3.1 Dateien

• Ihr Programm soll EINE Prolog-Datei sein.
• Sie sollten die zu lösenden Rätsel auf eine Datei sudokuraetsel.pl, die sich im gleichen Verzeichnis befindet, schreiben. Diese Datei können Sie von Ihrem Hauptprogramm aus mittels consult(sudokuraetsel) laden.
• Die Darstellung der Matrix erfolgt als Liste von Listen, z.B.
  

  [
  [1,n,n,n,n,n,n,n,n],
  [n,3,n,n,n,n,n,n,n],
  [n,n,5,n,n,n,n,n,n],
  [n,n,n,4,n,n,n,n,n],
  [n,n,n,n,2,n,n,n,n],
  [n,n,n,n,n,1,n,n,n],
  [n,n,n,n,n,n,5,n,n],
  [n,n,n,n,n,n,n,1,n],
  [n,n,n,n,n,n,n,n,2]
  ]
  

• Nicht besetzte Positionen werden durch n dargestellt.
• Die in sudokuraetsel.pl abgelegten Rätsel müssen dort als Fakten (r/2) vorliegen.

  r(2,[
  [8,n,n,n,7,n,n,n,2],
  [n,n,6,4,n,2,8,n,n],
  [n,5,n,n,3,n,n,1,n],
  [n,1,n,5,n,4,n,2,n],
  [2,n,5,n,n,n,6,n,7],
  [n,3,n,2,n,7,n,5,n],
  [n,2,n,n,1,n,n,3,n],
  [n,n,9,7,n,3,4,n,n],
  [3,n,n,n,4,n,n,n,8]
  ]
  ).
  

3.2 Prädikate

Ihr Hauptprädikat muss test/2 heißen. Der erste Parameter ist das zu lösende Rätsel, der zweite die Lösung.

Die Lösung muss selbstverständlich wieder eine Liste von Listen sein.

4 Projektablauf

• Maximal 2er Teams.
• Abgabe des Projektes bis: 15.5.06.
• Bitte eine kurze Doku, in der aber alles erläutert ist.