Bonjour à tous, je viens de finir ma MPSI et suis à la recherche d'un TIPE. Il y a peu de temps j'ai pris connaissance du jeu "Takuzu" qui m'a semblé mathématiquement intéressant. Des connaisseurs pourraient-ils m'aider ?
Je rappelle les règles du jeu, qui sont très simple (c'est pour ça que le jeu est intéressant): On a une grille n*n avec un certain nombre de 0 et de 1, on va appeler ça le positionnement initial. Il faut remplir la grille de 0 et de 1 en respectant :
R1: autant de 1 et de 0 sur chaque ligne et sur chaque colonne (ce qui peut se reformuler en termes de somme);
R2: pas plus de 2 chiffres identiques côte à côte ;
R3:2 lignes ou 2 colonnes ne peuvent être identiques.
J'ai déjà réfléchi à plusieurs questions qui pourraient constituer un embryon de TIPE, mais qui restent sans réponses:
- pour quel positionnement initial de 0 et de 1 y a-t-il une solution ? Y a-t-il une solution pour n'importe quel positionnement initial ?
- y a-t-il unicité de la solution lorsqu'elle existe ? Si non, sur une grille n*n, quel est le nombre minimal de 0 et de 1 positionnés initialement pour obtenir une solution unique ?
- étant donnée une grille vierge, combien y a-t-il de solutions possibles ? (Question ardue je pense)
- existe-t-il un algorithme pour résoudre un Takuzu n*n ?
Il y a d'autres questions comme le lien que l'on pourrait faire avec les matrices ou la complexité de l'algorithme s'il existe.
Je n'attends pas forcément de réponse, loin de là ! Je voudrais seulement savoir si ces questions sont pertinentes, et abordable à mon niveau de fin de sup (plutôt à l'aise en maths). Enfin, je voudrais savoir si des gens (mathématiciens, informaticiens) se sont déjà penchés sur ces questions, car un TIPE doit être sourcé et muni d'une bibliographie.
Merci à tous, j'attends vos réponses avec impatience.
-----
Envoyé par branstenjamin 
) et ça ne devrait pas te faire peur. 
