# Best-First Algorithm in Ruby?

**URL:** <https://www.ruby-forum.com/t/best-first-algorithm-in-ruby/175709>\
**Category:** Ruby\
**Created:** [September 18, 2009, 7:10am UTC](https://www.ruby-forum.com/t/best-first-algorithm-in-ruby/175709 "2009-09-18T07:10:57Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![masonkessinger](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/4da419/32.png) [@masonkessinger](https://www.ruby-forum.com/u/masonkessinger)\
**Post date:** [September 18, 2009, 7:10am UTC](https://www.ruby-forum.com/t/best-first-algorithm-in-ruby/175709/1 "2009-09-18T07:10:57Z")

</div>

I am writing a Best-First Search program in Ruby but I have never done  
tree  
searches before and so am a bit lost. This routine is being applied to  
the  
8-puzzle problem of moving 8 tiles plus a blank space in an 3 x 3 grid.  
Since I am new to both Ruby and search algorithms in general, I a  
looking  
for a template or actual code as a Ruby program. I’ve already written  
the  
Manhattan move method to determine the heuristic value of each state,  
and  
the move function for making a move, and a third method for determining  
what  
moves are possible. But writing the first-best routine without some  
template to use is beyond my current capabilities. I’m trying to move  
beyond that limitation.

I’ve done a Google search and referenced five books on Ruby and not  
found  
any good template, pseudo code, or even a Ruby routine that would do the  
searches. Does anyone know of a coded example in Ruby of the Best-First  
search algorithm? It it is applied to the 8-puzzle that is even better,  
but  
if I can find a template I should be able to apply it to my problem.

Thanks in advance for being pointed in the right direction.

Always something new to learn.

No Sam

---

<div class="post-metadata">

**Author:** ![masonkessinger](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/4da419/32.png) [@masonkessinger](https://www.ruby-forum.com/u/masonkessinger)\
**Post date:** [September 18, 2009, 11:07am UTC](https://www.ruby-forum.com/t/best-first-algorithm-in-ruby/175709/2 "2009-09-18T11:07:29Z")

</div>

-------- Original-Nachricht --------

> Datum: Fri, 18 Sep 2009 14:10:27 +0900  
> Von: Mason K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
> An: removed\_email\_address@domain.invalid  
> Betreff: Best-First Algorithm in Ruby?

> I am writing a Best-First Search program in Ruby but I have never done  
> tree  
> searches before and so am a bit lost. This routine is being applied to  
> the  
> 8-puzzle problem of moving 8 tiles plus a blank space in an 3 x 3 grid.

Dear Mason,

> Since I am new to both Ruby

welcome!  
If you are looking for a nice and short introduction to Ruby, you can  
have  
a look at this tutorial :

[http://pine.fm/LearnToProgram/?Chapter=00](http://pine.fm/LearnToProgram/?Chapter=00)

It’s an introduction that will take you all the way from no computing  
knowledge at all to coding object-orientedly … so maybe it is a good  
idea to go through this first.

With respect to search algorithms, your problem can be solved using the  
A\* algorithm, which is a best-first search algorithm. You can  
find a description of how to apply it here:

[http://www.redfish.com/dkunkle/mypapers/EightPuzzle.pdf](http://www.redfish.com/dkunkle/mypapers/EightPuzzle.pdf) ,

In the Ruby community, there is a collection of problems and Ruby  
solutions called Ruby quiz, whose solutions are thoughtfully commented  
by the maintainers of the quiz.  
A\*-search is here:

[http://rubyquiz.com/quiz98.html](http://rubyquiz.com/quiz98.html)

And of course, you can adapt the pseudocode on the Wikipedia A\* search  
page.

Best regards,

Axel