Heuristic function in an algorithm of First-Best search for the problem of Tower of Hanoi: optimal route for n disks

Headnote

Abstract - Along this paper we propose a new algorithm for solving the Tower of Hanoi puzzle. We focus on computer memory efficiency by applying the Artificial Intelligence 's method "Best-First Search ". We develop the algorithm with detailed explanations, taking in mind it may be coded in any programming language. Furthermore, we set a heuristic function and several mathematical definitions, diagrams, and examples in order to make the reader understand fully. Finally, we present the solution implemented in python, adding proofs of its logical functioning as well as results about execution time made for 16 cases (from using only 3 disks until 18).

Keywords: Tower of Hanoi, best-first search, heuristic, function, python.

(ProQuest: ... denotes formulae omitted.)

1 Introduction

The Tower of Hanoi, mathematical puzzle, is an example to apply programming techniques such as recursive algorithms [1][2]. Recursive algorithms are relatively simple to implement in most programming languages. These algorithms aid to solve a wide variety of problems and have been selected, by software companies such as Microsoft [8], Oracle, and Facebook, and at robotics challenges [3], to test the aspirants programming abilities. Mainly in the first stage of the recruitment process. These companies change the constraints of the puzzle to increase the complexity of the algorithm. For example, changing the number of disks the algorithm has to solve for.

However, as the authors describe in [5], solving this problem by a recursive algorithm takes up a lot of computing resources. And, although many algorithms have been developed, few times they are measured in efficiency and memory spending.

Thereby we put forward a method where we minimize the use of memory.

First we take as a base a 3D model from the original Hanoi Tower. From there, we make a geometric projection to a 2D model (new model). Then, we redefine the allowed movements from 3D model, now for the 2D model. At the end we abstract the new model like an array or a list for each tower (depending on the programming langue which is talking on).

Having this abstraction, we proceed to establish an evaluation function which is the main point of the algorithm.

Solving this problem by different methods has a great relevance. It is not only related with the...