8 ms·

I have two comments about the Prolog code: First, the article claims: "the sudoku solver above does a brute force search", but that is specifically not the cas

by zmonx 9y ago

I have two comments about the Prolog code: First, the article claims: "the sudoku solver above does a brute force search", but that is specifically not the case. In fact, quite the opposite holds: The Prolog Sudoku formulation shown in the article uses a powerful technique known as Constraint Logic Programming over Finite Domains, which automatically performs pruning before and also during the search for solutions. This effectively eliminates large portions of the search space in practice, and degenerates to brute force only in those cases where almost nothing can be deduced from initial constraints. In the particular case of Sudoku, the pruning is especially effective and can in many cases eliminate the search entirely, since the initial constraints (hints) basically determine the whole solution. Second, yes, it is easy to write an O(n!) search algorithm in Prolog. However, it is almost as easy to implement much more efficient search algorithms in Prolog. For example, here is Quicksort in Prolog: quicksort([]) --> []. quicksort([L|Ls]) --> { partition(Ls, L, Smalls, Bigs) }, quicksort(Smalls), [L], quicksort(Bigs). Note how natural the declarative description of "first the smaller elements, then the pivot element, then the bigger elements" is in Prolog. This only requires a suitable implementation of partition/4, which is very easy to implement in at most 7 lines of Prolog code.

chubot 9y ago
Eh, I'm pretty sure that suffers from the problem noted here: https://news.ycombinator.com/item?id=13375108 https://news.ycombinator.com/item?id=13375108 See the "genuine sieve of eratosthenes" paper, and also: http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html http://augustss.blogspot.com/2007/08/quicksort-in-haskell-qu...
- zmonx 9y ago
  I do not dispute your point. However, the main issue is that the worst case complexity of this Prolog quicksort, whether in place or not, is already only polynomial, in contrast to the O(n!) permutation sort given in the article, and only about equally hard to implement. In Prolog, an arguably more natural sorting method is merge sort, and it can (also) be implemented with asymptotically optimal efficiency in Prolog as follows: mergesort(Ls0, Ls) :- length(Ls0, L), zcompare(C, L, 1), halving(C, L, Ls0, Ls). halving(<, _, Ls, Ls). halving(=, _, Ls, Ls). halving(>, L, Ls0, Ls) :- Half #= L // 2, length(Lefts0, Half), append(Lefts0, Rights0, Ls0), mergesort(Lefts0, Lefts), mergesort(Rights0, Rights), merge(Lefts, Rights, Ls). merge/3 is a built-in in several Prolog systems, and if your system does not provide it, you can easily implement it in less than 10 lines of Prolog code. Both quicksort and merge sort Prolog implementations are (even in their respective worst cases) vastly faster than the sorting algorithm given in the article (in its worst case, and also in its average case), and are at most marginally more complex to implement. For this reason, I think the article could be improved by simply showing one of these algorithms instead. We cannot consider it a drawback of Prolog that computing all permutations takes O(n!) time in this language. It's the same for C, for example. If someone wants faster sorting, we can implement it also in a declarative language! Somewhat strangely, the fact that you can easily write a Prolog program to generate all N! permutations of a list with N elements is more likely to be counted as a disadvantage than as an advantage, in my experience. If people looked at C and Prolog a bit more fairly in such overview documents, they could as well count it as a disadvantage of C that such a program is harder to write in C than in Prolog. Yet, I have never seen a C program implementing permutation sort in such articles, and never seen a comparable argument or suggestion about C as I routinely see it about Prolog. Permutation sort is slow in C! Well, that's a well-known shortcoming of an imperative language such as C.
sriku 9y ago
FD constraint programming is powerful. Mozart/Oz goes one step further by making the search strategies programmable within the language using the idea of computational spaces. I think two of the OP's notes are covered in Mozart/Oz - concurrent programming using data floor variables (roughly equivalent to promises) and logic programming, including finite domain constraints.
- zmonx 9y ago
  I agree, with only one small additional remark: In general, a programmable search strategy sacrifices termination guarantees for more generality. That's a completely defensible approach of course, and not an argument against this path of development! Still, it comes at a price, and researchers working in termination analysis may prefer precisely the tighter reins and more stringent resulting properties we obtain when we eschew programmable strategies in specific parts of the language. For finite domain constraints, such guarantees are a major attraction in the Prolog community: If setting up the constraints terminates, then setting up the constraints plus search also terminates. That's a rather valuable and strong guarantee (since it is the search that can take take infeasibly long more often than setting up the constraints), and it breaks down if the search itself is more generally programmable.
taeric 9y ago
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 9y ago
  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.
  - adrianN 9y ago
    What algorithm for ILP do you use? I think most (all?) solvers use a variation of branch-and-bound.
    - Pamar 9y ago
      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 9y ago
        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 https://en.wikipedia.org/wiki/Cutting-plane_method
tomxor 9y ago
Pruning is an optimisation though, not a computational reduction... the remaining computation is still brute force. While it may be effective with low n, the complexity will still grow in roughly the same way as n increases - for this reason I would still call it brute force. Isn't this why sudoku is still considered NP hard? (unless there has been a recent breakthrough).

by zmonx 9y ago

chubot 9y ago

Eh, I'm pretty sure that suffers from the problem noted here: https://news.ycombinator.com/item?id=13375108 https://news.ycombinator.com/item?id=13375108 See the "genuine sieve of eratosthenes" paper, and also: http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html http://augustss.blogspot.com/2007/08/quicksort-in-haskell-qu...

zmonx 9y ago
I do not dispute your point. However, the main issue is that the worst case complexity of this Prolog quicksort, whether in place or not, is already only polynomial, in contrast to the O(n!) permutation sort given in the article, and only about equally hard to implement. In Prolog, an arguably more natural sorting method is merge sort, and it can (also) be implemented with asymptotically optimal efficiency in Prolog as follows: mergesort(Ls0, Ls) :- length(Ls0, L), zcompare(C, L, 1), halving(C, L, Ls0, Ls). halving(<, _, Ls, Ls). halving(=, _, Ls, Ls). halving(>, L, Ls0, Ls) :- Half #= L // 2, length(Lefts0, Half), append(Lefts0, Rights0, Ls0), mergesort(Lefts0, Lefts), mergesort(Rights0, Rights), merge(Lefts, Rights, Ls). merge/3 is a built-in in several Prolog systems, and if your system does not provide it, you can easily implement it in less than 10 lines of Prolog code. Both quicksort and merge sort Prolog implementations are (even in their respective worst cases) vastly faster than the sorting algorithm given in the article (in its worst case, and also in its average case), and are at most marginally more complex to implement. For this reason, I think the article could be improved by simply showing one of these algorithms instead. We cannot consider it a drawback of Prolog that computing all permutations takes O(n!) time in this language. It's the same for C, for example. If someone wants faster sorting, we can implement it also in a declarative language! Somewhat strangely, the fact that you can easily write a Prolog program to generate all N! permutations of a list with N elements is more likely to be counted as a disadvantage than as an advantage, in my experience. If people looked at C and Prolog a bit more fairly in such overview documents, they could as well count it as a disadvantage of C that such a program is harder to write in C than in Prolog. Yet, I have never seen a C program implementing permutation sort in such articles, and never seen a comparable argument or suggestion about C as I routinely see it about Prolog. Permutation sort is slow in C! Well, that's a well-known shortcoming of an imperative language such as C.

sriku 9y ago

FD constraint programming is powerful. Mozart/Oz goes one step further by making the search strategies programmable within the language using the idea of computational spaces. I think two of the OP's notes are covered in Mozart/Oz - concurrent programming using data floor variables (roughly equivalent to promises) and logic programming, including finite domain constraints.

zmonx 9y ago
I agree, with only one small additional remark: In general, a programmable search strategy sacrifices termination guarantees for more generality. That's a completely defensible approach of course, and not an argument against this path of development! Still, it comes at a price, and researchers working in termination analysis may prefer precisely the tighter reins and more stringent resulting properties we obtain when we eschew programmable strategies in specific parts of the language. For finite domain constraints, such guarantees are a major attraction in the Prolog community: If setting up the constraints terminates, then setting up the constraints plus search also terminates. That's a rather valuable and strong guarantee (since it is the search that can take take infeasibly long more often than setting up the constraints), and it breaks down if the search itself is more generally programmable.

taeric 9y ago

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 9y ago
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.
- adrianN 9y ago
  What algorithm for ILP do you use? I think most (all?) solvers use a variation of branch-and-bound.
  - Pamar 9y ago
    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 9y ago
      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 https://en.wikipedia.org/wiki/Cutting-plane_method

tomxor 9y ago

Pruning is an optimisation though, not a computational reduction... the remaining computation is still brute force. While it may be effective with low n, the complexity will still grow in roughly the same way as n increases - for this reason I would still call it brute force. Isn't this why sudoku is still considered NP hard? (unless there has been a recent breakthrough).