## 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.

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