Executa uma busca em extensao no quebra-cabeça das 8 pessoas e exibe a solução.

Jogo8.rb

# Jogo dos 8 - Busca em extensão
# Rafael Polo
# 01 Mai 2011


class Jogo8	

	# lê estado inicial e final de arquivos
	def initialize()	
		estado_inicial = to_array(File.open("inicio.txt").read)
		@no_inicial = No.new(0, 0, nil, estado_inicial)
		@estado_final = to_array(File.open("final.txt").read)
		@nos_abertos = [] #FIFO
		@time = Time.now
		@no = 0
	end
	
	# converte matrix 3x3 num array[9] linear
	def to_array(matriz)
		return matriz if matriz.class == Array
		vet=[]
		matriz.each_line do |linha|
			linha.split(" ").each do |piece|
				vet << piece
			end
		end	
		vet
	end
		
	# troca 0 pela posição indicada no array
	def troca(array, pos)		
		array[array.index("0")] = array[pos]
		array[pos] = "0"
		array
	end

	# move 0 pra cima
	def move_cima(no)
		estado = no.estado.clone
		vazio = estado.index("0")
		return false if vazio < 3
		index_cima = estado.index(estado[vazio-3])				
		estado_cima = troca(estado, index_cima)
		# Se não existir nó aberto com esse mesmo estado, cria
		if !No.existe_estado?(estado_cima)		
			no_cima = No.new(@no+=1, no.id, "cima", estado_cima)
			puts "\nNó #{no_cima.id} - Cima:"
			no_cima.imprime		
			expandiu(no_cima)
		end
	end

	# move 0 pra baixo
	def move_baixo(no)
		estado = no.estado.clone
		vazio = estado.index("0")
		return false if vazio > 5
		index_baixo = estado.index(estado[vazio+3])			
		estado_baixo = troca(estado.clone, index_baixo)
		# Se não existir nó aberto com esse mesmo estado, cria
		if !No.existe_estado?(estado_baixo)	
			no_baixo = No.new(@no+=1, no.id, "baixo", estado_baixo)
			puts "\nNó #{no_baixo.id} - Baixo:"
			no_baixo.imprime		
			expandiu(no_baixo)
		end
	end

	# move 0 pra direita
	def move_direita(no)
		estado = no.estado.clone
		vazio = estado.index("0")
		return false if vazio==2 || vazio==5 || vazio==8
		index_direita = estado.index(estado[vazio+1])			
		estado_direita = troca(estado.clone, index_direita)
		# Se não existir nó aberto com esse mesmo estado, cria
		if !No.existe_estado?(estado_direita)	
			no_direita = No.new(@no+=1, no.id, "direita", estado_direita)
			puts "\nNó #{no_direita.id} - Direita:"
			no_direita.imprime		
			expandiu(no_direita)
		end
	end
	
	# move 0 pra esquerda
	def move_esquerda(no)
		estado = no.estado.clone
		vazio = estado.index("0")
		return false if vazio==0 || vazio==3 || vazio==6
		index_esquerda = estado.index(estado[vazio-1])			
		estado_esquerda = troca(estado.clone, index_esquerda)
		# Se não existir nó aberto com esse mesmo estado, cria
		if !No.existe_estado?(estado_esquerda)	
			no_esquerda = No.new(@no+=1, no.id, "esquerda", estado_esquerda)
			puts "\nNó #{no_esquerda.id} - Esquerda:"
			no_esquerda.imprime		
			expandiu(no_esquerda)
		end
	end
	
	def expandiu(no)
		# verifica se é estado final
		if no.estado == @estado_final
			puts "\nBINGO!"
			
			# busca nó pai do estado meta até o nó inicial
			caminho = []
			caminho << no.id
			no_pai_id = no.id_pai
			while (no_pai_id>0)
				caminho << no_pai_id
				no_pai_id = No.pega_no(no_pai_id).id_pai
			end
			caminho.reverse!
			puts "\n#{caminho.count} passos para resolução: "
			# mostra operações realizadas
			resultado = "INICIO > "
			caminho.each do |no|
				op = No.pega_no(no).operacao
				resultado +=  op + " > "
			end
			puts resultado + "FIM"
			# milisegundos
			mls = (Time.now - @time) * 1000
			puts "\nResultado encontrado em #{mls} milisegundos\n\n"
			exit()
		else			
			# adiciona à lista de nos abertos
			@nos_abertos << no
		end
		no
	end
	
	# Expande! Realiza os movimentos possíveis no estado
	def expande(no)
		move_cima(no)		
		move_direita(no)		
		move_baixo(no)
		move_esquerda(no)
	end
	
	def busca_extensao
		puts "\n======== Estado Inicial ========\n\n"			
		@no_inicial.imprime		
		@nos_abertos << @no_inicial					
		# enquanto há nós abertos, os expande
		@nos_abertos.each do |no|
			puts "\n======== Nó #{no.id} Expandido ========\n"
			expande(no)
		end
			
	end
	
end

class No
	attr_accessor :id, :id_pai, :operacao, :estado
	
	def initialize(id, id_pai, op, estado)
		@id = id
		@id_pai = id_pai
		@operacao = op
		@estado = estado
	end

	# formata array[9] em matriz 3x3
	def imprime
		array = @estado
		puts "#{array[0]} #{array[1]} #{array[2]}\n#{array[3]} #{array[4]} #{array[5]}\n#{array[6]} #{array[7]} #{array[8]}\n"	if array.class == Array	
	end

	# retorna nó pelo id
	def self.pega_no(id)
		esse = nil
		ObjectSpace.each_object(No) do |no|
			esse = no if no.id == id
		end
		esse
	end
	
	# existe nó com estado igual?
	def self.existe_estado?(estado)
		existe = false
		ObjectSpace.each_object(No) do |o|
			existe = true if o.estado == estado
		end
		existe
	end
	
end

jogo = Jogo8.new()
jogo.busca_extensao

Lê inicio.txt e busca final.txt. output.txt:

======== Estado Inicial ========

1 0 3
4 2 6
7 5 8

======== Nó 0 Expandido ========

Nó 1 - Direita:
1 3 0
4 2 6
7 5 8

Nó 2 - Baixo:
1 2 3
4 0 6
7 5 8

Nó 3 - Esquerda:
0 1 3
4 2 6
7 5 8

======== Nó 1 Expandido ========

Nó 4 - Baixo:
1 3 6
4 2 0
7 5 8

======== Nó 2 Expandido ========

Nó 5 - Direita:
1 2 3
4 6 0
7 5 8

Nó 6 - Baixo:
1 2 3
4 5 6
7 0 8

Nó 7 - Esquerda:
1 2 3
0 4 6
7 5 8

======== Nó 3 Expandido ========

Nó 8 - Baixo:
4 1 3
0 2 6
7 5 8

======== Nó 4 Expandido ========

Nó 9 - Baixo:
1 3 6
4 2 8
7 5 0

Nó 10 - Esquerda:
1 3 6
4 0 2
7 5 8

======== Nó 5 Expandido ========

Nó 11 - Cima:
1 2 0
4 6 3
7 5 8

Nó 12 - Baixo:
1 2 3
4 6 8
7 5 0

======== Nó 6 Expandido ========

Nó 13 - Direita:
1 2 3
4 5 6
7 8 0

BINGO!

3 passos para resolução:
INICIO > baixo > baixo > direita > FIM

Resultado encontrado em 5.108 milisegundos