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.
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)
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.
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:
Sorry for the confusion, and thanks again for making me recheck my assumptions.