Enigmo 126 : Triancey

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;
}

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.

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;;

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..

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