# Solution to #90

**URL:** <https://www.ruby-forum.com/t/solution-to-90/225916>\
**Category:** Ruby\
**Created:** [August 17, 2006, 5:38pm UTC](https://www.ruby-forum.com/t/solution-to-90/225916 "2006-08-17T17:38:40Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![johnnybutler7](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/8491ac/32.png) [@johnnybutler7](https://www.ruby-forum.com/u/johnnybutler7)\
**Post date:** [August 17, 2006, 5:38pm UTC](https://www.ruby-forum.com/t/solution-to-90/225916/1 "2006-08-17T17:38:40Z")

</div>

The week is nearly up but here is my solution. My program solved it for  
5  
and 6 in about a second but is taking much longer for the rest.

(5…10).each { |i| Quiz90.new(i).solve }  
Success after 440 iterations!  
±------------------+  
| 13 3 22 14 4|  
| 24 16 11 25 17|  
| 21 8 5 20 9|  
| 12 2 23 15 1|  
| 6 19 10 7 18|  
±------------------+  
Success after 19953 iterations!  
±----------------------+  
| 6 26 12 7 27 13|  
| 23 9 4 24 10 1|  
| 17 33 21 18 36 31|  
| 5 25 11 8 28 14|  
| 22 19 3 32 20 2|  
| 16 34 29 15 35 30|  
±----------------------+

class Array  
def shuffle  
ret = self.dup  
len = self.length  
rand(2\*len).times do  
r1 = rand(len)  
r2 = rand(len)  
ret[r1],ret[r2] = ret[r2],ret[r1]  
end  
return ret  
end  
end

class Point  
attr\_accessor :x, :y

# two constructors in one!

# x,y for creation from integers

# “[x,y]” for creation from a Point.to\_s string

# 

# This is needed for a hash lookup because the hash lookup using a

point

# with a certain xy value can’t be found with a different point that

has

# the same xy values. Arrrgh! Am I just doing something wrong?

def initialize \*args  
if 2 == args.length  
@x = args[0]  
@y = args[1]  
else  
@x,@y = args[0].gsub(/[|]/,’’).split(’,’)  
@x = @x.to\_i  
@y = @y.to\_i  
end  
end

# reminder: “==” implicitly defines “!=”

def == (aPoint)  
aPoint.x == x and aPoint.y == y  
end

def + relativePoint  
Point.new( x + relativePoint.x,  
y + relativePoint.y )  
end

def to\_s  
“[#{x},#{y}]”  
end  
end

class Quiz90  
attr\_accessor :size, :grid

def initialize( sz )  
@dead\_ends = 0  
sz = 5 if sz \< 5 # minimum solvable size  
@size = sz  
@jumps = [ Point.new(-3,0), Point.new(3,0),  
Point.new(0,-3), Point.new(0,3),  
Point.new(-2,-2), Point.new(-2,2),  
Point.new(2,-2), Point.new(2,2) ]  
@grid = {}  
(1…sz).each do |x|  
(1…sz).each do |y|  
@grid[Point.new(x,y).to\_s] = 0  
end  
end  
end

def solve  
start\_positions = @grid.keys

```
start_positions.shuffle.each do |pos|
  solution = place_next_number( 1, Point.new(pos), @grid )
  #self.print( "Solution!", solution ) if solution
end

```

end

def dead\_end( n, g )  
@dead\_ends += 1  
#self.print( “Dead end #{@dead\_ends} after #{n} moves:”, g ) if  
(@dead\_ends % 10) == 0  
end

# place\_next\_number

# 

# Return nil unless we’re finished

# 

def place\_next\_number( number, pos, g )  
#puts “place\_next\_number( #{number}, #{pos} ) =\> #{g[pos.to\_s]}”  
#return nil if @dead\_ends \>= 50  
return nil unless g[pos.to\_s] and g[pos.to\_s] == 0  
g[pos.to\_s] = number  
if number == (@size \* @size)  
#pp pos  
self.print( “Success after #{@dead\_ends} iterations!”, g )  
return g  
end  
@jumps.shuffle.each do |jump|  
return g if place\_next\_number( number + 1, pos+jump, g )  
dead\_end( number, g )  
end  
g[pos.to\_s] = 0  
return nil  
end

def print( text, g )  
puts text  
puts “+#{’-’_(4_@size-1)}+”  
(1…@size).each do |x|  
line = []  
(1…@size).each do |y|  
#line \<\< g[Point.new(x,y).to\_s]  
line \<\< sprintf("%3d",g[Point.new(x,y).to\_s])  
end  
puts “|#{line.join(’ ')}|”  
end  
puts “+#{’-’_(4_@size-1)}+”  
end  
end