Prolog: Kleine Unterschiede, grosse Wirkung

Beim Durcharbeiten der "Hausaufgaben" von „Sieben Wochen, sieben Sprachen“ hatte ich beim Kapitel zu Prolog einige Schwierigkeiten zu lösen. Da ich mich sonst nicht mit Prolog beschäftige dauerte es recht lange bis ich meinen Fehler finden konnte. Auch wenn ich diesen Blog-Eintrag primär als Gedankenstütze für mich selber schreibe, so würde es mich freuen wenn andere Prolog-Neulinge auch davon profitieren könnten.

Die Aufgabe

An sich war die Hausaufgabe recht einfach: Die vorgegebene Lösung für ein 4x4 Sudoku muss so erweitert werden damit man ein reguläres 9x9 Sudoku lösen kann. Neben dem grösseren gültigen Zahlenbereich mussten vor allem mehr Spalten, mehr Zeilen und mehr Blöcke eingefügt werden.

Mein (fehlerhaftes) Resultat sah so aus:

valid([]).
valid([Head|Tail]) :-
        fd_all_different(Head),
        valid(Tail).

sudoku(Puzzle, Solution) :-
        Solution = Puzzle,


        Puzzle = [S11, S12, S13, S14, S15, S16, S17, S18, S19,
                  S21, S22, S23, S24, S25, S26, S27, S28, S29,
                  S31, S32, S33, S34, S35, S36, S37, S38, S39,
                  S41, S42, S43, S44, S45, S46, S47, S48, S49,
                  S51, S52, S53, S54, S55, S56, S57, S58, S59,
                  S61, S62, S63, S64, S65, S66, S67, S68, S69,
                  S71, S72, S73, S74, S75, S76, S77, S78, S79,
                  S81, S82, S83, S84, S85, S86, S87, S88, S89,
                  S91, S92, S93, S94, S95, S96, S97, S98, S99],

        fd_domain(Solution, 1, 9),

        Row1 = [S11, S12, S13, S14, S15, S16, S17, S18, S19],
        Row2 = [S21, S22, S23, S24, S25, S26, S27, S28, S29].
        Row3 = [S31, S32, S33, S34, S35, S36, S37, S38, S39],
        Row4 = [S41, S42, S43, S44, S45, S46, S47, S48, S49],
        Row5 = [S51, S52, S53, S54, S55, S56, S57, S58, S59],
        Row6 = [S61, S62, S63, S64, S65, S66, S67, S68, S69],
        Row7 = [S71, S72, S73, S74, S75, S76, S77, S78, S79],
        Row8 = [S81, S82, S83, S84, S85, S86, S87, S88, S89],
        Row9 = [S91, S92, S93, S94, S95, S96, S97, S98, S99],

        Col1 = [S11, S21, S31, S41, S51, S61, S71, S81, S91],
        Col2 = [S12, S22, S32, S42, S52, S62, S72, S82, S92],
        Col3 = [S13, S23, S33, S43, S53, S63, S73, S83, S93],
        Col4 = [S14, S24, S34, S44, S54, S64, S74, S84, S94],
        Col5 = [S15, S25, S35, S45, S55, S65, S75, S85, S95],
        Col6 = [S16, S26, S36, S46, S56, S66, S76, S86, S96],
        Col7 = [S17, S27, S37, S47, S57, S67, S77, S87, S97],
        Col8 = [S18, S28, S38, S48, S58, S68, S78, S88, S98],
        Col9 = [S19, S29, S39, S49, S59, S69, S79, S89, S99],

        Square1 = [S11, S21, S31, S12, S22, S32, S13, S23, S33],
        Square2 = [S41, S51, S61, S42, S52, S62, S43, S53, S63],
        Square3 = [S71, S81, S91, S72, S82, S92, S73, S83, S93],
        Square4 = [S14, S24, S34, S15, S25, S35, S16, S26, S36],
        Square5 = [S44, S54, S64, S45, S55, S65, S46, S56, S66],
        Square6 = [S74, S84, S94, S75, S85, S95, S76, S86, S96],
        Square7 = [S17, S27, S37, S18, S28, S38, S19, S29, S39],
        Square8 = [S47, S57, S67, S48, S58, S68, S49, S59, S69],
        Square9 = [S77, S87, S97, S78, S88, S98, S79, S89, S99],

        valid([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9,
                Col1, Col2, Col3, Col4, Col5, Col6, Col7, Col8, Col9,
                Square1, Square2, Square3, Square4, Square5, Square6, 
                Square7, Square8, Square9]),

        write( '\n' ), write( Row1 ),
        write( '\n' ), write( Row2 ),
        write( '\n' ), write( Row3 ),
        write( '\n' ), write( Row4 ),
        write( '\n' ), write( Row5 ),
        write( '\n' ), write( Row6 ),
        write( '\n' ), write( Row7 ),
        write( '\n' ), write( Row8 ),
        write( '\n' ), write( Row9 ).

Kompilierfehler

Als Arbeitsumgebung nutze ich meinen Linux-PC mit Ubuntu 11.4 und GNU Prolog 1.3.0. Nach dem Start von gprolog gab es beim Laden der Datei diese Fehlermeldung:

jgr@R:~/BLOG/$ gprolog
GNU Prolog 1.3.0
By Daniel Diaz
Copyright (C) 1999-2007 Daniel Diaz
| ?- ['sudoku.pl'].
compiling /home/jgr/BLOG/sudoku.pl for byte code...
/home/jgr/BLOG/sudoku.pl:6-23: warning: singleton variables [S31,S32,S33,S34,S35,S36,S37,S38,S39,S41,S42,S43,S44,S45,S46,S47,S48, S49,S51,S52,S53,S54,S55,S56,S57,S58,S59,S61,S62,S63,S64,S65,S66,S67, S68,S69,S71,S72,S73,S74,S75,S76,S77,S78,S79,S81,S82,S83,S84,S85,S86, S87,S88,S89,S91,S92,S93,S94,S95,S96,S97,S98,S99,Row1,Row2] for sudoku/2
/home/jgr/BLOG/sudoku.pl:24-64: warning: suspicious predicate (',')/2
/home/jgr/BLOG/sudoku.pl compiled, 64 lines read - 22767 bytes written, 187 ms

yes
| ?- 

Wer wie ich vor allem in C# entwickelt wird beim ersten Zusammentreffen mit so einer Fehlermeldung wenig anfangen können. Es stehen aber alle nötigen Informationen drin - nur muss man diese erst einmal „entschlüsseln“.

sudoku.pl:6-23: warning: singleton variables [S31,S32,S33,...] for sudoku/2

Laut dieser Fehlermeldung verwendet die Regel sudoku (mit 2 Parametern) die Variablen S31, S32, usw. nur 1 einziges Mal. Schaue ich den Inhalt meiner sudoku-Regel an, sollten diese Variablen aber alle mehrmals verwendet werden.

Auch die Zeilennummern erscheinen auf den ersten Blick nutzlos. Weder in Zeile 6 noch in Zeile 23 sehe ich etwas was nach einem Fehler aussieht. Meldet Visual Studio „; expected Line 97 Column 76“ weis ich das ein „;“ in Zeile 97 fehlt. Prolog ist ein wenig anders.

Die Fehlermeldung kann man aber auch so übersetzen:
„In der Regel sudoku mit 2 Parametern, die zwischen Zeile 6 und 23 definiert ist, werden die Variablen S32, ... nur 1 Mal verwendet.“

Für den Interpreter ist meine Regel zwischen den Zeilen 6 und 23 definiert. Für mich müsste diese aber bis zu Zeile 64 gehen – und hier liegt die Ursache der Fehlermeldung. Prolog nutzt einen Punkt um einzelne Fakten und Regeln zu trennen. Schaut man meinen Regelsatz noch einmal genau an findet man auf Zeile 22 am Ende der Definition von Row2 auch ein Punkt statt einem Komma. Dieser „kleine“ Unterschied hat aber grosse Wirkung. Sind die Regelsätze unvollständig wird Prolog damit kein Sudoku lösen können. Macht man trotzdem weiter sind die Folgefehler kaum mehr zu durchschauen.

Nachdem ich den Punkt durch ein Komma ersetzt hatte liessen sich meine Regeln fehlerfrei laden:

| ?- ['sudoku.pl'].
compiling /home/jgr/BLOG/sudoku.pl for byte code...
/home/jgr/BLOG/sudoku.pl compiled, 64 lines read - 19963 bytes written, 13 ms

yes
| ?- 

Um ein Sudoku zu lösen genügt es nun die bekannten Zahlen sowie ein _ für alle offenen Felder einzugeben. Prolog löst das Rätsel im Handumdrehen – oder noch schneller:

| ?- sudoku([_, _, _, 2, 4, _, 8, _, _,
             _, _, 2, 3, _, _, _, 6, _,
             _, _, _, 7, _, _, 9, 3, _,
             _, _, _, _, 9, _, _, _, 1,
             _, 9, _, 1, 2, 4, _, _, 3,
             _, _, 1, _, _, _, _, _, _,
             3, _, _, _, _, 8, _, 1, _,
             _, 8, 6, 4, 1, _, _, 5, _, 
             _, 7, 4, _, _, 5, _, _, _], Solution).

[6,3,9,2,4,1,8,7,5]
[7,5,2,3,8,9,1,6,4]
[4,1,8,7,5,6,9,3,2]
[2,6,3,8,9,7,5,4,1]
[5,9,7,1,2,4,6,8,3]
[8,4,1,5,6,3,7,2,9]
[3,2,5,9,7,8,4,1,6]
[9,8,6,4,1,2,3,5,7]
[1,7,4,6,3,5,2,9,8]

Tipps für die Problemlösung

Zum Abschluss möchte ich 2 Punkte herauspicken die ich im Nachhinein als besonders wichtig erachte:

1. Im Fehlerfall immer erst den 1. Fehler beheben. Viele Folgefehler werden damit auch gleich beseitigt.
2. Für Sprachen wie Prolog muss der Texteditor oder die Konsole unbedingt eine Schrift verwenden die Punkte und Kommas deutlich differenziert. (Monospace ist dafür nicht geeignet)

Fazit

So richtig spannend wird es erst wenn man vor Probleme gestellt wird. Eine ganz einfache uns simple Aufgabe (eine Lösung von 4x4 auf 9x9 erweitern) verwandelte sich in eine veritable Herausforderung. Wenn man die Antwort kennt ist es banal. Muss man sich aber durch die Fehlermeldungen und unzählige falsche Ansätze kämpfen beginnt erst das eigentliche lernen.

Auch kleine Aufgaben können einem viel beibringen.