Hi friends,
This post as promised is a detailed explanation of the working and code of the functions explained in previous post (Part 1).
So here it goes:
The first function was __init(): which initialized the sudoku from the sequence
(like seq='003000000400080036008000100040060073000900000000002005004070062600000000700600500
')
to the sudoku board and called the update function every time it made an update to a cell value.
Given below is the code of __init() function :
The two for loops of 'i' and 'j' are used to scan the sequence in a way such that it is easier for the program to apply a value to the 9x9 board . The formula 9*(i)+j comes handy in mapping the values from 'seq' to the board . The 'if' statement checks whether a cell value is available (non-zero) or not . If it is non-zero the integer value of that cell is stored in variable 'val' and update function is called .After updating it re-updates the position (i,j) in the grid 'a' with value 'val' as a double check.
Next function is the __update() function . This function takes the grid ,updating value, and the two co-ordinate for the position of the updation as its parameters.Before updating the position with the value it does 3 jobs.
i) It deletes any occurrence of that value 'val' in that particular col.
ii) It deletes any occurrence of that value 'val' in that particular row.
iii) it deletes any occurrence of that value 'val' in that particular block.
Given below is the code of __update() function :
The two line under the first if does job i), the two line under the next if does job ii) and the m,n, block does job iii).
After this it updates the gird position (i,j) with 'val' and return the grid.
The following functions is the implementation of the main idea that solves the sudoku.
Given below is the code of __Backtrack() function :
The backtrack function calls the complete function to know whether the sudoku is complete or not.
If it is complete it return '1' .
If the sudoku is not complete then the function searches for the smallest non-one length value of a cell.
The long line below the first else does this .
If this length is found out to be zero then it means that the sudoku is in a state where that particular cell can't have any value. Hence it return 0 as this sudoku is faulty and will not yield the correct solution.
If the smallest non-one length value of the board is not zero then it means that this particular cell is going to have one of these value. The function hence copies all these possible values in temp , and for each value in 'temp' it makes a copy of the original grid with the position (m,n) having value temp replaced with a single number value from temp.Next line makes an update in the position with this value and update the whole board according to this change by calling __update() function and the assigns the value in temp to position (m,n) as a double check.
the grid having been changed is sent back for backtracking and if the result is true the program copies the output to an output file using the out_file() function and makes an exit.
The 4th function __complete() could have also been written in the __backtrack() function but I separated it to make the backtrack function look simple.
The code for complete simply iterates over the whole grid ,it is provided with, and return 0 if there is a non-one length value in the grid and 1 otherwise.
Code of _complete() function is provided below :
Next function __out_file() is a dummy function that copies the state of the grid it is provided with to a file.
One may code this function according to his/her will.
Code for My _out_file() function is provided below :
List in this list is the 'main()' function . It first creates the grid a 9x9 string DDA and calls the _init() function to initialize the grid and then the __backtrack() function which would solve the sudoku and print the output in a separate file.
Code for the main() function is given below :
Apart from these six function i also used a self define deepcopy() function for making the copies of the grid in backtrack function.
Code for my deepcopy function is given below :
This post as promised is a detailed explanation of the working and code of the functions explained in previous post (Part 1).
So here it goes:
The first function was __init(): which initialized the sudoku from the sequence
(like seq='003000000400080036008000100040060073000900000000002005004070062600000000700600500
')
to the sudoku board and called the update function every time it made an update to a cell value.
Given below is the code of __init() function :
The two for loops of 'i' and 'j' are used to scan the sequence in a way such that it is easier for the program to apply a value to the 9x9 board . The formula 9*(i)+j comes handy in mapping the values from 'seq' to the board . The 'if' statement checks whether a cell value is available (non-zero) or not . If it is non-zero the integer value of that cell is stored in variable 'val' and update function is called .After updating it re-updates the position (i,j) in the grid 'a' with value 'val' as a double check.
Next function is the __update() function . This function takes the grid ,updating value, and the two co-ordinate for the position of the updation as its parameters.Before updating the position with the value it does 3 jobs.
i) It deletes any occurrence of that value 'val' in that particular col.
ii) It deletes any occurrence of that value 'val' in that particular row.
iii) it deletes any occurrence of that value 'val' in that particular block.
Given below is the code of __update() function :
The two line under the first if does job i), the two line under the next if does job ii) and the m,n, block does job iii).
After this it updates the gird position (i,j) with 'val' and return the grid.
The following functions is the implementation of the main idea that solves the sudoku.
Given below is the code of __Backtrack() function :
The backtrack function calls the complete function to know whether the sudoku is complete or not.
If it is complete it return '1' .
If the sudoku is not complete then the function searches for the smallest non-one length value of a cell.
The long line below the first else does this .
If this length is found out to be zero then it means that the sudoku is in a state where that particular cell can't have any value. Hence it return 0 as this sudoku is faulty and will not yield the correct solution.
If the smallest non-one length value of the board is not zero then it means that this particular cell is going to have one of these value. The function hence copies all these possible values in temp , and for each value in 'temp' it makes a copy of the original grid with the position (m,n) having value temp replaced with a single number value from temp.Next line makes an update in the position with this value and update the whole board according to this change by calling __update() function and the assigns the value in temp to position (m,n) as a double check.
the grid having been changed is sent back for backtracking and if the result is true the program copies the output to an output file using the out_file() function and makes an exit.
The 4th function __complete() could have also been written in the __backtrack() function but I separated it to make the backtrack function look simple.
The code for complete simply iterates over the whole grid ,it is provided with, and return 0 if there is a non-one length value in the grid and 1 otherwise.
Code of _complete() function is provided below :
Next function __out_file() is a dummy function that copies the state of the grid it is provided with to a file.
One may code this function according to his/her will.
Code for My _out_file() function is provided below :
List in this list is the 'main()' function . It first creates the grid a 9x9 string DDA and calls the _init() function to initialize the grid and then the __backtrack() function which would solve the sudoku and print the output in a separate file.
Code for the main() function is given below :
Apart from these six function i also used a self define deepcopy() function for making the copies of the grid in backtrack function.
Code for my deepcopy function is given below :
No comments:
Post a Comment