4 ms·
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
by taeric 10y 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 10y agoI 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 10y agoWhat algorithm for ILP do you use? I think most (all?) solvers use a variation of branch-and-bound.
- Pamar 10y agoI 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 10y agoI'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
- taeric 10y agoTo 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.
- taeric 10y agoWhile 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 10y agoIt 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 https://en.wikipedia.org/wiki/Linear_programming or to provide a link to a nice MOOC: https://www.edx.org/course/optimization-methods-business-analytics-mitx-15-053x 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 10y agoWhile 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 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/e7.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&context=etd http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&...
- zmonx 10y agoTo 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.
- sfrank 10y agoNo, 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 10y agoThis 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.