the meaning of the word sudoku AND COUNTING SUDOKU PROBLEMS

This week I had a chance to spent some time with my former professor from the Tokyo Institute of Technology, Osamu Watanabe. It is funny that I ended up seeing him here in Barcelona after not seeing him at all the last few years that I was in Tokyo a lot more often.

He explained me an anecdote about how he thought that Sudoku meant "numbers poison" since you could actually write it that way using Japanese kanji and how he told so an American that he met on a plane trip that was playing Sudoku. In fact, Sudoku is not written with the kanji for "number" (su) and "poison" (doku) but numbers and "single" (doku means also poison but with a different kanji) and as explained in this article, the game, not invented in Japan but in the US and popularize by a Japanese magazine under the new name which was trademarked (the game itself cannot be patented or trademarked) was originally referred to as "suji wa dokushin ni kagiru," which means "the numbers must be single"—meaning not repeated. The name was then shortened to Sudoku, which means "single numbers.

Watanabe-sensei is working with one of his student on trying to solve the problem of providing a way to enumerate Sudoku problems. As far as he knew (and few Internet searches confirmed this in an extremely experimental way), this problem has not been solved, what has been solved is counting how many Sudoku problems are out there.

Solving this problem and providing an algorithm for generating a unique number for each Sudoku number will prove to be very popular since someone could easily create a centralize database of known Sudoku problems (just the numbers) and then check against that to see whether that one exists and then claim that number or someone could be challenged to create Sudoku problem number 234,934 knowing that someone else has already created problems 234,933 and 234,935 and fill the gap. Notice that since every Sudoku problem has a unique solution, what we are counting here are unique solutions but for each solution one can generate a lot of different starting points just by removing numbers differently. That also leads to the problem of how many numbers can you remove while leaving the problem solvable which is another interesting problem. Since Sudoku is basically a constraint satisfaction problem, as a theoretical computer scientists will say, it is a a very interesting source for mathematicians and theorists to study it. You can apply known computer science techniques like integer programming to solve it.

Finally, the article in the American Scientist has a short but interesting discussion about Sudoku strategies and whether you can solve it by pure logic (you always put a number in a place knowing that is the only number that can go there and that allows you to continue) or backtracking basically guessing till you arrive to a mistake and then go back to the initial guess and try with another one). I have always solved Sudoku problems by logic (which is in fact why I like Sudoku since using backtracking is not mentally challenging) so it will be interesting to know whether this is in fact the only way to solve them or there are problems where backtracking is absolutely necessary.

CD