Wednesday, October 22, 2014

Solving Strategies for Sudokus

After I explained in the previous posts the basics about the posting series Solving / Generating of Sudokus I want to present in this post, as announced, the implemented solving strategies. These are taken from the sources mentioned in the previous post and labeled with a difficulty, so when generating a Sudoku we can check, how difficult it is. As already mentioned I cannot estimate the difficulty very well based on my experience. I would be very happy about feedback, whether the categorization is about right, and even more about new strategies the program definitely has to know.
The so far implemented rules to solve Sudokus are (the names are a mix from the names in Creating and the German Wikipedia Page - there also more detailed explanation -, but these techniques are common knowledge, their difficulty is increasing):

  • Stufe 1: 
    • Naked Single
    • Hidden Single
  • Stufe 2:
    • Naked Pair
    • Hidden Pair
    • Candidate Line
  • Stufe 3:
    • Naked Triple
    • Hidden Trippe
    • XWing
    • (in theory the method of the naked / hidden X is implemented for abitrary X, but is only conducted until X = 3)
  • Stufe 4:
    • Guessing
Now the explanation, what these rules are.
But first some basic notations: The single caskets of a Sudoku are called fields. I call entering a number as a solution in a field "to fill out the field". It helps to remember all possible numbers which still can, based on the current solution, fill out a field. These are the candidates of a field. Row and column should be clear, box is the casket consisting of 9 fields the field belongs to. Group means all fields in the row, column and box of a field.

Naked Single: If for one field only one candidate remains, it can be filled with this.

Hidden Single: If a candidate occurs in one row, column or box only one time, that field can be filled with it. (These first two techniques most will probably use intuitively, and many will probably have limited themselves to those so far - including me.)

Naked Pair: If in 2 different fields of a row, column or box only the 2 same candidates are possible, we do not know which candidate belongs to which field, but we know that the 2 candidates definitely have to fill these both fields. So we can delete the two candidates from all other fields of the row, column or box.

Hidden Pair: If 2 different candidates appear exactly in 2 fields of a row, column or box, we do not know which candidate belongs in which field, but that these candidates definitely belong in these fields. So we can delete all other candidates from these fields.

Candidate Line: If all candidates for a number in a box lie on one line, we can deduce from that, that these number also has to be filled somewhere on this line, and delete it from the candidate list of all fields on this line in the two other boxes.

Naked / Hidden Triple: The same for the Naked / Hidden Double, but with 3 fields.

XWing: For this I again refer to the literature for a visualization and explain the procedure here without a graphic. If there are 2 rows (columns), in which the 2 same candidates appear in exactly 2 fields which lie also in same columns, then we know, that these numbers have to appear in one of the 4 fields. Thus we can delete this numbers from the candidate lists of all fields in the 2 columns (rows) of the fields.

Guessing: Here we look for a solution by trying out, that means we run over all not yet filled fields and fill in a possible number. Then we move to the next field and check if still a solution is possible, if not, one has to go back one (or multiple) fields. (This description is very close to the implementation, surely there are many other possibilites to test all possible allocations of numbers.)

No comments:

Post a Comment