Select the previous cell according to the backtracking history.If there are no more cells to backtrack to - stop here because there.Blank out the current cell and enter the below loop. If none of the above is true, then it is time to backtrack.If there is at least one remaining choice for the current cell and there are no blank cells or all blank cells have been iterated, assign the remaining choice and continue to the next main iteration.If that cell has at least on possible digit, assign it and continue to the next main iteration. If there are blank cells choose the next cell.If the grid is valid stop here and return the solution. If there are no blank cells validate the grid.If all blank cells have been iterated and the last blank cell iterated doesn't have any remaining digits to be tried - stop here because there is no solution.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.
#Solving sudoku algorithm c uiuc 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.
0 kommentar(er)
