4 Effective implementation

4.1 Data structure

We have chosen the following implementation. It works. Nothing more, but nothing less...

1. The grid is implemented as a matrix named . An implementation as a vector (with auxiliary tables describing once forever the groups) could be a better choice. Additionnaly, when using Maple, a choice must be done between the new NAG LinearAlgebra:Matrix and the linalg:matrix. Here, is a NAG Matrix.
2. In order to accelerate the determination of the neighbors of a cell, all neighborhoods are computed once for ever and stored in an auxiliary matrix named . The element is a set whose elements are written as where is unassigned. Therefore subs(mA=ma, rel[j,k]) gives the set of the values of the neighbor cells of cell at a given time. This is done in  1.

   
   
   

3. We assume that 0 is not a letter. An easy way to enter by hand a given game is to key everything in a single line, separating the values by a comma and using 0 to code the empty cells. Nothing else : no brackets or any other annoying things.
4. A cosmetic feature is to allow any set of letters. The users's alphabet is stored in the list letters0, and by default letters0:= is used. On the other hand, a shorter formulation of algorithm totem ( 5) can be obtained by assuming that indices are not letters. Therefore, the letters are internally coded as letters:= and are transcribed during input/output operations.
5. The internal data storage is as follows. At any time, is a set. When it has been proven that cell contains the letter , then . Otherwise, the set contains the tag 0 and all the letters that are not yet proven wrong for the cell . Initialising from the description of a game is done in  2.

   
   
   

6. Obviously, an human readable rendering must be provided. In  3, block matrices are used to render the groups and sets are used only where they are useful. When the value is known, it is printed without braces and when nothing is known a blank is printed.

4.2 The taboo algorithm

 4 gives our implementation of the taboo algorithm described in Subsection 3.2. All the cells of the grid are examined in succession, from the top-left corner to the bottom-right one. When the focus is on cell , the matrix element contains all the letters that were not proven wrong during the last pass. If this set contains only one value, nothing remains to do with that cell. Otherwise, the neighbor cells are checked and all the yet affected letters are deleted from the possible values of cell . When taboo is called from the pick algorithm, the set of possible values can become empty. In such a case, a taboo error is returned.

If this set becomes a singleton, a taboo move can be done and a message is issued using the procedure given in parameter. In interactive mode print is a good choice. When nothing is given, the message is discarded.

After a taboo move, the matrix does not reflect all the available knowledge since the letter affected to can no longer be attributed to any neighbor of this cell. We have chosen to face this problem in a lazy way : a flag is set down before dealing with the top-left corner and set up at each taboo move. If this flag is set when leaving the bottom-right corner, all the process is done again. This ensures the correctness of the algorithm ... if not the smallest execution time.

4.3 The totem algorithm

 5 gives our implementation of the totem algorithm described in Subsection 3.2. The algorithm begins by a call to algorithm taboo in order to shorten the possibilities relative to each cell. Thereafter, the groups are considered each after the other and, for each letter, the possibility of a totem move is examined.

When such a move occurs, the matrix should be updated, and it could happen that new taboo/totem moves become available. But, here again, we have chosen a lazy way to face this problem. After a totem move, a flag is set up to keep track of the fact, but this flag is taken into account only when all the groups have been checked.

If the flag is up, a new cycle (taboo and then checking all the groups for a totem move) is undertaken.,

4.4 The pick algorithm

To facilitate the discussion, we have separated our implementation of the pick algorithm in two parts. The  6 describe how the pivot is chosen, i.e. how is obtained the empty cell where the attempts will be made. The chosen policy is as follow : determine the least value (say ) of the number of remaining possibilities over the non yet known cells. And then chose a random a cell having either or possibilities left.

At first sight, chosing the minimal value seems better, but it appears that allowing also introduces more variability and is more efficient.

When the pivot is chosen,

4.5 Build a minimal game