May 13, 2009 | 10 comments

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

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

By Dennis E. Shasha   

 
e-mail print comment

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.



Read Comments (10) | Post a comment 1 2 3 Next >


Share
Propeller    Digg!  Reddit delicious  Fark 
Slashdot    RT @sciam Puzzling Adventures: You've heard of Sudoku. But what about Sudokill?Twitter Review it on NewsTrust 
sharebar end

Discuss This Article


Click here to submit your comment.

VIEW:

2,573 characters remaining
 
  Email me when someone responds to this discussion.
 

risk free issue 

Sciam - cover Email:
Name:
Address:
Address 2:
City:
State:  
spacer



World Changing Ideas



Editor's Pick


Newsletter

Basic Science Newsletter

Get weekly coverage delivered to your inbox


 Podcasts

  • 60-Second Science     RSS  · iTunes Botoxed Face Impairs Bad Feelings
    click to enable

    Download

  • 60-Second Science     RSS  · iTunes Distracted Customers' Wait Times Fly
    click to enable

    Download





ADVERTISEMENT
 
 


Also on Scientific American


© 2010 Scientific American, a division of Nature America, Inc. All Rights Reserved.
ADVERTISEMENT