Urinal Protocol and Hilbert’s Hotel

There are two things I read this week and thought weird. One is about ‘Urinal protocol’.

Urinal protocol vulnerability

For those who don’t know what it is, read here. The point is, in a public rest room, every male should take due effort to use the buffer urinal. There are un-written rules, protocols people follow in using urinals. The common one being, using the urinal which is at the maximum distance to the one occupied already. Then, the point of using, allocating these resources effectively comes in as a concern.

Best 10 Jobs in and after recession times

Always one is curios to do the best job. With economy going southward, it is only normal for people to save their job. And if you are not doing good work, no matter what job you are in, you will be laid off. Having said all this, I am looking into some of the best jobs around, in this recession time and afterwards.

Top 10 jobs, 2009

A recent study listed the top ten jobs. They took several parameters to identify the ideal career. And here are those results.

Mathematics all the way – One, two and three

The top most job is that of a mathematician’s. Work is fairly safe and interesting. All you need to do is, to take couple of lectures. Guide few Ph. D scholars and publish papers if any. Unlike other branch of studies, mathematics doesn’t surprise often. Apart from people who are doing cut throat research, there is no need to keep learning much.

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.

One Way Only…

This time around, some thing interesting from the world of mathematics.

All of us dealt with functions of different types. We are introduced to functions when very early in school. Single varriable, multi varriable, simple and complex functions. And in college, functions declared, defined and studied. In this post, one such function, known as “one way function” is used widely in computer science.

Wonderful functions from math

Mathematics is full of functions. These functions are applied far and wide else where. Few are used many times where as few others are used little. And very often functions and equations are interchanged. The most celebrated of them all is -

Chances for Slumdog Millionaire to win Oscar

Let me not get into the bitter fight of what does slumdog millionaire portraits India to the world. Personally, I think it could have been better. But looking at the brighter side of it. Slumdog millionaire got nominated for ten oscars. It has created lot of curiosity and animosity.  As the Oscar day nears, I asked myself, What are the chances for Slumdog Millionaire to win Oscar? What are the odds in favour and against? We shall analyse it here.

Games Indians Misplay

People play several games. Few are for happiness; few others are for time passing; few are soft in nature; while few others are brutal. Few of the games are confined to meager purpose and few other have mega impacts. Some times they play with people, and some other with animals.

Few intelligent species set on an interesting journey to understand how games are played, what is the rationale behind the movements rather than playing it. They are very lazy in playing them. They are ambitious and want to know the chances of wining the game, without even playing it.