More than 5 years have passed since last update.

株式会社エイチームウェルネス

Rubyで数独を解いてみた（しらみつぶし法）

Last updated at 2019-05-29Posted at 2019-05-27

はじめに

Ruby勉強のために、昔好きだった数独を深さ優先探索などを利用して解きました。回答のし易さを優先し、回答速度は犠牲にしてます。

数独のルール

① 9列あるタテのどの列にも1から9の数字が1つずつ入ります。
② 9行あるヨコのどの行にも1から9の数字が1つずつ入ります。
③ 太線で囲まれた3×3のブロック内にも1から9の数字が1つずつ入ります。

引用 : 数独ナンプレの解き方

用語の説明

使う用語を統一しておきます。

グリッド : セル全体を
セル : 一つ一つのマス
row : 行
column : 行
正方形（square） : 3 × 3 のブロック
セルの番号は、以下の図に対応させている

引用 : 盤面・セル・候補数字の表記法

問題

今回は、下記の問題を解くことにします。

出典：「数独通信 Vol.26」 P.4

次に、プログラムで解く下準備を説明します。

問題のフォーマット

問題の入力を簡単にするために、グリッド表示されている数独の問題は以下の形式に変換しておきます。

problem.txt

.8.....1. 1..2..9.. ..7..4..3 3...1..9. ...7.2... .6..8...4 9..4..1.. ..4..3..5 .2.....8.

問題と回答プログラムは別ファイルで管理

同階層に問題と回答プログラムは別ファイルで管理するようにします。

index.rb（回答プログラム）
problem.txt（問題）

なので、problem.txtには、図（出典：「数独通信 Vol.26」 P.4）に示した問題を変換したものを入れておきます。

problem.txt

.8.....1. 1..2..9.. ..7..4..3 3...1..9. ...7.2... .6..8...4 9..4..1.. ..4..3..5 .2.....8.

index.rbには

$ ruby index.rb problem.txt

とコマンドを打てば、別ファイル（problem.txt）の内容を、（繰り返し呼びだせる）ARGFオブジェクトとして呼び出せるようにしました。

ARGF : スクリプトに指定した引数 (Object::ARGV を参照) をファイル名とみなして、それらのファイルを連結した 1 つの仮想ファイルを表すオブジェクト
object ARGF (Ruby 2.6.0)

index.rb

ARGF.each do |line|
 # 処理
end

引数（line）には、problem.txtに入っている1つ1つの数字や.をオブジェクト（Enumerable::Enumerator オブジェクト）として格納され処理させるようにしました。

解き方の方針

値が入ってないセルに入り得る値を入れてみて、しらみつぶしに検証していく方法で解きました。
（入るはずのない値は入れないようにしています）

基本的な手順

(1) 空のセルを選ぶ
(2) そのセルに値を一つ入れる
- そのセルに入ることができる候補の値が少なく、かつセル番号が若い順に、値を入れていく
(3) 数独のルールに従っているか検証
- 従ってる → (1)に戻る
- 従っていない → 別の値を試す

実際の全処理

実際の全処理は下記の用に書きました。

index.rb

ARGF.each do |line|
  remove_space_line = line.gsub(/\s/, '')
  value_or_nil_lists = convert_dot_to_nil_lists(remove_space_line)
  solved_lists = solve(value_or_nil_lists)
  print_grid(solved_lists)
end

上に書いた各処理が連結されています。順を追って解説しますが、全てのプログラムを書いていきます。

index.rb

# 
# param [Array] grid 1から9の値か、nilが81個並んだ配列
# return [Array] 改行とスペース消した値を9×9のgrid
#
def print_grid(grid, pad="\n")
  print (0..8).map{ |i|
    grid[9*i, 9].map{ |v|
      (v || ".") }.join("") }.join(pad), "\n"
end

# 
# param [String] string 1から9の値か、nilが81個並んだ一元配列
# return [Array] .をnilに変換
#
def convert_dot_to_nil_lists(string)
  string.split(//).map{ |c| c == "." ? nil : c.to_i }
end

# 
# param [Array] grid 
# param [Integer] cn セル番号
# return [Array] 該当する行に存在する値を配列としてを返す
#
def row(grid, cn)
  grid[9 * (cn / 9), 9]
end

# 
# param [Array] grid 
# param [Integer] cn セル番号
# return [Array] 該当する列に存在する値を配列としてを返す
#
def column(grid, cn)
  (0..8).map{ |k| grid[9 * k + cn % 9] }
end

# 
# param [Array] grid 
# param [Integer] cn セル番号
# return [Array] 該当する正方形に存在する値を配列としてを返す
#
def square(grid, cn)
  (0..8).map{ |k| grid[9*(3*(cn/9/3)+(k/3))+3*(cn%9/3)+(k%3)]}
end

# 
# param [Array] grid 1から9の値か、`nil`が81個並んだ配列
# return [Array] nil　になっている位置をインデックス番号にして配列として返す
#
def empty_cell_numbers(grid)
  (0..80).reject{ |p| grid[p] }
end

# 
# param [Array] grid 
# param [Integer] cell_number 
# return [Array] 該当するセル番号の行、列、正方形に存在しない値を配列としてを返す
#
def possible_numbers(grid, cell_number)
  (1..9).to_a - fixed_numbers(grid, cell_number)
end

# 
# param [Array] grid 
# param [Integer] cell_number 
# return [Array] 該当するセル番号の行、列、正方形に存在する値を配列としてを返す
#
def fixed_numbers(grid, cell_number)
  (
    row(grid, cell_number).compact |
    column(grid, cell_number).compact |
    square(grid, cell_number).compact
  )
end

# 
# param [Array] grid
# return [Array] grid 回答
#
def solve(grid)
  empty_cell_numbers = empty_cell_numbers(grid)

  candidates = empty_cell_numbers.map{ |cell_number|
    [cell_number, possible_numbers(grid, cell_number)]
  }

  ordered_candidates = candidates.sort_by{ |cell| cell[1].length }

  if ordered_candidates.empty?
    print "\e[31m"  # bash出力を赤色に
    puts 'complete↓'
    print "\e[0m"   # bash出力の色を元に戻す
    grid
  else

    p ordered_candidates[0]

    cell_number, candidate_values = ordered_candidates[0]

    candidate_values.each do |value|
      grid[cell_number] = value

      sleep(0.02)
      print_grid(grid)
      puts "残り#{grid.count(nil)}個"
      puts '---------'
      return grid if solve(grid)
    end

    p "grid[#{cell_number}] => #{grid[cell_number]} 取り消し"
    grid[cell_number] = nil  # 全て失敗したら未確定に戻す
    return false
  end
end

# 
# return [ARGF] 数独を表示
#
ARGF.each do |line|
  remove_space_line = line.gsub(/\s/, '')
  value_or_nil_lists = convert_dot_to_nil_lists(remove_space_line)
  solved_lists = solve(value_or_nil_lists)
  print_grid(solved_lists)
end

各メソッドの説明

問題が解かれる手順を説明しつつ、各メソッドの説明をします。基本的には、下記のメソッド内で別ファイルからデータを受け取って、ある処理をする中で、数独の問題を解いています。

ARGF.each do |line|
  remove_space_line = line.gsub(/\s/, '')
  value_or_nil_lists = convert_dot_to_nil_lists(remove_space_line)
  solved_lists = solve(value_or_nil_lists)
  print_grid(solved_lists)
end

一つづつメソッドの概要を説明すると、

print_grid()
- param [Array] grid 1から9の値か、nilが81個並んだ一元配列
- return [Array] 改行とスペース消した値を9×9のgrid
convert_dot_to_nil_lists()
- param [String] 1から9の値か、nilが81個並んだ一元配列
- return [Array] .をnilに変換
solve()
- param [Array] 1から9の値か、nilが81個並んだ一元配列
  - empty_cell_numbers()
    - param [Array] grid 1から9の値か、nilが81個並んだ一元配列
    - return [Array] nilになっている位置をインデックス番号にして配列として返す
  - 変数 candidates に入るデータ
    - index[0] : インデックス番号
    - index[1] : セルに入ることができる値の候補
    - => 配列 [index, [候補となる値（複数も可）]]で返す
  - 変数 ordered_candidates に入るデータ
    - 候補となる値の数が少ない順に並べる
    - => 配列 [index, [候補となる値（複数も可）]]で返す
  - 条件文 ordered_candidates.empty?
    - TRUE
      - 配列の中身が空（全てのセルに1から9の値が入っている）ならgridを返す
    - FALSE
      - 配列に要素が在る場合、指定したindex番号のセルに、候補となる値を格納してメソッドsolve()を再帰的に呼び出す
line.gsub(/\s/, '')
- 引数lineにあるスペースの削除

変数 `candidates` に関わる処理

変数 candidates に入るデータには、数独のルールに従っているかの条件をクリアしている値が、候補となる値として格納されます。

関わらない処理を...で省略しました。


# 
# param [Array] grid 
# param [Integer] cn セル番号
# return [Array] 該当する行に存在する値を配列としてを返す
#
def row(grid, cn)
  grid[9 * (cn / 9), 9]
end

# 
# param [Array] grid 
# param [Integer] cn セル番号
# return [Array] 該当する列に存在する値を配列としてを返す
#
def column(grid, cn)
  (0..8).map{ |k| grid[9 * k + cn % 9] }
end

# 
# param [Array] grid 
# param [Integer] cn セル番号
# return [Array] 該当する正方形に存在する値を配列としてを返す
#
def square(grid, cn)
  (0..8).map{ |k| grid[9*(3*(cn/9/3)+(k/3))+3*(cn%9/3)+(k%3)]}
end

# 
# param [Array] grid 1から9の値か、`nil`が81個並んだ配列
# return [Array] nil　になっている位置をインデックス番号にして配列として返す
#
def empty_cell_numbers(grid)
  (0..80).reject{ |p| grid[p] }
end

# 
# param [Array] grid 
# param [Integer] cell_number 
# return [Array] 該当するセル番号の行、列、正方形に存在しない値を配列としてを返す
#
def possible_numbers(grid, cell_number)
  (1..9).to_a - fixed_numbers(grid, cell_number)
end

# 
# param [Array] grid 
# param [Integer] cell_number 
# return [Array] 該当するセル番号の行、列、正方形に存在する値を配列としてを返す
#
def fixed_numbers(grid, cell_number)
  (
    row(grid, cell_number).compact |
    column(grid, cell_number).compact |
    square(grid, cell_number).compact
  )
end

def solve(grid)
...

  candidates = empty_cell_numbers.map{ |cell_number|
    [cell_number, possible_numbers(grid, cell_number)]
  }

...
end

メソッド row の処理内容

該当する行に存在する値を配列としてを返します。

例えば、セル番号0の行は以下の配列を返します。

=> [nil, 8, nil, nil, nil, nil, nil, 1, nil]

メソッド column の処理内容

該当する列に存在する値を配列としてを返します。

例えば、セル番号0の列は以下の配列を返します。

=> [nil, 1, nil, 3, nil, nil, 9, nil, nil]

メソッド square の処理内容

該当する正方形に存在する値を配列としてを返します。

例えば、セル番号0の正方形は以下の配列を返します。

=> [nil, 8, nil, 1, nil, nil, nil, nil, 7]

メソッド possible_numbers の処理内容

該当するセル番号の行、列、正方形に存在しない値を配列としてを返します。

例えば、セル番号0の場合は以下の配列を返します。

=> [2, 4, 5, 6]

メソッド fixed_numbers の処理内容

該当するセル番号の行、列、正方形に存在する値を配列としてを返します。

例えば、セル番号0の場合は以下の配列を返します。

=> [8, 1, 3, 9, 7]

上記のような、様々なメソッドを経て、数独の条件に合う値を選定しています。

答え合わせ

0.2秒間隔でセルに値を入力していく映像が以下になります。

数独のチェックツール（ナンプレ解答プログラム）を使って、問題がないか確認できました。

パフォーマンス

ruby index.rb problem.txt

0.36 real # コマンドを実行するためにかかった時間
0.20 user
0.07 sys

sleepはコメントアウトしている。

勉強になったこと

配列処理系のメソッドの挙動の理解（each, select, reject, map, compact）
アルゴリズム（深さ優先探索）

次回やること

数独の基本解法（ブロッケン, レッツミー, マスミ,いずれにしても理論,予約など）のプログラムを実装し解いてパフォーマンスを改善させたい
- しらみつぶし法のデメリットは、問題によってはとても処理が長くなる場合がある
最終的には、部分解答して、最適な基本解法を選択する、いわゆる「解き筋」をモデル化して解きたい

参考

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Rubyで数独を解いてみた（しらみつぶし法）

はじめに

数独のルール

用語の説明

問題

問題のフォーマット

問題と回答プログラムは別ファイルで管理

解き方の方針

実際の全処理

各メソッドの説明

変数 candidates に関わる処理

メソッド row の処理内容

メソッド column の処理内容

メソッド square の処理内容

メソッド possible_numbers の処理内容

メソッド fixed_numbers の処理内容

答え合わせ

パフォーマンス

勉強になったこと

次回やること

参考

変数 `candidates` に関わる処理