2 Some open questions

Definitions of the words used to state these questions are postponed to Section 3.

2.1 Mathematical questions

1. Determine the number of (complete) square grids having a given dimension .

   The very existence of at least one grid for each dimension is an interesting subproblem. An experimental positive answer is easy to obtain for small integers.

2. Given a grid, examine what can be said about all the associated minimal taboo-solvable games ? Have they all the same size ? What is their number ?
3. Does all grids of a given dimension behave in the same way relative to the previous question ? What is the size of the shortest taboo-solvable game ?
4. Change taboo into totem in questions 2 and 3.
5. What can be said upon tower-solvable problems that are non totem-solvable ?
6. Are there other classes of deterministic rules ?
7. When proceeding by trials and errors (pick-moves), several policies can be used for chosing the cell where the attempt will be made. For example, we can pick at random any empty cell, or prefer the cells with the least number of possibilities, etc. What is the most efficient policy ?
8. Given a pick-solvable game, and all his pick-solutions. Remember that solving is proving the uniqueness and examine if all solutions contain the same number of pick moves.
9. Change taboo into pick in questions 2 and 3.
10. Are there minimal totem-solvable games that are also minimal pick-solvable games ?

2.2 Complexity questions

1. Implemente the tower algorithm.
2. Compute the complexity of the taboo, totem and pick algorithms as implemented.
   1. complexity can be expressed in terms of elementary operations over mathematical integers... or in terms of elementary operations over machine words !!!
   2. when computing average complexity, the uniform measure over all the minimal problems can be a good choice
3. Describe better implementations for all these algorithms.
   1. Another data structures can be useful.
   2. In the given listing, the pick stack is implemented as worse as possible (in terms of complexity).
   3. When a letter is written into a cell, the taboo set of all the neighbor cells can be immediately updated. Examine if this lead to a better complexity.
4. Describe an efficient algorithm to generate from scratch a new complete grid. Determine its complexity and compare with obtaining a path by a succession of pick moves (as described in  7).
5. Describe an efficient algorithm to obtain a minimal game of a given kind from a given grid. Determine its complexity and compare with using a succession of erase and try (as described in  8).