Another breakable toy, my variation of Sudoku solver. I’ve created it without previously googling the topic , and I was quite surprised when latter I realized that most solutions out there use just dumb trial and error. I was also glad that I can re-invent backtracking algorithm ;)
Ok. let’s start, from having a Sudoku that we want to solve:
After a little consideration I decided to solve it by elimination of possible values. Let’s consider first block (by block I mean inner 3x3 cells squares), possible values for empty cells:
We can see that value 1 can be only in A1 cell so fill it in. Check remaining cells and no single value in a row or column. So we evaluate next block:
Now value 1 and 6 are only possible in cells B5 and B4 so we fill them in. Check remaining cells after reduction - no single possible values - we go to the next block.
We cycle through all blocks until all cells are filled in (will happen only for very simple Sudoku) or number of empty cells is not changed after a cycle. In the second case, we filled what we could using simple elimination and it’s time for more advanced solving techniques or guessing. This time I choose guessing, maybe later I’ll implement something more original. So we take first empty cell pick its first possible value fill it in and use recursion and backtrack algorithm to check if we can complete the puzzle. If not go back pick next possible value and try again.