Oui mais une grille est un graphe biparti bien particulier. Sait-on jamais ?

En effet il y a un problème

Il me semble qu'on peut le corriger de la façon suivante .

On considère une position P avec une seule case gagnante pour le joueur 1 que l'on pave avec un maximum de dominos . Alors toute case hors dominos est gagnante . En effet à chaque étape le joueur 2 va devoir entamer un domino que le joueur 1 va compléter . Le joueur 2 ne peut pas sortir du circuit de dominos . Supposons qu'il le fasse sans laisser de cases hors dominos pour que le joueur 1 continue son chemin alors en décalant les dominos sur le circuit parcouru on crée un nouveau domino sans en supprimer : impossible . Si au contraire il sort du circuit en laissant une case libre hors domino pour le joueur 1 , on pose un domino sur les deux dernières cases : toujours impossible .

Après c'est facile s'il n'y a qu'une case hors dominos on décale un domino voisin vers cette case et on crée une nouvelle case gagnante .

Je crois que je vais retourner aux gâteaux

Je plaisante , merci Titou

Vasimolo

En fait je ne cherchais pas à être bref mais plutôt explicatif car le problème est plus complexe qu'il en a l'air

Vasimolo

En voici un



Peut-on faire plus simple ?

Vasimolo

Pas là  (quoique j'en compte 24 sur l'exemple de vasimolo)

Oui et 26 pour Gwen donc la question reste ouverte : peut-on faire avec moins de 24 cases ?

Vasimolo

Je ne vois vraiment aucun moyen simple de caractériser les terrains non pavables . D'ailleurs l'idée de Gwen n'est pas la même que la mienne .

Pour la figure de Gwen le remplissage de la ligne du bas crée un blocage dans les  rectangles du haut . Mon idée était de "coller" deux morceaux présentant des déficits dans les couleurs opposées .

Ce qui est sûr c'est que s'il existe une caractérisation elle ne peut pas être uniquement locale .

Vasimolo

N'oublions pas qu'une CN est d'avoir autant de cases noires que de cases blanches.

J'avais idée, pour caractériser les assemblages pavables, de compter les nombres de cases pour chaque ligne et chaque colonne. Si toutes les colonnes et toutes les lignes ont un nombre pair de cases: pavable.
Les impairs marchent par 2 (car il y a un nombre pair de cases): Si impair sur ligne L et  impair suivant sur ligne L+S, alors il faut au moins S dominos horizontaux chevauchants dans l'intervalle (L;L+S).
Idem pour les colonnes.
Ce comptage est donc un outil d'aide à l'analyse du pavable ou pas, je n'arrive pas à aller plus loin.

Bon voici les quelques résultats qu'il m'a donnés, qui malheureusement ne sont pas des critères généraux, mais qui permettent tout de même de trancher quelques cas :

-Si le terrain (avec ou sans trous) n'a que des côtés longueur paire, alors il est pavable.

-Si le terrain (sans trous) n'a que des côtés de longueur impaire, alors il n'est pas pavable.

Le critère n'est intéressant que s'il est facilement applicable.

Si je dis qu'un terrain est pavable si et seulement si c'est une réunion de rectangles de surface paire, ça nous fait une belle jambe !

Oui la méthode est intéressante pour montrer qu'un terrain n'est pas pavable.

Voici un article qui parle de dominos si ça vous intéresse : http://dev.ulb.ac.be/urem/IMG/pdf/domin … ominos.pdf