[taeric]

I think you are just using a different definition of brute force than the post is using. It doesn't try all permutations of the digits, but it does do a search over the tree to find the solutions.

Now, to your point, this is really the only way you can solve sudoku. There is an odd belief that you can make an algorithm that "never guesses." And folks think that that would be the definition of a non-brute force algorithm. In reality, you either have a solver that is ready to backtrack, or you have one that can't solve all puzzles.

[Pamar]

I am not sure about your backtracking point. Sudoku can be solved by Integer Programming (i.e. a special subset of Linear Programming) and this does not require any kind of backtracking.

[taeric]

While I wouldn't be shocked to know that I'm wrong on requiring backtracking, I am not sure how the integer programming claim refutes it. In particular, those look to still be "search" solvers and almost certainly have to perform some "guess" in making the search.

Do you happen to have a recommended link on how this can be accomplished? First few results in searching just show farming this out to a specialized function in matlab. :)

[Pamar]

It is a bit difficult to explain Linear Programming in a forum post (so I will have to default to Wikipedia: https://en.wikipedia.org/wiki/Linear_programming or to provide a link to a nice MOOC: https://www.edx.org/course/optimization-methods-business-ana...).

There is absolutely no "guessing" involved, though: you describe your sudoku problem as a series of linear equations (which represent the edges of your search space) and then the algorithm travels from one vertex to the next until it finds the solution. There is no backtracking at all.

[Pyxl101]

While this may be true for linear programming, is it true for integer linear programming or binary integer programming, which one would presumably use to model Soduku? The Wikipedia article you posted claims that integer programming problems are NP-hard.

> If all of the unknown variables are required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) NP-hard. 0-1 integer programming or binary integer programming (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version was one of Karp's 21 NP-complete problems.

Here is an article on the topic of "Binary and Mixed Integer Programming" which explains part of the Balas Additive Algorithm (infeasibility pruning, I believe) in terms of backtracking:

> At this point, both of the nodes just created are not eligible for further expansion, so we back up the tree, looking for a level at which one of the nodes is unexplored.

http://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf

Another paper describes a method by Glover characterized as "A backtracking procedure for implicit enumeration".

> A particularization of the procedure based on Balas' algorithm. In S2 we presented and justified a flexible and economical back-tracking procedure for finding an optimal feasible solution of (P) by implicit enumeration.

See Figure 1 on page 182 (or page 6 in the PDF):

http://www.anderson.ucla.edu/faculty/art.geoffrion/home/docs...

This branch of mathematics is not my forte however, so if I've misunderstood then I'd appreciate clarification. It seems like the algorithm is not backtracking in the sense of generating possible solutions and checking them, but is backtracking in the sense of fathoming which next cheapest (partial) solution might be feasible, and abandoning it if proven to be definitely infeasible, in favor of examining the (then) next cheapest potential solution.

Finally, see the following paper that compares and contrasts Constraint Programming with Integer Programming, and characterizes both of them as instances of Tree Search:

http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&...

[Pamar]

Extremely Coarse Approximation Alert

Try to imagine this: by manipulating an n-dimensional matrix in a certain way, you get, at each step, a result which is guaranteed to be part of your solution space. You also have a way to find out, at each step, if you have found the optimal solution (in terms of your objective function) or if no solution exists.

So the process goes like this: Put your constraints in the matrix.

  Loop -
    Manipulate Matrix
    Is this the optimal Solution?
      Yes - return solution
    Is the solution space empty/concave/unbound?
      Yes - return error
  End.

No backtracking in the sense of "try this... hmm... no, try this other".

I have used LP professionally in the past, and recently participated in the MOOC I linked above (as a refresher) but I might surely be missing something (the theory I studied at UNI too many years ago - now I just use it as a tool) or overgeneralizing too much. If anyone can provide corrections these will be welcomed.

[Pyxl101]

Could you clarify which algorithm you're referring to? Or name an example algorithm that works in the way you describe? What I find in academic literature seems to characterize Integer Programming as a search problem. See the following article that compares Constraint Programming with Integer Programming:

http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&...

> Since tree search is a basic solution technique employed in both constraint and integer programming, we begin with a generic overview of tree search as a technique for finding feasible solutions to mathematical models.

> Every tree search algorithm is defined by four elements: a node- processing procedure, pruning rules, branching rules, and search strategy. The processing step is applied at every node of the search tree beginning with the root node, and usually involves some attempt to further reduce the feasible set associated with the node by applying logical rules. [...]

> One particularly well-developed solution technique, called branch and bound, was introduced by Land and Doig. Branch and bound is frequently used to find solutions to integer programming problems; it is a tree search procedure in which a bound on the optimal value to each subproblem is obtained by solving a relaxation. In this thesis we assume the use of a linear programming relaxation in the branch and bound tree.

> The last piece of a branch and bound algorithm is a search strategy specifying the order in which to explore nodes of the tree. Depth-first search can be used to save memory in a branch and bound tree, since we must only remember the difference in solution between two successive nodes of the search tree.

Chapter nine of Applied Mathematical Programming from MIT classifies integer program solvers into three major groups:

http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf

> Whereas the simplex method is effective for solving linear programs, there is no single technique for solving integer programs. Instead, a number of procedures have been developed, and the performance of any particular technique appears to be highly problem-dependent. Methods to date can be classified broadly as following one of three approaches:

> i) enumeration techniques, including the branch-and-bound procedure;

> ii) cutting-plane techniques; and

> iii) group-theoretic techniques. [...]

> Branch-and-bound is essentially a strategy of ‘‘divide and conquer.’’ The idea is to partition the feasible region into more manageable subdivisions and then, if required, to further partition the subdivisions. In general, there are a number of ways to divide the feasible region, and as a consequence there are a number of branch-and-bound algorithms.

> An integer linear program is a linear program further constrained by the integrality restrictions. Thus, in a maximization problem, the value of the objective function, at the linear-program optimum, will always be an upper bound on the optimal integer-programming objective. In addition, any integer feasible point is always a lower bound on the optimal linear-program objective value. The idea of branch-and-bound is to utilize these observations to systematically subdivide the linear programming feasible region and make assessments of the integer-programming problem based upon these subdivisions.

The book describes the "cutting-plane" approach, which does seem to work more like how you're describing (a series of transformations), but also says:

> In practice, the branch-and-bound procedures almost always outperform the cutting-plane algorithm. Nevertheless, the algorithm has been important to the evolution of integer programming. Historically, it was the first algorithm developed for integer programming that could be proved to converge in a finite number of steps. In addition, even though the algorithm generally is considered to be very inefficient, it has provided insights into integer programming that have led to other, more efficient, algorithms.

[adrianN]

What algorithm for ILP do you use? I think most (all?) solvers use a variation of branch-and-bound.

[Pamar]

I am answering here (hoping that it will be read by others too).

First of all: thanks everyone for forcing me to go back and re-visit some stuff about LP/IP - I think I was wrong - some sort of search tree/branch and bound is not just a speedup trick - it looks like it is the only way to actually get a correct solution for IP problems.

So let me amend my two previous statements:

  Linear Programming does not require any search tree or backtracking is CORRECT.
  Linear Programming can solve Sudoku is *WRONG* - for Sudoku you need Integer Programming, and that requires an approach that involves search trees/backtracking.

Sorry for the confusion, and thanks again for making me recheck my assumptions.

[zodiac]

I'm pretty sure cutting-plane methods for IP don't strictly require "tree search" (of course, they still require super-polynomial time to solve IP problems)

https://en.wikipedia.org/wiki/Cutting-plane_method

[taeric]

To your original point, they do not consider these "backtracking" in the standard sense. So, I'd actually agree to your original point and that I was wrong.

I should also have stressed harder that I agreed with your definition of brute force. I was just offering an explanation for where I think the post went awry.

[sfrank]

No, a domain-consistent all-different propagator such as the one desccribed in [1] is sufficient to determine a valuation domain for a Sudoku puzzle without any search.

Of course that does not hold in general, but in the special case of Sudokus and problem modelling by a domain-consistent all-different propagator, no search is required for a solution.

[1] A filtering algorithm for constraints of difference in CSPs, J-C. Régin, 1994

[taeric]

This thread exploded after I went to sleep. Apologies for the silence and again a huge thanks to everyone else in the thread.

It is possible to craft a sudoku that has a unique solution without having any forced moves at the beginning. Turns out most are not actually hard, but it is doable. When I get back near my book at home, I an post an example, if folks are interested.

[zmonx]

To see what I mean, please consider the Prolog program for solving Sudoku puzzles that is shown in this article, and try the following query:

    | ?- sudoku(X, Y).

This is called the most general query, since all arguments are fresh variables. Declaratively, we are asking Prolog: "Are there any solutions whatsoever?" In this case, the system answers with:

    X = [_#3(1..4),_#24(1..4),...etc.]
    Y = [_#3(1..4),_#24(1..4),...etc.]

This shows that the Prolog program did not perform any search at all: No concrete value is instantiated, and the system does not ask for alternatives. That's right! No search whatsoever, and no backtracking at all, is performed in this program. No matter which definition of brute force search you are applying, this definitely does not fall into "search" at all!

In the article, a more concrete query is also shown, as well as its solution. This solution is found via constraint propagation alone. This means that the system has deduced the unique solution purely by reasoning about the available constraints, which it does automatically every time a constraint is posted. This is one example of an algorithm that does not guess.

This also shows that even supposing you cannot make an algorithm that "never guesses", you can definitely make an algorithm that has to do much less guessing than searching over the whole tree. In Prolog, such algorithms are implemented and encapsulated in powerful combinatorial constraints like all_distinct/1, which are available in many Prolog systems and which you can use in your applications. Internally, the associated constraint propagators prune the search tree by applying various algorithms for you behind the scene. The ability to use such constraints and their strong pruning are major attractions of using Prolog for combinatorial tasks.

You are right that there may be cases where such propagation, albeit quite strong, may not suffice to fully solve a concrete combinatorial task. For this reason, you have to apply a concrete enumeration of remaining variables. In Constraint Logic Programming over Integers, this search is called labeling and provided by predicates like fd_labeling/2 or similar, depending on your Prolog system. The article does not use them though, and even if it did, the search could be guided by various heuristics by simply supplying a few options, which together with the pruning applied by constraints distinguish such a search from more uninformed search strategies.

Note also that the posted solution is quite hard to generalize elegantly. A shorter and equivalent Prolog program that describes 4x4 Sudoku puzzles is:

    sudoku(Rows) :-
            Rows = [Row1,Row2,Row3,Row4],
            maplist(same_length(Rows), Rows),
            blocks(Row1, Row2), blocks(Row3, Row4),
            append(Rows, Vs),
            fd_domain(Vs, 1, 4),
            maplist(fd_all_different, Rows),
            transpose(Rows, Cols),
            maplist(fd_all_different, Cols).

    blocks([], []).
    blocks([A1,A2|As], [B1,B2|Bs]) :-
            fd_all_different([A1,A2,B1,B2]),
            blocks(As, Bs).

This assumes the availability of append/2 and transpose/2, which are likely already provided by your Prolog system, and easy to implement if they aren't.

[taeric]

You can actually make a sudoku problem where, by the rules of the game, all open pieces have at least 2 possible values while still having a unique solution. So, to that end, I am unaware of how you could make a solver that doesn't have to guess. (As noted in a sibling post, I wouldn't be shocked to find I was wrong, but I would be interested in the details.)

So, I'm ultimately wary of the claims here. The system has to be doing a search. It may be crafted in such a way that it just walks straight to the solution for some specifications, but that is as much from luck of easy constraints as it is the algorithm.

[zmonx]

When you say "all open pieces have at least 2 possible values", how can the solution be unique? Surely for each piece, some values are not admissible, otherwise this would be a contradiction. Sufficiently strong pruning could have eliminated them, either by search or by more reasoning.

[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?

[Pyxl101]

Consider the Eight Queens problem. There are multiple valid solutions to the problem on a given chessboard. They are symmetric solutions, yet distinct. Any algorithm that finds a single solution and not all of them must be prioritizing arbitrarily among solutions, i.e., searching or fathoming them in some particular order.

> This solution is found via constraint propagation alone. This means that the system has deduced the unique solution purely by reasoning about the available constraints, which it does automatically every time a constraint is posted. This is one example of an algorithm that does not guess.

Have you considered how that constraint propagation algorithm works? What specific algorithm are you referring to? Constraint Programming is an alternative formulation of the same problem that Integer Linear Programming tackles, and the latter is known to be NP-hard.

https://en.wikipedia.org/wiki/Linear_programming#Integer_unk...

Constraint Programming and Integer Programming are both characterized as examples of Tree Search:

http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&...

> Since tree search is a basic solution technique employed in both constraint and integer programming, we begin with a generic overview oftree search as a technique for finding feasible solutions to mathematical models. [...]

> Every tree search algorithm is defined by four elements: a node- processing procedure, pruning rules, branching rules, and search strategy. The processing step is applied at every node of the search tree beginning with the root node, and usually involves some attempt to further reduce the feasible set associated with the node by applying logical rules.

> Overall a tree search algorithm works as follows. A list of nodes that are candidates to be processed is maintained throughout the algorithm. This list initially contains only the root node. At each step in the algorithm, a node is chosen and processed. If the processing results in pruning of the node by one of the pruning rules, then the node is discarded. Otherwise, the node is further divided, resulting in two or more children, which are then added to the list of candidates. This procedure is iterated until no nodes remain on the candidate list.

> [...] the constraint program is made up of two pieces: the constraints that comprise the formulation and a search strategy for solving the problem (emphasis mine). This is in contrast to a mathematical program, which describes a model but does not specify how to solve it.

> Traditionally, a constraint programming formulation consists only of a list of decision variables, domains, a set of constraints to be satisfied, and a search procedure (emphasis mine). This traditional definition refers to a constraint satisfaction problem (CSP), since a solution is any assignment of values to variables such that all constraints are satisfied.

Can you clarify which algorithm you're referring to, and how it manages to solve the problem without employing Tree Search?

[zmonx]

One of the most important and characteristic aspects of constraint programming is alluded to in the following part of your quote (emphasis mine):

"involves some attempt to further reduce the feasible set associated with the node by applying logical rules"

These propagation rules are among the major attractions of CP, and distinguish the paradigm from uninformed search strategies that have to consider much larger portions of the search space in general. I think a description of CP should put at least equal emphasis on this pruning mechanism as on the actual search itself, because sufficiently strong propagation may render the search completely unnecessary. In fact, this is exactly what happens in the Sudoku example of the article!

In a sibling thread, sfrank has cited a very important reference as an example of such a propagation algorithm, which serves to illustrate this idea and is also widely used in practice in CP systems and their applications:

A filtering algorithm for constraints of difference in CSPs, J-C. Régin, 1994

To see this algorithm in action, consider the following example: Take three variables X, Y and Z, all of them integers that are either 0 or 1, with the additional constraint that they must be pairwise distinct. In Prolog with CLP, and said algorithm available under the name all_distinct/1, we can state this task as follows:

    ?- X in 0..1, Y in 0..1, Z in 0..1,
       all_distinct([X,Y,Z]).

In response to this query, the system says:

    false.

This means the system has deduced that there are no solutions. Note that this result is obtained without applying any search! For comparison, suppose we naively post pairwise disequalities instead:

    ?- X in 0..1, Y in 0..1, Z in 0..1,
       X #\= Y, Y #\= Z, X #\= Z.

In response, the system now answers:

    X in 0..1,
    X#\=Z,
    X#\=Y,
    Z in 0..1,
    Y#\=Z,
    Y in 0..1.

This means that there could potentially be solutions. The system does not know whether there are any, so it shows us remaining constraints that must hold for any solution. Now, an additional search makes clear that there are none:

    ?- X in 0..1, Y in 0..1, Z in 0..1,
       X #\= Y, Y #\= Z, X #\= Z,
       label([X,Y,Z]).

Here, I have simply added the goal label/1, which is the explicit enumeration and thus the search I have mentioned in an earlier post. In response, we now again of course get:

    false.

As another example of propagation, please consider:

    ?- X in 0..1, Y in 0..1, Z in 0..2,
       all_distinct([X,Y,Z]).
    Z = 2,
    X in 0..1,
    all_distinct([X, Y, 2]),
    Y in 0..1.

Here, the system has deduced that Z is necessarily 2, again without any search. For the other variables, both values are still admissible, and to obtain concrete solutions, we must again label them explicitly. However, we do know that there is a solution in this case, due to the strength of all_distinct/1, which internally uses a complex reasoning about the value graph of the CSP that is somewhat anticlimactically encapsulated in such a superficially trivial predicate, but propagates much more strongly than simply stating pairwise disequalities would.

This shows that you can arrive at a solution (or prove the lack of a solution) either via a search or by using a sufficiently strong propagation mechanism. Doing more of one requires less work of the other. Please note that, as I said before, you indeed need an explicit search in general, because the propagation algorithms alone are, while often quite effective, not effective enough in general to guarantee consistency when different constraints interact, even if they guarantee domain consistency individually. This is a practical trade-off between propagation strength and efficiency of the available constraints. You also need search to enumerate all solutions, if there are more than one. However, note that propagators are also triggered during the search, and so unifying even a single remaining variable with a concrete integer may again lead to a situation where no additional search is necessary. Thus, the initial size of the search space is not a satisfactory measure for the eventual complexity of the search, because it does not account for the additional propagation that is applied during the search itself.

Even in the case of Sudoku, and even if you use the most powerful individual all_distinct/1 constraints, you need to search, in general, to truly generate the unique solution explicitly. But the Prolog code shown in the article doesn't (hence, it will lead to floundering constraints in general), and the concrete puzzle shown in the article is, coincidentally or not, correctly solved just by such propagation algorithms, without any search. This situation is also not particularly rare: In many cases of practical importance, constraint propagation alone already tightens remaining domains so significantly that no or only very little additional search is necessary.

Thus, everything you said is true: Yes, you need search in general, also when using CP, to obtain concrete solutions. However, to repeat, it is quite different from what one would call "brute force" search because the sophisticated and often very effective propagation algorithms prune the search space, often substantially, and can moreover help to guide the search with various heuristics. In practice, you typically buy a Prolog system just to benefit from these propagation algorithms! Various notions of consistency exist, and you can find more such algorithms in the literature references that are for example included in SICStus Prolog and other Prolog systems with constraints.

Second, note that the description you quote does not even cover the particular case that arises in the article and also many other cases in practice: That is, there are no nodes at all, because everything is already settled by constraint propagation before any search even starts, making the whole solution explicitly available without search.

The Eight Queens problem you cite is quite different from Sudoku, because it may have multiple solutions. For this reason, as you correctly observe, search is needed to generate the different solutions in such cases. But this does not invalidate the Sudoku example, where we know that exactly one solution exists, and sufficiently strong pruning could always determine it, whether by internal propagation or other algorithms that simply eliminate all values that do not participate in the unique solution of the puzzle. Nor does it show that the cost for the search outweights that of constraint propagation in either case.

For these reasons, I recommend to put at least equal focus on constraint propagation as on the search when discussing CP.