# Arguments are not sufficiently instantiated

I’m using: SWI-Prolog version 9.0.4 on Windows 11 64-bit

Rank newbie here, so please be patient!

Having read the Prolog chapter in Seven Languages In Seven Weeks, I’m trying to write a sudoku solver without looking at his code. Like him, I’m starting with a 4x4 puzzle to keep things simple.

To force myself to learn the language better, I decided not to use any built-in Prolog helpers (like `fd_all_different` and `fd_domain` that he uses). Instead, I decided to write `in_range(List)` that checks all these elements in the list are between 1 and 4, and `unique(List)` that checks that all the elements in List are different. To support that, I also wrote `not_in(E, List)` that checks that the given element E does not appear in the list List.

My code for these is as follows…

``````in_range([]).
in_range([H|T]) :- H > 0, H < 5, in_range(T).

not_in(_, []).
not_in(E, [E]) :- false.
not_in(E, [H|T]) :- E =\= H, not_in(E, T).

unique([]).
unique([H|T]) :- not_in(H, T), unique(T).
``````

I tried these out on a few sample lists, and they seem to wrk fine.

I then tried to use them together to solve a puzzle…

``````sudoku([A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,D3,D4]) :-
% all numbers have to be between 1 and 4
in_range([A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,D3,D4]),
unique([A1,A2,A3,A4]), % row A
unique([B1,B2,B3,B4]), % row B
unique([C1,C2,C3,C4]), % row C
unique([D1,D2,D3,D4]), % row D
unique([A1,B1,C1,D1]), % col 1
unique([A2,B2,C2,D2]), % col 2
unique([A3,B3,C3,D3]), % col 3
unique([A4,B4,C4,D4]), % col 4
unique([A1,A2,B1,B2]), % tl square
unique([A3,A4,B3,B4]), % tr square
unique([C1,C2,D1,D2]), % bl square
unique([C3,C4,D3,D4]), % br square
!.                     % take 1st result
``````

However, this gave an error “Arguments are not sufficiently instantiated.”

I’ve spent quite a bit of time searching, but can’t underatand what I’m doing wrong.

As I said, I’m a rank newbie at prolog, so if anyone can explain what I’m doing wrong I’d be very grateful.

Thanks

The error is happening because the comparison predicates (</2, >/2), only work when both sides are instantiated (i.e. given a value). Typical examples for sudoku solvers use things like library(clpfd), where writing something like `H #> 5` actually creates a constraint (using something called “attributed variables”).

If you just want to stick with the built-ins, I would try using between/3 instead of `> 0` and `< 5`, as that will actually give the variables a value, but leave a choice point, to allow back-tracking; that is, `in_range/1` could look like this:

``````in_range([]).
in_range([H|T]) :- between(1, 4, H), in_range(T).
``````

@jamesnvc Thanks very much for the clear explanation. I can see I still have a lot to learn!

With your one change, the solver works fine. Compared to the amount of code I would have to write in one of the imperative languages I use on a daily basis, this is amazing!

Thanks again.

1 Like

You can also make your own constraints. For example `freeze(H, H > 5)` will provisionally succeed, and then when `H` gets a value, it will either succeed or fail at that point. This can lead to huge speed-ups in combinatoric problems, by pruning the solution space earlier. For this style of programming, you change the generate-and-test to test-and-generate, where the tests are delayed until their arguments are sufficiently instantiated.

This doesn’t come for free because there’s additional overhead in freeze/2 … sometimes pure brute force is the fastest, but if your program runs really slowly, then using the constraint style can lead to big performance gains. Also: programs that use constraints can be difficult to debug; you can see this if you do `trace, freeze(H, (H > 0, H < 5)), H = 6`.

2 Likes

first time I see a clear explanation of what freeze does … thanks!

Wish such easy to grasp explanation also existed for custom using attribute variables

Let me try …

Suppose you want to make a finite domain solver. In formulating the problem that you’re trying to solve, part of it is:
`X ∈ {1,2,3,4,5} ∧ Y ∈ {4,5,6,7,8} ∧ X=Y`. You can then write:

``````?- member(X, [1,2,3,4,5]), member(Y, [4,5,6,7,8]), X=Y.
``````

which produces two solutions:

``````X = Y, Y = 4 ;
X = Y, Y = 5 ;
false.
``````

Another way of doing this is by changing the definition of “unification” to be “narrowing” – that is, with a variable you associate a set of possible values and the =/2 predicate succeeds if there is at least one value that satisfies being in both sets of possible values. We can model the sets with `library(ordsets)`, using intersection for the “narrowing” operations (which =/2 does):

``````?- list_to_ord_set([1,2,3,4,5], X), list_to_ord_set([4,5,6,7,8], Y), ord_intersect(X, Y, Intersection).
Intersection = [4, 5].
``````

This gives the same answer as before, but as a set rather than one value at a time (you can get the values from `Intersection` by using member/2).

To do this, we need two predicates (see the Attributed Variables section of the manual):

• a way of specifying the initial set of possible values (`domain/2`), that uses list_to_ord_set/2.
• a “hook” that is called when unification happens, which uses ord_intersection/2.

So, the query becomes:

``````?- domain(X, [1,2,3,4,5]), domain(Y, [4,5,6,7,8]), X=Y.
``````

and when execution reaches `X=Y` the unification causes `X` and `Y` to become the “same”, with their domain being the value of `Intersection` (that is, `[4,5]`), which is is computed by `ord_intersect(X,Y,Intersection)`.
(There are some additional refinements – if the result of ord_intersect/2 is a singleton list, it is replaced by the single value; and if the result of intersection is `[]`, then `X=Y` fails.)

So, each attributed variable has a value associated with it and a predicate that is executed whenever unification occurs. This has the effect of delaying the “hook” until unification occurs (which is how freeze/2 and when/2 cause a delay – for these, the attribute value contains the variable(s) to check for being instantiated and the goal to run when that happens).

I hope this helps. If not, maybe this will help: Attributed Variables in Prolog (and there’s probably a video somewhere).

1 Like