I'm really bored because of quarantine. I've gotten so bored that I started playing sudoku. After getting better at the beginner puzzles, I started trying the harder ones. Eventually, I found one that I couldn't finish. After two days unable to find a solution to it, I thought about how I could program an answer to the general case.
*Sometimes a puzzle has multiple solutions. This will find the
easiest one
Most people use the backtracking (recursive) method when making a
sudoku solving program (this one did). But there's also
other ways to solve it.
There's basically two
functions that make up this program: the validation function and
the recursion. The validation function just checks to see if a
number makes sense in a specific cell on the puzzle. The recursion
is where the magic happens. It loops through the possible numbers in
each cell and finds the number that works. Compared to regular brute
force search, backtracking uses a depth-first search. This
drastically increases performance.
If you wanna read more about
recursion check this
out.
If you're like me you're probably wondering "what would be the
hardest puzzle to solve". Well, Arto Inkala answers that
question in this
really cool article. If you feed it into the solver above I
it'll take a while to solve though...
If you're also bored
and want something to do, check out these puzzles
online. That is, until you get stuck on one and program a solver 🤧