3 ms·
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 o
by ant6n 10y ago
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 10y ago> 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 10y agoI 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.