アルゴリズム・パズル q50 のすべてのルートの画像化

q50a.rb

require_relative "q50disp"

W, H = 6, 5

def putout
  return if @memo.include?([@yoko, @tate])
  @memo << (a = Marshal.load(Marshal.dump([@yoko, @tate])))
  Disp.show(*a)
end

def yoko?(y)
  @yoko[y].inject(:+) < 2
end

def tate?(x)
  @tate[x].inject(:+) < 2
end

def search(x, y, co)
  if x == W and y == H
    putout if co >= 25
    return
  end
  if x < W and yoko?(y)
    @yoko[y][x] += 1
    search(x + 1, y, co + 1)
    @yoko[y][x] -= 1
  end
  if y < H and tate?(x)
    @tate[x][y] += 1
    search(x, y + 1, co + 1)
    @tate[x][y] -= 1
  end
  if x > 0 and yoko?(y)
    @yoko[y][x - 1] += 1
    search(x - 1, y, co + 1)
    @yoko[y][x - 1] -= 1
  end
  if y > 0 and tate?(x)
    @tate[x][y - 1] += 1
    search(x, y - 1, co + 1)
    @tate[x][y - 1] -= 1
  end
end

@tate = Array.new(W + 1) {Array.new(H, 0)}
@yoko = Array.new(H + 1) {Array.new(W, 0)}
@memo = []

search(0, 0, 0)

q50disp.rb

require 'cairo'

L = 40

module Disp
  @co = 0
  
  def self.line(c, x1, y1, x2, y2)
    c.move_to(x1, y1)
    c.line_to(x2, y2)
    c.stroke
  end
  
  def self.show(yoko, tate)
    surface = Cairo::ImageSurface.new(260, 220)
    context = Cairo::Context.new(surface)
    
    context.set_source_rgb(0, 0, 0)
    context.rectangle(0, 0, 260, 220)
    context.fill

    context.set_source_rgb(0, 1, 0)
    
    x0, y0 = 10, 10
    yoko.each_with_index do |ar, y|
      ar.each_with_index do |f, x|
        x1 = x0 + L * x
        y1 = y0 + L * y
        x2 = x1 + L
        line(context, x1, y1, x2, y1) if f != 0
      end
    end
    tate.each_with_index do |ar, x|
      ar.each_with_index do |f, y|
        x1 = x0 + L * x
        y1 = y0 + L * y
        y2 = y1 + L
        line(context, x1, y1, x1, y2) if f != 0
      end
    end
    
    context.target.write_to_png("./picture/route%03d.png" % (@co += 1))
  end
end

#カレントディレクトリに picture フォルダを作っておく