Quadrilles

Placer les 28 dominos sur une grille compacte de sorte que chaque bloc de 4 cases soit formé de cases de même valeur.

Intéressons nous tout d'abord à la position des dominos, sans tenir compte des points.
Bien évidemment un quadrille ne peut pas être formé de deux dominos seulement, qui seraient alors deux doubles identiques !
Il peut être formé à partir de 3 ou 4 dominos de 7 façons différentes.

On notera que lorsque deux dominos "dépassent" du même côté, ils appartiennent forcément à deux quadrilles différents.
Ceci impose l'orientation des dispositions B,D,E,F, les quadrilles voisins ne pouvant pas être en ligne avec celui considéré (bleu).

On remarque alors que les "coins" de la grille ne peuvent être réalisés que par la disposition C. Ceci impose les 4 doubles dans les coins, dont on peut sans perte de généralité imposer la valeur 0-0, 1-1, 2-2 et 3-3.
Il reste 3 doubles à répartir dans la grille. Les dispositions A,B,C à 3 dominos imposent un double dans le quadrille.

Il y a au plus 3 quadrilles en dehors des coins avec la disposition A,B ou C

En dehors de ces doubles dans un quadrille, l'autre façon de les obtenir est que deux quadrilles "voisins" aient la même valeur.

Pour simplifier la recherche exhaustive des solutions, la grille peut être représentée par un graphe, chaque sommet représentant un quadrille et les arcs les dominos.
La disposition des quadrilles donne les arcs possibles en vert. Les arcs noirs étant imposés par la remarque ci-dessus.
Le problème devient alors choisir 28 arcs de sorte que chaque sommet voie 4 extrémités d'arcs.

La supression de toutes les boucles (aucune disposition A,B,C en dehors des coins) conduit à une position réduite où les sommets d et g ont 5 arcs, la seule solution est alors de supprimer l'arc d-g.
Les seuls sommets de même valeurs ne peuvent être que c = f et e = h.
Par exemple si a = b, on aurait deux dominos d-a = d-b
Il manque donc un double et cette disposition est impossible.

Il y a au moins un quadrille en dehors des coins avec la disposition A,B ou C
C'est à dire une boucle sur le graphe

Ceci permet de séparer la recherche en 3 classes selon l'emplacement de ce double (de cette boucle sur le graphe)
Par symétrie, on peut se limiter aux cas où a, c ou d est ce double.

a est un double

Il reste en a un et un seul arc parmi a-c, a-b, a-d

arc ac
alors pour avoir 4 extrémités d'arc en b, on doit choisir la boucle en b, et donc un seul de b-d ou b-e
Il ne reste au plus qu'une boucle possible. Si c est une boucle, ceci supprime l'arc cd et donc d est aussi une boucle.
Donc c n'est pas une boucle et on doit prendre les arcs c-d et c-f
Si d n'est pas une boucle, alors les arcs c-d, b-d, d-e et d-g sont obligatoires.
L'arc b-e est donc absent (car b est complet) et donc e est une boucle
Il n'y a alors plus d'autre boucle. ... mais alors il faut supprimer l'un des arcs g-f, g-h, g-i ou g-j, ce qui impose une quatrième boucle en g,h,i ou j !
Finalement, il y a donc forcément une boucle en d et il n'y en a pas d'autres
Ceci conduit à la suppression de l'arc d-g (à cause du nombre d'arcs en g) et à la solution unique
arc ab
Alors (a-c absent) c est un double. Si b est aussi un double (le dernier), cela supprime l'arc b-d et d est un 4ème double.
Donc b n'est pas un double, et les arcs b-d et b-e sont obligatoires
le dernier arc en c est soit c-d soit c-f,
- Si c'est c-d, alors f est le dernier double et une deuxième solution (topologiquement)
- Si c'est c-f, alors d est le dernier double et une autre solution
arc ad
Alors b et c sont obligatoirement des doubles, et il n'y en a pas d'autres.
Ceci impose les arcs aux sommets e, f, h, i, j, et pas assez d'arcs en d
Donc pas de solution pour ce cas.

c est un double

Sans que a soit un double car déja traité au cas précédent
Cela impose les arcs a-b, a-c, a-d et supprime les arcs c-d et c-f, f est donc forcément un double. L'arc restant en f ne peut être f-g car i serait un double et déja traité en a, c'est donc f-i
Le choix d'un 3ème double entraînerait d'autres doubles, par suppression d'arcs.
Il n'y a alors aucune autre boucle dans le graphe et le dernier double est obtenu par deux sommets de même valeur. La seule possibilité est alors d = g ou e = h et les deux solutions.

d est un double

Sans que ni a ni c (ni b, e, h, i, j par symétrie) ne soit un double, car déja traité aux cas précédents.
Ceci impose les arcs issus de a, c, b, e, h, i, j et l'impossibilité car trop d'arcs convergent en d.

Reste maintenant à déterminer toutes les façons d'affecter les points sur ces dominos.

Etudions tout d'abord la dernière configuration trouvée.
On peut sans perte de généralité affecter arbitrairement les doubles c=4, e=5 et f=6
Parmi les non-doubles a,b,d,g,i,j, il y a un de chaque parmi 0,1,2,3 (chaque valeur de quadrille apparaît exactement deux fois)
Examinons les emplacements possibles pour le 3.
Il ne peut pas être en j car il y aurait deux 3-3
Il ne peut pas être en b, d, g car il y aurait deux 3-e
Il ne peut pas être en i car il y aurait deux 3-j
a=3 et de même i=1
L'autre 6 ne peut être ni en b, g ou j car il y aurait deux 6-1,donc d=6 et de même g=4
Mais alors il n'y a pas de 0-2 (serait b-j) ! Cette configuration est donc impossible.
Un examen, détaillé plus loin, des autres configurations donne par contre des solutions et

Il y a, à symétrie près, seulement 4 manières de placer les dominos, sans tenir compte des points

(Les doubles sont en vert)

Equivallences

Deux solutions seront identiques si elles sont la même solution vue sous un autre angle (pivotée de 180°)
Deux solutions seront équivallentes si elles se déduisent l'une de l'autre par symétrie et/ou permutation des valeurs 0..6.
Nous avons déja utilisé la symétrie pour la recherche ci-dessus des positions des dominos vidés de leurs points.
La permutation des valeurs a permis d'affecter arbitrairement les doubles.
Pour définir de façon unique un représentant de chaque classe d'équivallence, définissons un ordre lexicographique sur les solutions.

Les doubles sont d'abord choisis aux quatre coins 0-0, 1-1, 2-2, 3-3 comme ci-dessus
les valeurs de a,b,c,d,e,f,g,h,i,j libres sont alors affectées dans cet ordre aux points suivants 4,5,6, en commançant par les doubles.
Nota : Pour chaque disposition topologique, la seule donnée des valeurs des quadrilles définit de façon unique la valeur des points sur chaque domino.
On peut donc raisonner sur le seul graphe, ou même représenter une solution par ses seuls sommets :

   0 a b 1
    c d e
    f g h
   2 i j 3

Disposition D

Etudions complètement, à titre d'exemple, la disposition D. Par ordre lexicographique c=4, d=5, f=6.
Alors 1 ne peut être ni a (car il y aurait deux 1-b) ni b, ni e, ni h donc 1 est i ou j
On a aussi pour les mêmes raisons 3 = a ou b
b=3 et j=1 est bien entendu impossible (car deux 1-3), il reste 3 cas à examiner :

a=3 i=1 : le choix de b est impossible

0---3---b---1
 \ / \ / \ /          
  4   5---e
      |   |
  6   5---h
 / \ / \ / \
2---1---j---3

a=3 j=1 : alors {b,h} = {2,6}, {e,i} = {0,4} et 4 solutions

0---3---b---1
 \ / \ / \ /           0 3 2 1      0 3 2 1      0 3 6 1      0 3 6 1
  4   5---e             4 5 0        4 5 4        4 5 0        4 5 4
      |   |             6 5 6        6 5 6        6 5 2        6 5 2
  6   5---h            2 4 1 3      2 0 1 3      2 4 1 3      2 0 1 3
 / \ / \ / \             [1a]         [1b]         [1c]         [1d]
2---i---1---3

b=3 i=1 : {a,h} = {2,6} et {e,j} = {0,4} et 4 solutions

0---a---3---1
 \ / \ / \ /           0 2 3 1     0 2 3 1       0 6 3 1     0 6 3 1
  4   5---e             4 5 0       4 5 4         4 5 0       4 5 4
      |   |             6 5 6       6 5 6         6 5 2       6 5 2
  6   5---h            2 1 4 3     2 1 0 3       2 1 4 3     2 1 0 3
 / \ / \ / \             [2a]        [2b]          [2c]        [2d]
2---1---j---3

Mais ... ces 8 solutions sont équivallentes deux à deux, par symétrie selon l'axe horizontal.
Par exemple le retournement H/B de la solution [1a] donne

La permutation (02)(13)(46)(5) pour normaliser dans l'ordre lexicographique donne

qui est la solution [2d]
On a les équivallences [1a]=[2d], [1b]=[2b], [1c]=[2c] et [1d]=[2d]
Il reste ainsi 4 solutions seulement :

0 2 3 1        0 2 3 1      0 3 5 1     0 3 6 1
 4 5 0          4 5 4        4 5 0       4 5 0 
 6 5 6          6 5 6        6 5 6       6 5 2 
2 1 4 3        2 1 0 3      2 4 1 3     2 4 1 3

Disposition A

Les doubles restants sont alors a=4, b=5 (ordre lexicographique) et reste d=6
Il faut ensuite affecter {c,e,f,g,h,i,j} à {0,1,2,3,4,5,6}, sans doublons. Sans entrer dans les détails, on trouve de même 16 solutions deux à deux équivallentes par symétrie G/D, soit 8 solutions.

   0 4 5 1     0 4 5 1     0 4 5 1      0 4 5 1
    1 6 2       1 6 2       1 6 2        1 6 2 
    3 5 0       3 5 4       3 6 0        3 6 4 
   2 4 6 3     2 0 5 3     2 4 5 3      2 0 5 3


   0 4 5 1     0 4 5 1      0 4 5 1      0 4 5 1
    3 6 4       3 6 4        3 6 4        3 6 4 
    1 0 2       1 6 2        5 0 2        5 6 2 
   2 6 5 3     2 0 5 3      2 6 1 3      2 0 1 3

Disposition B

La même méthode, que nous ne détaillerons pas, donne les 8 solutions.

  0 4 2 1      0 4 2 1      0 4 3 1      0 4 3 1
   5 3 0        5 3 0        5 2 0        5 2 0 
   6 1 6        6 4 6        6 1 6        6 4 6 
  2 5 4 3      2 5 1 3      2 4 5 3      2 1 5 3


  0 4 3 1      0 4 3 1      0 4 6 1      0 4 6 1
   5 6 0        5 6 0        5 3 0        5 3 0 
   6 1 2        6 4 2        6 1 2        6 4 2 
  2 4 5 3      2 1 5 3      2 5 4 3      2 5 1 3

Ici c'est plus simple car la solution étant topologiquement dissymétrique, toutes les solutions trouvées sont différentes (non équivallentes).

Disposition C

On obtient les 14 solutions

   0 4 2 1     0 4 2 1     0 4 3 1     0 4 3 1    0 4 3 1    0 4 3 1    0 4 3 1
    5 6 5       5 6 5       5 6 0       5 6 0      5 6 0      5 6 0      5 6 0 
    3 1 4       3 6 4       1 4 2       1 6 2      4 1 2      4 6 2      6 1 2 
   2 0 6 3     2 0 1 3     2 6 5 3     2 4 5 3    2 6 5 3    2 1 5 3    2 4 5 3


   0 4 3 1     0 4 3 1     0 4 3 1     0 4 5 1    0 4 5 1    0 4 5 1    0 4 5 1
    5 6 0       5 6 5       5 6 5       5 6 2      5 6 2      5 6 2      5 6 2 
    6 4 2       4 1 2       4 6 2       3 1 0      3 1 4      3 6 0      3 6 4 
   2 1 5 3     2 6 0 3     2 1 0 3     2 4 6 3    2 0 6 3    2 4 1 3    2 0 1 3

Ici aussi la position dissymétrique donne ces 14 solutions toutes différentes.

Soit en tout 34 solutions de base.
Et ainsi 34×7!×2 = 342720 en tenant compte des permutations de 0..6 et des images miroir par symétrie
Ce dernier facteur 2 doit être justifié soigneusement.
Une position dissymétrique donne à priori 4 solutions avec les symétries horizontales et verticales, mais comme le produit des deux symétries est une rotation de 180°, cela ne donne que deux dispositions différentes.
Une position symétrique donne aussi deux solutions par la symétrie de la position elle même (car l'autre symétrie est traitée comme identique à une permutation !)

Autres dispositions

Lucas propose les deux dispositions suivantes dans ces "Récréations mathématiques"

La première impose 6 doubles "dans les coins"
Il reste à choisir l'orientation des deux doubles des coins supérieurs et à placer le 7ème double. En fait il y a une seule possibilité sans mettre deux doubles dans le même quadrille.

d est alors 3 ou 4, et à symétrie G/D et permutation près, on peut sans perte de généralité affirmer d=3 puis de proche en proche b=5, g=1, e=0, a=2, f=4 et c=6, et donc une seule solution, à équivallence près.

La dernière forme a forcément ses coins imposés avec des doubles : et on obtient les seules dispositions :

La première donne les 11 solutions :

    0 4 5 6 1     0 4 5 6 1     0 4 5 6 1     0 4 5 6 1     0 4 5 6 1     0 4 5 6 1  
     1 5 2 4       5 1 2 4       6 4 2 5       6 4 2 0       1 4 2 5       5 1 2 0
    2 3 0 6 3     2 3 0 6 3     2 3 1 0 3     2 3 1 5 3     2 3 6 0 3     2 3 4 6 3
    
    
    0 4 5 6 1     0 4 5 6 1     0 4 5 6 1     0 4 5 6 1     0 4 5 6 1
     3 5 2 4       5 3 2 4       5 3 2 0       3 1 2 4       1 3 2 4
    2 1 0 6 3     2 1 0 6 3     2 1 4 6 3     2 5 0 6 3     2 5 0 6 3

La deuxième donne les 8 solutions :

    0 4 5 6 1     0 4 5 6 1     0 4 5 6 1     0 4 5 6 1  
     1 5 2 4       5 1 2 4       5 1 2 0       3 5 2 4
    2 3 0 6 3     2 3 0 6 3     2 3 4 6 3     2 1 0 6 3


    0 4 5 6 1     0 4 5 6 1     0 4 5 6 1     0 4 5 6 1
     5 3 2 4       5 3 2 0       3 1 2 4       1 3 2 4
    2 1 0 6 3     2 1 4 6 3     2 5 0 6 3     2 5 0 6 3

On notera que ces solutions ont le même "code numérique" que 8 des solutions précédentes, même si la disposition des dominos dans les quadrilles est différente.

Il affirme aussi que ce sont les seuls formes que peut prendre le paquet de dominos.
Sans vouloir chercher à vérifier cette affirmation, on peut montrer assez facilement l'impossibilité de certaines d'entre elles : il y a au plus 7 coins ! (qui doivent avoir un double)
Par exemple une pyramide a 8 "coins" (les deux du bas étant partagés avec ceux juste au dessus), et est donc impossible.

D'autres formes sont éliminées par ce même critère ou d'autres "topologiques".