What Are Finite Domains and How Does GNU Prolog's FD Solver Work?

Updated

Finite domains (FD) in GNU Prolog let a logic variable range over a bounded set of integers instead of being a free, unbound term. You post constraints over those variables, and the solver prunes impossible values before any search happens. GNU Prolog is a free Prolog compiler with a built-in FD constraint solver, so you get constraint programming and ISO-standard Prolog in one system without a separate library or explicit domain declarations.

Finite domains vs. plain Prolog unification

In plain Prolog, an unbound variable stands for anything, and X = 3 simply binds it. There is no notion of "X must be between 1 and 9." You can only test a value after it is bound, so combinatorial problems are solved by generate-and-test: enumerate candidates, then check each one. That is correct but slow, because failures are detected late.

A finite-domain variable is different in one key way: its possible values are restricted up front, and constraints propagate that restriction. If X has domain 1..9 and you post X #> 7, the solver immediately narrows X to 8..9. Any later constraint that would empty a domain fails at once rather than after a long enumeration.

How GNU Prolog integrates FD variables

GNU Prolog's FD variables are fully compatible with ordinary Prolog variables and integers, and the site states there is no need for explicit FD declarations. You do not open a special mode or declare a variable's type; you introduce a domain by using FD constraints on it. This keeps FD code readable as normal Prolog and lets you mix constraint solving with the rest of the language (unification, recursion, DCGs, the C interface).

The solver itself is described as very efficient and comparable to commercial solvers, and high-level constraints can be described in terms of simple primitives. That means the predefined constraints are convenient surface syntax over a smaller core, which is useful to know when you want to write your own propagator.

The typical workflow

Constraint programs in GNU Prolog follow three phases:

  1. Declare domains — restrict each variable to a finite range, e.g. X :: 1..9 or via an arithmetic FD constraint.
  2. Post constraints — relate variables with arithmetic relations, all_different, and similar predefined constraints. The solver propagates and prunes domains.
  3. Label / search — assign concrete values to the remaining variables (labeling), backtracking through the reduced search space.

The important point is ordering: propagation does the pruning, labeling does the enumeration. If you label too early you lose the benefit of propagation; if you never label you get a store of constrained variables but no concrete solution.

A small example

A classic fit is Sudoku-style or assignment puzzles, where each cell has domain 1..9 and rows, columns, and boxes must be all-different. In GNU Prolog you would:

  • give every cell the domain 1..9,
  • post all_different on each row, column, and 3×3 box,
  • post the given clues as equalities,
  • then label the cells.

Propagation alone often fills many cells before search begins, which is exactly the gain over generate-and-test. The same pattern applies to scheduling: tasks with start times in a range, precedence constraints between them, and all_different on shared resources.

What you get beyond the solver

GNU Prolog is a compiler as well as an interpreter. It accepts Prolog+constraint programs and produces native, stand-alone executables (comparable to how gcc turns C into a binary), and it avoids linking most unused built-in predicates, so executables can be small. The Prolog side conforms to the ISO standard with extensions such as global variables, DCGs, sockets, and an OS interface, and there are more than 300 built-in predicates plus a Prolog debugger and a low-level WAM debugger.

Choosing it, with conditions

GNU Prolog suits you if you want FD constraint solving and native compilation in one free system, and you are comfortable with Prolog syntax. It is a strong fit for combinatorial puzzles, scheduling, and assignment problems where domains are naturally finite integer ranges. If your problem needs continuous or real-valued constraints, or a large ecosystem of external constraint libraries, this FD solver is not aimed at that. The current stable version listed on the site is gprolog-1.5.0; check the manual and supported-platforms pages for details on your target system before committing.