SUDOKU STRATEGY TUTORIAL CODE

For my implementation of the backtracking I have used a while loop because no branching is needed, the algorithm searches in a single-threaded linear fashion. The advantage of the recursion is that it is capable of branching out and generally supports more complex logics and algorithms, but the disadvantage is that it is more difficult to implement and often tricky to debug. Both of them can continue iterating until a solution is found or until a lack of solution is proven. Therefore, you really have two options - to use a while loop or to use recursion. It's important to note that there is no deterministic way to know how many steps or iterations you will need to solve the puzzle. The gist of the algorithm is to start iterating the grid and making decisions what to do - populate a cell, or try another digit for the same cell, or blank out a cell and move back to the previous cell, etc.

SUDOKU STRATEGY TUTORIAL CODE

But here I will focus on the algorithm and code itself. You might also want to check out my answer in this thread about optimizing the algorithm. It is a backtracking algorithm too, but I wanted to share my implementation as well.īacktracking can be fast enough given that it is moving within the constraints and is choosing cells wisely.

But the most interesting and natural of the sudoku solving strategies I came across is this one from here The above one is very basic backtracking algorithm which is explained at many places. SecTopX, secTopY = 3 *(i//3), 3 *(j//3) #floored quotient should be used here. # finding the top left x,y co-ordinates of the section containing the i,j cell RowOk = all( for x in range(9)])ĬolumnOk = all( for x in range(9)]) A cell with value 0 indicates that it is not filled. It takes 9X9 grid partially filled with numbers.

For each legal value, Go recursively and try to solve the grid.It's the bare minimum code which solves the problem. It uses simple backtracking algorithm to solve the puzzle.įor simplicity no input validations or fancy output is done.

Sudoku strategy tutorial