OKlibrary  0.2.1.6
Generators.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 2.12.2007 (Swansea) */
00002 /* Copyright 2007, 2008, 2009 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007
00022 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/BranchingTuples/Basic.mac")\$
00023 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/ConstraintProblems/Domains.mac")\$
00024 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/Backtracking/ConstraintSatisfaction.mac");
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")\$
00026
00027
00028 /* ************
00029    * n Queens *
00030    ************
00031 */
00032
00033 /* The domain association for n Queens: */
00034 Queens_dom(n) := block([sn : setn(n)], create_list(sn,i,1,n))\$
00035
00036 /* The simplest propagator for n queens, just crossing out values which are
00037    not compatible with a variable which has a singleton domain: changes its
00038    arguments, returns true if a change took place: */
00039 Queens_propagator(dom) := block([n : length(dom), prop : false],
00040   for i : 1 thru n do
00041     if length(dom[i]) = 1 then block([j : listify(dom[i])[1]],
00042       for k : 1 thru n do if k # i then block([dom_k : dom[k]],
00043         dom[k] : setdifference(dom_k, {j,j-k+i,j+k-i}),
00044         if length(dom[k]) < length(dom_k) then prop : true)),
00045   return(prop))\$
00046
00047 /* Iterated propagator for n queens: */
00048 Queens_propagator_it : prop_fixedpoint(Queens_propagator)\$
00049
00050 /* The look-ahead version of the iterated propagator: */