This Sudoku Must Be Solvable

Unique Rectangle

In this post I’ll share my favorite Sudoku trick, called the Unique Rectangle. It is really clever and comes up in actual puzzles. I’ve been solving the New York Times hard Sudoku every night for years, and I’ve used this trick on maybe 10-20% of them.

Imagine you’re solving a Sudoku and you’ve penciled in:

     1   2   3
   +===+===+===+
A  |12 |12 | ? |
   +---+---+---+
B  | ? | ? | ? |
   +---+---+---+
C  | ? | ? | ? |
   +===+===+===+
D  |12 |123| ? |
   +---+---+---+

You’ve eliminated all possibilities except 1 and 2 for grids A1, A2 and D1, and you know D2 can only be 1, 2 or 3.

The Unique Rectangle rule says that D2 must be 3.

“Why?” You object. “There are only 3 rules in Sudoku - all 9 3x3 blocks, 9 rows and 9 columns must all contain numbers 1-9. If D2 is 1 or 2, we can still fill in A1, A2 and D1 without violating the rules!”

You are right that the normal constraints of Sudoku aren’t enough. This trick relies on a leap of faith: we assume that the puzzle has a unique solution. This is true for all valid Sudokus – if there are more than one solutions, then the puzzle will not be solvable using logic, and is therefore invalid. (Using the fact that the puzzle is solvable to solve the puzzle might feel like cheating, but I have no personal issues with it.)

In the above example, if D2 isn’t 3, we have 2 possibilities:

(I)       1   2   3     (II)      1   2   3
        +===+===+===+           +===+===+===+
     A  | 1 | 2 | ? |        A  | 2 | 1 | ? |
        +---+---+---+           +---+---+---+
     ...                     ...
        +===+===+===+           +===+===+===+
     D  | 2 | 1 | ? |        D  | 1 | 2 | ? |
        +---+---+---+           +---+---+---+

The only constraints that can be used to solve these 4 grids are columns 1 and 2, rows A and D and the 3x3 blocks, but in all these constraints, (I) and (II) are indistinguishable, and we are left with an unsolvable puzzle. So D2 has to be 3.

More generally, the Unique Rectangle rule states that if you have 4 grids in 2 3x3 blocks forming a rectangle, and 3 of them have only 2 choices, then the fourth grid cannot be either of those choices.

There are some extensions to this trick. One is chaining which I have also used:

     1   2   3
   +===+===+===+
A  |12 |12 | ? |
   +---+---+---+
...
   +===+===+===+
D  |23 |23 | ? |
   +---+---+---+
...
   +===+===+===+
G  |13 |134| ? |    G2 cannot be 1 or 3
   +---+---+---+

Another one that I recently figured out during solves:

     1   2   3
   +===+===+===+
A  |12 |12 | ? |
   +---+---+---+
B  | ? | ? | ? |
   +---+---+---+
C  | ? | ? | ? |
   +===+===+===+
D  |123|123|34 |
   +---+---+---+

Either D1 or D2 must be 3, so we know D3 must be 4.

Here is a website with other advanced Sudoku techniques. I have not found the other tricks to be as interesting or as applicable to NYT puzzles.

Leap of Faith

This sort of “if there is a solution, it must be this” thinking comes up in other occasions as well. Here are a few that I can immediately think of.

In minesweeper, it is very common to run into unsolvable boards, but the same logic can still apply. In this example:

     1   2   3   4
   +===+===+===+===+ ...
A  |   |   | 1 | 0 | 
   +---+---+---+---+
B  |   |   | 2 | 1 |
   +---+---+---+---+
C  | 1 | 2 | |>| 1 |
   +---+---+---+---+
D  | 0 | 1 | 1 | 1 |
   +---+---+---+---+
...

There are three possibilities:

(I)            (II)          (III)
+===+===+ ...  +===+===+ ... +===+===+ ...
| X |   |      |   | X |     |   |   |
+---+---+      +---+---+     +---+---+
|   | X |      | X |   |     |   | X |
+---+---+      +---+---+     +---+---+
...            ...           ...            

When you finish the rest of the board, you can see how many mines are left. If it’s 1, you know it must be (III); but you can’t tell between (I) and (II). Either way, clicking on A2 or B1 is never wrong, so you can do it without solving the rest of the board. (In minesweeper, if you must guess, it is better to guess earlier so that you don’t waste time in an unsolvable game).

Another example is Alice at the Convention of Logicians. Everything on this wiki page is worth a read, so I won’t bother explaining the puzzle here.

I’ve also found that this line of thinking is useful in solving math puzzles in general, or even problems that aren’t necessarily designed to be solvable. It is like a less blasphemous form of Pascal’s wager – if you’re right, then great, otherwise it doesn’t matter.