Solving the Mysteries of Sudoku

[quetzalcoatl9]

http://en.wikipedia.org/wiki/Sudoku

I have found myself addicted to working on them.

has anyone else here found these things interesting? I'm currently trying to work out the probability of degeneracy when given a particular square, it has proven challenging...

 

[AKG]

I do these things every day, but the ones I do seem a little easier. The ones I get give more initial numbers, and it normally takes me 3-4 minutes to do them. The one you've shown would take a little longer, but there's a pretty simple algorithm that makes it easy, and if you do them every day, it's quite quick. With the ones I do, there are normally enough numbers that you can look at say the middle 3x3 box, realize what numbers need to go in its empty squares, and find one of the numbers which you can immediately place. For example, if you look at the top-middle square in the bottom-right 3x3 box, and imagine a 2 were there, then you could immediately place a 2 in the bottom-left square of the grid. As you do this, you get more numbers obviously, and can normally find other boxes where you can do this, and fill up the whole grid in this way.

If you don't have enough numbers for this (although with the one you posted, you can place a 4 in the bottom-middle square of the top-left box, and then using that 4, place a 4 in the left-middle square of the top-middle box), then you can look at any given square, and by process of elimination list what numbers can go there. If the grid is not "degenerate" then this will necessarily solve it. If you're trying to see which grids are degenerate, you may want to consider the conditions under which this algorithm fails.

 

[quetzalcoatl9]

well, i know some conditions for which you are guaranteed a degenerate solution. one would be having any two rows or columns within a 3 row/column "block" be empty (by "block" here, i mean row1,2 and 3, for example), since rows and columns within a "block" can be swapped and still have a square. "blocks" themselves can also be swapped.

however, i cannot yet prove that there are no additional degenerate positions. consider an empty 3x3...is there a degenerate answer? it is hard to say, and may involve a probabilty function based upon the distribution of the given squares.

and btw, i had thought that the game gives you only 30 numbers, i was not aware of variations where you have more numbers than this.