OKlibrary  0.2.1.6
ConstraintSatisfaction.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 21.11.2009 (Swansea) */
00002 /* Copyright 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/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/Backtracking/ConstraintSatisfaction.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/ConstraintProblems/Generators.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00026 
00027 kill(f)$
00028 
00029 
00030 /* ***************
00031    * Propagators *
00032    ***************
00033 */
00034 
00035 okltest_constraint_backtracking(f) := block(
00036   assert(f([{}],trivial_propagator,trivial_variable_heuristics) = [false,1]),
00037   assert(f(Queens_dom(1),Queens_propagator_it,trivial_variable_heuristics) = [[1],1]),
00038   assert(f(Queens_dom(2),Queens_propagator_it,trivial_variable_heuristics) = [false,1]),
00039   assert(f(Queens_dom(3),Queens_propagator_it,trivial_variable_heuristics) = [false,1]),
00040   assert(f(Queens_dom(4),Queens_propagator_it,trivial_variable_heuristics) = [[2,4,1,3],2]),
00041   /* XXX */
00042   true)$
00043 
00044 
00045 /* ***********
00046    * Solvers *
00047    ***********
00048 */
00049 
00050 
00051 
00052 /* **************
00053    * Heuristics *
00054    **************
00055 */
00056 
00057 /* Removes the first element from the first domain with at least two elements:
00058 */
00059 test_propagator(D) := block([i:1], for d in D do
00060   if length(d) >= 2 then 
00061     (D[i] : disjoin(first_element(d),d), return(done))
00062   else i : i+1
00063 )$
00064 
00065 okltest_test_propagator(f) := block([D],
00066   D:[],f(D),assert(D = []),
00067   D:[{}],f(D),assert(D = [{}]),
00068   D:[{1}],f(D),assert(D = [{1}]),
00069   D:[{1,2}],f(D),assert(D = [{2}]),
00070   D:[{1,2},{1,3}],f(D),assert(D = [{2},{1,3}]),
00071   D:[{1},{},{1,2},{1,3}],f(D),assert(D = [{1},{},{2},{1,3}]),
00072   true)$
00073 
00074 okltest_variable_heuristics_tau(f) := block(
00075   assert(f([{1,2}],identity) = [1,[1,2]]),
00076   assert(f([{1,2},{1,2}],identity) = [1,[1,2]]),
00077   assert(f([{1,2},{1,2,3}],identity) = [1,[1,2]]),
00078   assert(f([{1,2,3},{1,2,3,4}],identity) = [1,[1,2,3]]),
00079   assert(f([{1,2,3,4},{1,2,3}],identity) = [1,[1,2,3,4]]),
00080   assert(f([{1,2}],test_propagator) = [1,[1,2]]),
00081   assert(f([{1,2},{1,2}],test_propagator) = [1,[1,2]]),
00082   assert(f([{1,2},{1}],test_propagator) = [1,[1,2]]),
00083   assert(f([{1},{1,2},{1}],test_propagator) = [2,[1,2]]),
00084   assert(f([{1,2,3},{1,2}],test_propagator) = [1,[1,2,3]]),
00085   assert(f([{1,2},{1},{1,2,3},{1,2,3}],test_propagator) = [3,[1,2,3]]),
00086   /* XXX */
00087   true)$
00088