Allen Computing and Business Analysis Home Contact - Email Contact - Address & Telephone What's New

Page Content

• [Audit Trails]
• [Nomenclature]
• [Analysis Frame]
• [Row by Row Evaluation]
• [Presenting Results]
• [Evaluating Alternative Results]
• [Groups of 3 Analysis]
• [Worked Example]

Related Pages

• [Home]
• [Spreadsheet Design and Development]
• [Oddments]

Auditing Su Doku Puzzles

This is an approach for creating auditable solutions to Su Doku puzzles within an Excel workbook. It can prove that your solution is one that meets all the criteria for solving Su Doku puzzles or, in some cases, that the original grid does not resolve to a unique solution.

The approach creates an audit trail of every decision a puzzle solver makes when deciding the solution to each individual cell within the total 81 cell grid. There is no VBA code used in creating the audit trail and solutions. Two worked examples of the process are available for downloading from the link Auditing Su Doku.xls.

If you want to try the process of creating an audit trail yourself, you will need the templates and the ACBA Electronic Working Papers software.

The Mechanics of Creating an Audit Trail

The ACBA audit process requires that the user completes a series of templates (worksheets) that deliver

• a record of the puzzle and the solutions created so far, while showing clearly those cells that were pre-set in the original grid
• the solutions that are still available for the unsolved cells in each row of the puzzle grid
• a record of the decisions made for cells within a specified row of the puzzle
• a record of the solutions generated

For each template, the user must

• identify the worksheet (template) with the original puzzle,
• identify the worksheet (template) that has the latest analysis,
• select a row to examine,
• complete an analysis of the available solutions for each cell (column) within that row, and
• create a revised version of the grid recording the solutions (if any) you have just generated.

In principle the user user will look again and again at each row and the cells within the row until all the cells are solved.

Aids to Identifying Solutions

The object of a (standard) Su Doku puzzle is to create an 81 cell grid of 9 rows and 9 columns, and comprising 9 sub-grids (of 3 x 3 cells), such that each row and each column of the main grid contains the numbers 1 to 9 as well as each of the sub-grids. Therefore the logical approach to solving a puzzle is to prove for each cell there there is only one possible solution by identifying the cells within the row, column or sub-grid containing all the other numbers in the 1 - 9 series.

Nomenclature

ACBA has given each cell in the main grid a unique name based on

The templates all have a nomenclature Grid the users can refer to

An Analysis Frame

When analysing the possible solutions to an individual cell the user is presented with an analysis frame. This frame already has the solutions taken up by other cells in the row excluded from it. Note in the diagram below that the possible solutions 1, 2, 6 and 9 are not indicated as available.

In the above case, solutions 3, 4, 5, 7 and 8 are available and it is the role of the puzzle solver to eliminate all the solutions that can be excluded by reference to other members of the relevant column or grid.

Row by Row Analysis

In the example above the user might enter the following rationale for excluding available numbers that have already been used to solve cells elsewhere in the grid or column associated with cell '1_12'. This is the cell in column 1 of row 2 in the main grid.

Note that for solutions 3 and 4 there are two reasons to exclude them but only one is needed for the grid to evaluate a final result. The user examines each column in turn for the whole row. There is hyperlink to take the user to the next analysis frame (for the next cell/column in the row) rather than having to use the scroll bars to look for it. The final result of the analysis for Row 2 might look like this.

Presenting the Results of your Decisions

Before going on to examine the next row you are invited to re-evaluate the decisions you have taken on the current row. In this approach you are presented with

• cells that were pre-set in the original puzzle in red
• cells that you have solved unambiguously in the current round in green
• cells that you have identified as being restricted to one of two possible solutions in blue

The user analyses a whole row at a time and does not calculate a result until all the columns in the row have been examined. Typically, this will sometimes lead to results that look wrong. For example cell '3_72' above suggests that the solution could be either 4 or 8 but right next to it in cell '3_82' the cell has an unambiguous solution of 4. When the user next reviews this row - and he or she would probably review it again immediately since they are very close to achieving a full solution to the row - the ambiguity for '3_72' would resolve to a single solution of 8.

Iterations of this kind maintain the integrity of the audit trail and are essential to the primary purpose of the process.

Analysing '1 of 2' results

There is one specific occasion when you can use the '1 of 2' cases to solve a cell unambiguously. If you have two cells with a row, column or sub-grid where the '1 of 2' values are identical than the puzzle solver may assume that both alternative values belong to those cells even though he does not know which of the alternatives goes in which particular cell. See below.

This grid has several cells where the possible results have been limited to 2 option. Also in many cases there are two cells with in a row, column or sub-grid with identical values (e.g. column 1 and row 8 above). The automated '1 of 2' analysis will only generate a usable result in the circumstances shown in column 9.

In this context we know that cells '3_91' and '3_92' must have either a 2 or a 5, but further down the column the analysis suggests that cell '6_96' could have the values of 2 or 9. But since we know that values 2 and 5 have already been taken then the result of cell '6_96' must be 9.

This is analysed by an 'alternatives analysis' template.

In this template the process

• identifies those cells that are presenting alternative results
• identifies any matching values
• extracts the alternative values that are excluded
• searches for any other strings that uses one of the excluded values and
• delivers the other one as the final result

The alternatives analysis will only generate a result in these specific circumstances.

Reviewing a Group of Three Rows or Columns for a Specified Number

The final analytical approach in the audit process explores the presence of individual numbers in groups of rows or columns.

The logic is that for any group of three rows or columns, which also cover the whole of three sub-grids, any individual number must occur three times - once in each sub-grid member and once in each of the three rows (or columns). If two of the occurences of the number under examination are already present, we can reduce the the options for locating the third occurrence to three specific cells within the sub-grid that has the number missing.

Moreover, we can examine these three cells for the presence of a previous solution or prove that the location is not available by reference to an occurence of the number in the opposite dimension.

The diagram below shows how this works.