undefined | Better HN

0 pointsSideburnsOfDoom1y ago0 comments

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"

0 comments

3 comments · 1 top-level

irchans1y ago· 2 in thread

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".)

yetihehe1y ago

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.

SideburnsOfDoomOP1y ago

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.

j / k navigate · click thread line to collapse