I bet everyone has heard and play Sudoku. Personally, I love this game and I often play this game on my handphone when I don’t have anything to do or when I am waiting for something or someone. After spending quite much time, I finally realized the algorithm for solving Sudoke game and I decided to create a Sudoku solver with MATLAB. If you are having hard time solving 9×9 SudoKu puzzle, you can download my m-files in my MATLAB Fun Toolbox page.:D
The algorithm for Sudoku solver is relatively simple. Here is the following algorithm for Sudoku solver:
- Based on Sudoku’s rules (each number must exist only once in a row, a column and a 3×3 region box), create a possibility array for each empty box in the Sudoku board. Possibility array for an empty box consist of a list of number that is possible to be put in the said empty box. This is done by first preparing a possibility array for an empty box that consists of numbers from 1 to 9 and then eliminating those numbers with numbers is already exist in the column or row or 3×3 box of the said empty box. Repeat this until all possibility array for all empty box is obtained.
- Find an empty box whose possibility array only consists of one member of number, fill the empty box with those number, and then re-updates possibility array for all empty boxes (Step 1). Repeat this step until no more empty box with just one member of possibility array is exist. (Usually for easy or medium Sudoku puzzle, step 2 is sufficient to solve the problem).
- If no more empty box with just one member of possibility array is exist, evaluate a row, column or 3×3 box, and combine the possibility array of all empty boxes in it. Evaluate the members of the combined possibility array, if there is a number that appears only once in the combined possibility array, fill the empty box (in the said row or column or 3×3 box) whose possibility array contains that number. If there is not, try another row or column or 3×3 box. After you find any, reupdate possibility array (Step 1) and try executing Step 2 again. (Performing step 3 one or two times and then finishing the puzzle with Step 2 will solve most Sudoku puzzle)
- If Step 2 and Step 3 can no longer be used to fill any empty box, then it is time to guess. Find an empty box with the least member of possibility arrays (usually the one with two members) and fill that empty box with one number in the possibility array. If your guess is right, your puzzle will be solved. If it is not, it will cause impossibility and some point and you’ll have to start over from the guessing point and try to make another guess. (Rarely needed for solving Sudoku puzzle)
I have tested my code for about so many hard games of 9×9 Sudoku in my handphone and in websudoku.com and it works well. It give the correct solution for all cases. However, note that my code’s algorithm does not included step 4 of the algorithm of the Sudoku solver algorithm that I explained above (because it is too complicated and I’m too lazy to make it and it is rarely used). So, at some cases (for example: the evil diffuculty puzzle at websudoku.com), you may find out that my code does not work.
For the follow-up, I’m gonna improve my code to includes step 4 that I explained above. I may also create a GUI game of Sudoku. However, please don’t expect me to do this in a short time because I’m still busy with my thesis. This Sudoku solver that I created is just a runaway from my boredom in doing my thesis. So, in the meanwhile, check out my code and leave a comment/critic/sugestion.
Update for this post: Sudoku Reloaded!