[QUIZ] Pen and Paper (#90)

[James_Edward_Gray_II]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Eric DUMINIL

Some classmates and I used to play a lot of pen and paper games while sitting
in the last row of the classroom. My favorite game was this one.

We had to fill a 5x5 board as fast as possible with numbers from 1 to 25,
beginning at a random position and then going from one square to another:

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

Here is an example with numbers from 1 to 14 (it would be impossible to keep on
filling the board, since 1, 13, and 8 are blocking the way):

   -------------------
  > . 1 4 . 14|
  > 10 . . 11 6|
  > 3 . 8 2 .|
  > . 12 5 . 13|
  > 9 . . . 7|
   -------------------

Here is a completed 5x5 board:

   -------------------
  > 14 1 8 25 2|
  > 6 23 16 5 22|
  > 18 10 13 19 9|
  > 15 4 7 24 3|
  > 12 20 17 11 21|
   -------------------

Though this game is impossible with 2x2, 3x3 or 4x4 boards, it appears that NxN
boards can be filled when N>4 (or n=1). For example, 6x6:

   -----------------------
  > 33 21 10 32 35 11|
  > 16 26 5 13 25 6|
  > 9 31 34 22 30 1|
  > 4 20 17 27 36 12|
  > 15 23 8 14 24 7|
  > 18 28 3 19 29 2|
   -----------------------

7x7:

   ---------------------------
  > 46 33 26 8 32 35 9|
  > 17 14 5 37 15 6 38|
  > 27 22 47 34 25 48 31|
  > 45 42 16 7 43 36 10|
  > 18 13 4 21 12 3 39|
  > 28 23 44 29 24 49 30|
  > 1 41 19 2 40 20 11|
   ---------------------------

Here comes the quiz!

  - Write a ruby script that fills a board (with a given NxN size)
    as fast as possible
  - Try to fill the biggest board you can with this script, in a
    reasonable amount of time (let's say 48 hours minus scripting time)

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:
  
    -------------------
   > . 6 3 . 7|
   > . . 9 . .|
   > 4 1 . 5 2|
   > . . . . 8|
   > . . 10 . .|
    -------------------
   
  - Filling a board with a cycle pattern, i.e. where you can jump from
    the last square to the first square:
    
     -------------------
    > 22 10 7 23 11|
    > 14 19 4 1 16|
    > 8 24 12 9 6|
    > 21 2 15 20 3|
    > 13 18 5 25 17|
     -------------------
    
     -----------------------
    > 16 9 27 17 8 28|
    > 35 12 6 30 13 23|
    > 26 18 15 10 19 2|
    > 5 31 34 22 7 29|
    > 36 11 25 1 14 24|
    > 33 21 4 32 20 3|
     -----------------------

I can't wait to look at your solutions!

I daresay that brute-forcing won't help you much (it took me 98,268,583 attempts
and 4 days on a decent computer to fill a 10x10 board) but I don't know many
other ways to fill a board.

Have fun with this quiz.

[James_Edward_Gray_II]

$ time ruby grid_fill.rb -s 6

···

On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:

  - Try to fill the biggest board you can with this script, in a
    reasonable amount of time (let's say 48 hours minus scripting time)

-------------------------------

15 8 26 16 7 27 |
34 11 5 29 12 22 |
25 17 14 9 18 1 |
4 30 33 21 6 28 |
35 10 24 36 13 23 |
32 20 3 31 19 2 |

-------------------------------

real 0m0.037s
user 0m0.026s
sys 0m0.010s
$ time ruby grid_fill.rb -s 6
-------------------------------

28 21 3 29 20 4 |
11 24 18 6 25 35 |
2 30 27 22 31 14 |
17 7 10 34 19 5 |
12 23 1 13 26 36 |
9 33 16 8 32 15 |

-------------------------------

real 0m0.037s
user 0m0.026s
sys 0m0.010s
$ time ruby grid_fill.rb -s 6
-------------------------------

19 12 30 20 11 31 |
2 15 9 33 16 26 |
29 21 18 13 22 5 |
8 34 1 25 10 32 |
3 14 28 4 17 27 |
36 24 7 35 23 6 |

-------------------------------

real 0m0.037s
user 0m0.026s
sys 0m0.010s

James Edward Gray II

[7rans]

Ruby Quiz wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Eric DUMINIL

Some classmates and I used to play a lot of pen and paper games while sitting
in the last row of the classroom. My favorite game was this one.

We had to fill a 5x5 board as fast as possible with numbers from 1 to 25,
beginning at a random position and then going from one square to another:

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

Here is an example with numbers from 1 to 14 (it would be impossible to keep on
filling the board, since 1, 13, and 8 are blocking the way):

   -------------------
  > . 1 4 . 14|
  > 10 . . 11 6|
  > 3 . 8 2 .|
  > . 12 5 . 13|
  > 9 . . . 7|
   -------------------

Here is a completed 5x5 board:

   -------------------
  > 14 1 8 25 2|
  > 6 23 16 5 22|
  > 18 10 13 19 9|
  > 15 4 7 24 3|
  > 12 20 17 11 21|
   -------------------

I know I'm stupid and all that, but I'm not sure there's enough
explination here for someone who's never played this game before. Could
you explain the rules of game a little better.

Thanks,
T.

[Robert_Evans]

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

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

Bob

···

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

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Eric DUMINIL

Some classmates and I used to play a lot of pen and paper games while sitting
in the last row of the classroom. My favorite game was this one.

We had to fill a 5x5 board as fast as possible with numbers from 1 to 25,
beginning at a random position and then going from one square to another:

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

Here is an example with numbers from 1 to 14 (it would be impossible to keep on
filling the board, since 1, 13, and 8 are blocking the way):

   -------------------
  > . 1 4 . 14|
  > 10 . . 11 6|
  > 3 . 8 2 .|
  > . 12 5 . 13|
  > 9 . . . 7|
   -------------------

Here is a completed 5x5 board:

   -------------------
  > 14 1 8 25 2|
  > 6 23 16 5 22|
  > 18 10 13 19 9|
  > 15 4 7 24 3|
  > 12 20 17 11 21|
   -------------------

Though this game is impossible with 2x2, 3x3 or 4x4 boards, it appears that NxN
boards can be filled when N>4 (or n=1). For example, 6x6:

   -----------------------
  > 33 21 10 32 35 11|
  > 16 26 5 13 25 6|
  > 9 31 34 22 30 1|
  > 4 20 17 27 36 12|
  > 15 23 8 14 24 7|
  > 18 28 3 19 29 2|
   -----------------------

7x7:

   ---------------------------
  > 46 33 26 8 32 35 9|
  > 17 14 5 37 15 6 38|
  > 27 22 47 34 25 48 31|
  > 45 42 16 7 43 36 10|
  > 18 13 4 21 12 3 39|
  > 28 23 44 29 24 49 30|
  > 1 41 19 2 40 20 11|
   ---------------------------

Here comes the quiz!

  - Write a ruby script that fills a board (with a given NxN size)
    as fast as possible
  - Try to fill the biggest board you can with this script, in a
    reasonable amount of time (let's say 48 hours minus scripting time)

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:
  
    -------------------
   > . 6 3 . 7|
   > . . 9 . .|
   > 4 1 . 5 2|
   > . . . . 8|
   > . . 10 . .|
    -------------------
  
  - Filling a board with a cycle pattern, i.e. where you can jump from
    the last square to the first square:
  
     -------------------
    > 22 10 7 23 11|
    > 14 19 4 1 16|
    > 8 24 12 9 6|
    > 21 2 15 20 3|
    > 13 18 5 25 17|
     -------------------
  
     -----------------------
    > 16 9 27 17 8 28|
    > 35 12 6 30 13 23|
    > 26 18 15 10 19 2|
    > 5 31 34 22 7 29|
    > 36 11 25 1 14 24|
    > 33 21 4 32 20 3|
     -----------------------

I can't wait to look at your solutions!

I daresay that brute-forcing won't help you much (it took me 98,268,583 attempts
and 4 days on a decent computer to fill a 10x10 board) but I don't know many
other ways to fill a board.

Have fun with this quiz.

[Elliot_Temple]

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

[Elliot_Temple]

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.

[Elliot_Temple]

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

···

On Aug 11, 2006, at 5:58 AM, Ruby Quiz 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:

  -------------------------

. . . . . . |
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 Temple

Curiosity Blog – Elliot Temple

[Suraj_Kurapati]

Here is my solution, which uses recursion like the Civilization II
map generation example in Chris Pine'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

[Collins_Justin]

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.
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

[Boris_Prinz]

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 - 3*w) if y > 2
     # north east
     yield(pos - 2*w + 2) if y > 1 and x < w - 2
     # east
     yield(pos + 3) if x < w - 3
     # south east
     yield(pos + 2*w + 2) if y < w - 2 and x < w - 2
     # south
     yield(pos + 3*w) if y < w - 3
     # south west
     yield(pos + 2*w - 2) if y < w - 2 and x > 1
     # west
     yield(pos - 3) if x > 2
     # north west
     yield(pos - 2*w - 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

[Robert_Evans]

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[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[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

[darren_kirby]

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
--
darren kirby :: Part of the problem since 1976 :: http://badcomputer.org
"...the number of UNIX installations has grown to 10, with more expected..."
- Dennis Ritchie and Ken Thompson, June 1972

[Daniel_Martin]

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

[Mitchell_Koch]

Here's my solution. It starts in the middle of the board and hops to
one of the next spaces that has a large amount of moves that can be
made from there. It's not all that fast though, I didn't really spend
too much time optimizing.

Mitchell Koch

penandpaper.rb (2 KB)

[Morton_Goldberg]

This is my submission for Ruby Quiz #90.

My solution's best feature is that it's based on a simple search algorithm and that's also its worst feature. The randomized depth-first search I use is easy to understand, was easy to code, and required almost no debugging. But it has O(e**n) worst-case behavior. Which means it works well enough for small n, but it quickly becomes intolerable as n grows. When does it begin to suck? Depends on how patient you are. I ran out of patience at n = 7.

The search is programmed to terminate as soon as it finds one, cyclic solution. Of course, from any cyclic solution, you can generate n**2 - 1 additional cyclic solutions by applying the included Grid#shift method for n = 1 to 35.

My solution's second best feature is that it's short. Even with a fair amount of commenting, it comes in at less than 200 lines.

Here are some results from running it with n = 5 and n = 6.

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb

···

------------------------

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

------------------------
real 0m0.095s
user 0m0.053s
sys 0m0.014s

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
------------------------

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

------------------------
real 0m0.048s
user 0m0.017s
sys 0m0.011s

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
------------------------

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

------------------------
real 0m0.166s
user 0m0.108s
sys 0m0.014s

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
----------------------------

  1 15 22 36 5 23 |
26 9 19 25 10 18 |
21 29 6 16 30 35 |
  2 14 11 33 4 24 |
27 8 20 28 7 17 |
12 32 3 13 31 34 |

----------------------------
real 0m3.004s
user 0m2.827s
sys 0m0.034s

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
----------------------------

  1 8 31 36 7 30 |
27 13 16 24 12 17 |
20 35 2 9 32 3 |
15 23 28 14 6 29 |
26 10 19 25 11 18 |
21 34 5 22 33 4 |

----------------------------
real 1m18.337s
user 1m12.836s
sys 0m0.567s

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
----------------------------

  1 15 29 36 16 28 |
  9 6 18 26 7 19 |
22 33 11 14 30 35 |
  2 25 8 5 17 27 |
10 13 21 34 12 20 |
23 32 3 24 31 4 |

----------------------------
real 0m1.126s
user 0m1.027s
sys 0m0.021s

Notice the wide variation in run times. You have to be lucky to get a really short run. This suggests some interesting statistical questions:

1. What is the distribution of run times as a function of n?

2. What is the mean number of backtracking events over all the possible searches as a function of n?

3. What is the probability that a search proceeds to a solution with at most k backtracks as a function of n?

I don't know the answer to any of these questions, but I would like to.

<code>
#! /usr/bin/ruby -w
# Author: Morton Goldberg
#
# Date: August 15, 2006
#
# Ruby Quiz #90 -- Pen and Paper Game

# A grid is a matrix of cells.
class Grid

    def initialize(dims)
       @rows, @cols = dims
       @size = @rows * @cols
       @grid = Array.new(@rows) {|i| Array.new(@cols) {|j| Cell.new(i, j)}}
    end

    # Return a deep copy.
    def copy
       result = Grid.new(dimensions)
       result.grid.each_with_index do |row, i|
          row.each_with_index {|cell, j| cell.val = self[i, j].val}
       end
       result
    end

    # Shifts the values of the cells in the grid by <offset> under the
    # constraint that values are folded into the range 1..@size.
    def shift!(offset)
       @grid.each do |row|
          row.each do |cell|
             val = (cell.val + offset) % @size
             cell.val = (val == 0 ? @size : val)
          end
       end
       self
    end

    # Return the dimensions of the grid.
    def dimensions
       [@rows, @cols]
    end

    # Return the cell at positon [row, col].
    # Call as <grid-name>[row, col]
    def (*args)
       row, col = args
       @grid[row][col]
    end

    # Assigns a cell to the positon [row, col].
    # Call as <grid-name>[row, col] = cell
    def =(*args)
       row, col, cell = args
       @grid[row][col] = cell
    end

    # Format the grid as a bordered table.
    def to_s
       rule = '-' * (4 * @cols + 4) + "\n"
       grid_str = ""
       @grid.each do |row|
          grid_str << row.inject("| ") do |row_str, cell|
             row_str << ("%2d " % cell.val)
          end
          grid_str << "|\n"
       end
       "" << rule << grid_str << rule
    end

    attr_reader :rows, :cols, :size, :grid

end

# A path is an array of cells, where no two cells occupy the same location
# in some grid. A complete path fills the grid.
class Path < Array

    # Make a deep copy of a path.
    def copy
       result = Path.new
       each {|cell| result << cell.dup}
       result
    end

   # Sequentially number the cells in the path.
    def number!
       each_with_index {|cell, i| cell.val = i + 1}
       self
    end

    # Report whether or not a path is cyclic.
    def cyclic?
       p0, p1 = self[0], self[-1]
       delta = [(p1.row - p0.row).abs, (p1.col - p0.col).abs]
       delta == [3, 0] || delta == [0, 3] || delta == [2, 2]
    end

    # Make a grid from a path.
    # Warning: if the path isn't complete, the resulting grid wont't
    # represent a solution.
    def to_grid(size)
       result = Grid.new([size, size])
       each {|cell| result[cell.row, cell.col] = cell}
       result
    end

end

# A cell is a simple object that knows its value and its position in
# a grid. It also encodes the game's movement rule.
class Cell

    def initialize(row, col, val=0)
       @row, @col = row, col
       @val = val
    end

    # Return a list of targets -- an array containing all the cells in the
    # grid reachable from this cell in one step.
    def targets(grid)
       size = grid.rows
       result =
       result << grid[@row, @col - 3] if @col - 3 >= 0 # north
       result << grid[@row + 2, @col - 2] \
          if @row + 2 < size && @col - 2 >= 0 # northeast
       result << grid[@row + 3, @col] if @row + 3 < size # east
       result << grid[@row + 2, @col + 2] \
          if @row + 2 < size && @col + 2 < size # southeast
       result << grid[@row, @col + 3] if @col + 3 < size # south
       result << grid[@row - 2, @col + 2] \
          if @row - 2 >= 0 && @col + 2 < size # southwest
       result << grid[@row - 3, @col] if @row - 3 >= 0 # west
       result << grid[@row - 2, @col - 2] \
          if @row - 2 >= 0 && @col - 2 >= 0 # northwest
       result
    end

    attr_accessor :row, :col, :val

end

# A solver uses a depth-first search to find one solution for a square grid # of a given size.
class Solver

    def initialize(size)
       @size = size
       @solution = nil
       @test_grid = Grid.new([@size, @size])
       cell = @test_grid[0, 0]
       targets = cell.targets(@test_grid)
       goals = targets.dup
       @backtrack_chain = [[Path.new << cell, targets, goals]]
    end

    # Return a new link for the backtrack chain if it can be extended;
    # otherwise, return nil.
    def next_link
       path, targets, goals = @backtrack_chain.last
       return nil if targets.empty? || goals.empty?
       # Here is where the randomization takes place.
       cell = targets[rand(targets.size)]
       next_path = path.dup << cell
       # Restricts target list to accessible cells not already on the path.
       next_targets = cell.targets(@test_grid) - path
       next_goals = goals.dup
       next_goals.delete(cell) if goals.include?(cell)
       # Make sure cell won't be picked again if backtrack occurs.
       targets.delete(cell)
       [next_path, next_targets, next_goals]
    end

    # The algorithm is a randomized depth-first search.
    def solve
       final_size = @size * @size
       loop do
          link = next_link
          if link then
             @backtrack_chain.push(link)
          else
             @solution = @backtrack_chain.pop.first
             break if @solution.size == final_size
             if @backtrack_chain.empty? then
                raise(RuntimeError, "No solution for #@size x #@size grid")
             end
          end
       end
       @solution.number!
    end

    attr_reader :solution

end

SIZE = 5
solver = Solver.new(SIZE)
puts solver.solve.to_grid(SIZE)
</code>

Regards, Morton

[Mat_Schaffer]

Do you by any chance have a background in artificial intelligence? That's really impressive how quickly you cranked out a solution to a problem I can't yet see a decent strategy for. Hats off to you, my friend.
-Mat

···

On Aug 11, 2006, at 2:39 PM, James Edward Gray II wrote:

On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:

  - Try to fill the biggest board you can with this script, in a
    reasonable amount of time (let's say 48 hours minus scripting time)

[snip: lots of fast filled boards]

[Suraj_Kurapati]

James Edward Gray II wrote:

    - Try to fill the biggest board you can with this script, in a
      reasonable amount of time (let's say 48 hours minus scripting time)

[timings for 6x6 square snipped]

Here's what I get, although I'm sure we have different hardware.

[sun@yantram j0 s0 ~/src/ruby_quiz]
612$ time ruby -w 90.rb 10
- -----------------------------------------------------

  17 62 28 18 65 60 48 95 89 79 |
   6 20 39 7 86 40 75 87 97 76 |
  27 9 66 61 47 67 88 78 98 91 |
  16 63 29 19 64 59 49 94 90 80 |
   5 21 38 8 85 41 74 84 96 77 |
  26 10 33 23 46 68 53 43 99 92 |
  15 1 30 12 35 58 50 70 55 81 |
   4 22 37 3 32 42 73 83 52 72 |
  25 11 34 24 45 69 54 44 100 93 |
  14 2 31 13 36 57 51 71 56 82 |

- -----------------------------------------------------

real 0m0.011s
user 0m0.007s
sys 0m0.002s
[sun@yantram j0 s0 ~/src/ruby_quiz]
613$ time ruby -w 90.rb 10
- -----------------------------------------------------

  30 21 8 31 22 54 73 47 87 74 |
  14 37 93 15 38 94 81 60 95 82 |
   7 69 46 53 70 45 1 75 88 98 |
  29 20 9 32 23 55 72 48 84 61 |
  13 36 92 16 39 91 80 59 96 83 |
   6 68 41 52 71 44 2 76 89 99 |
  28 19 10 33 24 56 65 49 85 62 |
  12 35 26 17 40 51 79 58 97 78 |
   5 67 42 4 66 43 3 77 90 100 |
  27 18 11 34 25 57 64 50 86 63 |

- -----------------------------------------------------

real 0m0.011s
user 0m0.009s
sys 0m0.000s
[sun@yantram j0 s0 ~/src/ruby_quiz]
614$ time ruby -w 90.rb 10
- -----------------------------------------------------

  61 19 46 30 20 100 73 64 88 83 |
  12 36 59 13 37 66 93 81 67 94 |
  45 29 62 44 74 63 87 75 97 84 |
  60 18 47 31 21 48 72 65 89 82 |
  11 35 58 14 38 57 92 80 68 95 |
   6 28 1 43 25 52 40 76 98 85 |
   3 17 8 32 22 49 71 54 90 78 |
  10 34 5 15 39 56 24 51 69 96 |
   7 27 2 42 26 53 41 77 99 86 |
   4 16 9 33 23 50 70 55 91 79 |

- -----------------------------------------------------

real 0m0.011s
user 0m0.009s
sys 0m0.000s

···

On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:

[Suraj_Kurapati]

Trans wrote:

Could you explain the rules of game a little better.

1. Grab a pen and piece of paper.

2. Draw a 5x5 grid (or table or matrix or whatever you like
   to call it).

3. Pick a cell or slot, whichever one you like, in the grid.

4. Write the number "1" in that chosen cell.

5. Starting from the cell you just marked (with the number "
   1"), travel to a different cell by following these rules:

        a. jump over 2 cells when traveling horizontally or
           vertically

        b. jump over 1 cell when traveling diagonally

6. Once you have traveled to the new cell, mark it with the
   number "2".

7. Starting from the cell you just marked (with the number "
   2"), travel to a different cell by following the rules a.
   and b. shown above.

8. Once you have traveled to the new cell, mark it with the
   number "3".

See the pattern? Now you need to travel from the one you
    just marked (with the number "3") to a new cell (which you
    will mark with the number "4"). Continue this process until
    you have marked all cells in the grid (the last cell will be
    marked with the number "25" for a 5x5 grid).

Hope that helps.

[Eric2 (Eric)]

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

On Aug 11, 2006, at 5:58 AM, Ruby Quiz wrote:
> The three rules of Ruby Quiz:
>
> 1. Please do not post any solutions or spoiler discussion for this
> quiz until
> 48 hours have passed from the time on this message.
>
> 2. Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3. Enjoy!
>
> Suggestion: A [QUIZ] in the subject of emails about the problem
> helps everyone
> on Ruby Talk follow the discussion. Please reply to the original
> quiz message,
> if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> =-=-=-=-=-=-=
>
> by Eric DUMINIL
>
> Some classmates and I used to play a lot of pen and paper games
> while sitting
> in the last row of the classroom. My favorite game was this one.
>
> We had to fill a 5x5 board as fast as possible with numbers from 1
> to 25,
> beginning at a random position and then going from one square to
> another:
>
> - jumping over 2 squares when traveling horizontally or vertically
> - jumping over 1 square when traveling diagonally.
>
> Here is an example with numbers from 1 to 14 (it would be
> impossible to keep on
> filling the board, since 1, 13, and 8 are blocking the way):
>
> -------------------
>
> > . 1 4 . 14|
> > 10 . . 11 6|
> > 3 . 8 2 .|
> > . 12 5 . 13|
> > 9 . . . 7|
>
> -------------------
>
> Here is a completed 5x5 board:
>
> -------------------
>
> > 14 1 8 25 2|
> > 6 23 16 5 22|
> > 18 10 13 19 9|
> > 15 4 7 24 3|
> > 12 20 17 11 21|
>
> -------------------
>
> Though this game is impossible with 2x2, 3x3 or 4x4 boards, it
> appears that NxN
> boards can be filled when N>4 (or n=1). For example, 6x6:
>
> -----------------------
>
> > 33 21 10 32 35 11|
> > 16 26 5 13 25 6|
> > 9 31 34 22 30 1|
> > 4 20 17 27 36 12|
> > 15 23 8 14 24 7|
> > 18 28 3 19 29 2|
>
> -----------------------
>
> 7x7:
>
> ---------------------------
>
> > 46 33 26 8 32 35 9|
> > 17 14 5 37 15 6 38|
> > 27 22 47 34 25 48 31|
> > 45 42 16 7 43 36 10|
> > 18 13 4 21 12 3 39|
> > 28 23 44 29 24 49 30|
> > 1 41 19 2 40 20 11|
>
> ---------------------------
>
> Here comes the quiz!
>
> - Write a ruby script that fills a board (with a given NxN size)
> as fast as possible
> - Try to fill the biggest board you can with this script, in a
> reasonable amount of time (let's say 48 hours minus scripting time)
>
> 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:
>
> -------------------
>
> > . 6 3 . 7|
> > . . 9 . .|
> > 4 1 . 5 2|
> > . . . . 8|
> > . . 10 . .|
>
> -------------------
>
> - Filling a board with a cycle pattern, i.e. where you can jump from
> the last square to the first square:
>
> -------------------
>
> > 22 10 7 23 11|
> > 14 19 4 1 16|
> > 8 24 12 9 6|
> > 21 2 15 20 3|
> > 13 18 5 25 17|
>
> -------------------
>
> -----------------------
>
> > 16 9 27 17 8 28|
> > 35 12 6 30 13 23|
> > 26 18 15 10 19 2|
> > 5 31 34 22 7 29|
> > 36 11 25 1 14 24|
> > 33 21 4 32 20 3|
>
> -----------------------
>
> I can't wait to look at your solutions!
>
> I daresay that brute-forcing won't help you much (it took me
> 98,268,583 attempts
> and 4 days on a decent computer to fill a 10x10 board) but I don't
> know many
> other ways to fill a board.
>
> Have fun with this quiz.