It works! It solves puzzles! Victory! Well not quite yet but it's a big step in the right direction.
The article I mentioned in my previous post said that there are 2 rules for solving a sudoku puzzle.
The article I mentioned in my previous post said that there are 2 rules for solving a sudoku puzzle.
1. If a cell has only one possible value, then eliminate that value from the cell's peers.
2. If a unit has only one possible place for a value, then put that value there.
2. If a unit has only one possible place for a value, then put that value there.
So, as an example of rule 1, if we know that cell A3 contains a 7, we can eliminate 7 from the possible values of A3's peers (A1, A2, B3, etc). We may find that after eliminating 7 from all those peers that one of them has only one value left so we can then remove that value from all it's peers. We can keep recursing through the puzzle until all the cells have only one possible value in which case the puzzle is solved!
My parser for reading in JSON puzzles stored blank cells as "0" rather than lists of potential values so I needed to change this before I could go any further. Easy enough. After working on the algorithm for a little while though I realised you really need to have the entire puzzle made of blank squares and then assign the certain values afterwards, checking for potential eliminations as you go. I therefore changed my parser back to the way it used to be and added another Puzzle object called worksheet which was filled entirely with blank values (or complete lists of potential values if I'm being precise). Worksheet would be the puzzle I actually change and would be the one that gets exported as the solution.
I then tried to implement the first rule which I found quite a challenge. The example I was following along with was in Python (which I have negligible experience in) and the author really loved his single character variable names. This meant I kept running into phrases like "d2=[s for s in u if d in v[s]]" which made me go "Whaaa?". I wrote out the example on paper in ActionScript style pseudocode to try and get a better understanding of exactly what it was doing and this helped a bit. The end result is 2 methods called "assignNumber" and "eliminateNumber".
The program iterates through the puzzle and, for every cell that isn't blank, calls the assignNumber method and passes it the key of the cell and the value to assign it. The assignNumber method then iterates through all the potential values for that cell (excluding the one looking to be assigned) and attempts to eliminate them one by one by passing them to the eliminateNumber method.
The eliminateNumber method removes the number to be eliminated from the worksheet cell. If this leave only 1 value in that cell then it know for sure that this value is correct for that cell and it will call the eliminateNumber method on all of that cell's peers. A lot of recursion happens here.
When I fed a simple puzzle into the program it keeled over with a stack overflow. This confused me since it was obviously caused by too much recursion and this whole theory was based on recursion. I stepped through the whole thing with a debugger to try and see where it was getting stuck and I eventually found that it was due to me not updating the worksheet as I went. The python example did all its operations during the elimination method on the worksheet directly. This made me nervous since there were several places the method could bail out if it found something problematic (like finding there was no place on the grid to put a certain number). I didn't want it to remove any numbers from the worksheet before it was sure that was the right thing to do so I had it copy the potential values for a cell into a seperate array, do all its operations on that, then copy them back into the worksheet once it was done. This turned out to be a mistake since it caused this endless loop of recursion. Basically what happened was it would assign the value 5 to cell A1 and would therefore iterate through all the peers of A1 and eliminate 5 from their potential values. While doing this it would discover that after eliminating 5 from the potential values of A3, that it only had the value 2 left. It would then recurse into all the peers of A3 to eliminate 2 from all of their potential values. One of the peers of A3 is A1 which only had 2 and 5 as potential values (5 was still there since I hadn't operated directly on the worksheet and instead operated on a copy). Once 2 was eliminated 5 was the only value left so it recursed into A1's peers again to go and eliminate 5 from all of them meaning it found A3 again and discovered it only had 2 left so it recursed into all of its peers again and so on until it caused a stack overflow. Changing the eliminateNumber method so that it operated directly on the worksheet fixed this problem and, in hindsight, my worry about it removing a value it shouldn't was a silly one. The method will only bail out if there is a fundamental problem with the puzzle that would render it unsolvable, in which case the whole thing would be stopping anyway so who cares?
Once that was fixed I fed in the simple puzzle again and BING! Solved! Awesome!
But wait... I forgot to implement rule number 2! If my algorithm can solve sudoku puzzles with just one of the rules implemented, what's the point in implementing the second? I wondered if it would maybe solve puzzles more efficiently by using 2 rules rather than just one so I went ahead an implemented the second rule.
This involved looping through each unit that the cell in being assigned to was a part of, and then for each cell in that unit, seeing if the potential values for that cell contained the number being eliminated. If it did, then that cell was added to an array of potential places to put that value. If, after checking every cell in the unit, there was only 1 element in the potential places array, then the program knows that the number being eliminated belongs in that cell and will assign it there with all the eliminations and whatnot that that involves.
I wasn't sure exactly how to check if adding the second rule made the program any more efficient. I added a counter to count how many times the eliminate method was being called since that was the only method I thought might get fewer calls if the algorithm was more efficient (the other methods were on fixed loops so wouldn't change). This didn't prove anything however since it actually called the eliminate method more times with 2 rules active than just the first one. I still don't know what advantage the second rule is giving me but I decided to just play it safe and leave it in there. I'm sure it wouldn't be a rule if it wasn't required.
So far, my program can only solve deterministic puzzles (puzzles with only one solution). If I feed it an non-deterministic puzzle then it will leave a lot of cells with multiple possible values still in them. To make it solve more complex puzzles I need to have it use a form of search once it has exhausted the assign/eliminate method. This will be what I try to tackle tomorrow.
My parser for reading in JSON puzzles stored blank cells as "0" rather than lists of potential values so I needed to change this before I could go any further. Easy enough. After working on the algorithm for a little while though I realised you really need to have the entire puzzle made of blank squares and then assign the certain values afterwards, checking for potential eliminations as you go. I therefore changed my parser back to the way it used to be and added another Puzzle object called worksheet which was filled entirely with blank values (or complete lists of potential values if I'm being precise). Worksheet would be the puzzle I actually change and would be the one that gets exported as the solution.
I then tried to implement the first rule which I found quite a challenge. The example I was following along with was in Python (which I have negligible experience in) and the author really loved his single character variable names. This meant I kept running into phrases like "d2=[s for s in u if d in v[s]]" which made me go "Whaaa?". I wrote out the example on paper in ActionScript style pseudocode to try and get a better understanding of exactly what it was doing and this helped a bit. The end result is 2 methods called "assignNumber" and "eliminateNumber".
The program iterates through the puzzle and, for every cell that isn't blank, calls the assignNumber method and passes it the key of the cell and the value to assign it. The assignNumber method then iterates through all the potential values for that cell (excluding the one looking to be assigned) and attempts to eliminate them one by one by passing them to the eliminateNumber method.
The eliminateNumber method removes the number to be eliminated from the worksheet cell. If this leave only 1 value in that cell then it know for sure that this value is correct for that cell and it will call the eliminateNumber method on all of that cell's peers. A lot of recursion happens here.
When I fed a simple puzzle into the program it keeled over with a stack overflow. This confused me since it was obviously caused by too much recursion and this whole theory was based on recursion. I stepped through the whole thing with a debugger to try and see where it was getting stuck and I eventually found that it was due to me not updating the worksheet as I went. The python example did all its operations during the elimination method on the worksheet directly. This made me nervous since there were several places the method could bail out if it found something problematic (like finding there was no place on the grid to put a certain number). I didn't want it to remove any numbers from the worksheet before it was sure that was the right thing to do so I had it copy the potential values for a cell into a seperate array, do all its operations on that, then copy them back into the worksheet once it was done. This turned out to be a mistake since it caused this endless loop of recursion. Basically what happened was it would assign the value 5 to cell A1 and would therefore iterate through all the peers of A1 and eliminate 5 from their potential values. While doing this it would discover that after eliminating 5 from the potential values of A3, that it only had the value 2 left. It would then recurse into all the peers of A3 to eliminate 2 from all of their potential values. One of the peers of A3 is A1 which only had 2 and 5 as potential values (5 was still there since I hadn't operated directly on the worksheet and instead operated on a copy). Once 2 was eliminated 5 was the only value left so it recursed into A1's peers again to go and eliminate 5 from all of them meaning it found A3 again and discovered it only had 2 left so it recursed into all of its peers again and so on until it caused a stack overflow. Changing the eliminateNumber method so that it operated directly on the worksheet fixed this problem and, in hindsight, my worry about it removing a value it shouldn't was a silly one. The method will only bail out if there is a fundamental problem with the puzzle that would render it unsolvable, in which case the whole thing would be stopping anyway so who cares?
Once that was fixed I fed in the simple puzzle again and BING! Solved! Awesome!
But wait... I forgot to implement rule number 2! If my algorithm can solve sudoku puzzles with just one of the rules implemented, what's the point in implementing the second? I wondered if it would maybe solve puzzles more efficiently by using 2 rules rather than just one so I went ahead an implemented the second rule.
This involved looping through each unit that the cell in being assigned to was a part of, and then for each cell in that unit, seeing if the potential values for that cell contained the number being eliminated. If it did, then that cell was added to an array of potential places to put that value. If, after checking every cell in the unit, there was only 1 element in the potential places array, then the program knows that the number being eliminated belongs in that cell and will assign it there with all the eliminations and whatnot that that involves.
I wasn't sure exactly how to check if adding the second rule made the program any more efficient. I added a counter to count how many times the eliminate method was being called since that was the only method I thought might get fewer calls if the algorithm was more efficient (the other methods were on fixed loops so wouldn't change). This didn't prove anything however since it actually called the eliminate method more times with 2 rules active than just the first one. I still don't know what advantage the second rule is giving me but I decided to just play it safe and leave it in there. I'm sure it wouldn't be a rule if it wasn't required.
So far, my program can only solve deterministic puzzles (puzzles with only one solution). If I feed it an non-deterministic puzzle then it will leave a lot of cells with multiple possible values still in them. To make it solve more complex puzzles I need to have it use a form of search once it has exhausted the assign/eliminate method. This will be what I try to tackle tomorrow.
RSS Feed
