I had UVM trainings(thanks to my company ADI), I finally got into some OOPS, which I was wanting to learn right since my first year of College but because it was not really required then, I didn't take much effort to learn it by self(though I did purchase C++ by Kanetkar during my PS at Ceeri but anyways)
One main concept which I was taught was in OOPS (for UVM) our aim is to add extra functionality to the code without affecting the already working code.
As always, browsing through my PC, I came accross, my old Sudoku solver C code.(It is quite amateur written during my first year Btech and that too while the Compre was going on, so it just did basic stuff and solved mediocre level sudokus).
I decided to analyse my code and see where all could have I improved upon to make my code more readable, oraganised and algo-wise additional improvements if possible.
The function implementation could have had external and put into another file.-- This would have made left only the crux of the code, making it more readable.
Post this, additional pseudo random brute-force algortihm can be applied to reach to an answer.Would have to be a recurrsive approach where you take a cell which has two possibilities, proceed along and if the sodoku gets solved no issues .Otherwise,retract back and take the other possibility and proceed.
One main concept which I was taught was in OOPS (for UVM) our aim is to add extra functionality to the code without affecting the already working code.
As always, browsing through my PC, I came accross, my old Sudoku solver C code.(It is quite amateur written during my first year Btech and that too while the Compre was going on, so it just did basic stuff and solved mediocre level sudokus).
I decided to analyse my code and see where all could have I improved upon to make my code more readable, oraganised and algo-wise additional improvements if possible.
The function implementation could have had external and put into another file.-- This would have made left only the crux of the code, making it more readable.
- The array should have been a user defined data type
- Each element could have had been a struct(in case of C again this was taught in second year), which has a field data and and possible values[9] array.This would have made code even more readable and shorter(I expect).Or otherwise,it could have had been defined as a 3-D array.
- Entering sudoko values from terminal element by element is painful, as a wrong element entered would spoil play and I will have to restart the program and start all over again.Using fscanf which I learnt in the second year would have been much better.
- A update function could be defined.Rather after finding a valid candidate , the Update being automatically called would be more intuitive.
- Algorithm termination is heuristic which I didn't like at all, waiting for 1000 loop cycles, though is practical but not a clean way to terminate.
- Algorithm for display routine is good but could be abstracted in to a function.
Post this, additional pseudo random brute-force algortihm can be applied to reach to an answer.Would have to be a recurrsive approach where you take a cell which has two possibilities, proceed along and if the sodoku gets solved no issues .Otherwise,retract back and take the other possibility and proceed.
If a conflict is reached while proceeding with the assumption, it implies our choice is wrong and it is definitely the other candidate.
It might be possible that either ways too we may have no conflicts reached and we again get stalled at some point.
In which case , we select another random candidate where we got stuck and proceed along.The chances to getting a conflict here are high and reaching the solution too (inner feeling as we would have very few non filled spots) .I feel that more than two level of guesswork may not be required(can only check this if I can solve escargot sudoku with this).
But even then the method of random selection is not true/correct. A human solver would not proceed this way I guess.There would be other logical steps which help eliminating step wise and proceeding along.But since I don't know them and I want to learn how to do permutation and combination, I am planning to go this way.
Lets see if I get time to cleanup this stuff today.
The link to my old code is here : Sudoko
It might be possible that either ways too we may have no conflicts reached and we again get stalled at some point.
In which case , we select another random candidate where we got stuck and proceed along.The chances to getting a conflict here are high and reaching the solution too (inner feeling as we would have very few non filled spots) .I feel that more than two level of guesswork may not be required(can only check this if I can solve escargot sudoku with this).
But even then the method of random selection is not true/correct. A human solver would not proceed this way I guess.There would be other logical steps which help eliminating step wise and proceeding along.But since I don't know them and I want to learn how to do permutation and combination, I am planning to go this way.
Lets see if I get time to cleanup this stuff today.
The link to my old code is here : Sudoko