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. :)
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.
> 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&...
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.
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.