This paper deal with the sudoku game. In this game, a given square
grid is to be completed in such a way that each of the letters of
a given set appears once and only once in each row, column and submatrice
of the grid. A quite obvious example of this game is given in FIG. 1,
where the letters are 
.
A solution to such a game is a list of moves, each of them being a
proof that a designed cell must contain a designed letter. Therefore,
solving is proving the existence and the uniqueness of a completion.
A possible solution of our example is given in FIG. 2,
where 
is the move number, 
is the row,
column position of the cell and 
is the letter attributed. The
in the why column are comming from 4 and
the 
from 5.
The key part of this paper is Section 2 that states a list of open questions. This list is divided in two parts. Subsection 2.1 contains question relative to existence and counting, while Subsection 2.2 contains questions relative to complexity of effective algorithms that can be used for obtaining answers to sudoku challenges... as well as for building these challenges.
Section 3 gives a precise definition of all terms used for stating these open questions : Subsection 3.1 gives some elementary definitions, Subsection 3.2 describe three deterministic algorithms (taboo, totem and tower) while 3.3 describes a probabilistic algorithm (pick). Let us remember that we have defined ''solving'' as ''proving the existence and the uniqueness of a complete grid that solves a given game''.
The paper ends with Section 4 that gives a precise implementation of our algorithms. These programs were written using Maple V6, and are presented using a revised version of algorithmic, the well-known latex package. Obviously, a sound discussion over complexity must take into account primitives like member(elem, set) that are not realy primitive in terms of machine words.
.
