# \[QUIZ\] Pen and Paper (#90)

**URL:** <https://www.ruby-forum.com/t/quiz-pen-and-paper-90/65054>\
**Category:** Ruby\
**Created:** [August 15, 2006, 9:51pm UTC](https://www.ruby-forum.com/t/quiz-pen-and-paper-90/65054 "2006-08-15T21:51:41Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [August 15, 2006, 9:51pm UTC](https://www.ruby-forum.com/t/quiz-pen-and-paper-90/65054/1 "2006-08-15T21:51:41Z")

</div>

# 

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

---

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [August 15, 2006, 11:00pm UTC](https://www.ruby-forum.com/t/quiz-pen-and-paper-90/65054/2 "2006-08-15T23:00:52Z")

</div>

# 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

---

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [August 16, 2006, 3:50pm UTC](https://www.ruby-forum.com/t/quiz-pen-and-paper-90/65054/3 "2006-08-16T15:50:24Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [August 17, 2006, 9:04am UTC](https://www.ruby-forum.com/t/quiz-pen-and-paper-90/65054/4 "2006-08-17T09:04:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [August 17, 2006, 12:19am UTC](https://www.ruby-forum.com/t/quiz-pen-and-paper-90/65054/5 "2006-08-17T00:19:10Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [August 17, 2006, 3:50pm UTC](https://www.ruby-forum.com/t/quiz-pen-and-paper-90/65054/6 "2006-08-17T15:50:21Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [August 17, 2006, 10:52am UTC](https://www.ruby-forum.com/t/quiz-pen-and-paper-90/65054/7 "2006-08-17T10:52:53Z")

</div>

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