From: John Baylor <john.baylor@...>
Date: 2006-08-18T00:36:47+09:00
Subject: [QUIZ] Solution to #90

------=_Part_159584_9769599.1155829003296
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

------=_Part_159584_9769599.1155829003296--