Hi felas ,
This post is the discription of my way of solving a sudoku (in code). Both Utsav and I were eager to code the solver for sudoku and so we both have have our own version of Sudoku Solver.
Since both of these codes were base on backtracking ,they are similar in there basic approach but differ in implementation . My code is in python using a DDA (or Double Dimensional list as they are called in python) of strings as the Sudoku board.
The input of the incomplete sudoku is accepted in the form of a sequence of 81 numbers where the numbers in the sequence are the 81 cell values for the 9x9 sudoku . The value zero corresponds to an incomplete cell where as any other value(a single integer from 1-9) is considered as the value for that cell.
Ex: seq = '003000000400080036008000100040060073000900000000002005004070062600000000700600500'
the sudoku board is first initialized to a value of '123456789' in each cell. A value in a cell shows the possible values that the particular cell can take . Thus before accepting the question the sudoku board looks somewhat like the image below.
After initialization the Sudoku board is sent to the update function which updates the row,column and block according to each new element updated in a co-ordinate. After updation the Sudoku board looks like the image below.
Finally the backtacking function is called to solve the sudoku.
the solved piece looks somewhat like this.
My code consist of 6 important functions including the 'main' .Here they are with the discription of what they do:
1) _init(): This function initializes the board with the unsolved sudoku.
2) _update(): This function rules out the possibility of occurrence of a number in other cells.
3) _backtrack(): As the name suggest this function finds a solution to the initialized sudoku by finding assuming values for each cell with different possible values and then updating the sudoku board using the _update() function.
4) _complete() : The backtrack function makes use of this function to find the state of sudoku ( Sudoku states are i) right and complete , ii) incomplete.
5) _out_file(): This is a dummy function used only to write the output to a file.
6) _main(): Finally this is the main function from where the code begins. It calls the init() function to initialize the Sudoku board and then the backtrack function to find the solution.
Detailed explanation of the working and code of these function are discussed in part - 2.
This post is the discription of my way of solving a sudoku (in code). Both Utsav and I were eager to code the solver for sudoku and so we both have have our own version of Sudoku Solver.
Since both of these codes were base on backtracking ,they are similar in there basic approach but differ in implementation . My code is in python using a DDA (or Double Dimensional list as they are called in python) of strings as the Sudoku board.
The input of the incomplete sudoku is accepted in the form of a sequence of 81 numbers where the numbers in the sequence are the 81 cell values for the 9x9 sudoku . The value zero corresponds to an incomplete cell where as any other value(a single integer from 1-9) is considered as the value for that cell.
Ex: seq = '003000000400080036008000100040060073000900000000002005004070062600000000700600500'
the sudoku board is first initialized to a value of '123456789' in each cell. A value in a cell shows the possible values that the particular cell can take . Thus before accepting the question the sudoku board looks somewhat like the image below.
After initialization the Sudoku board is sent to the update function which updates the row,column and block according to each new element updated in a co-ordinate. After updation the Sudoku board looks like the image below.
Finally the backtacking function is called to solve the sudoku.
the solved piece looks somewhat like this.
My code consist of 6 important functions including the 'main' .Here they are with the discription of what they do:
1) _init(): This function initializes the board with the unsolved sudoku.
2) _update(): This function rules out the possibility of occurrence of a number in other cells.
3) _backtrack(): As the name suggest this function finds a solution to the initialized sudoku by finding assuming values for each cell with different possible values and then updating the sudoku board using the _update() function.
4) _complete() : The backtrack function makes use of this function to find the state of sudoku ( Sudoku states are i) right and complete , ii) incomplete.
5) _out_file(): This is a dummy function used only to write the output to a file.
6) _main(): Finally this is the main function from where the code begins. It calls the init() function to initialize the Sudoku board and then the backtrack function to find the solution.
Detailed explanation of the working and code of these function are discussed in part - 2.
No comments:
Post a Comment