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: */
00051 Queens_propagator_it_la : look_ahead(Queens_propagator_it)$
00052 
00053 /* The look-ahead version iterated: */
00054 Queens_propagator_it_la_it : prop_fixedpoint(Queens_propagator_it_la)$
00055 
00056 /* Using the default backtracking algorithm to solve it: */
00057 Queens_constraint_backtracking(n) := constraint_backtracking(Queens_dom(n),Queens_propagator_it,variable_heuristics_tau)$
00058 /* For comparison, using the trivial heuristics: */
00059 Queens_constraint_backtracking_th(n) := constraint_backtracking(Queens_dom(n),Queens_propagator_it,trivial_variable_heuristics)$
00060 /* Counting all solutions: */
00061 Queens_constraint_backtracking_counting(n) := constraint_backtracking_counting(Queens_dom(n),Queens_propagator_it,variable_heuristics_tau)$
00062 
00063