Inscription / Connexion Nouveau Sujet
Niveau 2 *
Partager :

Enigmo 126 : Triancey

Posté par
jamo Moderateur
01-08-09 à 17:49

Bonjour,

dans le dernier magazine du numéro de Tangente, j'ai lu un tout petit article sur un nouveau jeu crée par un français. Ce jeu s'appelle le Triancey, et je vous laisse deviner pourquoi ce nom ...

Ce petit jeu m'a semblé assez intéressant, et je me suis dit que j'allais vous en proposer une petite grille en tant qu'énigme. J'ai alors contacté l'auteur du jeu qui m'a donné son accord.

On peut jouer seul au Triancey, mais aussi à plusieurs. Ici, je vais vous proposer d'y jouer en solo. Les règles sont très simples, tout le monde peut jouer et proposer une réponse.

Tout d'abord, je vous livre le lien vers le site internet de ce jeu :

Ensuite, je vais vous en expliquer rapidement les règles à appliquer pour l'énigme, ainsi que dérouler le début d'une partie en tant qu'illustration.

On dispose d'un rectangle pavé de triangles, qui sont en contact par leurs côtés en entier. De plus, et c'est important, il faut considérer que les triangles d'un bord sont en contact avec ceux du bord opposé. Ainsi, chaque triangle possède exactement 3 voisins, pas un de plus, pas un de moins.

A chaque tour de jeu, on choisit un triangle qu'on colorie.
La règle est la suivante : tout triangle en contact avec deux triangles coloriés se retrouve automatiquement colorié.
Selon ce principe, on comprend que des "réactions en chaine" sont possibles ...
Dans une partie à 2 joueurs, l'objectif est de conquérir la plus grande zone possible.

La grille de 24 triangles que je propose est celle ci-dessous. J'ai numéroté chaque triangle afin que vous puissiez répondre à l'énigme sans avoir à refaire des figures.

Dans les six petites grilles en dessous, j'ai détaillé le début d'une partie.
Coup 1 : je colorie le triangle 1.
Coup 2 : je colorie le triangle 3.
Le triangle 2, en contact avec les triangles 1 et 3 qui sont coloriés, se colorie alors automatiquement.
Coup 3 : je colorie le triangle 23.
Coup 4 : je colorie le triangle 19.
Le triangle 18, en contact avec les triangles 2 et 19 qui sont coloriés, se colorie alors automatiquement.
Le triangle 24, en contact avec les triangles 18 et 23 qui sont coloriés, se colorie alors automatiquement.

Voilà, je m'arrête là pour l'exemple, je ne finis pas la partie. En 4 coups, j'ai réussi à colorier 7 triangles.

Question : Quel est le nombre minimal de coups pour colorier toute la grille ?
Vous me donnerez ce nombre de coups, mais aussi la liste, dans l'ordre, des cases à colorier pour y parvenir.

Je me débrouillerai pour les triangles coloriés automatiquement en étudiant vos propositions.

Je ne possède pas la solution optimale pour cette grille que j'ai inventé. Celui ou ceux qui proposeront la solution la plus courte auront droit au smiley.
Et pour la difficulté de l'énigme, je n'en ai aucune idée. Le principe est très simple, mais trouver l'optimum est sans doute compliqué ...

Et si le jeu vous a plu, n'hésitez pas à aller visiter le site de l'auteur pour prolonger le plaisir !

Bonne recherche !

Enigmo 126 : Triancey

Enigmo 126 : Triancey

Posté par
link224
re : Enigmo 126 : Triancey 01-08-09 à 18:10

perduSalut jamo!

Allez je tente : solution minimale en 8 coups.
Coup 1 : je colorie le triangle 1
Coup 2 : je colorie le triangle 3
        => Coloration du triangle 2
Coup 3 : je colorie du triangle 19
        => Coloration du triangle 18
Coup 4 : je colorie du triangle 4
        => Coloration du triangle 20
Coup 5 : je colorie du triangle 13
        => Coloration des triangles 12 et 21
        => Coloration du triangle 11
        => Coloration du triangle 10
Coup 6 : je colorie du triangle 24
        => Coloration du triangle 17
        => Coloration du triangle 9
Coup 7 : je colorie le triangle 6
        => Coloration des triangles 5 et 22
        => Coloration du triangle 14
        => Coloration du triangle 15
Coup 8 : je colorie le triangle 23
        => Coloration des triangles 16, 7 et 8 dans cet ordre.
Tous les triangles sont alors coloriés.

@+ et merci pour l'énigme

Posté par
yoyodada
re : Enigmo 126 : Triancey 01-08-09 à 19:44

gagnésalut jamo

Je ne trouve pas moins que 7 coups:

11
13
1
20
24
6
23

sans grande conviction...
Merci pour l'énigme

Posté par
geo3
re : Enigmo 126 : Triancey 01-08-09 à 20:52

gagnéBonjour
en continuant comme vous avez commencé :
coup 5 : je colorie le triangle 9 => 8 et 17 sont à coloriés et 10 et 11 et 12
coup 6 : je colorie le triangle 21 => 20 et 13 sont à coloriés et 4
coup 7 : je colorie le triangle 15 => 22 et 16 et 14 sont à coloriés et 5 et 7 et 6
A+

Posté par
Daniel62
re : Enigmo 126 : Triancey 01-08-09 à 23:19

gagnéBonsoir Jamo,

réponse en 7 coups: 17 - 14 - 23 - 16 - 20 - 3 - 1

Posté par
dhalte
re : Enigmo 126 : Triancey 02-08-09 à 00:38

gagnéBonjour
7 coloriages volontaires entrainent le coloriage des 17 autres
3 13 14 16 17 18 20

Posté par
jimss
re : Enigmo 126 : Triancey 02-08-09 à 04:25

gagnéBonjour,

Je propose de colorier toute la grille en sept coups.
Voici une des nombreuses possibilités permettant d'y parvenir.
Sont notifiés entre parenthèses, les numéros des triangles automatiquement coloriés.

Coup 1 : 1
Coup 2 : 17 (9 - 10)
Coup 3 : 18 (2 - 24)
Coup 4 : 12 (3 - 11 - 19)
Coup 5 : 5 (4 - 20)
Coup 6 : 7 (6 - 8 - 23 - 16)
Coup 7 : 13 (14 - 15 - 21 - 22)

Posté par
castoriginal
Enigmo 126: Triancey 02-08-09 à 09:35

perduBonjour,

personnellement, j'ai trouvé au moins 7 solutions à 7 coups; mais la meilleure est en

6 coups. Voici graphiquement la solution. Peut importe l'ordre des coups.

On peut néanmoins dire 10,2,12,20,22,8

bien à vous

Enigmo 126: Triancey

Posté par
integral
re : Enigmo 126 : Triancey 02-08-09 à 10:34

gagnéBonjour, je ne parviens pas à trouver une solution en moins de \textrm\red\fbox{7 coups}.
Pour cela on peut colorier les cases 5, 8, 12, 16, 17, 19 et 21.
Merci pour l'énigmo, en espérant que personne ne trouvera mieux...

Posté par
Nofutur2
re : Enigmo 126 : Triancey 02-08-09 à 11:15

gagnéJe pense qu'il faut 7 coups au minimum.
J'ai trouvé une solution en 7 coups dans laquelle il faut colorier les triangles
1, 2, 4, 6, 8, 11 et 15

Posté par
castoriginal
Enigmo 126: Triancey 02-08-09 à 12:22

perduBonjour,

il y a erreur de ma part, il n'y pas de solution à 6 coups.
Voici un certain nombre de solutions en 7 coups
A bientôt

Enigmo 126: Triancey

Posté par
pacou
re : Enigmo 126 : Triancey 02-08-09 à 13:07

gagnéBonjour, Jamo.

Hum! Ça sent le poisson! Je n'ai pas trouvé moins de 7 coups.
Voici une des solutions à 7 coups:

\fbox{1}  \fbox{3}  \fbox{5}  \fbox{7}   \fbox{13}   \fbox{19}   \fbox{23}

Merci pour l'énigmo.

Posté par
Rudi
re : Enigmo 126 : Triancey 03-08-09 à 11:04

gagnéBonjour

====== Réponse proposée ======

7 cases : 1-3-17-19-5-15-8

Rudy

Posté par
Rumbafan
Triancey 03-08-09 à 11:40

perduJe pense que 8 serait suffisant... :

16 6 22 4 20 2 9 10

Tangente est une revue SUPER recommandée à tous


Bonne recherche

Posté par
13or
re : Enigmo 126 : Triancey 03-08-09 à 14:40

gagnéRéponse : 7 coups : 1 2 4 6 8 13 19

Merci pour l'énigmo

Posté par
lo5707
re : Enigmo 126 : Triancey 03-08-09 à 18:01

gagnébonjour,

je prends le risque de répondre même si je pense qu'il y a mieux...

Voici la liste des triangles à colorier : (entre parenthèses se trouvent ceux qui se colorient d'office)

5
15 (14)
7 (6 - 16 - 22)
13 (21)
3 (12 - 4 - 20)
9 (8 - 23)
18 (19 - 24 - 17 - 11 - 10 - 1 - 2)

ce qui fait 7 coups.


Merci pour l'énigme.

PS : le titre de l'énigmo 125 n'est pas bon, c'est indiqué Enigmo 126 aussi

Posté par
Francois86
re : Enigmo 126 : Triancey 03-08-09 à 19:26

gagnéVoici une réponse en 7 coups, je ne sais pas si elle est optimale :

17 19 12 2 15 7 5

Voici le détail, avec entre parenthèses les triangles qui se colorient automatiquement

17 19 12 (11 10) 2 (1 18 24 3 9) 15 7 (16 8 23) 5 (14 13 6 22 4 20 21)

Posté par
godefroy_lehardi Posteur d'énigmes
re : Enigmo 126 : Triancey 03-08-09 à 20:52

gagnéBonjour,

Je pense qu'on ne peut pas faire moins que 7 coups (en tout cas, moi je n'y suis pas arrivé).

Voici mon meilleur score (la première colonne représente les coups joués et les chiffres suivants les triangles coloriés automatiquement):
17
2
11 10 1 9
23 24 8 18 19
4 3 12 20
6 5 7 16
13 14 21 15 22

Merci pour cette énigme sympathique.

Posté par
dpi
trianglescolorés 04-08-09 à 12:18

perduj'ai pas trouve mieux que 10 contamineurs :
18 11 1 3 14 22 6 8 17 23

Posté par
bibe
re : Enigmo 126 : Triancey 04-08-09 à 14:53

perduje dirais qu'il faut 8 coups :
1) 18
2) 20
3) 1
4) 7
5) 9
6) 23
7) 14
8) 5

Posté par
-Orny-
re : Enigmo 126 : Triancey 05-08-09 à 13:51

perduA première vue, et de façon tout à fait empirique, je dirais 7 coups.
En 5 minutes, j'ai trouvé ces deux là :
3,1,23,19,11,21
ou encore
1,3,23,7,11,21,5

Posté par
gloubi
re : Enigmo 126 : Triancey 06-08-09 à 16:17

gagnéBonjour,

Pas sûr du tout, mais j'ai une foultitude de solutions en 7 coups.
Par exemple: 10 - 12 - 14 - 16 - 24 - 2 - 5.

A+,  

Posté par
Kacs
re : Enigmo 126 : Triancey 10-08-09 à 21:59

gagnéLe nombre minimal de coup nécessaires pour remplir la grille est 7. Il y a alors plusieurs (et même beaucoup) de solutions distinctes.
Par exemple :  10  23  9  14  22  3  19
Ou bien  23  12  19  9  6  14  2.


Et 7 est le nombre minimal (i.e. il n'existe aucune solution avec 1, 2, 3, 4, 5 ou 6 coups).

Posté par
_Michel
re : Enigmo 126 : Triancey 12-08-09 à 15:55

gagnéPour ne rien rater, j'ai écrit un bruteforce en C:

Citation :
/*
    Triacey - bruteforce de l'énigme 126 sur Ilemaths.

    Dernière modification le 12/08/2009 15h49.
*/

#include <stdio.h>
#include <windows.h>

#define NBR_COUP_MAX    (6)

/*
    Structure du tableau :
        - octet 0 : nombre de cases coloriées
        - bits 8-31 : état des cases 1-24
*/
#define CASE(Tableau, i)              ( (Tableau>>(i+7))&1 )
#define SET_CASE(Tableau, i)          \
    Tableau |= (1<<(i+7));            \
    Tableau+=1;
#define NBR_CASE(Tableau)             ( (unsigned char)Tableau )


/*
    Voisin - Description des correspondances entre les cases.
*/
const unsigned char Voisin[25][3] = {
    {0, 0, 0},
    {2, 9, 10},
    {1, 3, 18},
    {2, 4, 12},
    {3, 5, 20},
    {4, 6, 14},
    {5, 7, 22},
    {6, 8, 16},
    {7, 9, 23},
    {8, 1, 17},
    {1, 17, 11},
    {10, 12, 19},
    {11, 13, 3},
    {12, 14, 21},
    {13, 15, 5},
    {14, 16, 22},
    {15, 23, 7},
    {9, 24, 10},
    {24, 2, 19},
    {11, 18, 20},
    {19, 21, 4},
    {20, 22, 13},
    {21, 15, 6},
    {16, 24, 8},
    {23, 17, 18}
};

/*
    Reaction - Colorie les cases ayant deux voisins coloriés

    Paramètres :
        Tableau - Pointeur sur le tableau car il est susceptible d'être modifié.
        i - Numéro de la case qui viens d'être modifiée.
*/
void Reaction (unsigned long *Tableau, int i)
{
    unsigned char _Voisin, a, b, c;

    _Voisin = Voisin[i][0];
    if (!CASE (*Tableau, _Voisin)) {
        a = CASE (*Tableau, Voisin[_Voisin][0]);
        b =    CASE (*Tableau, Voisin[_Voisin][1]);
        c = CASE (*Tableau, Voisin[_Voisin][2]);
        if ((a&&(b||c))||(b&&c)) {        // Si au moins deux voisins sont cooriés
            SET_CASE (*Tableau, _Voisin);
            Reaction (Tableau, _Voisin);
        }
    }

    _Voisin = Voisin[i][1];
    if (!CASE (*Tableau, _Voisin)) {
        a = CASE (*Tableau, Voisin[_Voisin][0]);
        b =    CASE (*Tableau, Voisin[_Voisin][1]);
        c = CASE (*Tableau, Voisin[_Voisin][2]);
        if ((a&&(b||c))||(b&&c)) {        // Si au moins deux voisins sont cooriés
            SET_CASE (*Tableau, _Voisin);
            Reaction (Tableau, _Voisin);
        }
    }

    _Voisin = Voisin[i][2];
    if (!CASE (*Tableau, _Voisin)) {
        a = CASE (*Tableau, Voisin[_Voisin][0]);
        b =    CASE (*Tableau, Voisin[_Voisin][1]);
        c = CASE (*Tableau, Voisin[_Voisin][2]);
        if ((a&&(b||c))||(b&&c)) {        // Si au moins deux voisins sont cooriés
            SET_CASE (*Tableau, _Voisin);
            Reaction (Tableau, _Voisin);
        }
    }
}

/*
    Jeu - Bruteforce à partir d'un tableau donné. Affiche toutes les solutions trouvées.

    Paramètres :
        Tableau - Tableau de départ
        NbrCoup - Nombre de coup déjà effectués.
        Coup - Pointeur sur l'historique des coups. Cette solution permet de ne pas passer par la pile le tableau.
*/
void Jeu (unsigned long Tableau, int NbrCoup, unsigned char (*Coup)[8])
{
    int i;
    unsigned TableauCopie = Tableau;

    for (i=1; i<=24; i++) {
        if (!CASE(Tableau, i)) {    // Si la case i n'est pas coloriée
            // Colorie la case
            SET_CASE (Tableau, i)
            (*Coup)[NbrCoup] = (unsigned char)i;

            // Réaction en chaîne
            Reaction (&Tableau, i);

            // Vérifie si la tableau est fini
            if (NBR_CASE (Tableau) == 24) {
                printf ("Solution : %d, %d, %d, %d, %d, %d, %d, %d.\n",
                    (*Coup)[0], (*Coup)[1], (*Coup)[2], (*Coup)[3], (*Coup)[4], (*Coup)[5], (*Coup)[6], (*Coup)[7]);
            }

            // Joue les autres coups
            if (NbrCoup != NBR_COUP_MAX-1) {
                Jeu (Tableau, NbrCoup+1, Coup);
            }

            // Retourne à l'état initial
            Tableau = TableauCopie;
            (*Coup)[NbrCoup] = 0;
        }
    }
}

int main ()
{
    unsigned char Coup[8] = {0, 0, 0, 0, 0, 0, 0, 0};

    Jeu (0, 0, &Coup);

    system ("pause");
    return 0;
}


Résultat :
Pas de solution pour 6 coups ou moins (9").
42477120 solutions pour 7 coups (2'30" de calcul, 2'39"d'écriture, 1,7Go de données générées pour lister toutes les solutions).

Merci pour cette énigme amusante.

Posté par
_Michel
re : Enigmo 126 : Triancey 12-08-09 à 15:56

gagnéOups j'ai oublié de donner une solution...
la plus petite : 1, 2, 4, 6, 8, 11, 15.

Posté par
LeFou
re : Enigmo 126 : Triancey 14-08-09 à 21:28

gagné7 coups:
23,17,11,2,4,7,14

Posté par
totti1000
re : Enigmo 126 : Triancey 15-08-09 à 01:06

gagnéSalut Jamo,
Je n'ai pas réussi à faire mieux que 7 coups...
1-11-18-21-14-16-17
Voir l'image, en rouge les coups, et en jaune les cases qui se colories automatiquement selon la règle du jeu...

Enigmo 126 : Triancey

Posté par
Bcracker
re : Enigmo 126 : Triancey 16-08-09 à 19:42

gagnéBonjour,

  Après quelques brèves recherche, j'arrive à un minimum de 7 coups. Doutant de ce résultat, j'ai crée un petit programme CAML (bon entraînement pour l'info ) permettant de rechercher des coloriages à x coups en générant aléatoirement des coloriages et vérifiant s'il permettent de couvrir toute la zone après coloriage automatique. J'ai aussi écris une fonction qui teste tous les coloriages possibles pour 6 coups soit 134596 coloriages différents, et CAML ne semble rien trouver...

Donc je propose un jeu en 7 coups minimum.

Citation :
  Voici une solution parmi d'autres : Je colorie successivement les triangles 3,5,8,10,16,21,24.De façon évidente, les triangles 4,23 et 7 se colorient automatiquement car communs à deux autres triangles coloriés, puis 6 se colorie car commun à 5 et 7. De plus 17 se colorie car commun à 10 et 24; puis 9 car commun à 17 et 8; puis 1 car commun à 10 et 9; puis 2 car commun à 1 et 3, puis 18 car commun à 2 et 24; puis 20 car commun à 4 et 21; puis 19 car commun à 18 et 20; puis 11 car commun à 10 et 19; puis 12 car commun à 3 et 11; puis 13 car commun à 12 et 21; puis 14 car commun à 5 et 13; puis 15 car commun à 14 et 16; puis 22 car commun à 21 et 15.


J'espère avoir été clair... Ci dessous, un petit programme CAML* que j'ai réalisé et une figure du triancey**.

* cela n'empêche bien évidemment pas que je me sois trompé quelque part... ()
** En rouge, les triangles que je colorie et en jaune ceux qui se colorient automatiquement

Sauf erreur, bien entendu

Merci pour l'énigme

Code CAML LIGHT

Citation :
(*couleur = bool vect | tableau des triangles coloriés
  associes =(int vect) vect | tableau des tableau des triangles associés au triangle i.*)
(*exemple*)

(*Représentation : On représente un triancey par un tableau de tableaux de 3 éléments correspondant au triangle commun au triangle i+1.
Par exemple triancey.(0) renvoie le tableau des indices des triangles commun au triangle 1.
Un coloriage sera représenté par un tableau de booléens tel que coloriage.(i) renvoie true si le triangle i+1 est colorié, false sinon
*)

let triancey = [|[|2; 10; 9|]; [|1; 3; 18|]; [|2; 4; 12|]; [|3; 5; 20|]; [|4; 6; 14|];
    [|5; 7; 22|]; [|6; 8; 16|]; [|7; 9; 23|]; [|1; 8; 17|]; [|1; 11; 17|];
    [|10; 12; 19|]; [|3; 11; 13|]; [|12; 14; 21|]; [|5; 13; 15|]; [|14; 16; 22|];
    [|7; 15; 23|]; [|9; 10; 24|]; [|2; 19; 24|]; [|11; 18; 20|]; [|4; 19; 21|];
    [|13; 20; 22|]; [|6; 15; 21|]; [|8; 16; 24|]; [|17; 23; 18|]|]
;;
(*Procédé : pour un entier n donné, on va colorier toute les partie de n triangle dans les N triangles totaux. De la, on voit si tout est colorié.*)

(*====================================================== Fonctions préliminaires - Combinatoire (inspiré ESIM 99) ======================================*)
let prem ens = match ens with
    | [] -> failwith "Erreur dans prem"
    | t :: q -> t;;
let sp ens = match ens with
    | [] -> failwith "Erreur dans sp"
    | t :: q -> q;;
let rec siem i ens = match ens with
    | [] -> failwith "Erreur"
    | t :: q -> if i = 1 then q else t :: (siem (i - 1) q);;
let rec ieme i ens = match ens with
    | [] -> failwith "Erreur dans ieme"
    | t :: q -> if i = 1 then t else ieme (i - 1) q;;
let rec ajout e lst_ens = match lst_ens with
    | [] -> []
    | t :: q -> (e :: t) :: (ajout e q);;
(* Determinations d'ensembles *)
let rec parties e =
  if e = [] then [[]]
  else let x = prem e and e_1 = sp e
    in let part = parties e_1
      in part @ (ajout x part);;

let rec combinaisons p e =
  if p > list_length e then []
  else if p = 0 then [[]]
  else let x = prem e and e_1 = sp e in
      combinaisons p e_1 @ (ajout x (combinaisons (p - 1) e_1))
;;
let construire_tableau p e =
  vect_of_list (combinaisons p e)
;;
combinaisons 3 [1;2;3;4];;

(*Quelques fonctions de calcul*)

let rec facto n = match n with
    | 1 -> 1
    | x -> x * facto (x - 1)
;;
facto 5;;
let comb (i: int) (n: int) =
  (facto n) / ((facto i) * (facto (n - i)))
;;
comb 3 10;;

(*====================================================== Fonctions de création des coloriages  ========================================================*)


let lister n = let l = ref [] in
for i = 1 to n do l:=i::!l done;
rev !l;;
                  (* _ Créer la liste des parties de i élément sur les n totaux*)
let partiesDeTriangles (i:int) (n:int) = construire_tableau i (lister n);;

partiesDeTriangles 2 6;;

(*Fonctions de coloriage*)

(*Colorie les parties sélectionnées*)
let coloriageParties (i: int) (j: int) (n: int) = (*colorie la jeme partie calculée parmi les parties a i éléments de l'ensemble total a n éléments*)
  let parties = partiesDeTriangles i n in let partiesj = parties.(j) in let v = ref (make_vect n false) in
        let rec aux (ll: int list) =
          match ll with
            | [] -> ()
            | [x] -> !v.(x - 1) <- true
            | t :: q -> !v.(t - 1) <- true; aux q
        in aux partiesj; !v
;;

(*====================================================== Fonctions de coloriage automatique  ========================================================*)

let couleur (i: int) (v: bool vect) = v.(i);;
let nombre_associes (i: int) (v: bool vect) (l: int vect vect) = (*Determine le nombre de triangles coloriés en contact avec le triangle i*)
  let ll = l.(i) in let k = ref 0 in
      for j = 0 to 2 do
        if couleur (ll.(j) - 1) v then incr k
      done;
      !k
;;

let coloriageAuto (v: bool vect) (l: (int vect) vect) = let n = vect_length v in let vv = (make_vect n false) in
      for i = 0 to n - 1 do if ((nombre_associes i v l) >= 2 || couleur i v) then vv.(i) <- true done; vv
;;
let coloriageComplet (coloriage: bool vect) (triancey: int vect vect) = let n = vect_length triancey in let vtest = ref coloriage in
      while !vtest <> (coloriageAuto !vtest triancey) do
        vtest := coloriageAuto !vtest triancey done; !vtest;;
let coloriageComplet2 (coloriage: bool vect) (triancey: int vect vect) = let v = ref (make_vect 24 false) in
    for i = 0 to (vect_length triancey) do v := coloriageComplet coloriage triancey done; !v;;


(*====================================================== Fonctions de test des coloriages  ========================================================*)

(*Teste si le coloriage pris en argument permet de couvrir tout le triancey*)

let test_final (v: bool vect) = let ans = ref true and n = vect_length v in
    for i = 0 to n - 1 do if v.(i) = false then ans := false done; !ans;;

(*====================================================== Fonctions de conversions  ========================================================*)

let int_of_bool (b: bool) = if b then 1 else 0;;

let imprimerColoriage (coloriage: bool vect) =
  let n = vect_length coloriage in
    for i = 0 to n - 1 do print_int (int_of_bool coloriage.(i)) done;;

let valeurColoriage (coloriage: bool vect) = (*Determine le nombre de triangle coloriés dans un coloriage*)
  let n = vect_length coloriage and entier = ref 0 in
    for i = 0 to n - 1 do entier := !entier + (int_of_bool coloriage.(i)) done; !entier;;

(*ConstruireColoriage : convertir un code "binaire" en coloriage 1 = colorié, 0= non colorié*)
let construireColoriage (code: string) = let n = string_length code in let v = make_vect n false in
      for i = 0 to n - 1 do if (int_of_string (sub_string code i 1)) = 1 then v.(i) <- true done;
      v
;;


(*====================================================== Fonctions de recherche et vérification  ========================================================*)

let test = construireColoriage "001010010100000100001001";; (*Une solution au problème*)
coloriageComplet test triancey;; (*pas vraiment complet, on réitère => fonction "colorier"*)
coloriageComplet2 test triancey;;

(*======================================== Fonction de recherche par parties | Exhaustif, mais ne marche par pour toutes les valeurs (exn memoire)=======*)
exception stop of int;;
let trouveCombinaisonEtAffiche max = (*ne marche pas pour toutes le valeurs de max (exception memoire)*)
  try for i = 0 to 134595 do
      let c = coloriageParties max i 24 in if valeurColoriage (coloriageComplet c triancey) = 24 then raise (stop i) done;
  with
  | stop i -> print_string "Partie "; print_int i;
;;

trouveCombinaisonEtAffiche 6;;
comb 3 24;;
(*======================================== Fonction de recherche au Hasard| non exhaustif, mais ne fait pas d'exn memoire ==============================*)

(*Génère un coloriage de max triangle au hasard*)
#open "random";;
let coloriageAuPif (max: int) (n: int) = (*On créer un coloriage aléatoire que l'on teste*)
  let t = [|true; false|] in
    let v = make_vect n false in
      while valeurColoriage v <> max do
        for i = 0 to (n - 1) do if (valeurColoriage v < max) then v.(i) <- t.(int 2) done;
      done;
      (*De la, on procede au coloriage automatique*)
v
;;
init 0;;
coloriageAuPif 6 24;;
(*On teste m coloriage générés aléatoirement *)
exception stop of bool vect;;
let recherche max n m =
  try
    for i = 0 to m - 1 do
      let c = coloriageAuPif max n in let cc = coloriageComplet c triancey in
          if valeurColoriage cc = 24 then raise (stop c); done;
  with
  | stop c -> print_string "Le coloriage "; imprimerColoriage c; print_string " convient !";
        print_string "Rien trouvé"
;;

recherche 7 24 1000;;
let coloriageTest = coloriageAuPif 7 24;;
let solution = construireColoriage "001010010100000100001001";; (*Une solution au problème, en 7 coups*)
coloriageComplet solution triancey;;


Enigmo 126 : Triancey

Posté par
jamo Moderateur
re : Enigmo 126 : Triancey 19-08-09 à 08:36

Clôture de l'énigme

Visiblement, on ne pouvait pas faire moins de 7 coups. Certains semblent l'avoir prouvé par une recherche des solutions à l'aide d'un programme.

Sinon, en corrigeant, j'ai remarqué que l'ordre de coloriage n'avait pas d'importance pour l'énigme.

Maintenant, si vous voulez laisser votre avis sur ce petit jeu, c'est à vous !

Posté par
Nofutur2
re : Enigmo 126 : Triancey 19-08-09 à 17:51

gagnéJ'ai l'impression qu'il suffit de sélectionner au hasard 6 triangles "non en contact deux à deux" pour pouvoir trouver un 7ème triangle qui permette de conclure..
J'ai fait 5 ou 6 essais et çà marche !!

Posté par
kiko21
re : Enigmo 126 : Triancey 19-08-09 à 20:11

Bonjour,

J'étais à 7 coups aussi, mais j'attendais encore avant de répondre pour voir si je trouverai 6 coups... tant pis pour moi.
> Nofutur2

Citation :
J'ai l'impression qu'il suffit de sélectionner au hasard 6 triangles "non en contact deux à deux" pour pouvoir trouver un 7ème triangle qui permette de conclure..

Moi aussi, j'ai trouvé plusieurs combinaisons où on conclut au 7ème avec un méga enchainement.

> Jamo
Citation :
Maintenant, si vous voulez laisser votre avis sur ce petit jeu, c'est à vous !

Je suis allé sur le site de Jean-Luc Ancey. Sa règle du solitaire est un peu différente de la tienne mais les deux sont très intéressantes.
J'ai aussi téléchargé son jeu. J'espère qu'il fera une version réseau...

Merci Jamo. A+, KiKo21.

Posté par
Nofutur2
re : Enigmo 126 : Triancey 20-08-09 à 09:18

gagnéJe complète ma remarque :
Non seulement il suffit de sélectionner au hasard 6 triangles qui sont au départ "non en contact deux à deux".
Mais, si on applique la colorisation à partir de ces 6 triangles, le 7ème triangle peut être choisi :
- au hasard parmi ceux qui ne sont pas en contact avec les triangles coloriés, s'il y en a.
- au hasard si tous les triangles restants sont en contact avec un triangle colorié.

Posté par
lo5707
re : Enigmo 126 : Triancey 20-08-09 à 13:59

gagnénofutur :

ta remarque n'est pas juste (sauf erreur de ma part...)

ex : On prend les 6 triangles suivants : 1 - 11 - 18 - 6 - 16 - 17
Se colorient alors les : 10 - 19 - 7 - 24 - 23 - 9 - 8 - 2

Ensuite, non seulement n'importe quel triangle ne fait pas l'affaire, mais en plus on est dans une impasse...
Impossible de finir !

Posté par
Nofutur2
re : Enigmo 126 : Triancey 20-08-09 à 15:07

gagné---> lo5707

Tu as raison !!
Peut être aurait il fallu préciser :
Non seulement il suffit de sélectionner au hasard 6 triangles qui sont au départ "non en contact deux à deux"....et tel que 3 triangles choisis ne soient pas en contact avec le même triangle.
Alors là je pense que çà marche ..

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 87:58:28.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !