Abstract Confusions

Complexity is not a cause of confusion. It is a result of it.

To run or not to run in rain? – A math solution

Ever faced with the inability to take decision whether to run or not to run in rain? or in a snow fall? The question is of course not about running on heavy rain.Most of the time when it drizzles you are left with inability to take decision whether you should ran like mad to home or just walk into it. Friends who wait for the rain to subside have always one easy solution to take. Few brave people decide to fancy it and run in the rain. I always used to run and think afterwards why I ran.

And hence the sudoku is solved

Sudoku is one of the interesting puzzles one might have played. Sudoku gained popularity in late 1990s. Sudoku is a not a complex game to understand. Sudoku doesn’t have confusing rules. It doesn’t need accessories to play. All you need is a pencil and perhaps an eraser. I have seen old age people getting more interested in solving it because of its simplicity. There are bunch of guys, who tried writing computer programs, so that, it solves the puzzle. What’s interesting is, even though there are strategies on how to play sudoku. No one had a proved method for solving sudoku.

Enter mathematics

People started looking for tools, steps or methods to solve sudoku. The reason being, sudoku is ridiculously easy but still posed rigidity from being conquered. Some times people get so much frustrated because there might be two or three numbers away from solving but still not able to finish it. Computer programs are no good. All they could do is trail and error.

Sudoku - Game of numbers

Enter mathematics, and things started to settle down. Sudoku is now solved mathematically. I was expecting this to happen. Because, sudoku to a certain extend can be played purely based on logic. For hard puzzles, others used another technique known as back tracking to solve it. But a mathematical method was lacking. Recently, this was supplied in an mathematical paper.

Pencil and paper algorithm

A professor of computer science, J. F. Crook from Winthrop university, US, has provided an algorithm, what he calls as, a pencil and paper algorithm for solving sudoku in an notice to AMS. The paper can be read from here. In that paper, J. F. Crook discussed how sudoku is played, rules and known strategies for solving it. Couple of definitions, examples and finally the algorithm to solve sudoku using pencil and paper. Here is that algorithm for you.

Algorithm: J. F. Crook’s pencil and paper algorithm.

1. Find all forced numbers in the puzzle.
This is a straight forward step. Just take a look at the puzzle and fix the obvious choices in the cell.
2. Markup the puzzle.
This is where you do the guessing. Start writing the possible numbers into a small set for every cell. This is known as ‘markup’.
3. Search iteratively for ‘preemptive set’.
This is looking for set of numbers or a singleton set in order to finalise the number for the cell. You need to repeat this for cells, rows and columns. Arriving at this preemptive set and hidden preemptive set is the key in finding solution for a sudoku puzzle. I am not going to explain in detail as needs lengthy explanation, and explained in detail in the paper.
4. If  solution is reached, stop. Else, make a random choice and continue from step 3.
There are chances, that you may not gracefully finish the puzzle without making a random choice. So make the necessary random choice to continue the game and solve it. Crook explained the need for making random choice by demonstrating that there are chances for a puzzle to have several possible solution.

Most of the mathematics is done in proving how preemptive sets are used to solve sudoku.

Critics

Mathematical proof for sudoku was expected for long time. Crook used combinatorial techniques in proving solution. The pencil and paper algorithm also needed a random input. Even though this is because of the non-uniqueness of sudoku solution, the algorithm looks in-complete. Even the best computer algorithms use random methods to solve sudoku. A definitive method for solving sudoku is still needed.

What Crook has shown is very important. When the news that sudoku is solved mathematically spread, people feared instead of rejoice. Papers reported that they don’t need a mathematical solution. At times, it is like some one telling the climax of a thriller. But, looking at the Crook’s pencil and paper algorithm, it is easy to do sudoku as one used to do previously rather then setting it up with mathematical methods. An comparison in the same paper states, it took 4 minutes for solving a sudoku puzzle normal way compared to 50 minutes using the pen and paper method. Perhaps with time and practice one might reduce the time taken from 50 minutes to 5 minutes. But you won’t be doing sudoku anymore.

At least in the foreseeable future, there won’t be a definitive algorithm, strategy or method to solve sudoku. You can still enjoy the happiness of finishing the puzzle on your own.