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

[David Tran]

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

 

[David Tran]

# 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

 

[James Edward Gray II]

# 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 Gray II

 

[David Tran]

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

 

[Morton Goldberg]

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

 

[darren kirby]

--nextPart1908664.2ia3vaFNi1
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

quoth the Morton Goldberg:

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

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

I'm at a loss as to why Kirby's technique=20
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

=2Dd
=2D-=20
darren kirby :: Part of the problem since 1976 :: http://badcomputer.org
"...the number of UNIX installations has grown to 10, with more expected..."
=2D Dennis Ritchie and Ken Thompson, June 1972

--nextPart1908664.2ia3vaFNi1
Content-Type: application/pgp-signature

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

iD8DBQBE5C3rwPD5Cr/3CJgRAmflAJ0VF/7pL75rp3U60Nm0/PFFNshIgQCfeOO7
URUNLoBkBASy7EQBSr+KEzg=
=99mJ
-----END PGP SIGNATURE-----

--nextPart1908664.2ia3vaFNi1--

 

[Morton Goldberg]

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.

<code>
#! /usr/bin/ruby -w
# Author: Morton Goldberg
#
# Date: August 17, 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
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] <size>
\twhere -c indicates cyclic solution required
\twhere <size> > 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
</code>

Regards, Morton