Skip to content

The purpose of this project is to resolve the Eternity 2 puzzle. It use genetic algorithms and the islands method. It's write in python. It's a french project, the README will be translate soon.

Notifications You must be signed in to change notification settings

nathan-pichon/Eternity2-research

Repository files navigation

puzzleOfDoom

Etude du problème:

  • Un puzzle est composé de 256 pièces.

  • Chaque pièce est composée de 4 faces

  • Chaque pièce peut être disposée sur le plateau suivant un axe x ou y

  • Chaque pièce peut être tournée

  • Différentes méthodes de résolution du puzzle ont déjà été exploités :

    • Equerre => Triangle => Carré
    • Bordure => intérieur
  • Différents algorithmes :

    • tabu search
    • backtrack

Etude des possibilités

  • Différentes îles:
    • Une par mutation:
      • rotation mutation => un gène tourné
      • swap mutation => échange deux gènes
      • swap & rotate => échange deux gènes et les tournes
      • rotate region mutation => prend une région >= 4 gènes et la tourne
      • swap region mutation => échange deux régions
      • region inversion mutation => inverse la position des gènes dans une région
      • row and column inversion mutation => swap deux gènes cote à cote
      • scramble mutation => garde un coin du plateau et mélange le reste
    • Une par croisement:
      • region exchange crossover => clone les deux parents et échange deux régions
      • uniform crossover => même chose que region exchange, sauf qu'on crée un template de régions 1 et 2 et on attribut les gènes correspondants au parent 1 ou 2 en fonction du template
      • rotation crossover => même chose que region exchange avec de la rotation
    • Une par choix de départ (0, 1 ou 5 indices)

Faire tourner chaque algo-genetic en solo pour calculer la fiabilité de chaque algo

Notation du projet

  • La cotation du projet se fait sur le nombre de bords de pièces qui matchent.
  • Le score maximal à atteindre pour la soutenance est 480
  • Le score maximal trouvé est de 467

About

The purpose of this project is to resolve the Eternity 2 puzzle. It use genetic algorithms and the islands method. It's write in python. It's a french project, the README will be translate soon.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published