Arguments are not sufficiently instantiated

Help!
1

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

2

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).
3

@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
4

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
5

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

6

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