Sudoku is a logical number placement puzzle. You have a 9x9 field and you need to fill each cell with numbers from 1 to 9 following the rules:
Link to Wikipedia: https://en.wikipedia.org/wiki/Sudoku
Here is a live coding session that shows how it can be done.
Duration: 3:50 (coding - 3:12)
Disclaimer: never use this code in production. It was created for fun.
Let's break down the solution and comment on some complex or interesting things. For this mini-project I decided to play around with Golang. Refer to installation guide.
This time it will be a console application that does not require any additional modules to be installed.
0:44 - starting to code application skeleton. It will contain only main function for now.
0:48 - defining an initial position for the puzzle. For this purpose we are using two dimensional array. Carefully copy the content from Wikipedia's image to the code. Remember that sudoku is 9 by 9 puzzle, therefore our array is also 9 by 9. For convenience let's consider 0 as empty cell (the one that should be filled by the solver).
1:15 - trying to output the game field. For this purpose we need fmt package that comes with Golang. draw function outpus the current position from field array to console row by row. Also first line of main function outputs initial position.
1:35 - starting to build solve function. Here we'll use an approach called "recursive backtracking". The idea is that we start with top-left corner and try to progress through the field and try to put every possible number in empty cells. If at some point of time we detect that no number can be put into the cell this would mean that we made a wrong decision somewhere before and we need to backtrack and try different options.
For example in the original scenario we see that 3-rd cell in top row can contain 1, 2 or 4 (this can be deduced from the current position). This means that our algorithm should try to put 1 first and proceed to next cell and try from there.
Our function is called solve and it accepts 2 parameters - x and y - these are position where our solver got to so far. It will start with (0, 0) position - top left corner.
Another important observation - if the solver came to a cell that is already filled in (i.e. it does not contain 0) this means that we can skip this cell and go to the next one.
Right now our solve function is incomplete - it lacks the logics how to proceed to the next step.
2:01 - now we need to implement a function that checks if certain number can be put to position at (x, y) coordinates. According to Sudoku rules there are 3 constraints:
2:15 - check for vertical (column) uniqueness is rather trivial. Just go though all rows and see if value in x-th column is same as desired number. Interestingly - here y parameter of the function is not used and it can be safely removed.
2:29 - check for horizontal (row) uniqueness is pretty much the same as previous step.
2:44 - check for the square is a bit more complex. Here we first of all need to understand to which 3 by 3 square our (x, y) coordinates belong to. Remember that top-left corner is (0, 0). To solve this problem we can use integer division by 3. For example if our (x, y) coordinates are (4, 2) that means that we are in middle top 3 by 3 square that starts at coordinates ((4 / 3) * 3, (2 / 3) * 3) = (3, 0).
Once we know which smaller square we are in what we need to do is just iterete through it. It is a 3 by 3 area and also here we need to check if there is already a number that we want to put.
3:05 - next function is simple by tricky. Remember that we decided to go column by column, row by row starting from top-left corner. That means that next position can be calculated based on the following logics:
(x, y) will be just (x + 1, y)(x, y) will be (0, y + 1)X coordinate just take it modulo 9. And if new value of X is 0 this means that we should go to the next row - therefore increasing Y value.
solve function.
next function returns a pair of integers (new X and Y coordinates) and we can use call of next function directly to pass arguments to recursive solve function call.
3:24 - last part of the solution - determine when we have found a solution. The most simple way is to check for Y coordinate. It it is 9 that means that all previous rows from 0 to 8 (9 in total) were already successfully processed and we have some partial solution before. This means that for every cell before we were able to find a solution.
Therefore at this point of time the whole field is filled with numbers according to the game rule - this is our solution.
3:28 - inside the main function let's output the solution if it is found. Note that not all Soduku puzzles have a solution. It might be intentional or by mistake. Anyway we handle both scenarios.
3:39 - running the application to see that it works and outputs the correct solution. Normally it should not take more than couple of seconds to find the solution. You can play around with initial position and see how inital densitity (how many numbers are put into the field initially) affects run time.
As you see the solution is not very complex. It does not require any deep knowledge of Golang or algorithms.
Such approach of recursive backtracking can be used to solve many similar combinatorical puzzles.
Sources: https://github.com/5minute/sudoku_solver
See live results:https://play.golang.org/p/mfegc9_ZaMw