Skip to content

treeSolver

treeSolver is a simple server written in GNU Prolog offering a socket connection to the constraint solver of GNU Prolog. One can send constraints encoded in a tree structure to the server which solves the constraint and sends a solution back (if any).

My main motivation to write this was to have an easy way of accessing the constraint solver of GNU Prolog via, e.g., Java programs. One can easily change the sourcecode in a way more suited for specific needs, e.g., adding partial arc consistency constraints. It can be compiled on various platforms.

treeSolver is licensed under the GNU General Public License Version 2.

Download

Current Version: 251010

Binary executables
treeSolver64 - GNU/Linux (64bit) [ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.4, not stripped]
treeSolver32 - GNU/Linux (32bit) [ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.4, not stripped]
treeSolver.exe - Windows (32bit) [PE32 executable for MS Windows (console) Intel 80386 32-bit]
treeSolverMac - Apple OS X [Mach-O executable i386]

Source
treeSolver.pl.zip
Compile with:
gplc --no-top-level treeSolver.pl

Manual

The server is started with:
treeSolver portnumber [vector_max]
Give here the number of the port where the server should run, and optionally a positive number vector_max, which sets the maximum of possible values for variables in case a sparse representation is necessary, see the GNU Prolog manual for details. If instead of a portnumber the minus sign "-" is given, treeSolver will let the operating system pick a port. If the vector_max parameter is missing, a default of 10000 is chosen. After being connected to the server-socket, the server sends a welcome message. Now one can send constraints encoded in a tree structure to the server.

The general format of a query is:
[VarList, Tree].
or
[VarList, Tree, Method].
(including the final point!)

Here VarList is a list of variables which appear in a constraint which is encoded in the Tree, having the form (in GNU Prolog syntax):
tree(node_c(Y,A,B,empty)) :- generic_var(Y), integer(A), integer(B).
tree(node_s(Y,empty)) :- generic_var(Y).
tree(node_s(Y,empty)) :- integer(Y).
tree(node_s(Y,X)) :- tree(X), constraint(Y).
tree(node_d(Y,X1,X2)) :- tree(X1), tree(X2), constraint(Y).
There are three kinds of nodes here:
  • node_c - This is a leaf representing a variable Y which is initially constrained by A <= Y <= B
  • node_s - This is either a leaf representing a variable or an integer, or a unary node representing a unary constraint (currently the boolean not is the only unary constraint possible here).
  • node_d - This is a binary node representing a binary constraint.

The Method determines the heuristics to select values in case of multiple solutions. It can be:
  • min - The smallest solution is returned.
  • max - The greatest solution is returned.
  • middle - The solution in the middle is returned.
  • random - A random solution is returned. Note that the range of a random solution depends on the fd_set_vector_max value.
If no method is given in the query, min is the default.

If random is used as the heuristics, the random seed is per default automatically randomly reinitialized for each query. One can also set a specific seed, which is useful to reproduce results. To do so, send:
[set_seed, seed].
Where seed is the seed you want to set (a non-negative integer). After this being sent the seed is fixed to the given value. To enable again the automatic random reinitialization, send:
[set_random_seed].
A solution is returned as a list of values for the variables in the VarList. If no solution is found, false is returned. If the constraint does not contain variables at all, and is true, true is returned.

To end the server send:
bye.
to the socket.

Most of the GNU Prolog constraints are embedded, see the following tables.

Arithmetic constraints (only full arc consistency constraints are supported):

GNU Prolog constraint treeSolver constraint
+ (sum) op_add
- (subtraction) op_subtract
* op_mult
/ op_div
** op_pow
min op_min
max op_max
dist op_dist
// op_divquot
rem op_rem
#=# op_eq
#\=# op_neq
#<# op_ls
#=<# op_leq
#># op_gr
#>=# op_geq


Boolean constraints:

GNU Prolog constraint treeSolver constraint
#\ op_not
#<=> op_equiv
#\<=> op_nequiv
## op_xor
#==> op_implies
#\==> op_nimplies
#/\ op_and
#\/\ op_nand
#\/ op_or
#\\/ op_nor


Example Queries
(all for the method min)
X <= 5:
[[X], tree(node_d(op_leq, node_s(X, empty), node_s(5, empty)))].
Returned solution: [0]
X > Y and Y > 5:
[[X,Y], tree(node_d(op_and, node_d(op_gr, node_s(X, empty), node_s(Y, empty)), node_d(op_gr, node_s(Y, empty), node_s(5, empty))))].
Returned solution: [7,6]
X <= 5 or X >= 7:
[[X], tree(node_d(op_or, node_d(op_leq, node_s(X, empty), node_s(5, empty)), node_d(op_geq, node_s(X, empty), node_s(7, empty))))].
Returned solution: [0]
X <= 5 and X >= 7:
[[X], tree(node_d(op_and, node_d(op_leq, node_s(X, empty), node_s(5, empty)), node_d(op_geq, node_s(X, empty), node_s(7, empty))))].
Returned solution: false
5 < 7:
[[], tree(node_d(op_ls, node_s(5,empty), node_s(7,empty)))].
Returned solution: true
A = 24 and B > 2 and C = A*B:
[[A,B,C], tree(node_d(op_and, node_d(op_and, node_d(op_eq, node_s(A, empty), node_s(24,empty)), node_d(op_gr, node_s(B, empty), node_s(2, empty))), node_d(op_eq, node_s(C, empty), node_d(op_mult, node_s(A,empty), node_s(B,empty)))))].
Returned solution: [24,3,72]
Changelog
  • Version 251010 - Instead of a port number a "-" can be given, which lets the operating system pick the port. One more flush for Windows is added.
  • Version 010909 - The random seed can be explicitly set and changed.
  • Version 050809 - The vector_max can be set via an additional parameter. When the client sends an EOF, the treeSolver terminates.
  • Version 110309 - The random seed is reinitialized after each query.
  • Version 170808 - The heuristics for selecting solutions can be chosen.
  • Version 180607 - Not flushing the the welcome message caused trouble under Windows, fixed.
  • Version 050607 - The main server loop is now done via a repeat/0 to prevent a trail stack overflow.
  • Version 300507 - First version.

Posted by Lars Frantzen | on