The first is about the normal form of a sudoku. The rules of sudoku have a huge symmetry group of order (3!)^8 x 2 x 9! = 1.22E12. It is generated by permutations of rows in a group of three rows, permutations of these groups, same thing for columns, transposition of the grid and permutations of the numbers 1,...,9 which are just labels for nine different things. So for each grid, there are 1.22E12 grids which are basically the same. Is there an easy way to determine if two puzzles are related by the symmetry and even better, is there a normal form (a distinct element for each orbit)?
There is a trivial solution to this problem: You just write out all 10^12 puzzles you obtain by acting with the symmetry group and then sort them according to some lexicographic ordering. This gives a normal form.
What I am asking for is a more direct construction. One which sounds more like: Use the 9! permutations of the symbols to make the first row read 123456789. Then use row permutations to make the square below the 1 as small as possible. Then use row permutations to make the next squares under that square as small as possible... Unfortunately, starting to permute colums screws up what was achieved with this ordering prescription. So how would a better algorithm read?
The other problem is how to rate the difficulty of a puzzle? Question one really applied after the puzzle is solved, this question is about puzzles to be done. Newepaper which publish these puzzles often give ratings such as "simple", "intermediate", "hard". But I found these ratings differ significantly between papers (what Zeit online considers hard is much much easier compared to what The Guardian calls a hard sudoku) but are also not consistent amongst themselves.
Earlier, I have talked about the perl program I wrote to solve sudokus. It recursively figures out for all squares which numbers are still allowed and then takes the square with the least number and tries to put these numbers there. If there is an empty square with no allowed numbers remaining it backtracks.
Thus the search can be represented by a tree where each node represents a square to be filled out and there are as many branches from that node as there are numbers which are not yet rules out. What I am looking for is a numerical rating for a puzzle which is a predictor of how hard I find to do the puzzle and for example correlates with the time it takes me to solve it. Even if I use a different strategy when doing these puzzles by hand I would expect the information could be obtained form the tree. Do you have any good idea for such a function from trees to the reals, say? Obviously the trees all have a depth given by the number of empty squares in the puzzle and each node can have at most nine branches but typically has much less (even for "hard" puzzles most of the nodes have only one branch).
An easy guess is of course the number of nodes or the number of leaves but I found those at least not be proportional to my manual solution time. To give you an idea: Today's hard puzzle from Die Zeit
..573.864
.4...8...
.83.....1
71....2..
3..6921.7
4...7..9.
....4.97.
..6..5..8
.......1.
has 52 nodes (four times the program encounters situtations with two possibilities, all others are unique or dead ends, manually it took me exactly 6:30) while
.98......
....7....
....15...
1........
...2....9
...9.6.82
.......3.
5.1......
...4...2.
has 2313 nodes and took me well over an hour some months ago.
Of course, if early on you have several possibilities and learn only much later which ones do not work this is much worse than having many possibilities which are ruled out immediately.
UPDATE: In case anybody is interested, I put up the decision tree for the difficult puzzle.
Posts
4 comments:
Just another 17 clue puzzle
798624315
315879246
264315978
129587463
683241759
457936182
942158637
531762894
876493521
www.onedollarsudoku.com
I haven't thought about this for very long, but are you sure that for the Sudoku symmetry group the operations you named are actually all independent generators? I was wondering whether the operation of renaming digits 1-9 couldn't possibly always, or at least sometimes, be reformulated as a sequence of row and column permutations, given that the entries in each row, column and square are distinct. In that case the real symmetry group would be reduced by some relations between the different generators.
As far as I can tell this is not a 17 but an 81 clue puzzle and thus even Die Zeit would not rate it as "hard".
Georg raises an interesting point: I think what I wrote about the symmetry group of all sudokus is correct. However, not all orbits will be of this full size, some puzzles will not change under specific transformations. You could imagine a puzzle where a permutation of row blocks could be undone by a relabeling of the symbols for example.
These transformations which leave a specific puzzle invariant form a subgroup of the full symmetry group called the stabiliser. This opens the possibility for a third sudoku problem: Find a puzzle with a large (the largest?) stabiliser!
I've read that most 'zines use a group of basic, human tactics as a measure for difficulty of the puzzle. (there's actually a solid library of quite a _lot_ of tactics... a puzzle that requires, from any some set, a particular strategy, requires that tactic's level of abstraction: so it isn't entirely ill-founded.)
As for your difficulty rating not scaling, just some thoughts (I'm no mathematician so forgive me):
can you combine leaf-count with backtrackings required?
Backtracking by itself may not show difficulty correctly, because it is required in places where, when working the puzzle yourself, you would just use an abstraction (for hard puzzles in the Washington Post, it is common-place to have to look at a 3x3 cell and mark possibilities, such that one square may just happen to only have one possibility: it's the pigeon hole principle!) So you need some further refinement..
Post a Comment