[Pamar]

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]

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

[taeric]

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.