Pavage d'une grille 8 x 8 par des dominos

[chan79]

Juste des idées en vrac
Avec un carré 4 x 4

Ce pavage correspond à l'ensemble de couples suivants:
{(1,2), (3,7), (4,8), (5,9), (6,10), (11,12), (13,14), (15,16)}
A partir des couples, on pourrait peut-être retrouver le nombre de "carrés" ???
Par exemple: (3,7) et (4,8) ont une longueur de domino en commun ( 3 et 4 se suivent, 7=3+4 et 8=4+4).
(11,12) et (15,16) ont aussi une longueur en commun (11 et 12 se suivent; 15=11+4 et 16=12+4).

Bon, en dimension 8 x 8, il y a 12988816 pavages à examiner ...

[beagle]

tu l'aurais pas mis à l'envers?
ou alors tu comptes de bas en haut?

[chan79]

tu l'aurais pas mis à l'envers?
ou alors tu comptes de bas en haut?

oui, gauche vers droite et bas vers haut

[beagle]

code= horizontal noté 00, vertical noté :
1
1

au départ matrice que des zéros
premiere rangée donc:
00000000
pour ne pas faire doublons je dois mettre du 1
si je mets du 1 aux extrêmes j'ai max zero en décalage:
00000000
10000001
1................1
idem si je met du 1aux extrêmes =max zero décalés
00000000
10000001
11000011
...100001...
ans so on
c'est là que min de doublon

je le mets sous une autre forme 1 au lieu des zéros et rotation
parce que c'est celui que j'avais initialement, mais c'est le même:
10000001
11000011
11100111
11111111
11111111
11100111
11000011
10000001

[beagle]

donc les 1 ou les zeros sont en nombre pair
j'ai mis le 0,2,4,6,6,4,2,0 pour zeros ou 2,4,6,8,8,6,4,2 pour les 1

Celui de chan79 page 1 est un
0,2,4,6,6,4,2,0
si on reprend le même début et on fait petite variation je colle les 11 aulieu de les mettre aux extrêmes en rangée 4, a priori moins bon donc:
cela nous donne:
00000000
10000001
11000011
11110011
11111001
11001100
10000111
00000011
qui est alors un 0,2,4,6,6,4,4,2 avec 3 carrés isolés non surposés .

[beagle]

bon cela doit ètre pénible à lire mais moi pas savoir faire beaux dessins du net.

[beagle]

another one, pour la route.
on démarre de façon non optimale avec un carré angle sup droit:

00000011
.................11

pour maximiser mes zéros idem je mets du 1 aux extrêmes
00000011
10000111
1...........1

encore 1 aux extrêmes:
00000011
10000111
11001100
...1.....1

là je suis coincé je concède un carré de zero
00000011
10000111
11001100
11001001
1.................1

je suis à deux carrés,par symétrie si je fais idem en bas j'aurais du 4 carrés.

[beagle]

c'est pénible à suivre, alors encore un
je ne place pas mes 1 sur position optimale, je coupe ma rangée de zéros ainsi:

00100100
......1.....1.....

ben si je ne veux pas faire des carrés de zéro avec première et deuxième rangée,
j'ai l'immense choix de faire des carrés de 1 avec deuxième et troisième rangée

00100100
11111111
11...11...11

bingo déjà 3 carrés en trois rangées
00100100
11111111
11111111
00100100

ensuite par exemple:
si je mets en dessous du
10011001
10011001
11000011
11000011

7 carrés ouarf 10 au total!!!Horrible!

[chan79]

Bravo déjà pour l'idée de coder un pavage avec des 0 et des 1.

[beagle]

Bravo déjà pour l'idée de coder un pavage avec des 0 et des 1.

bon après au niveau théorie je fais pas trop avancer le schimilibillick,
parce comment dire que je ne vais pas mettre deux 11 cote cote qu je ne dois pas les separer de 1 seul zéro...

Le truc d'additionner la parité, cela le fait pour démontrer certaines choses, = à supposer que ton dessin de la diago n'aurait pas été probant, ben tu pouvais voir que les colonnes allaient de 1 en 1, les rangées idem, alors que les colonnes fallait mettre que du 11 et les rangées que du 00 de chaque coté de la diago, donc cela ne pouvait pas marcher, mais bon je préfère le dessin de la diago jusqu'au bout.

Beagle: alors à rien, pour rien, c'était pour faire avancer le schimillibilick ...

[beagle]

[.................

[zygomatique]

salut

peut-être une idée ...

1/ est-il possible de paver un carré 4 * 4 sans répondre à la question (sans deux pavés formant un carré) ?

il me semble que non ...

2/ montrer qu'il existe au moins un carré 4 * 4 dans le carré 8 * 8 qui contient deux pavés formant un carré

en montrant que si ce n'est pas le cas alors on ne peut pas paver le carré 8 * 8

enfin faut voir ...

[chan79]

Pour l'instant, on a ce pavage avec un seul carré

On en a un autre par rotation de 90°.
On a vu avec l'ami beagle qu'il faut au moins un carré.(pour tout damier 2nx2n)
beagle a codé les pavages avec des 0 et des 1.
A partir de ces 0 et 1, y aurait-il un moyen de calculer le nombre de carrés ?
Est-il possible de faire un algorithme qui code tous les pavages ? ??? Pas facile sans doute ....

[chan79]

avec 3 carrés, il y a celui-là (et d'autres avec des rotations)

[beagle]

Salut chan79,
comme quoi il n' y a pas tant de structures que cela.
C'est la même structure par rotation 90° puis renversement que celui que j'avais mis en 3 carrés issu d'une légère modif de ton 2 faisant 3.(message 28/09 15h11mn)
Mais l'est plus beau à lire ton tien!

[chan79]

ah oui !
suis grillé alors ...

[beagle]

Si on reprend les mèmes repères,
on part de l'optimum où tous les zéros en première rangée
puis je place idéalement les 1 aux extremites rangée 2, alors 6 zéros en décalage
puis encore les 1 et 1 aux extrémités avec 4 =2fois les zéros bien décalés

si alors on regarde le carré central de 4x4 avec en haut mes 0000

1)je continue l'optimum en plaçant les 1 aux extrémités,
je vais avoir le 1 seul carré:
0000
1001
1001
0000

2)je place mes 1 au centre, cela donne le carré de chan79 2 carrés qui en font 3
0000
...11...
...11...

oblige à
0000
1111
1111
0000

3)je place les 11 cotes à cotes:
0000
......11
......11

ou
0000
11......
11.....

qui donne
0000
1100
1110(0)
0011
.......(1)
qui donnera celui que j'avais mis = le 3 carré de chan79 d'aujourd'hui.


Donc il me semble qu'au-delà on devrait retomber sur les 4 carrés.Pas sur que autres structures à 3 carrés.

[chan79]

Salut
Je suis tombé sur ceci http://www.h-k.fr/seb/these/data/these.pdf
on peut aller page 33 et suivantes.
Je ne me suis pas attaqué aux "groupes de pavage"

[beagle]

Salut
Je suis tombé sur ceci http://www.h-k.fr/seb/these/data/these.pdf
on peut aller page 33 et suivantes.
Je ne me suis pas attaqué aux "groupes de pavage"

j'ai parcouru, c'est intéressant, mais cela va vite ètre hard pour moi.

[chan79]

Pour moi aussi (c'est quand même une thèse de doctorat)

On peut peut-être y trouver la raison pour laquelle on ne peut pas avoir exactement deux carrés (enfin, c'est ce que je pense ...)