Casse tete

par **steamboy** » 26 Mar 2009, 19:30

salut all,

ne sachant où poster, jai decide de poster ici.
En faite ac mes amis on est a fond sur un jeu, je vous explique les regles :

- faire un tableau de 10 carre sur 10, soit 100 carreaux ...
- ecrire succesivement les chiffres (1 puis 2 ...)
-se deplacer en laissant 2 carreaux quand on va vers la droite, le bas le haut ou la gauche, et 1 quand on se deplace en diagonale.

avez vous compris ?

Y'a un t(-il un truc pour remplir systematiquement le carreaux de 1 à 100 ?
merci

par **nodgim** » 27 Mar 2009, 18:50

Avec des cases alternées noires et blanches, il est évident qu'on ne peut occuper que les cases d'une même couleur.

par **scelerat** » 28 Mar 2009, 12:33

steamboy a écrit:salut all,

ne sachant où poster, jai decide de poster ici.
En faite ac mes amis on est a fond sur un jeu, je vous explique les regles :

- faire un tableau de 10 carre sur 10, soit 100 carreaux ...
- ecrire succesivement les chiffres (1 puis 2 ...)
-se deplacer en laissant 2 carreaux quand on va vers la droite, le bas le haut ou la gauche, et 1 quand on se deplace en diagonale.

avez vous compris ?

Y'a un t(-il un truc pour remplir systematiquement le carreaux de 1 à 100 ?
merci

Ca sent le voyageur de commerce, donc le probleme NP-complet...s'il est faisable.

par **Patastronch** » 28 Mar 2009, 13:57

C'est pas un voyageur de commerce, plutot la recherche d'un chemin hamiltonien (et non un cycle, la différence est la puisque l'existance d'un cycle implique l'existance d'un chemin mais la réciproque est fausse ! ).

Mais de toute facon c'est un probleme np-complet aussi.

par **nodgim** » 29 Mar 2009, 17:37

Numérotons les cases de 1 à 100: la 1ère ligne de 1 à 10, la seconde de 11 à 20, etc...
37.40.10.7.4.1.31.34.64.61.91.94.97.100.70.67.
89.86.83.53.56.59.29.26.23.
45.42.12.15.18.48.78.75.72.
54.24.21.51.81.84.87.90.60.30.27.57.
79.76.73.43.46.49.19.16.13.
35.65.95.98.68.38.8.5.2.32.62.92.
74.77.80.50.20.17.47.44.14.11.41.71.
93.96.99.69.39.9.6.3.33.63.66.36.
58.28.25.22.52.82.85.88.

Manque le 55. :doh:

Qui trouvera la solution complète ?

par **nodgim** » 29 Mar 2009, 20:32

Une solution complète:
82.85.88.58.55.52.22.25.28.
46.49.79.76.73.43.13.16.19.
37.40.10.7.4.1.31.34.64.61.91.94.97.100.70.67.
89.86.83.53.56.59.29.26.23.
45.75.78.48.18.15.12.42.72.
54.24.21.51.81.84.87.90.60.30.27.57.
35.65.95.98.68.38.8.5.2.32.62.92.
74.77.80.50.20.17.47.44.14.11.41.71.
93.96.99.69.66.63.33.36.39.9.6.3.

Casse tete

casse tete

Qui est en ligne