News for hackers. Stuff that matters.
Re:Solving Every Sudoku Puzzle (2006) by skizm on Wednesday September 04, 2019 @04:10PM (#20880925)
The key insight when writing a sudoku solver is that it is just depth first search. Once someone told me that it just sort of clicked. Just guess each possible number at each open square and if you ever get to an un-solvable state, just undo the last change you made and try the next one. I was extremely satisfied with myself after writing my first really clean solver with backtracking.

I'm sure there are other, more efficient, ways to write sudoku solvers, but the simplicity and clarity the DFS solver offers is pretty cool IMO.

Re:Solving Every Sudoku Puzzle (2006) by 53x15 on Wednesday September 04, 2019 @05:00PM (#20881360)
It can be done with just depth first search, but if you want it to be fast you can go pretty far down the rabbit hole. The details of your representation, your heuristics, and the kinds of constraint propagation you support all matter a lot.

Here's a long walk through these issues in developing a fast solver: https://t-dillon.github.io/tdoku

Re:Solving Every Sudoku Puzzle (2006) by jkaptur on Wednesday September 04, 2019 @04:41PM (#20881202)
I don't think there are, actually. Some algorithms might run faster in practice, but, since the game is NP-complete, brute force is pretty much as good as it gets for exact solutions.
Re:Solving Every Sudoku Puzzle (2006) by war1025 on Wednesday September 04, 2019 @11:26PM (#20883617)
The constraint propagation bit is the main key. It still ends up being a DFS, but at most steps along the way, finding one number leads causally to several other spaces being found.

In most easy / medium puzzles, there are actually no points where you need to guess (i.e. recurse down the tree).

In many hard puzzles, there are only one of two guesses, which is where you would recurse down the decision tree.

Things get a bit more intense once you move into the puzzles specifically designed to be a pain in the neck for programs, but often those inputs aren't actually valid Sudoku puzzles.

Re:Solving Every Sudoku Puzzle (2006) by antod on Wednesday September 04, 2019 @08:40PM (#20882836)
I've only ever written one solver in Python about 10yrs ago. But it wasn't a search and never made guesses, it was an enumeration of all the analog elimination methods I'd ever figured out when solving them on paper.

It was fast, but there were a few difficult puzzles it couldn't solve - obviously there were some real world techniques/alogrithms I hadn't managed to figure out.

Re:Solving Every Sudoku Puzzle (2006) by zwkrt on Wednesday September 04, 2019 @10:43PM (#20883428)
There are sudoku puzzles which have a unique solution but which also force a “guess” in the solving process, so your approach doesn’t work in the general case.
Re:Solving Every Sudoku Puzzle (2006) by zwkrt on Thursday September 05, 2019 @03:48PM (#20890098)