3-in-einer-Reihe-Logik-Puzzle: Optimierung für sequenz Constraints in Listen/Arrays

Question

Im folgenden Puzzle wir versuchen, das Netz mit den blauen und weißen Quadraten in einer solchen Weise zu füllen, dass:

• A 3 Eine Reihe (oder Spalte) derselben Farbe ist nicht zulässig.
• Jede Zeile und Spalte hat die gleiche Anzahl von blauen und weißen Quadraten.

Wenn wir jetzt mit einem 0 und Blau mit einem 1 repräsentieren weiß, erhalten wir:

0 _ _ _ 1 _ 
_ 0 _ _ _ _ 
_ _ _ _ _ 0 
1 _ _ 0 _ _ 
_ _ 1 1 _ _ 
_ 0 _ _ 1 _ 

Und wir können ziemlich schnell überprüfen, ob

0 1 0 0 1 1 
0 0 1 1 0 1 
1 1 0 1 0 0 
1 1 0 0 1 0 
0 0 1 1 0 1 
1 0 1 0 1 0 

ist die Lösung für dieses Beispiel.

als Nebenbedingungen geschrieben ich folgende:

constraints(Board,N) :- 
    N2 is N // 2, 
    (for(I,1,N), param(Board,N2,N) 
    do 
     Row is Board[I,1..N], 
     Col is Board[1..N,I], 
     ic_global:sequence_total(N2,N2,1,2,3,Row), 
     ic_global:sequence_total(N2,N2,1,2,3,Col) 
    ). 

sequence_total/6 stellt sicher, dass der Wert 1 sollte genau N2-mal auftreten (die Hälfte der Zeit der N) in der Zeile/Spalte, und daß jede Folge in der angegebenen Zeile/col von 3 Elementen sollte zwischen 1 und 2 mal den Wert von 1 enthalten (also keine 3 Quadrate mit Wert 1 nebeneinander erscheinen können).

ich die folgenden Ergebnisse für eine 18x18 Puzzle-Instanz (*):

Solved in 147 backtracks 
Yes (10.39s cpu, solution 1) 

Es sieht aus wie die Zwänge sehr gut ihre Arbeit tun, bevor eine Suche durchgeführt wird, da ‚nur‘ 147 zieht zurück benötigt werden . Die Laufzeit scheint mir jedoch sehr lang zu sein, vor allem im Vergleich zu den Backtracks. Ich schätze, das liegt an der ganzen Sequenzprüfung, die passieren muss? Die Tatsache, dass sich eine der Auswahl-/Auswahlmethoden in search/6 kaum auf die Laufzeit auswirkt, scheint dies zu bestätigen.

Wenn ja, gibt es andere, effizientere Möglichkeiten, Constraint-Sequenzen in einer Liste/einem Array so zu begrenzen, dass N identische Elemente nicht nebeneinander liegen und die Laufzeit verbessert wird?

EDIT

Nach dem zerlegt Version von @jschimpf unten angegeben verwendet wird, werden folgende Ergebnisse erzielt:

Solved in 310 backtracks 
Yes (0.22s cpu, solution 1) 

Die neuen Einschränkungen als Folge nicht so stark sind/6, wir brauchen ein etwas mehr Backtracks, aber unsere Laufzeit sank von 10,39 Sekunden auf 0,22 Sekunden, so dass das Gesamtergebnis sehr wünschenswert ist.

Probendaten:

Puzzle für diese Frage verwendet (ohne löst zieht zurück)

Problem (p (6,1), [(1,1,0), (1, 5,1), (2,2,0), (3,6,0), (4,1,1), (4,4,0), (5,3,1), (5,4, 1), (6,2,0), (6,5,1)]).

Puzzle (*), für die ich meine Ergebnisse veröffentlicht:

Problem (p (18,1), [(1,3,0), (1,9,0), (1,10,0), (1,12,0), (1,14,0), (1,18,1), (2,4,0), (2,7,1), (2, 8,1), (3,2,1), (3,6,0), (3,16,0), (3,17,0), (4,2,1), (4,4, 1), (4,10,1), (4,13,1), (4,18,1), (5,8,1), (5,10,1), (5,15,0) , (5,16,1), (6,12,1), (7,3,0), (7,4,0), (7,6,1), (7,9,0), (7,12,1), (7,17,0), (8,1,1), (8,4,0), (8,8,1), (8,15,1), (8, 16,1), (9,7,0), (9,10,0), (9,14,0), (10,2,1), (10,4,1), (10,6, 1), (10,13,1), (11,7,0), (11,10,1), (12,1,1), (12,4,1), (12,7,1) (12,15,1), (12,16,1), (13,1,1), (13,6,0), (13,8,1), (13,10,0), (13,16,1), (14,5,1), (14,10,0), (14,13,1), (15,1,1), (15,3,1), (15, 12,0), (15,13,1), (15,15,0), (16,2,1), (16,4,0), (16,12,0), (16,18, 0), (17,9,0), (17,15,0), (17,18,0), (18,2,1), (18,8,1), (18,11,1), (18 , 15,1), (18,16,1)]).

Answer 1

Es stellt sich heraus, dass in diesem Fall eine handgefertigte, zerlegt Version der Sequenz Einschränkung ist viel effizienter. Verwenden zum Beispiel

sequence_1_2([X1,X2,X3|Xs]) :- !, 
    S #:: 1..2, 
    X1+X2+X3 #= S, 
    sequence_1_2([X2,X3|Xs]). 
sequence_1_2(_). 

, die die Summe aller 3-Element-Subsequenz 1 oder 2 beschränkt, und ersetzen die sequence_total/6 Constraints mit

..., 
    sum(Row) #= N2, 
    sequence_1_2(Row), 

Dies bringt die Lösungszeit bis zu 0,2 Sekunden.