ペントミノパズルソルバー

pentomino.rb

#!/usr/bin/ruby

require 'colorize'

COLOR_SCHEME = {
  'F' => [:light_yellow, :light_black],
  'I' => [:blue, :light_white],
  'L' => [:yellow, :light_white],
  'N' => [:light_yellow, :light_black],
  'P' => [:cyan, :light_white],
  'T' => [:red, :light_white],
  'U' => [:green, :light_white],
  'V' => [:yellow, :light_white],
  'W' => [:red, :light_white],
  'X' => [:blue, :light_white],
  'Y' => [:green, :light_white],
  'Z' => [:cyan, :light_white]}

######mama ペントミノパズルソルバー

CANON = {
  'F' => ['.FF',
          'FF.',
          '.F.'],
  'I' => ['IIIII'],
  'L' => ['L.',
          'L.',
          'L.',
          'LL'],
  'N' => ['NN..',
          '.NNN'],
  'P' => ['PP',
          'PP',
          'P.'],
  'T' => ['TTT',
          '.T.',
          '.T.'],
  'U' => ['U.U',
          'UUU'],
  'V' => ['..V',
          '..V',
          'VVV'],
  'W' => ['..W',
          '.WW',
          'WW.'],
  'X' => ['.X.',
          'XXX',
          '.X.'],
  'Y' => ['..Y.',
          'YYYY'],
  'Z' => ['ZZ.',
          '.Z.',
          '.ZZ']}

CANON.each_value { |v|
  v.map! { |str| str.each_char.to_a }
}

LETTERS = CANON.keys

def flip(mino)
  raise TypeError unless mino.is_a? Array

  mino.map { |arr| arr.reverse }
end

def show(mino)
  raise TypeError unless mino.is_a? Array

  mino.each do |row|
    puts row.join
  end
end

def show_color(mino)
  raise TypeError unless mino.is_a? Array

  mino.each do |row|
    row.each do |ch|
      pair = COLOR_SCHEME[ch]
      if pair
        bg, fg = pair
        print ch.colorize(color: fg,
                          background: bg)
      else
        print ch
      end
    end
    puts
  end
end

def rotvars(mino)
  raise TypeError unless mino.is_a? Array

  first = mino
  vars = [first]
  while true
    mino = rotate(mino)
    if mino == first
      break
    else
      vars << mino
    end
  end
  return vars
end

# ミノを90度右回転する
def rotate(mino)
  raise TypeError unless mino.is_a? Array
  flip(mino.transpose)
end

def allvars(ch)
  raise "Unknown letter #{ch}" unless CANON[ch]

  [*rotvars(CANON[ch]),
   *rotvars(flip(CANON[ch]))].uniq
end

VARIANTS = LETTERS.map { |c|
  [c, allvars(c)]
}.to_h

MINO_ANCHORS =  {}

def lower_left_empty_cell(board, i, j)
  w = board[0].size
  while i >= 0
    while j < w
      if board[i][j] == '.'
        return [i, j]
      end
      j += 1
    end
    j = 0
    i -= 1
  end
  nil
end

def lower_left_nonempty_cell(board)
  (board.size-1).downto(0) do |i|
    0.upto(board[0].size-1) do |j|
      if board[i][j] != '.'
        return [i, j]
      end
    end
  end
  nil
end

def solved?(board)
  return ! board.any? { |row| row.any? { |c| c == '.' } }
end

def erase!(board, mino, pos)
  i, j = pos
  mino.each_with_index do |row, di|
    row.each_with_index do |ch, dj|
      next if ch == '.'
      if board[i+di][j+dj] != ch
        raise '置いてないし'
      else
        board[i+di][j+dj] = '.'
      end
    end
  end
  return board
end

def place!(board, mino, pos)
  i, j = pos

  if i + mino.size > board.size ||
     j + mino[0].size > board[0].size ||
     i < 0 ||
     j < 0
    return false
  end


  mino.each_with_index do |row, di|
    row.each_with_index do |ch, dj|
      if ch != '.' && board[i+di][j+dj] != '.'
        return false
      end
    end
  end

  mino.each_with_index do |row, di|
    row.each_with_index do |ch, dj|
      if ch != '.'
        board[i+di][j+dj] = ch
      end
    end
  end
  return true
end

def space_size(board, i, j)
  recur = lambda do |i, j|
    if i < 0 || i >= board.size ||
       j < 0 || j >= board[0].size
      return 0
    elsif board[i][j] != '.'
      return 0
    else
      board[i][j] = '@'
      return 1 +
             recur.(i-1, j) +
             recur.(i+1, j) +
             recur.(i, j-1) +
             recur.(i, j+1)
    end
  end
  tot = recur.(i, j)
  board.each do |row|
    k = 0
    while k < row.size
      if row[k] == '@'
        row[k] = '.'
      end
      k += 1
    end
  end
  return tot
end

$COUNT = 0
def solve_all(board, letters = LETTERS, i = board.size-1, j = 0)
  if letters.empty?
    $COUNT += 1
    puts "#$COUNT ---"
    # show board # ←出力に色を付けたくない場合
    show_color board
    return true
  end

  i, j = lower_left_empty_cell(board, i, j)
  letters.each do |ch|
    letters1 = letters - [ch]
    VARIANTS[ch].each do |mino|
      di, dj = MINO_ANCHORS[mino.object_id]
      pos = [i-di, j-dj]
      if place!(board, mino, pos)
        if solve_all(board, letters1, i, j)
          erase!(board, mino, pos)
        else
          erase!(board, mino, pos)
        end
      end
    end
  end
  return false
end

VARIANTS.each_value do |minos|
  minos.each do |mino|
    MINO_ANCHORS[mino.object_id] = lower_left_nonempty_cell(mino)
  end
end

board = 10.times.map { '......'.chars }

solve_all(board)