Now that my program can solve simple puzzles, I need to make it solve more difficult ones. I'm going to do this by implementing a search function that will go through all the cells that don't have a definite value yet, and try assigning each of the possible values to that cell and see what sticks. This sounds like it would be incredibly inefficient but its actually not if I use the assign/eliminate methods from before.
So, if all the given values have been assigned to the worksheet and the puzzle still isn't solved, it executes a search. The search algorithm took me a long time to get my head round, again because I struggled to understand the Python examples, but now that it's written it's actually pretty simple. Well actually I don't think it's simple, just short. Who would have thought 20 lines of code would give me such a headache!
It starts by getting the key of an unsolved cell. This could be any cell but it's more efficient if it uses the one with the fewest possible values since then there's a better chance of getting it right. I added a method to Puzzle (my extended dictionary class that I use to store the values) that would return the key of the cell with the lowest number of possibilities. If a few have the same number it just returns the first one it finds. Once the search function has its key, it runs another function which, for each possible value, creates a clone of the worksheet and tries assigning that value to it to see if it works. If it doesn't find any conflicts, it returns that clone of the worksheet. It then passes that clone into the search function (Whee! More recursion!) and does it all again. The clone it passed in has had one of its cells solved so the getUnsolvedCell method will bring back a different answer from the first time. The function keeps drilling down until the getUnsolvedCell method brings back nothing, which means there are no unsolved cells left. At this point the most up to date clone of the original worksheet bubbles all the way back up the stack as the completed solution.
Since this method involves operating on clones of the worksheet I had to go back and alter the assignNumber and eliminateNumber methods so that they take in a worksheet to operate on as a parameter and pass it back out as a return value once they're finished with it. For the first part of the solver (before it starts searching) they just receive a reference to the global worksheet variable.
I must have spent hours trying to figure out exactly how to write this search algorithm. The recursion was just tying my brain in knots. Eventually I just wrote something and ran it with the intention of using the error message to try and understand exactly what it was doing. To my absolute astonishment it solved the puzzle without any problems. I was totally not expecting that and still didn't really have a firm grasp on what exactly was happening in the depths of the recursion. Now that I've written down an explanation of what the algorithm does on here though, I have a much better understanding of how it works. I guess this is one of the reasons people keep blogs about their programming projects.
Now that I've got a program that can, in theory, solve any sudoku puzzle, I need to put it through its paces. This means more unit tests! I downloaded a list of 50 easy sudoku puzzles and 95 hard ones from the internet and wrote a test that would read them all in and try to solve them. The easy and hard puzzles were in different files and formatted in completely different ways so I needed to write a test for each of them. I've written a the test for the easy one which reads in the file, parses all the puzzles into separate strings, and feeds each one to the solver. Sadly things did not go well. It crashed on puzzle number 5 with a null reference exception that was occurring about 4 recursions deep in the search method. I found that there was a point when the clone being passed into the assignAllValues method was null. Why it was null, I had no idea. I couldn't understand why this would work for the previous 4 puzzles and not this one. I followed it through the debugger and found that, at one point, one cell had "45" as its list of possible values when one of its peers had already been assigned the value 4 as its starting value. This is totally confusing me because this situation should be impossible. The assignNumber and eliminateNumber methods should eliminate a value from all the peers of a cell once that value has been assigned to it. I put in another breakpoint and followed it through again. Luckily the cells that were conflicting were A6 and A8 so i didn't have to wait long for the situation to arise. I followed the debugger as it assigned 4 to A8, as given by the original puzzle, and watched as it eliminated 4 from the possible values of A6. All is in order. I let it run a few more loops and saw that everything was still fine. The possible values for A6 still didn't contain 4. I then stepped out of the initial assigning phase and let it run until it was ready to start the search algorithm. I checked on the worksheet again and found that 4 was back in the possible values list! I also noticed that A8 didn't have a definite value anymore! What the hell is going on here? I watched this thing assign those values! Where did they go? My gut feeling is that something has gone wrong with one of the clones (as so often happens when creating an army of clones). I haven't tried running the puzzle in question through the solver without it being part of my big 50 puzzle unit test yet either so it could even be a problem with the test rather than the solution. This is going to be the first thing I try tomorrow. Hopefully it's something simple and I just can't see it because it's so late at night.
So, if all the given values have been assigned to the worksheet and the puzzle still isn't solved, it executes a search. The search algorithm took me a long time to get my head round, again because I struggled to understand the Python examples, but now that it's written it's actually pretty simple. Well actually I don't think it's simple, just short. Who would have thought 20 lines of code would give me such a headache!
It starts by getting the key of an unsolved cell. This could be any cell but it's more efficient if it uses the one with the fewest possible values since then there's a better chance of getting it right. I added a method to Puzzle (my extended dictionary class that I use to store the values) that would return the key of the cell with the lowest number of possibilities. If a few have the same number it just returns the first one it finds. Once the search function has its key, it runs another function which, for each possible value, creates a clone of the worksheet and tries assigning that value to it to see if it works. If it doesn't find any conflicts, it returns that clone of the worksheet. It then passes that clone into the search function (Whee! More recursion!) and does it all again. The clone it passed in has had one of its cells solved so the getUnsolvedCell method will bring back a different answer from the first time. The function keeps drilling down until the getUnsolvedCell method brings back nothing, which means there are no unsolved cells left. At this point the most up to date clone of the original worksheet bubbles all the way back up the stack as the completed solution.
Since this method involves operating on clones of the worksheet I had to go back and alter the assignNumber and eliminateNumber methods so that they take in a worksheet to operate on as a parameter and pass it back out as a return value once they're finished with it. For the first part of the solver (before it starts searching) they just receive a reference to the global worksheet variable.
I must have spent hours trying to figure out exactly how to write this search algorithm. The recursion was just tying my brain in knots. Eventually I just wrote something and ran it with the intention of using the error message to try and understand exactly what it was doing. To my absolute astonishment it solved the puzzle without any problems. I was totally not expecting that and still didn't really have a firm grasp on what exactly was happening in the depths of the recursion. Now that I've written down an explanation of what the algorithm does on here though, I have a much better understanding of how it works. I guess this is one of the reasons people keep blogs about their programming projects.
Now that I've got a program that can, in theory, solve any sudoku puzzle, I need to put it through its paces. This means more unit tests! I downloaded a list of 50 easy sudoku puzzles and 95 hard ones from the internet and wrote a test that would read them all in and try to solve them. The easy and hard puzzles were in different files and formatted in completely different ways so I needed to write a test for each of them. I've written a the test for the easy one which reads in the file, parses all the puzzles into separate strings, and feeds each one to the solver. Sadly things did not go well. It crashed on puzzle number 5 with a null reference exception that was occurring about 4 recursions deep in the search method. I found that there was a point when the clone being passed into the assignAllValues method was null. Why it was null, I had no idea. I couldn't understand why this would work for the previous 4 puzzles and not this one. I followed it through the debugger and found that, at one point, one cell had "45" as its list of possible values when one of its peers had already been assigned the value 4 as its starting value. This is totally confusing me because this situation should be impossible. The assignNumber and eliminateNumber methods should eliminate a value from all the peers of a cell once that value has been assigned to it. I put in another breakpoint and followed it through again. Luckily the cells that were conflicting were A6 and A8 so i didn't have to wait long for the situation to arise. I followed the debugger as it assigned 4 to A8, as given by the original puzzle, and watched as it eliminated 4 from the possible values of A6. All is in order. I let it run a few more loops and saw that everything was still fine. The possible values for A6 still didn't contain 4. I then stepped out of the initial assigning phase and let it run until it was ready to start the search algorithm. I checked on the worksheet again and found that 4 was back in the possible values list! I also noticed that A8 didn't have a definite value anymore! What the hell is going on here? I watched this thing assign those values! Where did they go? My gut feeling is that something has gone wrong with one of the clones (as so often happens when creating an army of clones). I haven't tried running the puzzle in question through the solver without it being part of my big 50 puzzle unit test yet either so it could even be a problem with the test rather than the solution. This is going to be the first thing I try tomorrow. Hopefully it's something simple and I just can't see it because it's so late at night.
RSS Feed
