Su Doku

 

When I began exploring the subject, I just wanted to systematize Su Duko rules in order to better understand ways to solve Su Doku problems. I ended up with a template (an Excel worksheet) that makes them operational in the limited context of support to solution building. I never intended to create a program that will solve problems by itself; this template only registers the choices made by the user and simply indicates potential choices that are left.

The templates and its various components are described on a separate page and the procedures for using the template in an another, but before anything else, let us establish some premises tout better understand thus tool.

 

The XLS file can be freely downloaded as sudoku_template.zip

 

Rules and implementation

First, a reminder of the basic rules. Su Duko uses integers from 1 to 9 and a square 9*9 grid. Starting will partially filled grid, one must complete it in such a way that each integer is present once and only one time in each row, in each column and in each of the 3*3 groups of 3*3 cells, subsets of the main grid. 

 

Example of a "problem" and

  "performance" for integer 1

The template is based on the concept of "Integer performance table" that is a 9*9 grid initially filled with 1's. There is a similar table for each of the 9 integers. In such tables, 1 means that the cell is open to receive that integer, 0 that the integer cannot be assigned to that position. The change from 1 to 0 is made in several circumstances, one most obvious and not explicitly stated in the rules being that the position is already taken by another integer (initially the cells defined in the "problem"). Other circumstances are the direct translation of the 3 rules: if the integer is present in a cell, all the cells from that row, all from that column and all from the square group are set to 0.

The double illustration above shows how a problem is translated into an "Integer performance table' for integer 1. Five of the 9 square 3*3 groups are filled with 0 as the integer 1 is present 5 times in the problem and each time in a different group (one of the rules); furthermore after the "zeroing" of the 5 different rows and the five different columns in which 1 is present (the other rules) and of the cells containing the other integers given in the problem, there remains only 7 cells into which the integer 1 could be placed (only 4 are required, 5 be present in the problem).

Totals for rows and columns have been added. In this example, totals for row 9 (bottom) and column 6 (from the left) are equal to 1. That means that as the integer 1 must be present in that row and in that column, it MUST BE PLACED IN THAT POSITION (9,6). The same conclusion would have been reached after noting that the total for the square group (3,2) (bottom, center) is of 1; the only place for integer 1 in that group is position (9,6). If that example shows some concordance between the different approaches (row, column and group totals),  it is not by all means a general rule.

When starting to interpret the results from the implementation of the rules, we have slipped from dealing with a simple recording of the situation to some search for solution. A short step further will place us in the midst of problem solving. It is taken by creating another table named "Global performance" in which each cell is the sum of the cells in the same position in all 9 integer performance tables. The numbers making up that global performance table will vary from  0 (the cell is already filled and no other integer can be assigned to it) to 9 (any integer from 1 to 9 can be assigned to that cell; that situation is purely theoretical and may never be encountered in reality). In such as table, 1 means that there is only one integer that could be placed there (it must be identified by inspecting the integer performance tables and finding for which integer the position corresponding contains a 1) and that integer MUST BE PLACED IN THAT POSITION.

The proposed procedures for using the template are based on these simple but constraining findings.