Rätsel in Prolog

Question

Zuerst habe ich keinen richtigen Namen dieses Rätsels, es heißt einfach "ABC".

Zu Beginn geben sie mir eine Größe von Brett (nxm) und n, m = (1,10) und einen Buchstaben, zum Beispiel C, so in ma Lösung Ich kann nur eine Buchstaben bilden C.
Dann bekomme ich ein paar Dreier in Form (i, j, k), i < = n, j < = m und k gehören zu (A, C).

Zum Beispiel Brett, das es der Anfang wie folgt aussehen:
Example board

Zu jedem leeren Kasten ich die Buchstaben A, B, C in einer solchen Art und Weise geben muss, dass, wenn ich die Eingabe beenden sie die folgenden Voraussetzungen erfüllen müssen Bedingungen:

• wenn in einer Zeile (Spalte) sind verschiedene Buchstaben, wird in dieser Zeile (Spalte) gleich oft
• mindestens in einer Zeile (Spalte) alle Buchstaben die gleiche ist jeder der Buchstaben erscheinen, .

Haben Sie eine Idee, wie Sie diese Art von Rätsel zu lösen?
Vielleicht hat dieses Puzzle seinen eigenen Namen und ich kann irgendwo darüber lesen?

EDIT: Alle Daten muss ich aus der Datei lesen. Und diese Datei sieht wie folgt aus:

4. 4. 'C'. [(3,1, 'B'), (4,1, 'A'), (1,2, 'B'), (4,2, 'C'), (1,3, 'C')), (2,4, "A")].

Kleine richtig: In nur einer Zeile oder Spalte alle Buchstaben gleich sind, nicht in beiden. Lösung für mein Beispiel ist:

B A B A 
B C B C 
C C C C 
C A C A 

Answer 1

Das Problem, das Sie beschreiben kann als eine Art von Einschränkungen Problem über den endlichen Bereich von Buchstaben zu sehen. Ihre Variablen repräsentieren Orte auf dem Board, also haben Sie n * m davon. Jede Variable erstreckt sich über die endliche Domäne möglicher Werte, die durch den vom Benutzer angegebenen Buchstaben angezeigt werden. Schließlich sind die vom Benutzer eingegebenen Tripel und die von der Lösung zu erfüllenden Bedingungen Einschränkungen.

Um die Constraint-Programmierung über endliche Domänen zu implementieren, können verschiedene Werkzeuge und Bibliotheken verwendet werden, z.B. hat SWI-Prolog die clpfd-Bibliothek.

Answer 2

Ich denke, was @KarolyHorvath wollte, dass du teilst, war, wie man das Board in Prolog darstellt, zusammen mit allen Ideen, die du versucht hast, dies selbst zu lösen. Im Folgenden verwende ich eine Liste von Listenrepräsentationen, wobei die inneren Listen Zeilen und deren Elemente Symbole oder Atome sind (einfache Kleinbuchstaben, um es einfach zu halten).

Das Problem ist in gewissem Sinne eine Verallgemeinerung von lateinischen Quadraten, die in jeder Zeile und in jeder Spalte genau eines von jedem Symbol erfordern. Umranden Sie ein lateinisches Quadrat mit einer neuen Zeile und Spalte, die nur ein neues Symbol enthält, das sonst nicht im lateinischen Quadrat angezeigt wird, und Sie haben eine Lösung, die den Anforderungen Ihres Problems entspricht.

Das heißt, das Problem befasst sich mit einer teilweise fertiggestellten rechteckigen Platte, die nicht unbedingt quadratisch und mit dem Symbol-Frequenzen, die von Reihe zu Reihe und Spalte zu Spalte variieren.

Für kleinere Boards wie in Ihrem Example Board, einem 3x3-Array, ist der Brute-Force-Ansatz verlockend. Es gibt jedoch einige einfache Dinge zu codieren, um die Suche effizienter zu halten.

Einige Reihe und einige Spalte muss „Konstante“ sein, das heißt sie nur einen Buchstaben enthalten. Ich denke, ich würde dies zur obersten Wahl im Suchbaum machen, d. H. Eine Zeile und eine Spalte wählen, die ein einzelner Buchstabe sein kann. Beachten Sie, dass, da jede Zeile jede Spalte schneidet, wir den gleichen Buchstaben für diese Zeile und Spalte verwenden.

Aber bevor Sie für die Lösung gesucht werden sollen, müssen Sie die Daten eingeben, die das Board mit seinen „gegeben“ Einträgen darstellen. Verwenden Sie Ihr eigenes Urteil darüber, aber für vernünftige Größe Boards können Sie wahrscheinlich mit der Aufforderung an einen Benutzer, die Anzahl der Zeilen und die Anzahl der Spalten eingeben und dann sie Zeile für Zeile für die Einträge aufgefordert werden.

Beachten Sie, dass der Prolog Begriff Leser will Eingabe durch einen Punkt beendet werden. So könnte Eingang in etwa so funktionieren:

Enter a list of all letters: [a,b,c]. 
How many rows? 4. 
How many cols? 4. 
Enter a row as a list: [_,_,b,a]. 
Enter a row as a list: [b,_,_,c]. 
Enter a row as a list: [c,_,_,_]. 
Enter a row as a list: [_,a,_,_]. 

Der Unterstrich wirkt als anonymen Variable am Eingang und läßt die entsprechende Liste der Listeneinträge, die den Board als freie Variablen.

Sie damit die Liste aller Buchstaben in Ihrem Programm mit darstellen:

Symbols = [a,b,c] 

und der Platine mit einer Liste der Liste, die wie folgt aussehen könnte: es

Board = [[A1,A2,b,a],[b,B2,B3,c],[c,C2,C3,C4],[D1,a,D3,D4]] 

In dem speziellen Beispiel ist nur eine Möglichkeit, um alle Zeilen und Spalten auf den gleichen Buchstaben zu setzen, und zwar indem Sie in der zweiten Spalte und der letzten Zeile alle a:

Board = [[A1,a,b,a],[b,a,B3,c],[c,a,C3,C4],[a,a,a,a]] 

Aber jetzt finden wir die Suche nach Lösungen läuft in einem blinden Ende. Die zweite Reihe hat alle drei Buchstaben, aber in einer Reihe der Länge vier ist es unmöglich, dass die drei Buchstaben jeweils gleich oft erscheinen. Es gibt keine Lösung für dieses Beispiel.

jedoch das „keine Lösung“ Ergebnis ziemlich effizient erreicht wurde.

Hoffentlich gibt Ihnen einige Ideen, wie den allgemeinen Lösungsprozess in Prolog zu codieren.