## Wednesday, December 30, 2009

### Sudoku (unfinished)

It has been well said that "Sudoku is a denial of service attack on the human intellect".

Sudoku is an entirely mechanical procedure. Solving a Sudoku is just following an algorithm. Many sudokus can be solved by the most mindless constraint-propagation approach. All can be solved by combining this with a backtracking search.

Some very hard puzzles would take a long time to solve this way by hand, so one can make the algorithm faster by putting in shortcuts which are not immediately obvious from the ground rules. Perhaps the fun is in deducing what these shortcuts are as one develops an intuition for the puzzle?

But it is a bit as if newspapers printed long multiplications and divisions daily with their answers the next day.

I've never really got it, but many people do. Why is is it so addictive?

It's definitely maths, though. It distresses me when people say it's not on the basis that it doesn't involve any adding up.

Granted the numbers aren´t really doing anything numeric. They may as well be different colours. Are there nine easily distinguishable colours? It might prove quite pretty presented like that. You'd need special coloured pens to solve it though.

But the puzzle is saying ¨Given that these things are true, what else must be true?¨, which is pretty much a definition of mathematics: ¨All that which can be reasoned about without error¨.

In fact, why not teach sudokus in maths classes? If people really find these sorts of formal systems interesting, there's a lot to learn from examining them.

Of course a possible consequence would be an all consuming addiction, with the whole of society wasting endless amounts of time. But that is happening anyway. And it would be a nice environmentally friendly way to waste time, which wouldn't hurt anyone. What are people supposed to do? Go out and get jobs so that they can buy cars?

I wonder if there's a useful analogy between sudoku and formal logic.

The rules of sudoku would be analogous to logic itself.

If you had a blank grid, then there would be many possible solutions available, which would be the analogues of all the possible formal systems.

Specifying that a particular number had to go in a particular place would reduce considerably the number of possible solutions, and would be the equivalent of adding axioms.

Certain combinations of axioms would be compatible, certain combinations would lead to contradictions.

Deductions about what other number-placements were forced by the axioms would be theorems of the system.

Certain combinations would lead to unique solutions, analagous to axiom systems which are both consistent and complete.

Sadly there's no GĂ¶del theorem due to the finiteness of the system, but is it possible to make a sudoku like thing powerful enough to express the problem?