i-Vinci TechBlog
株式会社i-Vinciの技術ブログ

Rubyでパズルゲームを解いてみた

パズル系ゲーム好きのタナカです。
特に最近は Number Sums というスマホアプリにハマっています。
今回は時間泥棒なゲームと決別するべく、普段バックエンドで使っているRuby言語を使って、盤面から答えを導くプログラムを作ろうと思います。

ゲームルールの確認

初期画面
各行と列の数字の合計が、ボードの側面にあるヒントと等しくなるように数字を選択します。
例えば二行目の 9 | 8 7 6 3 に注目すると、合計が9になる組み合わせは6と3しかないので、
9の行
このように8と7を答えから外して、6と3にチェックをつけます。すべての行と列で正しい数字にチェックをつけることができればゲームクリアです。
ゲームクリア

盤面をデータに落とし込む

見た目そのままCSVにして

  ,  6,  3, 21, 19
19,  2,  4,  8,  9
 9,  8,  7,  6,  3
11,  4,  8,  1,  7
10,  2,  3,  7,  7

Rubyに読み込ませて、Tableクラスに渡します。

csv = CSV.read('sample.csv', converters: :integer)
game_table = Table.new(csv)

Tableクラスでは３つの要素を持たせます。

  • column_hints
    • 各列のヒントの配列。今回で言うと 6, 3, 21, 19
  • row_hints
    • 各行のヒントの配列。今回で言うと縦に並ぶ 19, 9, 11, 10
  • table_rows
    • ヒント以外の全てのマスの二次元配列

table_rows には各マスの値と状態を保持したCellクラスを入れていきます。
Cellクラスでは次の要素を持たせます。

  • number
    • マスの値
  • is_answer
    • 答えになるかを表現します。
    • なる -> true
    • ならない -> false
    • 不明 -> nil

盤面を解くアルゴリズムを考える

さまざまなアプローチが考えられますが、今回は仮置きを中心に考えていきます。
例えば 11 | 4 8 1 7 の列について以下の処理をします

仮置き法 1

あるマスを注目します。今回は4に注目
4を除いたマスたちのどの組み合わせでもヒントの11を作ることができなければ、4は答えに確定する

仮置き法 2

あるマスを注目します。今回は8に注目
8を含んだマスたちのどの組み合わせでもヒントの11を作ることができなければ、8は答えではないことが確定する

できたコード

全てのマスが確定した時、クリア判定としループを止める処理や、コンソール上に答えを表示する処理を追加し、ひとまず完成とします。出来上がったものがこちら

読み込みと処理の呼び出し

# main.rb
require 'csv'
require './table'
require './solve'

# sample.csvを読み込む
csv = CSV.read('sample.csv', converters: :integer)
game_table = Table.new(csv)

puts '処理前'
game_table.display

solve(game_table)

puts '処理後'
game_table.display

テーブルクラス

# table.rb
# テーブルクラス
class Table
  attr_reader :table_rows,
              :column_hints,
              :row_hints

  # @param csv [Array[Array]] 二次元配列
  def initialize(csv)
    @table_rows = init_cells(csv)
    @column_hints = csv.first.slice(1..)
    @row_hints = csv.slice(1..).map(&:first)
  end

  # 列の配列を返す
  def table_columns
    table_rows.transpose
  end

  def display
    # 省略
  end

  private

  def init_cells(csv)
    csv.slice(1..).map do |row|
      row.slice(1..).map { |number| Cell.new number }
    end
  end
end

# マスのクラス
class Cell
  attr_reader :number
  attr_accessor :is_answer

  def initialize(number)
    @number = number
    @is_answer = nil
  end
end

メイン処理

# solve.rb
# @param tb [Table]
def solve(tb)
  # 全てのマスが確定するまでループ
  until all_cells_confirmed?(tb.table_rows)
    # 各行を仮置きで解く
    assume_cells(tb.row_hints, tb.table_rows)
    # 各列を仮置きで解く
    assume_cells(tb.column_hints, tb.table_columns)
  end
end

# 全てのマスが確定したかを判定
# @param tb [Table]
def all_cells_confirmed?(rows)
  rows.all? do |row|
    row.all? { |cell| !cell.is_answer.nil? }
  end
end

# 仮置きで解く
def assume_cells(hints, rows)
  hints.zip(rows) do |hint, row|
    # ヒントから、正解マスを引いた値を控える
    truthy_cells = row.select(&:is_answer)
    remaining_hint = hint - truthy_cells.sum(&:number)

    # 未確定のマスから順に候補(ターゲット)を決めて調べる
    unconfirmed_cells = row.select { |cell| cell.is_answer.nil? }
    unconfirmed_cells.each do |target|
      remaining_cells = unconfirmed_cells.reject { |cell| cell == target }
      # 仮置き法 1のフラグ
      cant_make_hint_without_target = true
      # 仮置き法 2のフラグ
      cant_make_hint_with_target = true

      unconfirmed_cells.size.times do |n|
        remaining_cells.combination(n).each do |comb|
          # 候補抜きで、ヒントに一致する組み合わせがあるなら
          # 仮置き法 1では確定しないので、フラグを折っておく
          if cant_make_hint_without_target && comb.sum(&:number) == remaining_hint
            cant_make_hint_without_target = false
          end

          next unless cant_make_hint_with_target

          # 候補含んで、ヒントに一致する組み合わせがあるなら
          # 仮置き法 2では確定しないので、フラグを折っておく
          cant_make_hint_with_target = false if comb.sum(&:number) + target.number == remaining_hint
        end
      end

      # 候補抜きで、ヒントに一致する組み合わせが1つもない -> 候補は答えで確定
      target.is_answer = true if cant_make_hint_without_target
      # 候補含んで、ヒントに一致する組み合わせが1つもない -> 候補は答えではないで確定
      target.is_answer = false if cant_make_hint_with_target
    end
  end
end

出力してみる

少し大きめの盤面を読み込ませて、コンソールに出力してみるとこんな感じ
ゲームクリア

最後に

ひとまず大枠ができて良かったです。まだ改善点がありますが、私はこのゲームを卒業できそうです。
以下残った課題

  • 間違った盤面を与えた時、無限ループに落ちないように盤面が更新されたかのフラグを持たせる
    • 盤面に更新がない、かつまだ未確定のマスがある = 問題が間違ってる
  • 組み合わせの列挙を工夫し、無駄な処理を減らす

次はキラーナンプレを解かせるゾー！

最新記事