Too Busy For Words - The PaulWay Blog

12 08 2012

Sun, 12 Aug 2012

Satisfying Sudokus

I do like Sudoku puzzles. There's something satisfying about the types of logic, the positive and negative inferences, one uses to solve it. I have several processes I use, depending on whether I'm using a paper and pen or a computer or a phone. I'm up to solving some of the "Very hard" in GNOME Sudoku - in SudokuWiki terms I can usually solve anything that doesn't need one of their "tough" strategies, although I've had a couple of times when I've recognised e.g. a unique rectangle as well.

But some puzzles are more satisfying to solve than others. I hate ones where you have to use any kind of guesswork - in other words, trying out one number in a position and seeing if it breaks any rules anywhere. I don't like having to find positions where there's a unique number as a result of box, row and column intersection. Not being able to solve a puzzle that should be solvable at my skill level is frustrating - especially as I suspect that some puzzle setters rate things I find hard as easy. And there's a nagging doubt that, for some puzzles, my way of solving a Sudoku occasionally leads to it being harder to solve than if I just, for example, turned on GNOME Sudoku's "show possible numbers" display and filled in the places that only listed one possibility.

Incidentally, this is why I find it amusing that someone wrote a program to solve Sudokus as fast as possible by trying possible combinations in turn, as a kind of "so there" to all those humans who toil away thinking them so smart to solve a Sudoku. The point of climbing Mount Everest, Mount Kosciuszko or Mount Painter is simply because it's there; the amazing thing about a dog that walks on its hind legs is simply because it can do it at all. Computers might be much faster at solving virtually any logic puzzle than humans, but that doesn't diminish the satisfaction of doing one in the meaty confines of ones own brain.

And, strangely, the ones that are satisfying to solve also display a level of symmetry to the eye. One I solved just tonight looked a bit like a fylfot, and it was pleasing the way lines of two and three numbers would provide some insight into solving the next box. I could use one or two techniques for a while, and then switch to another couple of techniques later in the process. Others I've solved have looked like crosshatchings, or have many numbers clustered in boxes one and nine and have boxes three and seven blanks.

So I started wondering about writing my own Sudoku generator that would take five by five matrices listing the order in which cells were to be filled, and two symmetry options for horizontal or vertical: as is, mirrored, rotated clockwise, anticlockwise or 180 degrees. Use a character: 0, 1, 5, 2, 3. The cells could either be lettered A-Z or blank, so, for example:

ABCG____H____I_DEFJ______55 would indicate:

ABCG_D__A
___H_E__B
___I_F__C
DEFJ_JIHG
_________
GHIJ_JFED
C__F_I___
B__E_H___
A__D_GCBA
So the square pattern in the top left quadrant has been turned by 90 degrees clockwise ('5') to make the top right quadrant; this then gets turned 90 degrees clockwise again ('5') to make the bottom right quadrant and thus, symmetrically, the remaining quadrant is the last rotation of the quadrant. The overlapping in the fifth row and column is handled by not filling in a number if that cell already has one. Sudokus need at least 17 clues to be solvable, from Wikipedia, but with twenty-five to thirty-two clues being the more usual range, having letters A-J with four areas for symmetry should be enough.

Now to sit down and work out how to write a program to generate this.

posted at: 21:33 | path: /personal | permanent link to this entry


All posts licensed under the CC-BY-NC license. Author Paul Wayper.

You can also read this blog as a syndicated RSS feed.