Ruby

Rubyでののぐらむ(イラストロジック)を解いてみる

More than 1 year has passed since last update.

ののぐらむとは

パズルの一種です。パズルのマス目を白と黒で色分けしていき、完成すると絵が現れます。
それぞれの行(または列)のヒントには、その行(または列)に存在する黒マスの情報が書かれています。
sample_logic.png

ののぐらむを解くRubyスクリプト

ののぐらむのソルバーとしての機能を持つPuzzleクラスを作成し、ののぐらむを解かせます。

illust_logic.rb
#!/usr/bin/env ruby

require './puzzle.rb'

puzzle = Puzzle.new
puzzle.solve
puzzle.show_answer

Puzzleクラス

Puzzleクラスは、解く対象のパズルのマス目の情報と、それぞれの行および列のヒントの情報、そして解を求めるメソッドを持つクラスです。
メンバ変数@fieldが、パズルのマス目の状態を表す変数です。マス目の数だけの要素を持つ二次元変数であり、要素の値は、マス目が黒マスなら1、白マスなら0、確定していないなら−1、となります。
@row@colmunは、それぞれの行、または列のヒントを表す変数です。行、または列のヒントを記述したファイルを読み込み、Line_hintクラスの配列を作成します。

puzzle.rb
class Puzzle
  def initialize
    row_data = File.foreach('row.txt').map{|line| line.chomp.scan(/\d+/).map(&:to_i)}
    column_data = File.foreach('column.txt').map{|line| line.chomp.scan(/\d+/).map(&:to_i)}
    @row_length = row_data.length
    @column_length = column_data.length
    @field = Array.new(@row_length){Array.new(@column_length,-1)} # パズルの盤面
    @row = []
    # 上の行から格納していく
    # @row << Line_hint.new(@row_length,[3])
    # @row << Line_hint.new(@row_length,[1,1,1])
    # @row << Line_hint.new(@row_length,[1])
    # @row << Line_hint.new(@row_length,[1])
    # @row << Line_hint.new(@row_length,[3])
    row_data.each do |data|
      @row << Line_hint.new(@row_length,data)
    end

    @column = []
    # 左の列から格納していく
    # @column << Line_hint.new(@column_length,[1])
    # @column << Line_hint.new(@column_length,[1,1])
    # @column << Line_hint.new(@column_length,[5])
    # @column << Line_hint.new(@column_length,[1,1])
    # @column << Line_hint.new(@column_length,[1])
    column_data.each do |data|
      @column << Line_hint.new(@column_length,data)
    end

    @solved_flag = false # パズルが解けているかを判定するflag
  end

  def show_answer
    @field.each do |row|
      row.each do |val|
        if val == 1 then print "x"
        else print " "
        end
      end
      puts ""
    end
  end

  def solve(row=0)
    @row[row].each do |answer|
      set_row_answer(row, answer)
      if row != @row_length - 1
        # 最終行に到達していない場合。さらに深く探索
        solve(row+1)
      else
        # 最終行に到達した場合。盤面をチェックし、解けているかを確認
        @solved_flag = true if check_field
      end
      return if @solved_flag
    end
  end

  def set_row_answer(row_num,answer)
    # 引数で与えられた解の候補に従い、盤面を編集する
    counter = 0
    hint_index = 0
    answer.each do |num|
      num.times do
        @field[row_num][counter] = 0 # 白マスを配置
        counter += 1
      end
      return if hint_index == @row[row_num].hint_num
      @row[row_num][hint_index].times do
        @field[row_num][counter] = 1 # 黒マスを配置
        counter += 1
      end
      hint_index += 1
    end
  end

  def check_field
    # 盤面が完成し、解けているかをチェックするメソッド。
    # それぞれの行は必ず合っているので、それぞれの列についてチェックする
    @column.each_with_index do |column,i|
      value = []
      counter = 0
      @row.length.times do |y|
        if @field[y][i] == 0 then
          next if counter == 0
          value << counter
          counter = 0
        else
          counter += 1
          value << counter if y == (@row.length - 1)
        end
      end
      return false unless value == @column[i].nums # ヒントと一致しない行が1つでもあれば、チェック終了
    end
  end
end
row.txt
3
1,1,1
1
1
3
column.txt
1
1,1
5
1,1
1

Line_hintクラス

Line_hintクラスは、1つの行(または列)のヒントを表現するためのクラスです。メンバ変数として、ヒントの情報である黒マスの数字群を保持しており(メンバ変数@nums)、このメンバ変数の内容を基に、行(または列)に配置可能な黒マスの置き方の組み合わせを全て求めることができます。
create_answer_candidateメソッドが、黒マスの置き方の組み合わせを全て求めるメソッドです。黒マスの配置を、白マスの並び方で表現し、メンバ変数@answer_candidateに加えていきます。

puzzle.rb(続き)
class Line_hint
  def initialize(line_length,nums)
    @line_length = line_length
    @nums = nums.to_a # ヒントとなる数字群
    @answer_candidate
    create_answer_candidate
    #p @answer_candidate
  end

  attr_reader :nums

  def create_answer_candidate
    # 考えられる解の候補を、全て作成
    black_num = @nums.inject {|sum, n| sum + n} # 黒マスの総和
    white_num = @line_length - black_num # 白マスの総和

    candidate = Array.new(@nums.length+1,1)
    candidate[0] = 0
    candidate[-1] = 0
    remain_white_num = white_num - (candidate.length - 2) # 残っている、分配可能な白マスの数
    numbers = (0..candidate.length-1).to_a
    indexes = numbers.repeated_combination(remain_white_num).to_a # 白マスを割り当てるArrayのindex
    @answer_candidate = indexes.map do |arr|
      answer_element = candidate.dup
      arr.each do |each|
        answer_element[each] += 1
      end
      answer_element
    end
  end

  def each
    @answer_candidate.length.times do |i|
      yield @answer_candidate[i]
    end
  end

  def [](index)
    @nums[index]
  end

  def hint_num
    @nums.length
  end
end

黒マスの置き方の表現について

黒マスの置き方については、白マスがどのように並ぶかを表すことで表現します。例えば、図のようにマス目の数が5つの行に長さ1の黒マスを2つずつ置いた場合、左端の白マスは0個、黒マスの間の白マスは1個、右端の白マスは2個なので、[0,1,2]として黒マスの配置を表現します。

配置の表現方法.png

solveメソッド

solveメソッドでは、配置可能な黒マスの置き方全てについて探索を行い、解を探します。上にある行から順番に、それぞれの行での黒マスの配置を決めながら、深さ優先探索で解を探していきます。
全ての行の黒マスの配置が決まったら、全体の黒マスの配置が正解であるかどうかをチェックします。それぞれの列について黒マスが正しく配置されているかをチェックします。
行の表現.png

解の探索.png

実行結果

 xxx 
x x x
  x  
  x  
 xxx