/*-------------------------------------------------------------*/
/*    An NCL program for solving the 4-queens problem          */
/*    (C) 1993 Zdravko Markov, II-BAS                          */
/*-------------------------------------------------------------*/
/*
   This is an illustration of a combined use of net-clauses and
DD-rules. A DD-rule infers all solutions of the up to 4-queens
problem (for 1, 2, 3 and 4 queens) and a net-clause filters out
the solutions with less than 4 queens. The representation of the
problem is proposed by Philippe Jorrand (from LIFIA, France) and
used originally for illustrating his idea of "computation by
communication". We use an adapted version of this representation
suitable for an NCL implementation.
 
The chessboard is represented as a network of communicating
"agents", each one connected to the neighboring 8. The agent
connectors are represented by shared variables. Each agent has
two states - "containing a queen" and "passing messages". Being
in the first state, an agent has all its connectors bound to
its unique name (a number from 1 to 16). An agent in the second
state propagates massages (other agent names) through its
connectors in a way the queen moves. This behavior of the agent
is implemented by the two facts "square", defining static data
for the DD-rule. A solution of the problem is achieved when all
agents find a mutual agreement, i.e. all bindings of the shared
variables in the network are consistent with the agent behaviors.
This consistency is checked by the DD-rule, which reports the
states of all agents to a net-clause. The latter is activated
when four agents are in "has_queen" state.
*/
 
/*-------------------------------------------------------------*/
/* A DD-rule representing 16 agents on the 4X4 chessboard  */
start:
square( 1, _1, _2, _3, _4, _5, _6, _7, _8, S1):
square( 2, _9,_10,_11, _3,_12,_13,_14,_15, S2):
square( 3,_16,_17,_18,_11,_19,_20,_21,_22, S3):
square( 4,_23,_24,_25,_18,_26,_27,_28,_29, S4):
square( 5, _2,_30,_31,_32,_13,_33,_34,_35, S5):
square( 6,_10,_36,_37,_31,_20,_38, _8,_39, S6):
square( 7,_17,_40,_41,_37,_27,_42,_15,_43, S7):
square( 8,_24,_44,_45,_41,_46,_47,_22,_48, S8):
square( 9,_30,_49,_50,_51,_38,_52,_53,_54, S9):
square(10,_36,_55,_56,_50,_42,_57,_35,_58,S10):
square(11,_40,_59,_60,_56,_47,_61,_39,_62,S11):
square(12,_44,_63,_64,_60,_65,_66,_43,_67,S12):
square(13,_49,_68,_69,_70,_57,_71,_72,_73,S13):
square(14,_55,_74,_75,_69,_61,_76,_54,_77,S14):
square(15,_59,_78,_79,_75,_66,_80,_58,_81,S15):
square(16,_63,_82,_83,_79,_84,_85,_62,_86,S16)
   => S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11,S12,S13,S14,S15,S16.
 
/* Agent behavior */
square(Q,Q,Q,Q,Q,Q,Q,Q,Q,has_queen(Q)).
square(_,I,I,J,J,K,K,L,L,no_queen).
 
no_queen.
 
/* Net-clause activated if 4 agents are in "has_queen" state */
has_queen(A):
has_queen(B):
has_queen(C):
has_queen(D):
node(A,B,C,D,4,(write(A-B-C-D),nl)).
 
/*--------------------------------------------------------------*/
/* EXAMPLE:                                                     */
/*--------------------------------------------------------------*/
/*
?- start.
2 - 8 - 9 - 15
3 - 5 - 12 - 14
*/