Whenever I want to learn a new programming language, I like to think up a challenge and then I try to make it in that new language. I feel like it is a lot less tedious and I actually accomplish something in the end. A few years ago, I was playing around with PHP and decided to try my hand at solving a Sudoku puzzle, with code. I got caught up with things at work and never got around to doing it. Last week at work, a colleague of mine mentioned that someone had made a Sudoku solver.
My PHP is pretty good now, and I feel like it is a very good language for “fast and dirty” rapid prototyping, so I started this challenge. I built out two small classes and got to building the “board” and passing the numbers in. I started with iterating through the positions, checking for possibilities and if there was only one possible number, inserting it. Throwing in a little recursion it went on and on until it could solve the puzzle. That worked well and in no time, I had a “brain” that I had taught how to solve very basic Sudoku puzzles.
Not being content with average, I tried a more difficult one and sure enough, it failed to solve it. I adapted the code so that it would spit out the possibilities for each of the unknown places. I soon realised that each position needed more “context.” I then added some functions to solve for blocks, rows and columns. If there was a unique possibility in a row, column or block it needed to put that number in there. An hour or two later, this worked like a charm.
Feeling accomplished and ready to go to bed, I Googled “World’s Hardest Sudoku” and was disappointed to find out that my “brain” couldn’t solve this particular puzzle. In fact, it couldn’t event get one correct value. Looking at the possibilities of the empty squares, I realised that it had to have the ability to “guess” answers, continue to solve the puzzle with that assumption, if it failed, it had to go back and try the next guess. This seemed like another good job for recursion and a few lines of code later I had it making educated guesses for squares that had the least number of possibilities. Many iterations later, I had the answer to the “World’s Hardest Sudoku.” And by many iterations, I mean 435 in about 10 seconds. I looked through many more puzzles online and this is the most difficult one I have found so far. If you find anything that takes more iterations, or should be possible but my script can’t solve it, please let me know.
I have no doubt that it would have taken me longer to solve the actual Sudoku Puzzle than it took me to write this script. This got me thinking about the many calls some people have made to teach everyone to code. This probably isn’t the best example as I’m sure this would be considered cheating, but I accomplished solving the World’s Hardest Sudoku with code. I never have to “waste” another hour of my life solving a Sudoku.
If you want to check out my “fast and dirty” code, or just cheat at Sudoku, you can have a look on GitHub. Please feel free to do what you like with this code. So, is this cheating? Did I really solve that Sudoku? If you feel the need, let me know in the comments.