After more hours than I'm proud of, I was able to create a sudoku solver that works rather well. Beside the obvious eliminations to possible solutions to just one box (veritcal, horizontal and quadrant eliminations) I tried to add some more logical solutions. When I solve Sudoku puzzles (easy ones anyways) I use a method of checking for which number each box can be. In words, if I get a puzzle like the following:
I would start with the number 2. You can see that the first row has a 2 in it, and the second row has a 2 in it. This implies that there needs to be a 2 in the third row as well, which HAS to be found in the top right quadrant of numbers. In this top right 3x3 quadrant, there are only two spaces that can be that 2 and one of them has a 2 in its column already. That means that only one box in this top right quadrant can be a 2, and I fill it in. Apparently, after some googling, I found out this is called hidden singles. Upon adding this selection method and re-iterating (as well as adding a solution counter), I was able to solve 40 of the 50 problems.
At this point I conceded the logical method and began implementing a bruting method. I just looked for the first empty box that had between 2 and 4 possible numbers, chose the first "guess" and selected that as an answer. If a contradiction was found, the guess was broken and the next "guess" for that same box was taken. I let the guess run through each box until a solution was found and the loop would break.
Unfortunately, this now works for 49/50 of the problems. In fact, it is problem 49 that my code fails to solve. After some frustration, I solved it by hand and submitted my solution which was correct. Maybe I'll return to this one later.
No comments:
Post a Comment