2015-01-23

前回までにc言語なら0.9秒（さらなる高速化を追記した）でペントミノパズル（6×10）の全解を出力できるようになった。1秒切ったので、高速化についてはこれで満足。しかし、何かまだ満たされないものがある。
最速を狙ったコマンドは1度試せばそれで満たされてしまう。たぶん、もう二度と実行することはなくなる。そうではなく、何度も使いたくなるpentominoコマンドにしておきたい。

追加する機能

使って楽しいコマンドを目指して、以下の機能を追加するのだ。

味気ないローマ字表現はやめて、カラフルなブロックにしたい。
ブロックを置きながら試行錯誤する途中経過を見せたい。
コマンドらしく、オプション指定やboardサイズも指定できるようにしておく。

面倒な処理がありそうなので使い慣れているRubyで書いてみる。

現状のコード

# coding: utf-8
BROW, BCOL = 10, 6

# すべてのピース形状をPieceオブジェクトの配列に保存する
class Piece
  attr_accessor :used, :form, :loc_form, :letter

  def initialize(a, m, n, l)
    @used = false
    @form = []
    @loc_form = []
    @letter = l
    for i in (1..m)
      for j in (1..n)
        @form << [a, a.flatten.index(1)]
        a = a.transpose.reverse # rotate L
      end
      a = a.map(&:reverse) # flip LR
    end
  end
end
  
pp = [Piece.new([[0,1,0], [1,1,1], [0,1,0]], 1, 1, :X),
      Piece.new([[1,1,1], [1,0,1]]         , 1, 4, :U),
      Piece.new([[1,1,0], [0,1,1], [0,0,1]], 1, 4, :W),
      Piece.new([[1,1,0], [0,1,1], [0,1,0]], 1, 2, :F),
      Piece.new([[1,1,0], [0,1,0], [0,1,1]], 2, 2, :Z),
      Piece.new([[1,1,1], [1,1,0]],          2, 4, :P),
      Piece.new([[1,1,1,0], [0,0,1,1]],      2, 4, :N),
      Piece.new([[1,1,1,1], [0,1,0,0]],      2, 4, :Y),
      Piece.new([[1,1,1], [0,1,0], [0,1,0]], 1, 4, :T),
      Piece.new([[1,1,1,1], [1,0,0,0]],      2, 4, :L),
      Piece.new([[1,1,1], [1,0,0], [1,0,0]], 1, 4, :V),
      Piece.new([[1,1,1,1,1]],               1, 2, :I)]

pp.each_with_index do |piece, i|
  piece.form.each do |form|
    a = []
    form[0].each_with_index do |row, r|
      row.each_with_index do |col, c|
        a << r * (BCOL + 1) + c - form[1] if col == 1
      end
    end
    piece.loc_form << a
  end
end



# boardの初期化
board = Array.new((BROW + 1) * (BCOL + 1), 0)
board.each_with_index do |b, i|
  board[i] = 100 if ((i + 1) % (BCOL + 1)) == 0 || i >= ((BCOL + 1) * BROW)
end



# パズルの解を求める
def display_board(board, pp)
  $counter += 1
  puts "No. #{$counter}"
  a = []
  board.each_slice(BCOL + 1) do |line|
    a << line.reject {|i| i == 100}.map {|i| pp[i - 1].letter}
  end
  a[0..-2].transpose.each {|line| puts line.join}
  puts
end

def try_piece(board, pp, lvl)
  $try_counter += 1
  x = board.index(0)
  pp.each_with_index do |piece, i|
    next if piece.used
    piece.loc_form.each do |blocks|
      next if board[x + blocks[0]]>0 || board[x + blocks[1]]>0 || board[x + blocks[2]]>0 || board[x + blocks[3]]>0 || board[x + blocks[4]]>0
      # ピースを置く
      blocks.each {|b| board[x + b] = i + 1}
      piece.used = true
      # すべてのピースを置ききったらTrueを返す（recursiveコールの終了）
      if lvl == 11 then
        display_board(board, pp)
        # ピースを戻す
        blocks.each {|b| board[x + b] = 0}
        piece.used = false
        return
      end
      # 次のピースを試す
      try_piece(board, pp, lvl + 1)
      # ピースを戻す
      blocks.each {|b| board[x + b] = 0}
      piece.used = false
    end
  end
end

$counter = 0
$try_counter = 0
try_piece(board, pp, 0)
puts "解合計: #{$counter}"
puts "操作数: #{$try_counter}"

カラー表示

ターミナルでカラー表示するためには、エスケープシーケンスで色を指定する必要がある。
例えば、以前jcalコマンドを作った時の色指定はこんな感じ。

$ ruby -e 'puts "\e[31mRed"'
Red

"\e[31m"の部分がエスケープシーケンスによる色の指定部分。
- 30-37の数値によって、8色の色が指定できる。
ところが、今回のペントミノは全部で12ピースある。8色では足りない...。
しかも、白と黒を除くと、使えるカラーは6色のみ。
減光の指定をすればどうにか12色の区別はできるが、色の選択の余地がない。
カラフルにしたいのだけど、このままでは残念なカラーになりそうな予感...。

調べてみると、なんと今時のターミナルは256色表示に対応しているらしい！
以下のように指定すると、0-255の値でカラー指定ができる。
- 38は、フォアグラウンドカラーを意味し、（ちなみに、48=バックグラウンドカラーを意味する）
- 5は、0-255のカラーパレットコードを使うことを意味するようだ。
- 211は、ピンク色のカラーコード。

$ ruby -e 'puts "\e[38;5;211mPink"'
Pink

256色すべてのカラーサンプルは、以下のワンライナーで出力された。

$ for c in {0..255}; do printf "\e[48;5;${c}m%8d\e[m" $c; done; echo

これで色選択の自由は格段に向上した！自分好みの色を選択できそう。

ピース形状をカラーブロックで表示するように変更してみた。



 @@ -3,13 +3,14 @@ BROW, BCOL = 10, 6

  

  # すべてのピース形状をPieceオブジェクトの配列に保存する

  class Piece

 -  attr_accessor :used, :form, :loc_form, :letter

 +  attr_accessor :used, :form, :loc_form, :letter, :color

  

 -  def initialize(a, m, n, l)

 +  def initialize(a, m, n, l, c)

      @used = false

      @form = []

      @loc_form = []

      @letter = l

 +    @color = c

      for i in (1..m)

        for j in (1..n)

          @form << [a, a.flatten.index(1)]

 @@ -20,18 +21,18 @@ class Piece

    end

  end

    

 -pp = [Piece.new([[0,1,0], [1,1,1], [0,1,0]], 1, 1, :X),

 -      Piece.new([[1,1,1], [1,0,1]]         , 1, 4, :U),

 -      Piece.new([[1,1,0], [0,1,1], [0,0,1]], 1, 4, :W),

 -      Piece.new([[1,1,0], [0,1,1], [0,1,0]], 1, 2, :F),

 -      Piece.new([[1,1,0], [0,1,0], [0,1,1]], 2, 2, :Z),

 -      Piece.new([[1,1,1], [1,1,0]],          2, 4, :P),

 -      Piece.new([[1,1,1,0], [0,0,1,1]],      2, 4, :N),

 -      Piece.new([[1,1,1,1], [0,1,0,0]],      2, 4, :Y),

 -      Piece.new([[1,1,1], [0,1,0], [0,1,0]], 1, 4, :T),

 -      Piece.new([[1,1,1,1], [1,0,0,0]],      2, 4, :L),

 -      Piece.new([[1,1,1], [1,0,0], [1,0,0]], 1, 4, :V),

 -      Piece.new(1,1,1,1,1,               1, 2, :I)]

 +pp = [Piece.new([[0,1,0], [1,1,1], [0,1,0]], 1, 1, :X, 141),

 +      Piece.new([[1,1,1], [1,0,1]]         , 1, 4, :U,   6),

 +      Piece.new([[1,1,0], [0,1,1], [0,0,1]], 1, 4, :W, 104),

 +      Piece.new([[1,1,0], [0,1,1], [0,1,0]], 1, 2, :F, 172),

 +      Piece.new([[1,1,0], [0,1,0], [0,1,1]], 2, 2, :Z, 211),

 +      Piece.new([[1,1,1], [1,1,0]],          2, 4, :P,  70),

 +      Piece.new([[1,1,1,0], [0,0,1,1]],      2, 4, :N, 121),

 +      Piece.new([[1,1,1,1], [0,1,0,0]],      2, 4, :Y, 170),

 +      Piece.new([[1,1,1], [0,1,0], [0,1,0]], 1, 4, :T,  42),

 +      Piece.new([[1,1,1,1], [1,0,0,0]],      2, 4, :L,   3),

 +      Piece.new([[1,1,1], [1,0,0], [1,0,0]], 1, 4, :V,  75),

 +      Piece.new(1,1,1,1,1,               1, 2, :I, 217)]

  

  pp.each_with_index do |piece, i|

    piece.form.each do |form|

 @@ -45,6 +46,8 @@ pp.each_with_index do |piece, i|

    end

  end

  

 +BLOCK_COLOR = [250] + pp.map{|i| i.color} + [0]

 +

  

  

  # boardの初期化

 @@ -55,13 +58,20 @@ end

  

  

  

 +# エスケープシーケンス定義

 +def bgcolor(nnn); "\e[48;5;#{nnn}m" ; end # 色指定の開始（nnn=0..255）

 +def reset       ; "\e[m"            ; end # 色指定の終了

 +

 +# 出力コード生成

 +def create_block(color); bgcolor(BLOCK_COLOR[color]) + "  " + reset; end

 +

  # パズルの解を求める

  def display_board(board, pp)

    $counter += 1

    puts "No. #{$counter}"

    a = []

    board.each_slice(BCOL + 1) do |line|

 -    a << line.reject {|i| i == 100}.map {|i| pp[i - 1].letter}

 +    a << line.reject {|i| i == 100}.map {|i| create_block(i)}

    end

    a[0..-2].transpose.each {|line| puts line.join}

    puts

カラーブロック表示の完了！

途中経過を見せる

途中経過を見せるには、pieceが置けたらその状態を出力すれば良いだけなので、以下のように変更してみた。



 @@ -67,7 +67,6 @@ def create_block(color); bgcolor(BLOCK_COLOR[color]) + "  " + reset; end

  

  # パズルの解を求める

  def display_board(board, pp)

 -  $counter += 1

    puts "No. #{$counter}"

    a = []

    board.each_slice(BCOL + 1) do |line|

 @@ -87,8 +86,10 @@ def try_piece(board, pp, lvl)

        # ピースを置く

        blocks.each {|b| board[x + b] = i + 1}

        piece.used = true

 +      display_board(board, pp)

        # すべてのピースを置ききったらTrueを返す（recursiveコールの終了）

        if lvl == 11 then

 +        $counter += 1

          display_board(board, pp)

          # ピースを戻す

          blocks.each {|b| board[x + b] = 0}

しかし、これでは大量の途中経過によって、もの凄い速さでスクロールしてしまう...。
大量の途中経過の中に解が埋もれてしまって、肝心な解が見えなくなってしまう...。

途中経過の出力位置を固定する

そこで、途中経過は位置を変えずに常に同じ位置で出力して、解が見つかった時だけ次の出力位置に移動するようにしたい。

通常、echoやputsで出力すると、出力位置は自動的に次の文字位置となるようにコントロールされている。
- 改行があれば、次の行の先頭に移動するようにコントロールされている。
この出力位置を自分でコントロールできれば、途中経過の位置を変えずに常に同じ位置に出力できるのだ。

出力位置もエスケープシーケンスを使ってコントロールできる。
例えば以下のコマンドは、最初 ABC と出力して、1秒後に xyz と上書きする。
- 1秒後に ABC が消えて、xyz に変更されるのだ。

$ echo ABC; sleep 1; echo -e "\033[Axyz"

\033[A の部分がエスケープシーケンス。

- \033 = \e、エスケープシーケンスの8進数表記。
- echoの場合\eではエスケープしてくれなかった。

- A = 出力位置（カーソル位置）を1行上に移動する。
- 2行上に移動したい時は2Aと書く。
- 3行上に移動したい時は3Aと書く。

必要なエスケープシーケンスはあと二つ。
- \033[2J = 画面全体を消去、
- \033[H = 画面左上にカーソル移動。

以上のエスケープシーケンスを追加して、以下のように修正してみた。



 @@ -59,23 +59,28 @@ end

  # エスケープシーケンス定義

 +def home        ; "\e[H"            ; end # カーソル位置を画面左上へ移動（ホームポジション）

 +def clear(n=2)  ; "\e[#{n}J"        ; end # n=(0:画面先頭からカーソル位置まで消去, 1:カーソル位置から画面末尾まで消去, 2:画面全体を消去)

 +def moveup(n)   ; "\e[#{n}A"        ; end # カーソルを上方向へn行移動

  def bgcolor(nnn); "\e[48;5;#{nnn}m" ; end # 色指定の開始（nnn=0..255）

  def reset       ; "\e[m"            ; end # 色指定の終了

  

  # 出力コード生成

  def create_block(color); bgcolor(BLOCK_COLOR[color]) + "  " + reset; end

 +def reset_screen       ; home + clear                              ; end

 +def next_screen        ; "\n" * (BCOL + 2)                         ; end

  

 -# パズルの解を求める

 +# boardを表示

  def display_board(board, pp)

 -  puts "No. #{$counter}"

 +  puts moveup(BCOL + 1) + "No. #{$counter}"

    a = []

    board.each_slice(BCOL + 1) do |line|

      a << line.reject {|i| i == 100}.map {|i| create_block(i)}

    end

    a[0..-2].transpose.each {|line| puts line.join}

 -  puts

  end

  

 +# パズルの解を求める

  def try_piece(board, pp, lvl)

    $try_counter += 1

    x = board.index(0)

 @@ -91,6 +96,7 @@ def try_piece(board, pp, lvl)

        if lvl == 11 then

          $counter += 1

          display_board(board, pp)

 +        puts next_screen

          # ピースを戻す

          blocks.each {|b| board[x + b] = 0}

          piece.used = false

 @@ -107,6 +113,7 @@ end

  

  $counter = 0

  $try_counter = 0

 +puts reset_screen

  try_piece(board, pp, 0)

  puts "解合計: #{$counter}"

  puts "操作数: #{$try_counter}"

コマンドオプションを解析する

ここまで基本的な機能はほぼ完成したので、コマンドらしくオプション指定できるようにしておく。
- -qオプションは途中経過を表示しない指定。解だけを素早く出力してくれる。
- また、3から8の引数を指定することで、boardのサイズも変更できる。
  - 3×20、4×15、5×12、6×10、7×9-3、8×8-4。
  - 7×9-3、8×8-4は中央に穴が空いたドーナツ型のboard。

以上のオプション仕様にして、以下のように追記した。



 @@ -1,5 +1,46 @@

 +#!/usr/bin/ruby

  # coding: utf-8

 -BROW, BCOL = 10, 6

 +

 +require 'optparse'

 +

 +# オプション解析

 +$options = {}

 +OptionParser.new do |opt|

 +  opt.banner = 'Usage: pentomino [options] [board size(3-8)]'

 +  opt.on('-q', 'Hide progress putting a piece on board.(quiet mode)') {|v| $options[:quiet] = v}

 +  opt.separator('')

 +  opt.on('board size:',

 +         '    [3] x 20',

 +         '    [4] x 15',

 +         '    [5] x 12',

 +         '    [6] x 10 (Default)',

 +         '    [7] x  9 - 3',

 +         '    [8] x  8 - 4',

 +         )

 +  opt.separator('')

 +  opt.on('example:',

 +         '            6 x 10                        7 x 9 - 3                   8 x 8 - 4',

 +         '11 12 13 14 15 16 17 18 19 1A    11 12 13 14 15 16 17 18 19    11 12 13 14 15 16 17 18',

 +         '21 22 23 24 25 26 27 28 29 2A    21 22 23 24 25 26 27 28 29    21 22 23 24 25 26 27 28',

 +         '31 32 33 34 35 36 37 38 39 3A    31 32 33 34 35 36 37 38 39    31 32 33 34 35 36 37 38',

 +         '41 42 43 44 45 46 47 48 49 4A    41 42 43          47 48 49    41 42 43       46 47 48',

 +         '51 52 53 54 55 56 57 58 59 5A    51 52 53 54 55 56 57 58 59    51 52 53       56 57 58',

 +         '61 62 63 64 65 66 67 68 69 6A    61 62 63 64 65 66 67 68 69    61 62 63 64 65 66 67 68',

 +         '                                 71 72 73 74 75 76 77 78 79    71 72 73 74 75 76 77 78',

 +         '                                                               81 82 83 84 85 86 87 88',

 +         )

 +  begin

 +    opt.parse!(ARGV)

 +    BCOL = (ARGV[0] || 6).to_i

 +    BROW = 64 / BCOL

 +    raise "Invalid board size: #{BCOL}" if BCOL < 3 || 8 < BCOL

 +  rescue => e

 +    puts e

 +    exit

 +  end

 +end

 +

 +

  

  # すべてのピース形状をPieceオブジェクトの配列に保存する

  class Piece

 @@ -55,6 +96,8 @@ board = Array.new((BROW + 1) * (BCOL + 1), 0)

  board.each_with_index do |b, i|

    board[i] = 100 if ((i + 1) % (BCOL + 1)) == 0 || i >= ((BCOL + 1) * BROW)

  end

 +board[30], board[31], board[39], board[40] = 13, 13, 13, 13 if BCOL == 8

 +board[27], board[35], board[43]            = 13, 13, 13     if BCOL == 7

  

  

  

 @@ -91,7 +134,7 @@ def try_piece(board, pp, lvl)

        # ピースを置く

        blocks.each {|b| board[x + b] = i + 1}

        piece.used = true

 -      display_board(board, pp)

 +      display_board(board, pp) if !$options[:quiet]

        # すべてのピースを置ききったらTrueを返す（recursiveコールの終了）

        if lvl == 11 then

          $counter += 1

実行権限を追加して、ヘルプ表示してみた。

$ chmod a+x pentomino.rb
$ ./pentomino.rb -h
Usage: pentomino [options] [board size(3-8)]
    -q                               Hide progress putting a piece on board.(quiet mode)

board size:
    [3] x 20
    [4] x 15
    [5] x 12
    [6] x 10 (Default)
    [7] x  9 - 3
    [8] x  8 - 4

example:
            6 x 10                        7 x 9 - 3                   8 x 8 - 4
11 12 13 14 15 16 17 18 19 1A    11 12 13 14 15 16 17 18 19    11 12 13 14 15 16 17 18
21 22 23 24 25 26 27 28 29 2A    21 22 23 24 25 26 27 28 29    21 22 23 24 25 26 27 28
31 32 33 34 35 36 37 38 39 3A    31 32 33 34 35 36 37 38 39    31 32 33 34 35 36 37 38
41 42 43 44 45 46 47 48 49 4A    41 42 43          47 48 49    41 42 43       46 47 48
51 52 53 54 55 56 57 58 59 5A    51 52 53 54 55 56 57 58 59    51 52 53       56 57 58
61 62 63 64 65 66 67 68 69 6A    61 62 63 64 65 66 67 68 69    61 62 63 64 65 66 67 68
                                 71 72 73 74 75 76 77 78 79    71 72 73 74 75 76 77 78
                                                               81 82 83 84 85 86 87 88

./pentomino.rb 引数なしで6×10のペントミノパズルを解き始める。
./pentomino.rb 8 とすれば、8×8-4のドーナツ型のペントミノパズルを解き始める。
途中経過を見せずに素早く解を知りたい時は、./pentomino.rb -q 8。

修正後のコード

さらに幾つかの細々した修正をして、



 *       zariganitosh    37b694c 最初と最後にboardサイズを出力する

 *       zariganitosh    320cdce boardサイズの算出式を修正

 *       zariganitosh    ecc0da9 display_boardにタイトル表示の引数を追加する

 *       zariganitosh    94c4616 8x8正方形のboardは90度回転対称の重複解も除外する

現在のコードは以下の姿になった。

#!/usr/bin/ruby
# coding: utf-8

require 'optparse'

# オプション解析
$options = {}
OptionParser.new do |opt|
  opt.banner = 'Usage: pentomino [options] [board size(3-8)]'
  opt.on('-q', 'Hide progress putting a piece on board.(quiet mode)') {|v| $options[:quiet] = v}
  opt.separator('')
  opt.on('board size:',
         '    [3] x 20',
         '    [4] x 15',
         '    [5] x 12',
         '    [6] x 10 (Default)',
         '    [7] x  9 - 3',
         '    [8] x  8 - 4',
         )
  opt.separator('')
  opt.on('example:',
         '            6 x 10                        7 x 9 - 3                   8 x 8 - 4',
         '11 12 13 14 15 16 17 18 19 1A    11 12 13 14 15 16 17 18 19    11 12 13 14 15 16 17 18',
         '21 22 23 24 25 26 27 28 29 2A    21 22 23 24 25 26 27 28 29    21 22 23 24 25 26 27 28',
         '31 32 33 34 35 36 37 38 39 3A    31 32 33 34 35 36 37 38 39    31 32 33 34 35 36 37 38',
         '41 42 43 44 45 46 47 48 49 4A    41 42 43          47 48 49    41 42 43       46 47 48',
         '51 52 53 54 55 56 57 58 59 5A    51 52 53 54 55 56 57 58 59    51 52 53       56 57 58',
         '61 62 63 64 65 66 67 68 69 6A    61 62 63 64 65 66 67 68 69    61 62 63 64 65 66 67 68',
         '                                 71 72 73 74 75 76 77 78 79    71 72 73 74 75 76 77 78',
         '                                                               81 82 83 84 85 86 87 88',
         )
  begin
    opt.parse!(ARGV)
    BCOL = (ARGV[0] || 6).to_i
    BROW = (60.0 / BCOL).round
    raise "Invalid board size: #{BCOL}" if BCOL < 3 || 8 < BCOL
  rescue => e
    puts e
    exit
  end
end



# すべてのピース形状をPieceオブジェクトの配列に保存する
class Piece
  attr_accessor :used, :form, :loc_form, :letter, :color

  def initialize(a, m, n, l, c)
    @used = false
    @form = []
    @loc_form = []
    @letter = l
    @color = c
    for i in (1..m)
      for j in (1..n)
        @form << [a, a.flatten.index(1)]
        a = a.transpose.reverse # rotate L
      end
      a = a.map(&:reverse) # flip LR
    end
  end
end

r = BCOL == 8 ? 1 : 2
pp = [Piece.new([[0,1,0], [1,1,1], [0,1,0]], 1, 1, :X, 141),
      Piece.new([[1,1,1], [1,0,1]]         , 1, 4, :U,   6),
      Piece.new([[1,1,0], [0,1,1], [0,0,1]], 1, 4, :W, 104),
      Piece.new([[1,1,0], [0,1,1], [0,1,0]], 1, r, :F, 172),
      Piece.new([[1,1,0], [0,1,0], [0,1,1]], 2, 2, :Z, 211),
      Piece.new([[1,1,1], [1,1,0]],          2, 4, :P,  70),
      Piece.new([[1,1,1,0], [0,0,1,1]],      2, 4, :N, 121),
      Piece.new([[1,1,1,1], [0,1,0,0]],      2, 4, :Y, 170),
      Piece.new([[1,1,1], [0,1,0], [0,1,0]], 1, 4, :T,  42),
      Piece.new([[1,1,1,1], [1,0,0,0]],      2, 4, :L,   3),
      Piece.new([[1,1,1], [1,0,0], [1,0,0]], 1, 4, :V,  75),
      Piece.new([[1,1,1,1,1]],               1, 2, :I, 217)]

pp.each_with_index do |piece, i|
  piece.form.each do |form|
    a = []
    form[0].each_with_index do |row, r|
      row.each_with_index do |col, c|
        a << r * (BCOL + 1) + c - form[1] if col == 1
      end
    end
    piece.loc_form << a
  end
end

BLOCK_COLOR = [250] + pp.map{|i| i.color} + [0]



# boardの初期化
board = Array.new((BROW + 1) * (BCOL + 1), 0)
board.each_with_index do |b, i|
  board[i] = 100 if ((i + 1) % (BCOL + 1)) == 0 || i >= ((BCOL + 1) * BROW)
end
board[30], board[31], board[39], board[40] = 13, 13, 13, 13 if BCOL == 8
board[27], board[35], board[43]            = 13, 13, 13     if BCOL == 7



# エスケープシーケンス定義
def home        ; "\e[H"            ; end # カーソル位置を画面左上へ移動（ホームポジション）
def clear(n=2)  ; "\e[#{n}J"        ; end # n=(0:画面先頭からカーソル位置まで消去, 1:カーソル位置から画面末尾まで消去, 2:画面全体を消去)
def moveup(n)   ; "\e[#{n}A"        ; end # カーソルを上方向へn行移動
def bgcolor(nnn); "\e[48;5;#{nnn}m" ; end # 色指定の開始（nnn=0..255）
def reset       ; "\e[m"            ; end # 色指定の終了

# 出力コード生成
def create_block(color); bgcolor(BLOCK_COLOR[color]) + "  " + reset; end
def reset_screen       ; home + clear                              ; end
def next_screen        ; "\n" * (BCOL + 2)                         ; end

# boardを表示
def display_board(board, pp, title='')
  puts moveup(BCOL + 1) + title
  a = []
  board.each_slice(BCOL + 1) do |line|
    a << line.reject {|i| i == 100}.map {|i| create_block(i)}
  end
  a[0..-2].transpose.each {|line| puts line.join}
end

# パズルの解を求める
def try_piece(board, pp, lvl)
  $try_counter += 1
  x = board.index(0)
  pp.each_with_index do |piece, i|
    next if piece.used
    piece.loc_form.each do |blocks|
      next if board[x + blocks[0]]>0 || board[x + blocks[1]]>0 || board[x + blocks[2]]>0 || board[x + blocks[3]]>0 || board[x + blocks[4]]>0
      # ピースを置く
      blocks.each {|b| board[x + b] = i + 1}
      piece.used = true
      display_board(board, pp) if !$options[:quiet]
      # すべてのピースを置ききったらTrueを返す（recursiveコールの終了）
      if lvl == 11 then
        $counter += 1
        display_board(board, pp, "No. #{$counter} (TRY: #{$try_counter})")
        puts next_screen
        # ピースを戻す
        blocks.each {|b| board[x + b] = 0}
        piece.used = false
        return
      end
      # 次のピースを試す
      try_piece(board, pp, lvl + 1)
      # ピースを戻す
      blocks.each {|b| board[x + b] = 0}
      piece.used = false
    end
  end
end

$counter = 0
$try_counter = 0
puts reset_screen
puts "Pentomino #{BCOL}x#{BROW}"
puts next_screen
try_piece(board, pp, 0)
puts "Pentomino #{BCOL}x#{BROW}"
puts "解合計: #{$counter}"
puts "操作数: #{$try_counter}"

ひとまず完成。あとでgemに公開する予定。

ザリガニが見ていた...。

途中経過を表示しながら解くpentominoコマンドに仕上げる