Su Doku Navigation

Su Doku

Su Doku is usually played on a 9 by 9 board, divided into 3 by 3 cells. You can generalize this into playing on an M×M square board broken into non-overlapping rectangular cells, each containing M squares (an obvious question is to how define a puzzle where M is a prime number). The solution of the puzzle is to place M symbols on the board such that each row, column or cell contains each symbol exactly once, without moving the initial clues. Puzzles with M<9 are called Sub Dokus, those for M>9 are called Super Dokus.

Technorati tag:

Related topic: Kakuro

A Greedy Algorithm

What is the maximum number of clues?

A set of clues is called independent if none of them can be derived from the other. One interesting question about Su Doku is the maximum number of independent clues that can be placed in a puzzle. One algorithm to search for maximum Su Doku is the "Greedy Algorithm", which we outline here.

  1. Start with a blank grid and put in a symbol anywhere: for example write 1 in the upper left corner. Enumerate all eliminated possibilities.
  2. Examine each remaining square in turn, and find a combination of square and symbol such that putting that symbol in that square eliminates the minimum number of possibilities.
  3. Enumerate all eliminated possibilities. If one or more squares are rendered unique, then recursively eliminate possibilities from these. Such squares are not to be counted as hints, since they are clearly deductions.
  4. If some squares still exhibit a choice of fillings, then repeat step 2. Otherwise count the number of clues written.
© Sourendu Gupta. Mail me if you want to reproduce any part of this page. My mailing address is a simple (satisfactory) puzzle for you to solve. Created on 29 September, 2005. Last updated on 29 September, 2005.