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