[taeric]

First, apologies for going to sleep on you. Huge thanks for sticking with this and opening my eyes to this branch of programming. If you have recommended texts, is appreciate it.

For this question, I can really only refer to Knuth. This is exercise 515 of 7.2.2.2. I likely just messed you up on the wording. There are no forced moves for open squares. As soon as you pick one, though, it may force all others.

[zmonx]

In the solution of this exercise, 4 example puzzles are given. Here is the first one:

    knuth(a, [[1,_,_,_,_,6,_,8,_],
              [5,_,8,7,2,1,4,_,6],
              [_,6,_,3,8,_,2,_,1],
              [8,4,_,_,_,3,_,_,5],
              [_,_,5,_,6,_,8,_,_],
              [6,_,_,8,_,_,_,4,2],
              [3,_,6,_,4,8,_,2,_],
              [4,_,7,6,3,2,1,_,8],
              [_,8,_,5,_,_,_,_,4]]).

Consider now a Prolog solution for 9x9 (i.e., "normal") Sudoku puzzles, using integer constraints:

    sudoku(Rows) :-
            length(Rows, 9), maplist(same_length(Rows), Rows),
            append(Rows, Vs), Vs ins 1..9,
            maplist(all_distinct, Rows),
            transpose(Rows, Columns), maplist(all_distinct, Columns),
            Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
            blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is).

    blocks([], [], []).
    blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
            all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
            blocks(Ns1, Ns2, Ns3).

This is indeed exactly a case where search is necessary, because the pruning applied by this concrete constraint solver is not strong enough to deduce the unique solution. If we only post the constraints, we get:

    ?- knuth(a, Rows),
       sudoku(Rows),
       maplist(portray_clause, Rows).
    [1, _, _, _, _, 6, _, 8, _].
    [5, _, 8, 7, 2, 1, 4, _, 6].
    [_, 6, _, 3, 8, _, 2, _, 1].
    [8, 4, _, _, _, 3, _, _, 5].
    [_, _, 5, _, 6, _, 8, _, _].
    [6, _, _, 8, _, _, _, 4, 2].
    [3, _, 6, _, 4, 8, _, 2, _].
    [4, _, 7, 6, 3, 2, 1, _, 8].
    [_, 8, _, 5, _, _, _, _, 4].

However, it is exactly as you say: Even assigning a single variable a concrete value automatically enforces the solution by constraint propagation alone:

    ?- knuth(a, Rows),
       sudoku(Rows),
       Rows = [[_,Var|_]|_],
       indomain(Var),
       maplist(portray_clause, Rows).
    [1, 2, 3, 4, 5, 6, 7, 8, 9].
    [5, 9, 8, 7, 2, 1, 4, 3, 6].
    [7, 6, 4, 3, 8, 9, 2, 5, 1].
    [8, 4, 2, 1, 9, 3, 6, 7, 5].
    [9, 7, 5, 2, 6, 4, 8, 1, 3].
    [6, 3, 1, 8, 7, 5, 9, 4, 2].
    [3, 1, 6, 9, 4, 8, 5, 2, 7].
    [4, 5, 7, 6, 3, 2, 1, 9, 8].
    [2, 8, 9, 5, 1, 7, 3, 6, 4].

Note though the general point: A sufficiently strong constraint solver could have deduced the unique solution even without trying any concrete value, exclusively by reasoning about the posted constraints with sufficient sophistication! This concrete solver can't, due to the particular trade-off between efficiency and pruning strength that was chosen by the implementor, and so search must settle the remaining part.

One of the other puzzles is:

    knuth(d, [[1,_,3,_,5,6,_,8,9],
              [6,8,_,3,_,9,1,_,5],
              [_,9,5,1,8,_,6,3,_],
              [3,_,8,9,6,_,_,5,1],
              [_,1,9,5,_,8,3,6,_],
              [5,6,_,_,3,1,9,_,8],
              [_,5,6,_,9,3,8,1,_],
              [8,_,1,6,_,5,_,9,3],
              [9,3,_,8,1,_,5,_,6]]).

In this case, the solution is not unique. We can use the constraint solver to count the number of admissible solutions, again using search:

    ?- knuth(d, Rows),
       sudoku(Rows),
       findall(., maplist(labeling([ff]), Rows), Ls),
       length(Ls, L).

Yielding: L = 12.

This indeed shows that search is necessary in general also when applying constraint programming. Still, no such search is applied in the posted article. In the example contained in the article, the constraints alone suffice to determine the unique solution. I leave it as an exercise for the reader to determine whether this is the case for all 4x4 Sudoku puzzles.

[taeric]

Thanks for posting. Wasn't sure if folks were interested, but I've found Knuth's fun with Sudoku to be a lot of fun.

I'm curious on how you claim a strong enough solver could have solved this without a "guess."

Also, any thoughts on how treating them as constraint propagation compares to casting it as an exact cover problem?

[zmonx]

Regarding the strength of different solvers: The solution I posted is just one out of many possible constraint-based formulations of Sudoku, using one particular domain and one particular solver implementation. In this concrete case, I have used constraint logic programming over integers, also known as CLP(FD), which is available in many Prolog systems. This is one of the most important and most prominent applications of constraint logic programming and even of logic programming in general.

As an alternative, we can just as well model Sudoku puzzles as combinatorial tasks over Boolean variables, and hence use CLP(B), constraint logic programming over Booleans.

For example:

    sudoku(Rows) :-
            length(Rows, 9), maplist(same_length(Rows), Rows),
            maplist(row_booleans, Rows, BRows),
            maplist(booleans_distinct, BRows),
            transpose(BRows, BColumns),
            maplist(booleans_distinct, BColumns),
            BRows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
            blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is).

    blocks([], [], []).
    blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
            booleans_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
            blocks(Ns1, Ns2, Ns3).

    booleans_distinct(Bs) :-
            transpose(Bs, Ts),
            maplist(card1, Ts).

    card1(Bs) :- sat(card([1],Bs)).

    row_booleans(Row, Bs) :-
            same_length(Row, Bs),
            maplist(cell_boolean, Row, Bs).

    cell_boolean(Num, Bs) :-
            length(Bs, 9),
            sat(card([1],Bs)),
            element(Num, Bs, 1).

In this formulation, I use 9 Boolean variables to represent which of the 9 possible integers is assigned to a particular cell.

Let us apply this formulation to puzzle (b) that is shown in the solution of this exercise:

    knuth(b, [[1,_,3,_,5,6,_,8,9],
              [5,9,7,3,8,_,6,1,_],
              [6,8,_,1,_,9,3,_,5],
              [9,5,6,_,3,1,8,_,7],
              [_,3,1,5,_,8,9,6,_],
              [2,_,8,9,6,_,1,5,3],
              [8,_,9,6,_,5,_,3,1],
              [_,6,5,_,1,3,2,9,8],
              [3,1,_,8,9,_,5,_,6]]).

Here is the result:

    ?- knuth(b, Rows),
       sudoku(Rows),
       maplist(portray_clause, Rows).
    [1, 2, 3, 4, 5, 6, 7, 8, 9].
    [5, 9, 7, 3, 8, 2, 6, 1, 4].
    [6, 8, 4, 1, 7, 9, 3, 2, 5].
    [9, 5, 6, 2, 3, 1, 8, 4, 7].
    [7, 3, 1, 5, 4, 8, 9, 6, 2].
    [2, 4, 8, 9, 6, 7, 1, 5, 3].
    [8, 7, 9, 6, 2, 5, 4, 3, 1].
    [4, 6, 5, 7, 1, 3, 2, 9, 8].
    [3, 1, 2, 8, 9, 4, 5, 7, 6].

For comparison, here is the result of the CLP(FD)-based formulation that I posted earlier:

    ?- knuth(b, Rows),
       sudoku(Rows),
       maplist(portray_clause, Rows).
    [1, _, 3, _, 5, 6, _, 8, 9].
    [5, 9, 7, 3, 8, _, 6, 1, _].
    [6, 8, _, 1, _, 9, 3, _, 5].
    [9, 5, 6, _, 3, 1, 8, _, 7].
    [_, 3, 1, 5, _, 8, 9, 6, _].
    [2, _, 8, 9, 6, _, 1, 5, 3].
    [8, _, 9, 6, _, 5, _, 3, 1].
    [_, 6, 5, _, 1, 3, 2, 9, 8].
    [3, 1, _, 8, 9, _, 5, _, 6].

This shows that CLP(B), in contrast to CLP(FD), has determined the unique solution without any search. This is an example of a solver that propagates as strongly as possible, and hence achieves global consistency even across different constraints.

It also works for puzzle (a):

    ?- knuth(a, Rows),
       sudoku(Rows),
       maplist(portray_clause, Rows).
    [1, 2, 3, 4, 5, 6, 7, 8, 9].
    [5, 9, 8, 7, 2, 1, 4, 3, 6].
    [7, 6, 4, 3, 8, 9, 2, 5, 1].
    [8, 4, 2, 1, 9, 3, 6, 7, 5].
    [9, 7, 5, 2, 6, 4, 8, 1, 3].
    [6, 3, 1, 8, 7, 5, 9, 4, 2].
    [3, 1, 6, 9, 4, 8, 5, 2, 7].
    [4, 5, 7, 6, 3, 2, 1, 9, 8].
    [2, 8, 9, 5, 1, 7, 3, 6, 4].

At this point, you may wonder: Why have I started with (b) instead of (a)? The reason is easy to explain: For puzzle (a), the strong propagation of the CLP(B)-based formulation took so long that it only completed now, after I have finished typing this, a few minutes after I had posted the query, whereas it only took a few seconds for example (b).

Both examples have taken considerably longer to solve with CLP(B) instead of CLP(FD). That's not to say that one approach is better than the other in general or even in that particular case - instead, it is more an observation about the solver implementations and the chosen trade-offs between propagation strength and efficiency in both solvers.

CLP(B) achieves this strong consistency by internally considering, in a sense, the totality of all possible assignments, and this may require exponential space and hence also time. But for many important practical cases, the representation used by CLP(B) is very efficient, and indeed allows us to solve tough problems efficiently. Note that still, no search is involved here: Even the internal propagation of CLP(B) proceeds completely deterministically, and at no point in the computation do we have to guess anything.

It must also be said that the CLP(FD)-based formulation, in addition to being faster (despite the necessary search), is also shorter and arguably more natural than the Boolean variant. Casting this as an exact cover or hitting set task can definitely be done, either with CLP(B) or CLP(FD) constraints (since Booleans can also be considered as a special case of integers). However, it takes us even further away from the quite direct and readable "natural" CLP(FD) formulation. For cover problems in general, I recommend you obtain a CLP(B) solver that internally uses Zero Suppressed Binary Decision Diagrams (ZDDs). They let you efficiently represent cases where many of the variables (such as row selection indicators) are zero, which is typical for covering tasks.