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

 
 

Messages

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. Aucune obligation de publication ne pourra être opposée au webmaster, sauf éventuel droit de réponse dûment justifié.
ipv6 ready ipv6 test
Suivre ce site :
Recommander cette page :
Bookmark and Share
Traduire :

Réalisations


Dans la même rubrique

1988-2024 Courbis, « LE » Blog Officiel
Plan du site | | Contact | RSS 2.0

SPIP