Blog du grouik

Il y a des challenges absurdes sans intérêt tels que coder une calculatrice en Fortran, ou construire une cathédrale avec des allumettes. Là je me suis imposé d'écrire l’algorithme qui joue aux tours de Hanoï.

Il teste toutes les combinaisons, mais s’arrête lorsqu'il retombe sur une configuration (placement des disques) déjà connue.

Le challenge dans le challenge, c'est de faire court. L'algorithme en lui même tient en une trentaine de lignes:

<?php
/*
* Hanoi towers ' resolver
* Copyright (C) 2017 Gnieark https://blog-du-grouik.tinad.fr/
* licensed under the terms of the GNU General Public V3. See License file.
*/
$discCount = 6;
//load the class
include("inc.php");
$tower = new Tower($discCount);
$steps = new Steps(array());
$steps->add_step($tower);
resolveHanoi($tower,$steps);
function resolveHanoi(Tower $tower, Steps $steps){
    $result = false;
    
    if($tower->is_won()){
      echo "a winning suite was found:\n";
      foreach($steps->steps as $oneTower){
        echo $oneTower."\n";
      }
      return true;
    }
    $availablesMoves = $tower->list_moves_availables();
    
    foreach($availablesMoves as $move){
      $newTower = $tower->add_move($move);
      $newSteps = $steps;
 
      if($newSteps->add_step($newTower)){
        $r = resolveHanoi($newTower,$newSteps);
        if($r){
          $result = true;
        }
      }
    }
    return $result;
}

L'ensemble du dépôt (dont les classes PHP écrites et utilisées ci dessus) est sur mon dépot github https://github.com/gnieark/Hanoi-towers