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.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef enum status { BOARD_INCOMP, BOARD_BAD, BOARD_GOOD } status;

#define HEIGHT 5 // Odd number
#define STARTW 3 // Width of first line < HEIGHT

#define WIDTH  ((2*HEIGHT)-1)
#define PIECES (HEIGHT*HEIGHT-STARTW*(STARTW-1))
#define SEEKED ((PIECES*(PIECES+1))/(2*HEIGHT))

//#define EXITON1SOL exit(0);

#ifdef EXITON1SOL
#define FINALEXITCODE 1
#else
#define FINALEXITCODE 0
#define EXITON1SOL  
#endif

status CheckLine(int i, int board[HEIGHT][WIDTH])
{
   int j, sum=0, val, *b;	
   status stat = BOARD_GOOD;

   b=&board[i][0];

   for(j=0;j<WIDTH;++j)
   {
      if((val = b[j]) < 0) stat=BOARD_INCOMP; 
      else { sum += val; }
   }
   if(sum != SEEKED && stat != BOARD_INCOMP) return BOARD_BAD;
   else if(sum > SEEKED) return BOARD_BAD;
   else if(sum == SEEKED && stat != BOARD_INCOMP) return BOARD_GOOD;
   return stat;
}

status CheckDiags(int ci, int cj, int board[HEIGHT][WIDTH])
{
   int i, j, sum, val, s;
   status lstat, stat = BOARD_GOOD;
   
   for (s=-1; s<=1; s+=2)
   {
      j = cj + s*ci;
      sum = 0; lstat = BOARD_GOOD;

      for(i=0;i<HEIGHT;++i)
      {
         if(i<0||i>=HEIGHT||j<0||j>=WIDTH) ;
         else if((val = board[i][j]) < 0) stat=lstat=BOARD_INCOMP;
         else sum += val; 
	 j-=s;
      }
      if(sum != SEEKED && lstat != BOARD_INCOMP) return BOARD_BAD;
      else if(sum > SEEKED) return BOARD_BAD;
      else if(sum == SEEKED && lstat != BOARD_INCOMP) stat = BOARD_GOOD;
   }
   return stat;
}

status CheckSums(int i, int j, int board[HEIGHT][WIDTH])
{
   if(CheckLine(i, board) == BOARD_BAD) return BOARD_BAD;
   return CheckDiags(i, j, board);
}

void FindNextFree(int *i, int *j, int board[HEIGHT][WIDTH])
{
   int dj=1+(*j>0);

   for(;*i<HEIGHT;++*i)
   {
      for(;*j<WIDTH;*j+=dj)
         if(board[*i][*j] < 0) return;
      *j=0; dj=1;
   }
   *i = -1; *j = -1;

   return;
}

void ShowBoard(int board[HEIGHT][WIDTH])
{
   int i, j, val;

   printf("\n+"); for(i=0;i<HEIGHT*3-1;++i) printf("--");
   printf("+\n");

   for(i=0;i<HEIGHT; ++i)
   {
      printf ("|");
      for(j=0;j<WIDTH; ++j)
      {
         if((val=board[i][j]) == 0) printf("   ");
	 else printf(" %2d", val);
      }
      printf(" |\n");
   }
   printf("+"); for(i=0;i<HEIGHT*3-1;++i) printf("--");
   printf("+\n");
}

void Recurse(int p, int x, int y, int board[HEIGHT][WIDTH], int pieces[PIECES])
{
   int val, v, lp;
   status s;

   FindNextFree(&x, &y, board);

   lp = pieces[PIECES-p];

   for(v=0;v<=PIECES-p;++v)
   {
      board[x][y]=val=pieces[v];
      pieces[v] = lp;
      s = CheckSums(x, y, board);
      if(s != BOARD_BAD && p < PIECES) { Recurse(p+1, x, y+2, board, pieces); }
      else if( p == PIECES && s == BOARD_GOOD) {ShowBoard(board); EXITON1SOL}
      pieces[v] = val;
   }
   board[x][y] = -1;
}

void InitPieces(int pieces[PIECES])
{
   int i;
   for(i=0;i<PIECES;++i)
      pieces[i]=i+1;
}

void InitBoard(int board[HEIGHT][WIDTH])
{
   int x, y, w, inc, ex;

   for(y=0; y<HEIGHT; ++y)
      for(x=0; x<WIDTH; ++x)
         board[y][x] = 0;

   w = STARTW; inc = 1;
   for(y=0; y<HEIGHT; ++y)
   {
      x = (WIDTH-w-w+1)/2;
      ex = WIDTH-x;

      for(; x < ex; x+=2) board[y][x] = -1;

      if (w==HEIGHT) { inc = -1; w=HEIGHT-1; } else { w += inc; }
   }
}

void CheckProblem()
{
   int maxv, v, i;

   maxv=0;
   v=PIECES;

   for(i=0; i<STARTW; ++i) {maxv += v--; }

   if (SEEKED > maxv)
   {
      printf ("No solution (max value on first line is %d (seeked %d) !\n",
                maxv, SEEKED);
      exit(1);
   }

   printf("Seekeing solutions for %d pos. board (%d to %d), sum=%d\n",
                PIECES, STARTW, HEIGHT, SEEKED);
}

int main()
{
   int board[HEIGHT][WIDTH];
   int pieces[PIECES];

   CheckProblem();

   InitPieces(pieces);
   InitBoard(board);

   Recurse(1, 0, 0, board, pieces);
   exit(FINALEXITCODE);
}

Messages

1. Solution du puzzle des nombres d’Aristote, 9 janvier 2022, 10:16, par Setti

Bonjour. J’ai utilisé excel pour résoudre le casse tête d’Aristote en utilisant des simplifications... La parité et en recherchant les triplets possibles de la couronne extérieure puis les 7 restants par équations, mais c’est trop long. L’utilisation des listes est trop limitatif dans les calculatrices scientifiques mais je fais qq tentatives. J’ai trouvé votre travail mais pouvez-vous me donner le langage utilisé ? Merci. Salutation
- 1. Solution du puzzle des nombres d’Aristote, 11 janvier 2022, 11:16, par Paul Courbis
  
  Bonjour
  Le programme donné est écrit en langage C
2. Solution du puzzle des nombres d’Aristote, 13 avril 2023, 16:54, par taton

Pouvez-vous donner l’astuce pour résoudre ce puzzle… C’est très intéressant.. Merciiii
- 1. Solution du puzzle des nombres d’Aristote, 17 avril 2023, 15:36, par Paul Courbis
  
  L’astuce a juste été d’écrire un programme explorant de manière optimisée l’ensemble des dispositions possibles et d’afficher celles qui répondent aux contraintes...
3. Solution du puzzle des nombres d’Aristote, 9 août, 08:50, par Marbois

Bonjour,
Pouvez-vous me donner le programme en C ou autre permettant de trouver facilement toutes les solutions possibles ?
Merci.
- 1. Solution du puzzle des nombres d’Aristote, 10 août, 09:49, par Paul Courbis
  
  Le code est en bas de la page !

Un message, un commentaire ?

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

Suivre ce site : Follow @courbis_fr

Recommander cette page :

	Tweeter

Traduire :

Solution du puzzle des nombres d’Aristote

Messages

Un message, un commentaire ?

Réalisations

Dans la même rubrique