Accueil > Réalisations > Logiciels > Jeux de l’esprit > Divers > Solution du puzzle des nombres d’Aristote

Solution du puzzle des nombres d’Aristote

samedi 1er juin 2019, par Paul Courbis

Le puzzle des nombres d’Aristote est un hexagone de côté 3 composé de 19 pièces hexagonales numérotées de 1 à 19 qui doivent être placées de telles manière que la somme des nombre composant une ligne soit toujours égale à 38.

 

 
Plutôt que de me creuser la tête à trouver une solution ou de la chercher sur Internet, voici un court programme en C qui trouve toutes les solutions possibles.

Le programme trouve les 12 solutions existantes qui sont en fait toutes identiques à une rotation et/ou une symétrie près. En voici l’une d’entre elles :
 

 

Le programme a été fortement optimisé. Il trouve l’ensemble des solutions en moins de 5 secondes sur un processeur Intel Core i7-855U à 1.80 GHz.
 

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. typedef enum status { BOARD_INCOMP, BOARD_BAD, BOARD_GOOD } status;
  6.  
  7. #define HEIGHT 5 // Odd number
  8. #define STARTW 3 // Width of first line < HEIGHT
  9.  
  10. #define WIDTH  ((2*HEIGHT)-1)
  11. #define PIECES (HEIGHT*HEIGHT-STARTW*(STARTW-1))
  12. #define SEEKED ((PIECES*(PIECES+1))/(2*HEIGHT))
  13.  
  14. //#define EXITON1SOL exit(0);
  15.  
  16. #ifdef EXITON1SOL
  17. #define FINALEXITCODE 1
  18. #else
  19. #define FINALEXITCODE 0
  20. #define EXITON1SOL  
  21. #endif
  22.  
  23. status CheckLine(int i, int board[HEIGHT][WIDTH])
  24. {
  25.    int j, sum=0, val, *b;      
  26.    status stat = BOARD_GOOD;
  27.  
  28.    b=&board[i][0];
  29.  
  30.    for(j=0;j<WIDTH;++j)
  31.    {
  32.       if((val = b[j]) < 0) stat=BOARD_INCOMP;
  33.       else { sum += val; }
  34.    }
  35.    if(sum != SEEKED && stat != BOARD_INCOMP) return BOARD_BAD;
  36.    else if(sum > SEEKED) return BOARD_BAD;
  37.    else if(sum == SEEKED && stat != BOARD_INCOMP) return BOARD_GOOD;
  38.    return stat;
  39. }
  40.  
  41. status CheckDiags(int ci, int cj, int board[HEIGHT][WIDTH])
  42. {
  43.    int i, j, sum, val, s;
  44.    status lstat, stat = BOARD_GOOD;
  45.    
  46.    for (s=-1; s<=1; s+=2)
  47.    {
  48.       j = cj + s*ci;
  49.       sum = 0; lstat = BOARD_GOOD;
  50.  
  51.       for(i=0;i<HEIGHT;++i)
  52.       {
  53.          if(i<0||i>=HEIGHT||j<0||j>=WIDTH) ;
  54.          else if((val = board[i][j]) < 0) stat=lstat=BOARD_INCOMP;
  55.          else sum += val;
  56.          j-=s;
  57.       }
  58.       if(sum != SEEKED && lstat != BOARD_INCOMP) return BOARD_BAD;
  59.       else if(sum > SEEKED) return BOARD_BAD;
  60.       else if(sum == SEEKED && lstat != BOARD_INCOMP) stat = BOARD_GOOD;
  61.    }
  62.    return stat;
  63. }
  64.  
  65. status CheckSums(int i, int j, int board[HEIGHT][WIDTH])
  66. {
  67.    if(CheckLine(i, board) == BOARD_BAD) return BOARD_BAD;
  68.    return CheckDiags(i, j, board);
  69. }
  70.  
  71. void FindNextFree(int *i, int *j, int board[HEIGHT][WIDTH])
  72. {
  73.    int dj=1+(*j>0);
  74.  
  75.    for(;*i<HEIGHT;++*i)
  76.    {
  77.       for(;*j<WIDTH;*j+=dj)
  78.          if(board[*i][*j] < 0) return;
  79.       *j=0; dj=1;
  80.    }
  81.    *i = -1; *j = -1;
  82.  
  83.    return;
  84. }
  85.  
  86. void ShowBoard(int board[HEIGHT][WIDTH])
  87. {
  88.    int i, j, val;
  89.  
  90.    printf("\n+"); for(i=0;i<HEIGHT*3-1;++i) printf("--");
  91.    printf("+\n");
  92.  
  93.    for(i=0;i<HEIGHT; ++i)
  94.    {
  95.       printf ("|");
  96.       for(j=0;j<WIDTH; ++j)
  97.       {
  98.          if((val=board[i][j]) == 0) printf("   ");
  99.          else printf(" %2d", val);
  100.       }
  101.       printf(" |\n");
  102.    }
  103.    printf("+"); for(i=0;i<HEIGHT*3-1;++i) printf("--");
  104.    printf("+\n");
  105. }
  106.  
  107. void Recurse(int p, int x, int y, int board[HEIGHT][WIDTH], int pieces[PIECES])
  108. {
  109.    int val, v, lp;
  110.    status s;
  111.  
  112.    FindNextFree(&x, &y, board);
  113.  
  114.    lp = pieces[PIECES-p];
  115.  
  116.    for(v=0;v<=PIECES-p;++v)
  117.    {
  118.       board[x][y]=val=pieces[v];
  119.       pieces[v] = lp;
  120.       s = CheckSums(x, y, board);
  121.       if(s != BOARD_BAD && p < PIECES) { Recurse(p+1, x, y+2, board, pieces); }
  122.       else if( p == PIECES && s == BOARD_GOOD) {ShowBoard(board); EXITON1SOL}
  123.       pieces[v] = val;
  124.    }
  125.    board[x][y] = -1;
  126. }
  127.  
  128. void InitPieces(int pieces[PIECES])
  129. {
  130.    int i;
  131.    for(i=0;i<PIECES;++i)
  132.       pieces[i]=i+1;
  133. }
  134.  
  135. void InitBoard(int board[HEIGHT][WIDTH])
  136. {
  137.    int x, y, w, inc, ex;
  138.  
  139.    for(y=0; y<HEIGHT; ++y)
  140.       for(x=0; x<WIDTH; ++x)
  141.          board[y][x] = 0;
  142.  
  143.    w = STARTW; inc = 1;
  144.    for(y=0; y<HEIGHT; ++y)
  145.    {
  146.       x = (WIDTH-w-w+1)/2;
  147.       ex = WIDTH-x;
  148.  
  149.       for(; x < ex; x+=2) board[y][x] = -1;
  150.  
  151.       if (w==HEIGHT) { inc = -1; w=HEIGHT-1; } else { w += inc; }
  152.    }
  153. }
  154.  
  155. void CheckProblem()
  156. {
  157.    int maxv, v, i;
  158.  
  159.    maxv=0;
  160.    v=PIECES;
  161.  
  162.    for(i=0; i<STARTW; ++i) {maxv += v--; }
  163.  
  164.    if (SEEKED > maxv)
  165.    {
  166.       printf ("No solution (max value on first line is %d (seeked %d) !\n",
  167.                 maxv, SEEKED);
  168.       exit(1);
  169.    }
  170.  
  171.    printf("Seekeing solutions for %d pos. board (%d to %d), sum=%d\n",
  172.                 PIECES, STARTW, HEIGHT, SEEKED);
  173. }
  174.  
  175. int main()
  176. {
  177.    int board[HEIGHT][WIDTH];
  178.    int pieces[PIECES];
  179.  
  180.    CheckProblem();
  181.  
  182.    InitPieces(pieces);
  183.    InitBoard(board);
  184.  
  185.    Recurse(1, 0, 0, board, pieces);
  186.    exit(FINALEXITCODE);
  187. }

Télécharger

 
 

Un message, un commentaire ?

modération a priori

Ce forum est modéré a priori : votre contribution n’apparaîtra qu’après avoir été validée par un administrateur du site.

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.

Les spams donneront systématiquement lieu à dépôt de plainte. Les messages peu aimables ou comportant trop de fautes d'orthographe seront purement et simplement supprimés sans publication.
ipv6 ready ipv6 test
Suivre ce site :
Recommander cette page :
Bookmark and Share
Traduire :