[QUIZ] Pen and Paper (#90)

Ruby
1

This quiz reminds me about Knight Tour problem.

So, I solve this quiz using brute-forcing combine with JC Warnsdorff

(1823) rule.

Move to the next case where has the minimum number of exits,

if it fail then backtracking and move to next minimum number of

exits … and so on.

(puts “#$0 n (n > 0)”; exit) unless (@n = ARGV[0].to_i) > 0
MOVES = [[3,0], [-3,0], [0,3], [0,-3], [2,2], [2,-2], [-2,2], [-2,-2]]
@board = Array.new(@n) { Array.new(@n) }

def show_solution
digits = (@n*@n).to_s.size
print(" #{’-’ * (digits+2) * @n}\n|")
print(@board.map { |l| l.map{|e| " %#{digits}d " % e}.join
}.join("|\n|"))
print("|\n #{’-’ * (digits+2) * @n}\n")
exit
end

def nb_exit(x, y)
return 0 if (x < 0 || x >= @n || y < 0 || y >= @n || @board[x][y])
MOVES.inject(0) do |m, (i, j)|
i += x; j += y
(i < 0 || i >= @n || j < 0 || j >= @n || @board[i][j]) ? m : m+1
end
end

def jump(v, x, y)
return if (x < 0 || x >= @n || y < 0 || y >= @n || @board[x][y])
@board[x][y] = v
show_solution if v == @n*@n
MOVES.sort_by { |i,j| nb_exit(x+i, y+j) }.each { |i,j| jump(v+1, x+i,
y+j) }
@board[x][y] = nil
end

@n.times { |x| @n.times { |y| jump(1, x, y) } }
puts “No solution.”

END

If fact, change the MOVES constant to
MOVES = [[-1,2], [1,2], [-1,-2], [1,-2], [2,-1], [2,1], [-2,-1], [-2,1]]
and ask for n = 8, than it becomes Knight Tour solver.

2

Same logic as my first solution, simply make it more OO and clean up a

bit.

class PenAndPaperGame
MOVES = [[3,0], [-3,0], [0,3], [0,-3], [2,2], [2,-2], [-2,2], [-2,-2]]

def initialize(size)
@size = size
@largest = @size * @size
@board = Array.new(@size) { Array.new(@size) }
end

def to_s
return “No solution.” unless @board[0][0]
digits = @largest.to_s.size
" #{’-’ * (digits+2) * @size}\n|" +
(@board.map { |l| l.map{|e| " %#{digits}d " % e}.join
}.join("|\n|")) +
“|\n #{’-’ * (digits+2) * @size}\n”
end

def solve
@size.times { |x| @size.times { |y| return self if jump(1, x, y) } }
self
end

private

def valid(x, y)
x >= 0 && x < @size && y >= 0 && y < @size && !@board[x][y]
end

def nb_exit(x, y)
MOVES.inject(0) { |m, (i, j)| valid(x+i, y+j) ? m+1 : m }
end

def jump(nb, x, y)
@board[x][y] = nb
return true if nb == @largest
MOVES.map { |i,j| [x+i, y+j] }.select { |i,j| valid(i,j) }.
sort_by { |i,j| nb_exit(i,j) }.each { |i,j| return true if
jump(nb+1, i, j) }
@board[x][y] = nil
end
end

if FILE == $0
size = (ARGV[0] || 5).to_i
puts PenAndPaperGame.new(size).solve
end

3

On Aug 15, 2006, at 4:00 PM, David T. wrote:

Same logic as my first solution, simply make it more OO and clean

up a bit.

This is a clean and easy to follow solution. I really like it.

Oddly, it has some super weird behavior on my box. It will do any
size grid less than or equal to 17 in the blink of my eye. When I
pass 18 or higher it seems to hang forever. It’s not eating memory,
but it does max out a CPU. It’s very odd.

James Edward G. II

4

On Aug 16, 2006, at 9:49 AM, James Edward G. II wrote:

Oddly, it has some super weird behavior on my box. It will do any
size grid less than or equal to 17 in the blink of my eye. When I
pass 18 or higher it seems to hang forever. It’s not eating
memory, but it does max out a CPU. It’s very odd.

James Edward G. II

I think it might be because the garbage collector is working extra
hard. I have observed similar behavior with an improved version of my
Pen and Paper program. Whereas the original version was brought down
on its knees by a 7x7 grid, the new one can do a 9x9 in 0.1 sec or an
11x11 in about 10 sec, but strangely had not completed a 10x10 when I
killed it after running for 20 minutes. I have determined, in the
10x10 case, that my algorithm produces a huge amount of garbage and
that the GC is running constantly.

The improvement in my program comes from incorporating Darren Kirby’s
look-ahead technique into the search algorithm. As he asserted, it
really speeds things up. I’m at a loss as to why Kirby’s technique
doesn’t work on a 10x10 grid. It has something to do with my
requirement for a cyclic solution – if I remove this requirement,
the program finds a 10x10 solution in 0.1 sec, a 20x20 in 0.2 sec, a
39x30 in 0.4 sec, and a 50x50 in 0.6 sec (close to O(n log n) behavior).

Regards, Morton

5

This one will “possible” find solution for “cycle pattern”.
It simply uses JC Warnsdorff (1823) rule,
so, it may not always find solution.

After my test, it does find cycle solutin for n = 5, 6, 15, 16, 22, 24,
25 …
(Of couse, I could try add brute-forcing, but don’t have time to play
with it now… )

class PenAndPaperGame2
MOVES = [[3,0], [-3,0], [0,3], [0,-3], [2,2], [2,-2], [-2,2], [-2,-2]]
attr_reader :found

def initialize(size)
@size = size
@board = Array.new(@size) { Array.new(@size) }
@found = false
end

def to_s
return “No soultion” unless @found
digits = (@size * @size).to_s.size
" #{’-’ * (digits+2) * @size}\n|" +
(@board.map { |l| l.map{|e| " %#{digits}d " % e}.join
}.join("|\n|")) +
“|\n #{’-’ * (digits+2) * @size}\n”
end

def solve
half = (@size - 1) / 2 + 1
half.times do |x|
half.times do |y|
@head = 1
@tail = @size * @size
cc = head(nil, @head, x, y)
if cc
tail(cc, @tail, *next_pos(x, y))
end
return self if @found
end
end
self
end

private

def valid?(x, y)
x >= 0 && x < @size && y >= 0 && y < @size && !@board[x][y]
end

def nb_exit(x, y)
MOVES.inject(0) { |m, (i, j)| valid?(x+i, y+j) ? m+1 : m }
end

def next_pos(x, y)
MOVES.map { |i,j| [x+i, y+j] }.
select { |i,j| valid?(i, j) }.
sort_by { |i,j| nb_exit(i, j)} [0]
end

def head(tail, nb, x, y=nil)
@head = nb
@found = true if @head >= @tail
return if @found || !x
@board[x][y] = nb
tail = callcc { |cc|
return cc if !tail
tail.call cc
}
head(tail, nb+1, *next_pos(x, y))
end

def tail(head, nb, x, y=nil)
@tail = nb
@found = true if @head >= @tail
return if @found || !x
@board[x][y] = nb
head = callcc { |cc|
head.call cc
}
tail(head, nb-1, *next_pos(x, y))
end

end

if FILE == $0
size = (ARGV[0] || 5).to_i
puts PenAndPaperGame2.new(size).solve
end

6

OK, here is my reworked solver. It’s much faster than my first
submission, but can still be slow for some grid sizes. It takes a -c
flag to indicate a cyclic solution is required. Using -c will slow
things down quite a bit more.

Strangely, a 10x10 acyclic solution is arrived at faster than a 6x6
one. Grids that are a multiple of 5x5 seem to be solved especially fast.

#! /usr/bin/ruby -w # Author: Morton G. # # Date: August 17, 2006 # # Ruby Q. #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
   span = ('%d' % @size).size
   rule = '-' * ((span + 1) * @cols + 3) + "\n"
   grid_str = ""
   @grid.each do |row|
      grid_str << row.inject("| ") do |row_str, cell|
         row_str << ("%#{span}d " % cell.val)
      end
      grid_str << "|\n"
   end
   "" << rule << grid_str << rule
end

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

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

unmarked 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.select {|c| c.val == 0}
end

attr_accessor :row, :col, :val

end

A solver uses a depth-first search to find one, possibly cyclic,

solution

for a square grid of a given size.

class Solver

def initialize(size)
   @size = size
   @grid = Grid.new([@size, @size])
   cell = @grid[0, 0]
   cell.val = 1
   targets = cell.targets(grid)
   goals = targets.dup # solution must finish with one of these

cells
@backtrack_chain = [[cell, targets, goals]]
end

# Return a new link for the backtrack chain if it can be extended;
# otherwise, return nil. The <targets> array provides the one-step
# look-ahead. The <goals> array is used to ensure the solution is
# cyclic.
def next_link
   cell, targets, goals = @backtrack_chain.last
   return nil if targets.empty? || ($cyclic && goals.empty?)
   next_cell = targets.shift
   next_cell.val = cell.val + 1
   next_targets = next_cell.targets(@grid)
   next_targets = next_targets.sort_by {|c| c.targets(@grid).size}
   next_goals = goals.dup
   next_goals.delete_if {|c| c == next_cell}
   [next_cell, next_targets, next_goals]
end

# The algorithm is a depth-first search with one-step look-ahead.
def solve
   final_value = @size * @size
   loop do
      link = next_link
      if link then
         @backtrack_chain.push(link)
      else
         link = @backtrack_chain.pop
         if @backtrack_chain.empty? then
            puts link
            raise(RuntimeError,
                  "No solution for #@size x #@size grid")
         end
         cell = link[0]
         break if cell.val == final_value
         cell.val = 0
      end
   end
   @grid
end

attr_reader :grid

end

USAGE = <<txt
Usage: quiz_90.rb [-c]
\twhere -c indicates cyclic solution required
\twhere > 4
txt

def bad_arg
puts USAGE
exit
end

Print current grid before exiting on control-C.

Signal.trap(‘INT’) do
puts
puts $solver.grid
exit
end

$n = 0
$cyclic = false
ARGV.each do |arg|
case arg
when /-c/ then $cyclic = true
when /\d+/ then $n = arg.to_i
else bad_arg
end
end
bad_arg if $n < 5
$solver = Solver.new($n)
puts $solver.solve

Regards, Morton

7

quoth the Morton G.:

The improvement in my program comes from incorporating Darren Kirby’s
look-ahead technique into the search algorithm. As he asserted, it
really speeds things up.

In the interest of full-disclosure I want to point out is is certainly
not my
technique, I got the idea (but not the implementation) from the earlier
posted solutions…

I’m at a loss as to why Kirby’s technique
doesn’t work on a 10x10 grid. It has something to do with my
requirement for a cyclic solution – if I remove this requirement,
the program finds a 10x10 solution in 0.1 sec, a 20x20 in 0.2 sec, a
39x30 in 0.4 sec, and a 50x50 in 0.6 sec (close to O(n log n) behavior).

Can you post your second solution? I would love to see it…

Regards, Morton

-d