[ant6n]

I wrote a sudoku solver in my first year of college using some heuristsics and some sort of branch-and-cut algorithm, in java. It used bit masks to keep track of the state and possiblities, I was pretty proud, spent like weeks on that.

Recently I re-implemented in Pulp in an afternoon using ILP.

It's similarly fast, both can solve similar sets of problems. But the ILP solution was so much easier and shorter.

[wolfgke]

> I wrote a sudoku solver in my first year of college using some heuristsics and some sort of branch-and-cut algorithm, in java.

What class of cutting planes did you use in your B&C algorithm (full disclure: I do my PhD on cutting planes, thus I'm interested)?

[ant6n]

I mean branch-and-bound - i.e. just reject when solution becomes infeasible and back-track. No cutting planes in first year college. ;)

I think the heuristics may have been based on selecting cells that had the least possible solutions, in order to quickly 'zoom in' on the areas where you can quickly prune infeasible solutions.