Contemplating and Computing

Observables associated with a square in the grid ...

- location
- size
- background colour
- what digit is in the square
- what colour is the digit in the square
- is the digit in the square fixed in the puzzle?
- what possible digits might plausibly be put in the square?

Many contexts for observation

General observables are not specific to squares, others are only relevant when contemplating solution of the puzzle:

- which square is currently selected?
- what are the common dimensions of all squares?
- what colour conventions are used to highlight the selected square?
- currdigit : "the digit I'm currently thinking of"
- diffcountable : "how eliminating the current digit affects the possibilities for all squares"

How observables are implemented in the model

The observables display gives details of some of the observables within the model. The general nature of the observable being displayed is described in the green panel. If no square on the grid has been selected, the observables displayed will be of a generic nature, not associated with any particular square. When a specific square of the grid has been selected, a range of observables associated with this square can be inspected by clicking on the green panel to move from one observable to the next. The name and definition of each observable is shown in the panel below. In the case of an explicitly defined observable, clicking on the panel will display the current definition of the observable in the Output Window. If the definition is too long for the screen you should first adjust the setting of the observable maxcharindefn, which is initially set to 164, to a smaller value (e.g. 80). Clicking on the definition will then cause it to move to the left until the entire definition has been displayed.

Implementing simple solving rules

The plausible digits for a given square, such as square 45, are recorded in two observables: possdig45 and possdigit45 . When solving a Sudoku puzzle, possdig45 is most useful for empty squares: it records those digits that do not occur in the same region, row or column. If square 45 has a digit in it, this observable records the plausible alternatives to the current digit, which is not useful if the digit is given in the puzzle (unless there is an error in the puzzle!) but might be useful if the digit has been incorrectly entered by the solver. The observable possdigit45 takes account of the contents of square 45, admitting no plausible other than the digit already entered in that square, as is appropriate if this digit is given, or has been correctly entered.

A simple solving strategy

The simplest rules used in Sudoku solution relate to two kinds of observation: that only one digit is possible in a particular square, and that a particular digit can only be placed in one square within a row, column or region. Both kinds of updating action are revealed by considering the way in which eliminating digits from consideration affects the number of plausible digits for the squares in the grid. There are observables within the model that enable this kind of observation:

- the observables possdig45 and possdigit45 are dependent on the set of globally admissible digits (viz. {1,2,3,4,5,6,7,8,9}), which itself is recorded in the observable all . This means that removing a digit from all will eliminate that digit from the plausible values for any square as recorded in observables such as possdig45 and possdigit45 .
- the observable counttable records the number of plausible digits for each square of the grid.

Implementing the simple solving strategy

The simple solving rules can be carried out manually by the user with the help of the model. The effect of eliminating digits from consideration can be achieved by a sequence of EDDI redefinitions (NB - These redefinitions are functional, but trigger a parser error that is an annoyance - a technical workaround is suggested in the Technical Addendum on p11). First we record the true value of all so that it can be easily recovered, then we invoke an action that deletes a given digit (say 4) from all , then we restore all to its original value:

- %eddi
- ## NB remember to remove the invisible space
- ## from "%eddi " when cutting and pasting
- trueall = all;
- all !! [4];
- all = trueall;

Manual implementation of the simple solving rules ...

The application of the solving rules relies upon observing how deleting a specific digit affects the plausible digits for all squares of the grid. One way of doing this surveying task is to introduce the Colour Sudoku environment by pressing the "Add Colour" button, and seeing which cells have their colour changed when a digit is deleted. If a square turns black, that indicates that the digit eliminated must be put in that square. If there is only one square in a given row, column or region that changes colour, then this square must also contain the eliminated digit.

Redefining and observing observable values

The manual process of inspection has been automated in the model by introducing two further observables. To consider the impact of eliminating a particular digit, we can redefine currdigit . The table diffcounttable records whether or not the number of plausible digits for each square of the table has been affected by eliminating the current digit.

%eden

currdigit = 4;

?currdigit;

%eddi

?diffcounttable;

The automated checking process

The checking processes implemented via the button interface in the model (say "Check Rows") is a crude implementation of the manual process of eliminating a digit and examining the rows of the grid in turn to see whether exactly one square has been affected, or whether the only possible digit for a square has been identified. The implementation is crude because it manipulates the observable all many more times than is strictly necessary. The mental overhead involved in switching attention from a situation in which different digits are being eliminated or one in which a digit is no longer being eliminated is small compared with the cost of updating the dependencies on the observable all , which is implicated in the definition of many observables (such as possdig45 and possdigit45 ) all of which have quite complex definitions.

Acknowledgements

The Web EDEN environment in which the model runs was developed by Richard Myers in his prize-winning 3rd year Computing Systems project at Warwick 2007-8. The EDEN interpreter on which it is based also originated from a 3rd year project (by Yun Wai Edward Yung, dating from 1987), and - in its present form - is very largely the work of research and undergraduate students in Computer Science at Warwick. For more context for the Sudoku model and Empirical Modelling, see http://www.dcs.warwick.ac.uk/~wmb/sudokuExperience/workshops/ .

Technical addendum (Based on feedback from Antony Harfield, 23/11/08)

Without introducing a minor fix at this point, there is some problem with the EDDI parser, which registers an error in updating the CATALOGUE, but this doesn't affect the functionality of the redefinitions of the table all . A suitable workaround is to modify the EDDI parser by making the EDEN redefinition below. This fix is not ideal, as it eliminates the possibility of redefining a view as a table, but it suits the present purpose.

%eden

eddi_statement_6 =

[ "pivot", "=",

[ "table_name", "rel_exp" ],

[ "action",

[ "later", "if ($p2!=@) { execute("$s1 = "//$p2//";"); if (search_CAT($p1)==0) _CATALOGUE = addvals(_CATALOGUE, [$p1, "table", "", &$s1]); } else writeln("Invalid assignment");" ],

[ "now", "curr_agent=6;" ] ],

[ "fail", "eddi_statement_7" ] ];