ADVERTISEMENT

Puzzling Adventures: You've heard of Sudoku. But what about Sudokill?

A computer science professor encourages his students to break Sudoku's rules

More In This Article

I suspect that among the readers of this column, few are unfamiliar with Sudoku. The same cannot be said about Sudokill, a game invented for a graduate class I teach. Sukokill is a two-person game in which players try to force each other to violate the Sudoku rules.

Here's a quick refresher on Sudoku. The goal is to fill a nine-by-nine grid with digits between 1 and 9. Each digit should appear exactly once in each row, once in each column and once in each nonoverlapping three-by-three box starting from the upper left corner.

In the following example, we use 0 to represent a blank.

0 0 0 0 0 0 0 0 7 7 0 4 0 0 0 8 9 3 0 0 6 8 0 2 0 0 0 0 0 7 5 2 8 6 0 0 0 8 0 0 0 6 7 0 1 9 0 3 4 0 0 0 8 0 0 0 0 7 0 4 9 0 0 6 0 0 0 9 0 0 0 0 4 5 9 0 0 0 1 0 8

Consider the lower left box:

0 0 0             7 0 4             0 0 6             0 0 7             0 8 0             9 0 3             0 0 0 7 0 4 9 0 0 6 0 0 0 9 0 0 0 0 4 5 9 0 0 0 1 0

8

We know that of the five blanks in the lower left box, one must be 7. Because there is a 7 in the third column and also a 7 in the seventh (from the top) row, the only legal place for a 7 is to the right of the 6, yielding:

0 0 0             7 0 4             0 0 6             0 0 7             0 8 0             9 0 3             0 0 0 7 0 4 9 0 0 6 7 0 0 9 0 0 0 0 4 5 9 0 0 0 1 0

8

By contrast, the following would be illegal:

0 0 0             7 0 4             0 0 6             0 0 7             0 8 0             9 0 3             0 7 0 7 0 4 9 0 0 6 0 0 0 9 0 0 0 0 4 5 9 0 0 0 1 0

8

... because then there would be two 7s in the same row.

In Sudokill, two players alternate moves that consist of replacing a blank by a number. The first player is called the row player and the second is the column player. Initially, the row player can make any legal Sudoku move. Subsequently, the column player must move in the same column as the last move of the row player and the row player must move in the same row as the last move of the column player. If a player makes an illegal Sudoku move, even by accident, then that player loses.

If we represent blanks as 0s or letters and the row player moves where there is an x:

0 0 6 0 0 0 0 0 0 8 4 0 3 x 2 0 0 0 3 2 0 0 0 5 0 7 4 0 6 0 0 9 0 8 0 0 0 0 0 6 2 4 0 0 0 0 0 2 0 3 0 0 6 0 2 1 0 9 0 0 0 8 7 0 0 0 4 0 3 0 2 5 0 0 0 0 0 0 1 0 0

The the column player must replace a blank in the same column (marked with y's):

0 0 6 0 y 0 0 0 0 8 4 0 3 x 2 0 0 0 3 2 0 0 y 5 0 7 4 0 6 0 0 9 0 8 0 0 0 0 0 6 2 4 0 0 0 0 0 2 0 3 0 0 6 0 2 1 0 9 y 0 0 8 7 0 0 0 4 y 3 0 2 5 0 0 0 0 y 0 1 0 0

Suppose the column player chooses the one marked by an upper case Y:

0 0 6 0 y 0 0 0 0 8 4 0 3 x 2 0 0 0 3 2 0 0 y 5 0 7 4 0 6 0 0 9 0 8 0 0 0 0 0 6 2 4 0 0 0 0 0 2 0 3 0 0 6 0 2 1 0 9 y 0 0 8 7 0 0 0 4 Y 3 0 2 5 0 0 0 0 y 0 1 0 0

The row player must then move in one of the positions marked with a z:
0 0 6 0 y 0 0 0 0 8 4 0 3 x 2 0 0 0 3 2 0 0 y 5 0 7 4 0 6 0 0 9 0 8 0 0 0 0 0 6 2 4 0 0 0 0 0 2 0 3 0 0 6 0 2 1 0 9 y 0 0 8 7 z z z 4 Y 3 z 2 5 0 0 0 0 y 0 1 0 0

Toward the end of the game, the following rules prove important: If there are no blanks in the column where the row player last moved, then the column player may move anywhere. Likewise, if there are no blanks in the row where the column player last moved, the row player may move anywhere.

Warm-up Puzzle:
Suppose it is the row player's move in the following situation (where letters represent blanks) and the row player can move anywhere:

5 7 6 1 4 9 2 3 8 8 4 9 3 7 2 5 1 6 3 2 1 8 6 5 9 7 4 4 6 3 7 9 1 8 5 2 1 5 8 6 2 4 7 9 3 7 9 2 5 3 8 4 6 1 2 1 4 9 5 6 3 8 7 9 8 7 4 1 3 6 A 5 6 3 5 B 8 7 1 C 9

How can the row player force a win (that is, force the column player to make an illegal move)?

Solution to Warm-up Puzzle

Now it's your turn, but this time we'll favor the column player.

1. Can the column player force a win in two moves given the following board? (Here the column player can begin by moving anywhere.)

8 1 5 3 4 9 2 6 7 7 A 4 B 5 1 8 9 3 3 9 6 8 7 2 4 1 5 1 4 7 5 2 8 6 3 9 C 8 2 9 3 6 D E 1 9 6 3 F 1 7 G H I 2 3 1 J 8 K 9 5 6 6 7 8 1 9 5 2 3 4 L 5 9 2 M 3 1 7 N


Solution to Puzzle #1

2. Here's a harder one. Can the column player force a win in three moves given the following? (Again the column player can begin by moving anywhere.)

7 A 5 8 1 3 2 9 B C D 1 4 7 6 5 E F 3 4 G 2 5 9 H 1 7 9 1 4 5 ? 7 3 2 6 I 5 7 3 6 2 J 4 9 6 2 3 9 4 1 7 K L 1 3 2 6 9 8 4 7 M N 8 O P 2 5 9 3 1 Q 7 9 1 3 R 8 6 2

Solution to Puzzle #2

Here's an invitation. If you can produce a four-move forced win on a board initially having more blanks than assignments, please send it to me at shasha@cims.nyu.edu. Also, please play Sudokill at Yu Yiwen's Web site designed by a graduate student at New York University: http://homepages.nyu.edu/~yy497/projects/showcase/SudokillWebGame

Share this Article:

Comments

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Scientific American Back To School

Back to School Sale!

12 Digital Issues + 4 Years of Archive Access just $19.99

Order Now >

X

Email this Article

X