I've come across a Sudoku theorem. A bit of web searching didn't turn up anything quite like it. It isn't particularly helpful in solving them, but it seems worth reporting. Maybe someone can take it further. Within a 9x9 Sudoku, look at a horizontal block of three subsquares, forming a rectangle with three rows and nine columns. Within each 3x3 subsquare, consider the sets of three horizontal cells, *** ignoring the cells' order *** within each 1x3 rectangle. Then there are only two possible patterns of the 3x9 rectangle: abc ghi def def abc ghi Rare ghi def abc abc efg hid hig abd efc Common efd hic abg In the rare case, the horizontal triples abc, def, ghi rotate (either up or down) in the successive 3x3 subsquares. In the common case, each horizontal triple in the first subsquare has a pair of values that stay together in the second and third subsquares. In the example above, the pairs are ab, ef, and hi. The pairs rotate (either up or down) in successive boxes. The other three values (in the example, c, d, and g) rotate in the opposite direction. The proof (below) is easy, using the usual exclusion rules. This may explain why the theorem isn't much help in solving: The solver automatically applies the exclusion rules in each particular puzzle, deducing anything that the theorem provides. It does seem to work best in midgame, but usually there are a few different possible ways to assign the blank cells in a partially filled-in situation. I haven't explored trying to use both horizontal and vertical restrictions together. Proof: Name the three cells in the top left 1x3 rectangle ABC. In the middle subsquare, it's possible that ABC are still together in either the middle row or the bottom row. If so, the rare case follows immediately. Otherwise, if ABC are split up between the middle and bottom rows of the middle subsquare, two of them must be together, say AB, and assume they are in the middle row: ABC ... ... ... AB. ... ... ..C ... Filling in the right subsquare: ABC ... ... ... AB. ..C ... ..C AB. Naming some remaining cells D and EF: ABC ... ... ... ABD EFC ... ..C AB. Then DEF must occupy the lower left triple: ABC ... ... ... ABD EFC EFD ..C AB. Naming the remaining cells in the bottom row HI and G: ABC ... ... ... ABD EFC EFD HIC ABG The rest follows: ABC EFG HID HIG ABD EFC EFD HIC ABG [QED] I've arranged the pairs on the left of each 3x3 subsquare, and the singletons C,G,D on the right, to make the rotations obvious. In a real Sudoku, the arrangement within each 1x3 triple can be anything. The theorem is a description at a different level than the usual situation, where the possibilities for individual cells are listed, but listing combinations is infrequent. In an average midgame, I can examine the six 3x9 rectangles and make various deductions. If I see two values together in two of the three subsquares, they must be together in the third subsquare, and the direction of pair rotation is also determined. Usually the rare case is immediately obvious or refuted. Moreover, in the common case, I know that three of the nine values must rotate in one direction, and six in the other. Whenever a value occurs in two subsquares, the rotation direction is determined. Often, the pairs can be worked out from this, or the singletons. This usually doesn't determine values in a cell, but may allow some possibilities to be excluded. Rich
participants (1)
-
rcs@xmission.com