Saturday, 25 May 2019

Sudoku:A Game of Control and Error Management

The game of Sudoku and the methodologies for its solution have been  analysed by widely academics and other experts (for example The New Sudoku Players' Forum). The purpose of this article is to consider how we can demonstrate the relationship between the elements of the Sudoku once a particular Identity has gained control of an individual cell.

The modelling environment for this discussion is an Excel spreadsheet. An incidental consideration is the notion that spreadsheets have a wider modelling capacity than number crunching or simple database management.

Introduction - Names and Lists

The puzzled is built in a 9 x 9 grid of cells, but, from the perspective of a spreadsheet analyst, this is a very difficult structure to handle. We like simple lists. Also all Sudoku experts use a row/column nomenclature to describe their methodologies and solutions.

Conventional cell names for a Sudoku puzzle.

Our list is in the form of single column starting with the names of all the cells in row one and proceeding through each row. This gives a complete list of each of the 81 named cell.

Next we create a table, associated with the list of named controlling cells, of all the cells related to the controlling cells.

The cells which are logically associated with each 'master' cell. 
For example, if cell Id 42 contains the result 2 then it follows, by the rules of Sudoku, that a list of 20 further cells may NOT contain the result 2. These are:

  • In row 4 - cells 41, 43, 44, 45, 46, 47, 48 and 49
  • In column 2 - cells 12, 22, 32, 52, 62, 72. 82 and 92
  • and in the 4th sub-grid - cells 41, 51, 43 and 53

This analysis is repeated for each of the controlling cells within the list of 81 named list. The final table comprises 81 rows and 20 columns (excluding the name column).

Now we know the relationships between controlling cells and others in the Sudoku table, but the analysis depends both on whether the controlling cell contains a result AND the Sudoku identity of the result. In effect each Sudoku identity must be analyzed and computed separately.

The Analytical Process

The process for evaluating whether an individual Sudoku Id is still available as a possible solution to a cell is long winded. Each cell containing a result has been evaluated for its impact on its related cells (see above). The evaluation is now reversed. Each cell that is not a result cell is evaluated for whether a result cell eliminates the availability of that specific Sudoku Id. Inevitably, each Sudoku Id must be evaluated separately. See the table below. Where the summary table (the right hand column) is greater than zero, Sudoku identity 3 is not available to that cell.

In practice we start with a table of results that looks like this one immediately below. The row at the top refers to the individual Sudoku identities.

And end with a table of deletions that looks like this.

This is then combined with the original Sudoku puzzle to look like this,

This columnar presentation then has to be converted back to the standard looking Sudoku puzzle and will look as shown below.

My personal convention is to show result cells with a green background, the values of the original puzzle in red script, those that are user calculated in black script and the unsolved cells with a white background.

No comments:

Post a comment