Comment by SideburnsOfDoom
3 days ago
I have only once written a Suduoku solver. It brute-forced the whole problem space in a second or 2.
This works because it's very easy to prune invalid branches according to the rules of the game.
It just tried putting "1" in the top-left most empty square and checking if the configuration is valid. If not, try "2". recurse until you find a branch that completes.
Is this the smart way? IDK, but I was quite pleased with it. I found it more elegant than e.g. "find some square with only one possible solution"
I also wrote a brute force, kinda dumb, depth-first Suduoku solver. I think it took me a few hours in C or C++. At every node in the search tree, I just checked to make sure no constraints were violated. If I remember correctly, it would run in less than 30 seconds and it would always find a solution if a solution existed. (It might have been a lot less than 30 seconds. I only remember thinking, "That was quick".)
I wrote a sudoku solver, that will create 9x9 array of arrays filled with numbers 1-9 for "blank" fields and only the number in defined field. Then for each square with only one number, I removed the number in that square from all arrays in row, column and subsquare. That typically left me with a solved array, but will contain all possible results for "guessing" fields. It was written in php (the thing I leaned at the time) and ran too fast for me to bother measuring, less than a second. Since I've "solved all sudokus" they stopped being fun.
Yep, pretty much the same approach and experience, only mine was in c# as I was learning the language then. "brute force" by definition will find a solution, if it exists.