Brute-force Lösung zum Kirschkuchen-Rätsel

kirschkuchen.rb

#!/usr/bin/env ruby
#encoding: utf-8

class Tile
  def initialize (face)
    @face = face
  end

  attr_reader :face

  def size
    @face.length
  end

  def symmetric?
    @face == @face.reverse
  end

  def face_at (i)
    @face[i]
  end
end

class Board
  def initialize (width, height)
    @width, @height = width, height
    @coords = (0...@width).to_a.product((0...@height).to_a)
    @placements = []
  end

  def coord_free? (x, y)
    @coords.include?([x, y])
  end

  def coords_free? (coords)
    coords.all? { |x, y| coord_free?(x, y) }
  end

  class Placement
    def initialize (x, y, tile, vertical=false, reverse=false)
      @tile = tile
      @coords = (0...tile.size).map { |i| vertical ? [x, y+i] : [x+i, y] }
      @coords.reverse! if reverse
    end

    attr_reader :coords

    def length
      @coords.length
    end

    def coord_at (i)
      @coords[i]
    end

    def face_at (i)
      @tile.face_at(i)
    end
  end

  def place (x, y, tile, vertical=false, reverse=false)
    placement = Placement.new(x, y, tile, vertical, reverse)
    return nil unless coords_free?(placement.coords)
    @coords -= placement.coords
    @placements << placement
    placement
  end

  def place_first (tile, vertical=false, reverse=false)
    return nil if @coords.empty?
    x, y = @coords.sort.first
    place(x, y, tile, vertical, reverse)
  end

  def unplace_last
    return nil if @placements.empty?
    placement = @placements.pop
    @coords += placement.coords
    placement
  end

  def pattern
    fields = Array.new(@height) { Array.new(@width) }
    @placements.each do |placement|
      placement.length.times do |i|
        x, y = placement.coord_at(i)
        face = placement.face_at(i)
        raise 'Huh!?' if fields[y][x]
        fields[y][x] = face
      end
    end
    fields
  end

  def dump
    fields = Array.new(2*@height-1) { Array.new(2*@width-1) }
    @placements.each do |placement|
      lastx, lasty = -1, -1
      placement.length.times do |i|
        x, y = placement.coord_at(i)
        face = placement.face_at(i)
        fields[2*y][2*x] = face
        fields[2*y-1][2*x] = '|' if x==lastx && lasty >= 0 && y==lasty+1
        fields[2*y+1][2*x] = '|' if x==lastx && lasty >= 0 && y==lasty-1
        fields[2*y][2*x-1] = '-' if y==lasty && lastx >= 0 && x==lastx+1
        fields[2*y][2*x+1] = '-' if y==lasty && lastx >= 0 && x==lastx-1
        lastx, lasty = x, y
      end
    end
    fields.each do |line|
      line.each do |field|
        print field || '·'
      end
      puts
    end
    puts
  end
end

class BruteForceSolver
  def initialize (width, height, *tilefaces)
    @board = Board.new(width, height)
    @tiles = tilefaces.map { |face| Tile.new(face) }
  end

  def check
    print '.'
  end

  def try (tiles)
    tile = tiles.shift
    (tile.symmetric? ? [false] : [false, true]).each do |reverse|
      [false, true].each do |vertical|
        if @board.place_first(tile, vertical, reverse)
          if tiles.empty?
            check
          else
            try(tiles.dup)
          end
          @board.unplace_last
        end
      end
    end
  end

  def solve
    permutations = @tiles.permutation
    total = permutations.count
    count = 0
    permutations.each do |tiles|
      count += 1
      try(tiles)
      print "%6d / %6d (%3.2f%%)\r" % [count, total, count*100.0/total]
    end
    puts "Tried #{@tries} times, checked #{@checks} times"
  end
end

class KirschkuchenSolver < BruteForceSolver
  def initialize
    super(5, 5, 'O#', 'O#', 'O##', 'O##', '#O#', 'O###', 'O###', '#O##')
  end

  def check
    pattern = @board.pattern
    ok = true
    5.times do |y|
      5.times do |x|
        next unless pattern[y][x] == 'O'
        #puts "check #{y},#{x} in #{pattern.inspect}"
        [-1, 0, 1].product([-1, 0, 1]).each do |yofs, xofs|
          next if xofs == 0 && yofs == 0
          next if x+xofs < 0 || x+xofs >= 5
          next if y+yofs < 0 || y+yofs >= 5
          ok = false if pattern[y+yofs][x+xofs] == 'O'
          #puts "  check #{y+yofs},#{x+xofs} - ok: #{ok.inspect}"
        end
      end
    end
    if ok
      puts "FOUND POSSIBLE SOLUTION:"
      @board.dump
    end
  end
end

KirschkuchenSolver.new.solve