/*-------------------------------------------------------------*/ /* 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 */