From: Daniel Martin <martin@...>
Date: 2006-08-14T14:42:51+09:00
Subject: Re: [QUIZ] Pen and Paper (#90)

Here's my solution.  It's pretty similar in terms of fundamental
algorithm to what's gone before - that is, it simply tries a full
search, then tries again if it hits a dead end, then again.  At each
point, it chooses to jump to the square with the fewest remaining open
spots.  Nothing that hasn't already been posted.

However, check out this timing for solving a 100x100 search:

real    0m1.640s
user    0m0.121s
sys     0m0.031s

Of course, that's when it solves the problem the first time, which it
does maybe 1/4 of the time.  (When it doesn't find a solution the
first time, it seems to take many more re-attempts than one would
expect - I don't have an explanation for that)

My secret is NArray.  I was so impressed with its performance on quiz
86 that I decided to use it to tackle this problem too.  I'm sure that
there's more I could do to push even more of the algorithm into NArray
internals, but this is pretty fast already.

The best way to explain the code is to look at the different NArray
objects I use:

  tracker - this is an n by n array that notes where I've been.
            It's 1 for spots I have NOT visited, and 0 for
            spots I have.

  zoomarray - this is a 13 by 13 array that I use to focus
              on the part of tracker that's relevant to
              computing where I can go and how many free
              spots each of my destinations has.  This
              simplifies my code, since I don't have to
              worry about the current position or whether
              I'm close to a wall once I get zoomarray 
              set up - the current position is always
              (6,6) in zoomarray.

  jumparray - this is an array with dimensions
              (13,13,2,8) - the easiest way to think
              about it is as two parallel arrays
              that each contain 8 objects the same
              shape as zoomarray.
              jumparray(true,true,0,n), where n
              is from 0 to 7, has a "1" in the
              spot where I'd get to if I jumped
              in direction number "n".
              jumparray(true,true,1,n) has a "1"
              in every one of the places I could
              jump to if I jumped in direction n.

(See the variable jumppatterns for the meaning of "direction n")

This means that I can do this below in the code:
    workarr = zoomarray * jumparray
    workarr = workarr.sum(0,1)
with the end result that workarr is a structure like this:
NArray.byte(2,8):
[ [ 0, 0 ],
  [ 0, 0 ],
  [ 0, 2 ],
  [ 1, 3 ],
  [ 1, 5 ],
  [ 1, 3 ],
  [ 0, 2 ],
  [ 0, 0 ] ]

The first column tells me if I can jump in that direction at all, and
the second column tells me how many free spots my destination has.
The example is what I get on a 6x6 board when starting in the corner
at (0,0).

To the number of free spots, I add a random number between 0 and 1 so
that I randomize the choice of where to jump in the case of a tie.

Note that I don't use NArray to track my history; among other things,
for speed I wanted to use byte-typed NArrays and that won't work once
we get a board larger than 16 by 16.  Instead, I keep my history of
where I've been in one long list and then convert that into a ruby
Array-of-Arrays immediately prior to printing out the solution.

------------penpaper.rb--------------
require 'narray'

n = (ARGV.first||'6').to_i
tracker = NArray.byte(n,n)
jumparray = NArray.byte(13,13,2,8)

jumppatterns = [[-2,-2],[-3,0],[-2,2],
[0,3],[2,2],[3,0],[2,-2],[0,-3]]

jumppatterns.each_with_index{|(x,y),z|
  basex,basey = 6+x,6+y
  jumparray[basex,basey,0,z]=1
  jumppatterns.each{|x2,y2|
    jumparray[basex+x2,basey+y2,1,z]=1
  }
}
zoomarray = NArray.byte(13,13)
randarray = NArray.float(8)
loopctr = 1
foundit=false
pospath=[]
while !foundit
  tracker[] = 1
  x=rand((n/2.0).ceil)
  y=0
  pospath=[[x,y]]

  while pospath.size < n*n
    tracker[x,y] = 0
    zoomarray[] = 0
    left,right,top,bottom=x-6,x+6,y-6,y+6
    left=0     if left<0
    top=0      if top<0
    right=n-1  if right>=n
    bottom=n-1 if bottom>=n
    zoomarray[left-(x-6),top-(y-6)] =
      tracker[left..right,top..bottom]
    workarr = zoomarray * jumparray
    workarr = workarr.sum(0,1)
    randarray.random!
    randarray.add!(workarr[1,true])
    j = randarray.eq(randarray[workarr[0,true]].min).where[0]
    if (randarray[j] < 1 and pospath.size < n*n-1)
      # drat.  Try again
      break
    end
    x += jumppatterns[j][0]
    y += jumppatterns[j][1]
    pospath << [x,y]
  end
  if pospath.size == n*n
    foundit = true
    puts "Found solution on trial #{loopctr}:"
    a = Array.new(n){Array.new(n){nil}}
    pospath.each_with_index{|(x,y),z| a[x][y]=z+1}
    len = 1 + (n*n).to_s.length
    puts('-' * (len*n + 2))
    a.each{|m|
      print '|'
      m.each{|s| print("%#{len}d" % s)}
      puts '|'
    }
    puts('-' * (len*n + 2))
  else
    loopctr += 1
  end
end