(1823) rule.

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.

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

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

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

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

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|
@tail = @size * @size
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

@found = true if @head >= @tail
return if @found || !x
@board[x][y] = nb
tail = callcc { |cc|
return cc if !tail
tail.call cc
}
end

@tail = nb
@found = true if @head >= @tail
return if @found || !x
@board[x][y] = nb
}
end

end

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

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

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