A Greedy Algorithm
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.
- Start with a blank grid and put in a symbol anywhere: for example write 1 in the upper left corner. Enumerate all eliminated possibilities.
- 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.
- 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.
- 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.