4 ms·

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 requi

by 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
  - taeric 9y ago
    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.
taeric 9y ago
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 9y ago
  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 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 9y ago
    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 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&...

by 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
- taeric 9y ago
  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.

taeric 9y ago

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 9y ago
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 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 9y ago
  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 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&...