"How To Solve Sudoku Mathematically"

Discuss all puzzle-related subject here
Post Reply
detuned
Posts: 1672
Joined: Mon 21 Jun, 2010 2:25 pm
Location: London, UK
Contact:

"How To Solve Sudoku Mathematically"

Post by detuned » Fri 15 Oct, 2010 4:17 pm

Mike forwarded me an email from some chap called Harsh Goel who is the latest person to have claimed to have had some incredible new sudoku solving epiphany.

http://www.scribd.com/doc/39235249/How- ... ematically

Rather than reply via email, I thought there was potential for more than just me to have an input on things here. On the other hand this is probably only for sudokuphiles. We'll see.

The gist of what is going here is to transform the geometry of a sudoku puzzle. Boxes are now displayed as rows, paired off against a set of nine columns labelled 1-9. The solution coordinate of each number for each box is entered into the row/column intersections. Standard techniques can then be reprogrammed in this new format, and the claim is this is in fact a Wonderful New Thing.

It is at this point where I am unsure of the authors aims. To claim this makes human sudoku solving easier - at this stage - seems a little ridiculous. You have to draw out a whole new grid and painstakingly transpose information. You are then applying the same techniques every solver knows and loves as according to this new format. The ones detailed in this article seem frankly slow and clunky, and have no advantages to my eye over simply doing the puzzle as it is presented to you.

I suppose then this has more to do with computer solving. But perhaps here am I confused as well. If you simply want a solution, without any walkthrough as to how it is achieved, why not simply use brute force (a la scanraid) to get out a solution quickly and with a minimum of fuss? If you do want a walkthrough - then why bother with coding everything in this new format, when (for example scanraid) existing software does all this in the classic sudoku format already? perhaps my questions here are naive, but to be brutally honest computer solving doesn't interest me in the slightest.

Anyhow - if we ignore the motivations for a second, and take things at face value, lets try a little analysis of the situation. From a mathematical (combinatorial) point of view, a sudoku puzzle is nothing more than applying a 9-colouring to a fairly complicated graph (graph in the sense of joining a set of vertices with a set of edges). The geometry of the graph as grid is inherently stored by the edges of this graph. The interesting thing from this method's point of view is that it takes a different approach to colouring the vertices of the graph.

With a standard presentation you are given 81 vertices to be coloured so that no two adjacent vertices have the same colouring. Here by adjacent I mean two edges are shared. The idea is then the givens are vertices which have already been given a colouring, and you have to fill in the rest. With this approach, you are effectively given a configuration space of several (a very big number indeed!) copies of already coloured 81 vertices - each copy linked up with the same edges as before - but crucially also with several links between the copies. The solving process is to then delete edges - in effect pruning this monster graph - until what you are left with is the solution. Having this monster graph simplified into a grid format inevitably loses a lot of the geomery of the standard approach. With this loss of geometry, you lose a lot of the visually intuitive aspect of sudoku solving.

So as a curiosity, there is a little interest there - however I see no practical use. However, I have yet to see "extreme" techniques, for example xy-cycles or Almost Locked Cells or the like translated into this new format. If in this new format these techniques are elucidated a little more clearly then there is perhaps some interest to the sudoku solver who likes to torture themselves with hard puzzles. This will have little impact on your average sudoku solver.

Post Reply