3 Definitions

3.1 Elementary definitions

• [m, n]two positive integer.
• [dimension]. This is the common cardinal of letters, rows, columns and blocks. Everywhere ''given '' must be understood as ''given and a non-trivial factorisation ''.
• [letters](aka alphabet) the set or any other set of cardinal .
• [empty grid]a matrix, sometimes divided into blocks themselves being matrices.
• [row] : one of the rows of the grid.
• [column] : one of the columns of the grid.
• [block] : one of the blocks of the grid.
• [group]a row or a column or a block. Any group contains cells.
• [neighborhood]of a given cell : all the other cells that belong to the same row, or the same column or the same block as the given cell. Any cell has neighbors.
• [grid](aka a complete grid) a matrix such that any of it's groups is a permutation of the alphabet (i.e. any group contains exactly one letter of each kind).
• [erasing]substituting the value of a cell by the "blank letter", i.e. by anything that doesn't belong to the chosen alphabet.
• [problem](aka a general problem) is obtained from a (complete) grid by a sequence of erasing. The (complete) grid is said to be a completion of the problem.

3.2 Three deterministic algorithms

• [game](aka: a fair game, or a solvable problem) is a problem that has one and only one completion.
• [solution]a sequence of moves that proves the existence of one and only one completion for a given problem (i.e. proving that this problem is in fact a fair game).
• [size](of a problem) the number of published cells, the number of erased cells being .
• [taboo letter](relative to a given empty cell) : a letter that is yet affected to one or another neighbor of this cell.
• [taboo move]affecting a letter to a cell when all other letters are taboo for this cell.
• [taboo-solvable]a game that can be solved by successive taboo moves (remind that solving is proving the uniqueness).
• [totem_move]affecting a letter to a cell when this letter is taboo for all the cells of a group except from the given cell
• [totem-solvable]a game that can be solved by a mix of taboo and totem moves.
• [tower-move]when two letters are the only non-taboo letters for two given cells of a given group, these letters are not allowed for the other cells of the group.
• [tower-solvable]a game that can be solved by a mix of taboo/totem and tower moves.
• [minimal]a game of a given kind that cannot be shortened, i.e. such that erasing any cell leads to what is no more a game of the given kind.

3.3 A probabilistic algorithm

• [attempt]Suppose that, for a given problem, no taboo nor totem moves are available. Chose both an empty cell (the pivot) and a non taboo letter for that cell (the attempt), and see what happen when affecting this letter to that cell.
• [taboo/totem error]After a first attempt, let us apply all the possible taboo/totem moves. At some point of the process, it can happen that all letters become taboo for a given empty cell (taboo error) or that a given letter becomes taboo for all the cells of a group (totem error).
• [proven_wrong]The occurrence of a taboo/totem error is not a "bad thing". Being proven wrong, the attempt cannot be the right value of the pivot and another letter has to be attempted (among the remaining non taboo and non yet proven wrong).
• [dead-end]When a first attempt and its induced taboo/totem moves don't lead to a complete grid, the pick process can be iterated until completion. By the way, it can happen that, for a given pivot, all non-taboo letters become successively proven wrong (dead-end error).
• [backward move]is what to do after the occurrence of a dead-end error. In such a case, the attempt done for the previous pivot cannot be the right value and something else must be attempted at this previous level.
• [stack]In order to allow such backward moves, a LIFO stack must be used in order to record each attempt as well as the current status of the game just before the processing of the attempt.
• [path]is a successful mix of pick and totem/taboo moves, leading to a complete grid. This word is used in order to emphasize that such a mix doesn't give, by itself, a proof of the uniqueness of the completion obtained.
• [pick-solvable]a game that can be solved by providing a path and additionally proving that, for each pick move, all the other available attempts were wrong.