Pen and Paper (#90)

Ruby
21

On Aug 12, 2006, at 3:53 PM, Morton G. wrote:

You mean your first solution was cut and paste from the quiz
posting? That’s really cheating!
That’s what I did, too

You’re cracking me up. :wink:

In all fairness, I really would love to go back and add the solver,
but I am very, very busy this weekend. :frowning: We will see if I can
steal the time.

I bet we’re about to see some solvers tomorrow though… :wink:

but I was naive enough to believe you wrote a script that generated
at least one solution. :slight_smile:

The quiz said to build a solution that goes as fast as possible.
Then it gave me an idea for a hell of a shortcut. I couldn’t
resist. :smiley:

James Edward G. II

22

Is it acceptable to roll over the edges to the other side?

Please do! You might come up to interesting results by mapping the
square on a
torus.
And I bet that finding a solution rolling over edges is easier that way.

I wrote a solution that did, but then I thought perhaps that wasn’t
acceptable.

Can you still modify your solution to fit the initial goal?

Bob

23

Great explanation indeed!

Thank you very much for making this quiz easier to understand Suraj :slight_smile:

Eric

PS:
Do you also receive my emails twice?
Do you know where the problem can be?

24

Eric, if you use Gmail, it’ll show up twice because Gmail adds your
response as well as the email you get of what you just sent back from
the list. So, in effect, you keep your response as well as getting
your response back, and Google shows it twice.

:slight_smile: Sorry to be off topic!

M.T.

25

Thanks for your explanation Matt!

So if I get it right, the important thing is that I’m not bothering the
mailing list with double messages?

Sorry for being off topic too!

Eric

Am Sonntag, 13. August 2006 11:37 schrieb Matt T.:

26

Here’s my first solution. I have two completely different ones:

it works by assigning each square a point value based on how many
squares its connected to (there’s a whole second matrix for this). i
visit places with low point values first b/c they are harder to get
to. each move updates the values of places next to it. for a 50x50
game it fails roughly half the time. usually wins 10x10, maybe 90%.

require “pp”
$s = ARGV[0].to_i

if $s <= 0
$s = 10
end

printboard = true

if ARGV[1]
if ARGV[1] == “y”
printboard = true
end
if ARGV[1] == “n”
printboard = false
end
end

$board = Array.new($s) {Array.new($s) {nil}}

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

def coord_to_connected coord
res = []
Connections.each do |conn|
x,y=coord
dx,dy=conn
x += dx
y += dy
res << [x,y] if x >= 0 and x < $s and y >= 0 and y < $s
end
res
end

$score_board = Array.new($s) {[]}

$s.times do |i|
cur = $score_board[i]
$s.times do |j|
cur << coord_to_connected([i,j]).length
end
end

def success?
$board.each { |r| return false if r.include? nil }
true
end

def goto sq
$count += 1
$pos = sq
x,y=sq
$board[x][y] = $count
coord_to_connected(sq).each do |sq|
$score_board[x][y] = -1
x2,y2=sq
$score_board[x2][y2] -= 1
end
end

$count = 0
goto [0,0]

while true
options = coord_to_connected $pos
options.reject! {|sq| x,y=sq; not $board[x][y].nil?}
options.map! { |e| [$score_board[e[0]][e[1]], e] }
options = options.sort_by {|e| [e[0], rand]}
if options.length == 0
break
end
goto options.first[1]
end

if printboard
pp $board
end

if success?
puts “success”.upcase
else
puts “failed”.upcase
end

27

Here is my second solution.

Timings are on bottom but include size=15000 in under 5min. The way
this works is it starts with two solved 5x5 games with special
properties (end in center, and start on either the middle of the top,
or the middle of the left side – pretty print them if that’s
confusing). it then places as many of those as needed to fill the
entire board. it also has to deal with incrementing the numbers in
the original 2 patterns. i included some test code which makes sure
the final solution is valid.

The way placing the 5x5 pre-solved patterns works is i make a column
with a “left” on top and all the rest are the “up” variety. moving
from the middle of a 5x5 grid straight down takes you one square off
the grid, to they line up and all connect. now we’re in the middle of
the bottom 5x5 pattern, so what we need is to move right and have
that transition to the next pattern, and then go back up to the top,
then back down again, etc to get the second variety of column which
goes back up, i just reversed the rows in the first column. before
combining the columns for the final solution, they are transposed to
be rows so I can just use +

maybe a better way to get a feel for how it works is to set the size
to 10 or 15 and pp the solution. then scan the answer for
1,25,26,50,51,75 etc to see how it’s laid out

require “pp”
s = ARGV[0].to_i

if s <= 0
s = 165
end

if s % 5 != 0
puts “Invalid Input. Must be multiple of 5.”
exit
end

Left = [[17, 9, 2, 18, 24], [4, 14, 22, 7, 13], [1, 19, 25, 10, 20],
[16, 8, 3, 15, 23], [5, 11, 21, 6, 12]]

Up = [[17, 4, 1, 16, 5], [9, 14, 19, 8, 11], [2, 22, 25, 3, 21], [18,
7, 10, 15, 6], [24, 13, 20, 23, 12]]

num = s / 5
$items_in_a_column = 25 * num

$inc_col_count = -$items_in_a_column
def inc_col m
$inc_col_count += $items_in_a_column
m.map { |e| e.map { |e2| e2 + $inc_col_count} }
end

$inc_count = 0
def inc m
$inc_count += 25
m.map { |e| e.map { |e2| e2 + $inc_count} }
end

col = Left
(num-1).times do |j|
col += inc(Up)
end

col2 = col.reverse.transpose
col = col.transpose

sol = []

(num/2).times {sol += inc_col(col) + inc_col(col2)}

if num % 2 == 1
sol += inc_col(col)
end

pp sol

=========

= tests =

=========

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

def check_valid_movement m
flat = m.flatten
n = flat.length
rt_n = Math.sqrt(n).to_i
1.upto(n-1) do |i|
a = flat.index i
b = flat.index i+1
fail “num not found #{i}” if a.nil? or b.nil?
x1 = a % rt_n
y1 = a / rt_n
x2 = b % rt_n
y2 = b / rt_n
move = [x1-x2, y1-y2]
return false unless Connections.include? move
end
true
end

if true # warning: SLOW. took 9 minutes with size = 265. it’s n^4 if
you treat the input number as n.
fail “dups” unless sol.flatten.uniq.length == sol.flatten.length
fail “invalid moves” unless check_valid_movement(sol)
puts “valid moves!”
end

END

cg5:~/cs/rb/quizzes >time ruby 90take3.rb 10000

real 1m34.483s
user 1m29.471s
sys 0m3.695s

cg5:~/cs/rb/quizzes >time ruby 90take3.rb 15000

real 4m47.336s
user 4m30.390s
sys 0m11.935s

cg5:~/cs/rb/quizzes >time ruby 90take3.rb 25000

real 23m0.525s
user 21m47.343s
sys 0m50.721s

26700 = gave up after 45min, incomplete. 30000 = gave up after 3
hours, incomplete.

28

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Here is my solution, which uses recursion like the Civilization II
map generation example in Chris P.'s “Learn to Program” book.

With a stack limit of:

$ ulimit -s
8192

the maximum square size my solution can handle is 67x67. However, it
can handle larger squares if you increase the stack size.

Cheers.

#!/usr/bin/ruby -w

@param 1 width of square

@param 2 starting row (X coordinate)

@param 3 starting column (Y coordinate)

class Square < Array
def initialize aWidth
super(aWidth) { Array.new aWidth }
@mark = 0
end

Walks this square, from the given position,

while marking unmarked (nil) cells.

def walk x, y
# skip invalid positions and marked cells
return if
x < 0 or x >= length or
y < 0 or y >= length or
self[x][y]

# mark the current cell
  self[x][y] = @mark += 1

# walk to adjacent cells
  walk x + 3, y     # east
  walk x + 2, y - 2 # north east
  walk x,     y - 3 # north
  walk x - 2, y - 2 # north west
  walk x - 3, y     # west
  walk x - 2, y + 2 # south west
  walk x,     y + 3 # south
  walk x + 2, y + 2 # south east

end

Pretty-prints this square.

def to_s
# pretty-print each row
fmt = ‘|’ << "%#{length.to_s.length * 2}d " * length << ‘|’

  lines = inject([]) do |memo, row|
    memo << fmt % row
  end

# add a border to top & bottom
  border = '-' * lines.first.length

  lines.unshift border
  lines << border

lines.join("\n")

end
end

if $0 == FILE

create a square with user’s parameters

width = (ARGV.shift || 5).to_i
square = Square.new(width)

walk the square from random position

origin = Array.new(2) { (ARGV.shift || rand(width)).to_i }
square.walk(*origin)

pretty-print the walked square

puts square.to_s

end
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE32aYmV9O7RYnKMcRAqRyAKCxvnyB1ncwLl4IhM6vg20wjKz9AACfTZgC
yQFdSn2EBLE1YWrts0TGRXk=
=4dbC
-----END PGP SIGNATURE-----

29

Here’s my solution, which works the same way as Elliot’s first solution,
although with very different code:
It picks a random starting position, then finds all available moves from
there, sorts them randomly, then picks the one with the fewest moves
available.
Without the random sort, you’ll always move in a similar pattern. It
seems to work a little bit better with the random sort.

I also ended up spending some time on getting nice looking output. :slight_smile:
And it could certainly be made more efficient.

class Board
def initialize(size)
@board = Array.new(size) { Array.new(size) { ‘.’ } }
@size = size
@current = 1
end

#Checks if the spot at (x, y) is available
def available?(x, y)
    if x >= 0 and x < @size and y >= 0 and y <= @size
        @board[x][y] == '.'
    else
        false
    end
end

#Returns a list of pairs which can be reached from (x, y)
def available_from(x, y)
    available = [[x, y - 3], [x + 2, y - 2], [x + 3, y], [x + 2, y +

2], [x, y + 3], [x - 2, y + 2], [x - 3, y],[x - 2, y - 2]].map { |pair|
available?(*pair) ? pair : nil }.compact
end

#Checks if the board is completed
def full?
    @size**2 < @current
end

#Marks the spot at (x,y)
def mark(x, y)
    if available?(x, y)
        @board[x][y] = @current
        @current += 1
    else
        raise "#{x},#{y} is not available"
    end
end

#Nice box output
def to_s
    lines = "-" + "-"*5*@size + "\n"
    out = ""
    out << lines
    @board.each do |row|
        out << "|" << row.map { |num| num.to_s.rjust(4) }.join(' ')

<< “|\n”
end
out << lines
end
end

raise “Please supply size” if ARGV[0].nil?

size = ARGV[0].to_i
raise “Size must be greater than 4” if size < 5

success = false

until success
board = Board.new(size)

#Pick random starting point
x = rand(size)
y = rand(size)

#Mark the board there
board.mark(x,y)
success = true

#Fill the board
until board.full?
    avail = board.available_from(x, y).sort { rand }

    #No moves available
    if avail.empty?
        puts "Cannot proceed"
        success = false
        break
    end

    #Pick the best available move
    best = avail.inject { |best, pair|
        board.available_from(*pair).length <

board.available_from(*best).length ? pair : best
}

    #Mark the board
    x, y = best
    board.mark(x, y)
end

end

#Output the solution
puts board

-Justin

30

Hi,

my solution is recursive and works only for small boards. The largest
I solved was
9x9 (in 45 minutes):
1 81 70 2 15 35 3 10 17
72 58 41 79 59 38 78 60 24
69 53 46 36 29 9 16 30 4
40 80 71 39 14 34 25 11 18
73 57 42 52 47 37 77 61 23
68 54 45 65 28 8 21 31 5
43 51 48 56 13 33 26 12 19
74 64 67 75 63 66 76 62 22
49 55 44 50 27 7 20 32 6

The main work is done in “each_neighbour” which iterates through all
possible hops.
The board is a one-dimensional array, so it’s easy to clone.

Regards,
Boris

pnp.rb

class PenAndPaper
def initialize(width)
@width = width
end

def each_neighbour(pos)
w = @width
x = pos % w
y = pos / w
# north
yield(pos - 3w) if y > 2
# north east
yield(pos - 2w + 2) if y > 1 and x < w - 2
# east
yield(pos + 3) if x < w - 3
# south east
yield(pos + 2w + 2) if y < w - 2 and x < w - 2
# south
yield(pos + 3w) if y < w - 3
# south west
yield(pos + 2w - 2) if y < w - 2 and x > 1
# west
yield(pos - 3) if x > 2
# north west
yield(pos - 2w - 2) if y > 1 and x > 1
end

def solve(pos=0)
board = []
board[pos] = 1
@board = solve_board(board, pos, 2)
end

def solve_board(board, pos, ind)
return board if ind > @width*@width
each_neighbour(pos) do |n|
next if board[n] # position already taken?
f = board.dup
f[n] = ind
f2 = solve_board(f, n, ind + 1)
return f2 if f2
end
nil # no more positions
end

def to_s
s = ‘’
(0…@width).each do |y|
(0…@width).each do |x|
s += "%3d " % @board[y*@width+x]
end
s += “\n”
end
s
end
end

test_pnp.rb

require ‘test/unit’
require ‘pnp’

class PenAndPaperTest < Test::Unit::TestCase
def neighbours_of(pos)
neighbours = []
pnp = PenAndPaper.new(5)
pnp.each_neighbour(pos) {|i| neighbours << i}
neighbours
end

def test_neighbours
assert_equal [ 3, 12, 15], neighbours_of(0)
assert_equal [14, 17, 10], neighbours_of(2)
assert_equal [18, 11, 0], neighbours_of(3)
assert_equal [22, 11, 2], neighbours_of(14)
assert_equal [ 2, 9, 5], neighbours_of(17)
assert_equal [ 5, 12, 23], neighbours_of(20)
assert_equal [ 9, 21, 12], neighbours_of(24)
end

def test_solve
pnp = PenAndPaper.new(5)
pnp.solve(0)
assert_equal <<END, pnp.to_s
1 22 12 2 7
19 25 5 20 10
13 16 8 23 15
4 21 11 3 6
18 24 14 17 9
END
end
end

31

On Aug 11, 2006, at 5:58 AM, Ruby Q. wrote:

You get extra points for:

  • Finding more about this game (name, origin, related articles)
  • Filling a 5x5 board with only pen and paper
  • Filling a bigger board with only pen and paper
  • Finding the worst attempt possible for a given size. For example,
    getting stuck after 10 steps on a 5x5 board is pretty bad:

You can get stuck in 6 steps on 6x6 or larger:

| . . . . . . |
| 5 . . 4 . . |
| . . . . . . |
| . . 1 . . 2 |
| . . . . . . |

6 . . 3 . .

For 5x5, I found 9 steps (which is just your example with the first
step removed b/c it wasn’t needed):

| . 5 2 . 6|
| . . 8 . .|
| 3 . . 4 1|
| . . . . 7|

. . 9 . .

– Elliot T.

32

Justin C. wrote:

Here’s my solution, which works the same way as Elliot’s first
solution, although with very different code:

Forgot to include some times, for those interested:

[justin@cheese ruby]$ time -p ruby penpaper.rb 5 > /dev/null
real 0.00
user 0.00
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 50 > /dev/null
real 0.63
user 0.63
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 100 > /dev/null
real 2.66
user 2.65
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 200 > /dev/null
real 11.59
user 11.58
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 300 > /dev/null
real 233.48
user 233.45
sys 0.02
[justin@cheese ruby]$ time -p ruby penpaper.rb 400 > /dev/null
real 332.94
user 332.91
sys 0.02

Note that the times for the larger boards almost certainly include
multiple attempts.

-Justin

33

My solution also uses the Warnsdorff heuristic (moving to the square
with the least amount of possible moves left).
It works very well for sizes under 100 or so, gets worse after that
and starts taking hundreds of tries at about n=175.

I also included an option to see how long tours are starting from each
square (give the script any second parameter to show this).
This shows how well (or poor) the algorithm works for that size, but
it’s obviously quite slow for larger sizes as it runs the algorithm
for every square.

Pastie link: Parked at Loopia
Code:

module Enumerable
def x(enum) # Cartesian product
map{|a| enum.map{|b| [a,b].flatten }}.inject([]) {|a,b| a+b}
end
def (n) # Cartesian power
if n == 1
self
else
self.x(self(n-1))
end
end
end

module OpenStructable
def method_missing(method,*args)
(class<<self;self;end).send(:attr_accessor, method.to_s.sub(‘=’,‘’)
)
send(method,*args)
end
end

class Vertex < Array
include OpenStructable
def initialize(name)
self.name = name
end
end

class Graph
def initialize
@vertices = Hash.new{|h,k| h[k] = Vertex.new(k) }
end

def add_edge(from,to)
@vertices[from] << @vertices[to]
end

def warnsdorff_tour(start)
@vertices.each_value{|v|
v.score = v.size
v.done = false
}
curr_node = @vertices[start]
tour = []
while curr_node
tour << curr_node
curr_node.done = true
curr_node.each{|v| v.score -= 1}
curr_node = curr_node.reject{|v| v.done}.sort_by{|v|
v.score}.first
end
tour.map{|t| t.name}
end

end

n = (ARGV[0] || 5).to_i
graph = Graph.new

dirs = [2,-2]**2 + [[0,3],[3,0],[0,-3],[-3,0]]

valid = 0…n

(valid**2).each {|x,y|
dirs.each{|dx,dy|
to_x, to_y = x + dx, y + dy
graph.add_edge([x,y] , [to_x,to_y]) if valid.include?(to_x) &&
valid.include?(to_y)
}
}
grid = Array.new(n){Array.new(n)}

This shows how long a tour starting from each square is

if ARGV[1]
full_count = 0
(valid**2).each{|x,y|
grid[y][x] = graph.warnsdorff_tour([x,y]).length
full_count += 1 if grid[y][x] == nn
}
puts "#{full_count} / #{nn} = #{‘%.2f’ %
[100full_count.to_f/(nn)]} % of the possible starting positions give
a full tour."
else

solution = []
try = 0
([0,n-1]**2 + [0].x(1…n-2) + (1…n-2)**2).each{|sx,sy| # for
starting square, try corners first, then one edge, then inside
try += 1
solution = graph.warnsdorff_tour([sx,sy])
break if solution.length == n*n
}

if solution.length != n*n
puts “Failed to find tour.”
exit!
end
puts “Found tour in #{try} tries.”

solution.each_with_index{|(x,y),i| grid[y][x] = i+1 }
end

max_len = (n * n).to_s.length

sep = (‘+’ + ‘-’ * (max_len+2) ) * n + ‘+’
puts sep, grid.map{|row| ‘| ’ + row.map{|n| n.to_s.center(max_len)
}.join(’ | ‘) + ’ |’ }.join(“\n” + sep + “\n”), sep

34

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Suraj N. Kurapati wrote:

Here is my solution, which uses recursion like the Civilization II
map generation example in Chris P.'s “Learn to Program” book.

With a stack limit of:

$ ulimit -s
8192

the maximum square size my solution can handle is 67x67. However, it
can handle larger squares if you increase the stack size.

Well, I discovered that this solution doesn’t always find the
correct answer, so I fixed it accordingly. Now I can see why Eric
DUMINIL said a brute force approach is too slow. :slight_smile:

Thanks for the fun quiz.

#!/usr/bin/ruby -w

@param . width of square

@param . starting row

@param . starting column

class Square < Array
def initialize aWidth
super(aWidth) { Array.new aWidth }
@mark = 0
@size = aWidth ** 2
end

Walks this square, from the given position,

while marking unmarked (nil) cells.

def walk row, col
# skip invalid positions and marked cells
return false if
row < 0 or row >= length or
col < 0 or col >= length or
self[row][col]

# mark the current cell
  self[row][col] = @mark += 1

# explore adjacent paths
  if @mark >= @size or
     walk(row + 3, col    ) or # east
     walk(row + 2, col - 2) or # north east
     walk(row,     col - 3) or # north
     walk(row - 2, col - 2) or # north west
     walk(row - 3, col    ) or # west
     walk(row - 2, col + 2) or # south west
     walk(row,     col + 3) or # south
     walk(row + 2, col + 2)    # south east

    true
  else
    # unmark the current cell
      @mark -= 1
      self[row][col] = nil

    false
  end

end

Pretty-prints this square.

def to_s
# pretty-print each row
fmt = ‘|’ << "%#{length.to_s.length * 2}d " * length << ‘|’

  lines = inject([]) do |memo, row|
    memo << fmt % row
  end

# add a border to top & bottom
  border = '-' * lines.first.length

  lines.unshift border
  lines << border

lines.join("\n")

end
end

if $0 == FILE

create a square with user’s parameters

width = (ARGV.shift || 5).to_i
square = Square.new(width)

walk the square from random position

origin = Array.new(2) { (ARGV.shift || rand(width)).to_i }
square.walk(*origin)

pretty-print the walked square

puts square.to_s

end
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE35TumV9O7RYnKMcRAkezAKCUQQS7HsRq+MkdRsi4xYWbjXIdnQCfS6no
2e9bpIoRRP1XuXgHe275Pso=
=miH9
-----END PGP SIGNATURE-----

35

Here’s my solution that does not roll over the edges. I’ll post that
one in a bit as this one ended up with a lot more modification that
I’d like to throw in that one too.

This follows the Warnsdorff algorithm. This one started out as a
decently clean program although not super-idiomatic Ruby or
particularly OO. In trying to get it to go faster, I have added some
pretty ugly versions of some of the methods. The profiler was telling
me that I spent most of my time in array accessing, since I was
building up a collection of next moves, then filtering them. I
decided to make more of the checks inline instead of building arrays
first. The methods prefixed with fast_ represent the denormalized
version.

Getting rid of those extra array operations took the 500x500 grid
from 47s of user time to 29s of user time!

Bob

RESULTS
[segovia:~/Documents/projects/rubyplay] bobevans% /usr/bin/time -p
ruby quiz90c.rb 10
starting at (7, 7)
Completed!
10 81 32 9 82 48 22 62 49 23
76 27 12 75 26 13 51 25 14 52
33 8 95 86 31 69 85 47 21 61
11 80 77 28 83 78 29 63 50 24
98 91 34 74 94 87 54 70 15 53
38 7 96 79 30 68 84 46 20 60
35 41 99 90 65 71 18 64 57 3
97 92 37 73 93 88 55 1 16 45
39 6 66 40 5 67 58 4 19 59
36 42 100 89 43 72 17 44 56 2
real 0.01
user 0.01
sys 0.00

[segovia:~/Documents/projects/rubyplay] bobevans% /usr/bin/time -p
ruby quiz90c.rb 50
starting at (31, 33)
Completed!
real 0.30
user 0.29
sys 0.00

[segovia:~/Documents/projects/rubyplay] bobevans% /usr/bin/time -p
ruby quiz90c.rb 100
starting at (98, 12)
Completed!
real 1.14
user 1.13
sys 0.00

That one took a few runs to pass. Given the high rate of false starts
on larger grids, it makes sense to implement a different strategy,
perhaps the Conrad-like strategy that Elliot used.

class Grid
SM = 3 # square move length
DM = 2 # diagonal move length

def initialize(size)
@matrix = Array.new(size).map{Array.new(size)}
@counter = 0
@max = size * size
@size = size
end

def solve
no_moves_left = false
pick_start_place
while !no_moves_left && @counter < @max
next_move = pick_move
if next_move.nil?
no_moves_left = true
else
move(next_move[0], next_move[1])
end
end

 puts no_moves_left ? "Out of moves :-(" : "Completed!"
 print_matrix unless @size > 30

end

def pick_start_place
x = rand(@size)
y = rand(@size)
puts “starting at (#{x}, #{y})”
move(x, y)
end

def pick_move
moves = fast_available_moves
if !moves.empty?
moves.sort[0][1]
else
nil
end
end

def move(x,y)
@x = x
@y = y
# puts “moving to #{x},#{y}”
@matrix[x][y] = @counter += 1
# print_matrix
end

def available_moves
[n(@x,@y), ne(@x,@y), e(@x,@y),
se(@x,@y), s(@x,@y), sw(@x,@y),
w(@x,@y), nw(@x,@y)].reject{ |ma| move_illegal?(ma) || !clear?
(ma[0], ma[1]) }.map { |m| [count_moves(m), m] }
end

def fast_available_moves
moves = []
moves << [fast_count_moves([@x-SM, @y]), [@x-SM, @y]] unless
coord_illegal?(@x-SM) || !clear?(@x-SM, @y)
moves << [fast_count_moves([@x-DM, @y+DM]), [@x-DM, @y+DM]]
unless (coord_illegal?(@x-DM) || coord_illegal?(@y+DM)) || !clear?(@x-
DM, @y+DM)
moves << [fast_count_moves([@x, @y+SM]), [@x, @y+SM]] unless
coord_illegal?(@y+SM) || !clear?(@x, @y+SM)
moves << [fast_count_moves([@x+DM, @y+DM]), [@x+DM, @y+DM]]
unless (coord_illegal?(@x+DM) || coord_illegal?(@y+DM)) || !clear?(@x
+DM, @y+DM)
moves << [fast_count_moves([@x+SM, @y]), [@x+SM, @y]] unless
coord_illegal?(@x+SM) || !clear?(@x+SM, @y)
moves << [fast_count_moves([@x+DM, @y-DM]), [@x+DM, @y-DM]]
unless (coord_illegal?(@x+DM) || coord_illegal?(@y-DM)) || !clear?(@x
+DM, @y-DM)
moves << [fast_count_moves([@x, @y-SM]), [@x, @y-SM]] unless
coord_illegal?(@y-SM) || !clear?(@x, @y-SM)
moves << [fast_count_moves([@x-DM, @y-DM]), [@x-DM, @y-DM]]
unless (coord_illegal?(@x-DM) || coord_illegal?(@y-DM)) || !clear?(@x-
DM, @y-DM)
moves
end

def n(x, y); [x - SM, y]; end

def ne(x, y); [x - DM, y + DM]; end

def e(x, y); [x, y + SM]; end

def se(x, y); [x + DM, y + DM] ; end

def s(x, y); [x + SM, y]; end

def sw(x, y); [x + DM, y - DM] ; end

def w(x, y); [x, y - SM]; end

def nw(x, y); [x - DM, y - DM]; end

def count_moves(m)
x = m[0]
y = m[1]
[n(x, y), ne(x, y), e(x, y),
se(x, y), s(x, y), sw(x, y),
w(x, y), nw(x, y)].reject{ |ma| move_illegal?(ma) || !clear?(ma
[0], ma[1])}.length
end

def fast_count_moves(m)
x = m[0]
y = m[1]
count = 0
count += 1 unless coord_illegal?(x-SM) || !clear?(x-SM, y)
count += 1 unless (coord_illegal?(x-DM) || coord_illegal?(y+DM))
|| !clear?(x-DM, y+DM)
count += 1 unless coord_illegal?(y+SM) || !clear?(x, y+SM)
count += 1 unless (coord_illegal?(x+DM) || coord_illegal?(y+DM))
|| !clear?(x+DM, y+DM)
count += 1 unless coord_illegal?(x+SM) || !clear?(x+SM, y)
count += 1 unless (coord_illegal?(x+DM) || coord_illegal?(y-DM))
|| !clear?(x+DM, y-DM)
count += 1 unless coord_illegal?(y-SM) || !clear?(x, y-SM)
count += 1 unless (coord_illegal?(x-DM) || coord_illegal?(y-DM))
|| !clear?(x-DM, y-DM)
count
end

def clear?(x,y)
@matrix[x][y].nil?
end

def move_illegal?(m)
x = m[0]
y = m[1]
x >= @size || x < 0 || y >= @size || y < 0
end

def coord_illegal?(n)
n >= @size || n < 0
end

def print_matrix
@matrix.each { |r| r.each { |c| printf("%2d ", c)}; puts “\n”}
end
end

def run(size=6)
g = Grid.new(size)
g.solve
nil
end

if $0 == FILE
run(ARGV[0].to_i)
end

36

Well, here is my terrible contribution. It is just a bruteforce and it
starts
taking a real long time 7*7 and higher. I tried writing some logic to
make
better moves but couldn’t really figure out how. In fact, even after
reading
some other solutions I still can’t really figure out how to do this.

I will play around some more and repost if I can figure it out…
######################################

#!/usr/bin/ruby

PnP.rb :: quiz no.90

def mov_hori(ip, matrix, gridsize)
moves = []
if ip[1]-3 >= 0 and matrix[ip[0]][ip[1]-3] == “.”
moves << “l” # left
end
if ip[1]+3 < gridsize and matrix[ip[0]][ip[1]+3] == “.”
moves << “r” # right
end
moves
end

def mov_vert(ip, matrix, gridsize)
moves = []
if ip[0]-3 >= 0 and matrix[ip[0]-3][ip[1]] == “.”
moves << “u” # up
end
if ip[0]+3 < gridsize and matrix[ip[0]+3][ip[1]] == “.”
moves << “d” # down
end
moves
end

def mov_diag(ip, matrix, gridsize)
moves = []
if ip[0]-2 >= 0 and ip[1]+2 < gridsize and matrix[ip[0]-2][ip[1]+2] ==
“.”
moves << “ur” # up-right
end
if ip[0]-2 >= 0 and ip[1]-2 >= 0 and matrix[ip[0]-2][ip[1]-2] == “.”
moves << “ul” # up-left
end
if ip[0]+2 < gridsize and ip[1]+2 < gridsize and
matrix[ip[0]+2][ip[1]+2]
== “.”
moves << “dr” # down-right
end
if ip[0]+2 < gridsize and ip[1]-2 >= 0 and matrix[ip[0]+2][ip[1]-2] ==
“.”
moves << “dl” # down-left
end
moves
end

def print_matrix(matrix)
matrix.each do |row|
row.each do |cell|
print " %3s " % cell
end
print “\n”
end
exit
end

def do_it(gridsize,ind_p)
moves_offset = {
“l” => [0,-3],
“r” => [0,3],
“u” => [-3,0],
“d” => [3,0],
“ur” => [-2,2],
“ul” => [-2,-2],
“dr” => [2,2],
“dl” => [2,-2]
}

array = ["."]
matrix = []
totalnums = gridsize*gridsize

gridsize.times do
matrix << array * gridsize
end

matrix[ind_p[0]][ind_p[1]] = 1
nextint = 2

totalnums.times do
hori = mov_hori(ind_p, matrix, gridsize)
vert = mov_vert(ind_p, matrix, gridsize)
diag = mov_diag(ind_p, matrix, gridsize)
moves = hori + vert + diag

if moves.length == 0
  return # try again
end

try_a_move = moves[rand(moves.length)]
x,y = moves_offset[try_a_move]
ind_p[0] += x
ind_p[1] += y

matrix[ind_p[0]][ind_p[1]] = nextint
nextint += 1
if nextint == totalnums + 1
  print_matrix(matrix)
end

end
end

gridsize = ARGV[0].to_i
ind_p = [rand(gridsize), rand(gridsize)] # random initial coords

while 1:
(1…10000).each do
matrix = do_it(gridsize,ind_p)
end
puts “10k iterations…”
end
######################################
-d

37

On Aug 13, 2006, at 7:11 PM, darren kirby wrote:

| . . . . . . |

6 . . 3 . .

Am I missing something here? Your vertical moves are jumping 3
squares…
From the rules:

   - jumping over 2 squares when traveling horizontally or

vertically
- jumping over 1 square when traveling diagonally.

i think jumping over 2 squares means landing on third square away.
that’s what it looked like in the examples.

– Elliot T.

38

quoth the Elliot T.:

You can get stuck in 6 steps on 6x6 or larger:

| . . . . . . |
| 5 . . 4 . . |
| . . . . . . |
| . . 1 . . 2 |
| . . . . . . |

6 . . 3 . .

Am I missing something here? Your vertical moves are jumping 3
squares…
From the rules:

   - jumping over 2 squares when traveling horizontally or vertically
  - jumping over 1 square when traveling diagonally.

– Elliot T.
Curiosity Blog – Elliot Temple
-d

39

On Aug 13, 2006, at 7:44 PM, Elliot T. wrote:

| 5 . . 4 . . |

   - jumping over 2 squares when traveling horizontally or

vertically
- jumping over 1 square when traveling diagonally.

i think jumping over 2 squares means landing on third square away.
that’s what it looked like in the examples.

oh haha. there are typos. the 4 and 5 should be one row lower. i
think it’s right then.

– Elliot T.

40

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 < nn
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 < nn-1)
# drat. Try again
break
end
x += jumppatterns[j][0]
y += jumppatterns[j][1]
pospath << [x,y]
end
if pospath.size == nn
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 + (nn).to_s.length
puts(’-’ * (lenn + 2))
a.each{|m|
print ‘|’
m.each{|s| print("%#{len}d" % s)}
puts ‘|’
}
puts(’-’ * (lenn + 2))
else
loopctr += 1
end
end