Hatena::ブログ(Diary)

ザリガニが見ていた...。 このページをアンテナに追加 RSSフィード

2015-01-23

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

前回までに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

f:id:zariganitosh:20150122180147p:image:w450

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

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

 @@ -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


f:id:zariganitosh:20150123080457p:image:w450

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

途中経過を見せる

  • 途中経過を見せるには、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}

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

f:id:zariganitosh:20150123082034p:image:h450

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

  • そこで、途中経過は位置を変えずに常に同じ位置で出力して、解が見つかった時だけ次の出力位置に移動するようにしたい。
  • 通常、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に公開する予定。

ledled 2015/08/17 10:29 むか〜し購入した片面縛りのペントミノがありまして、この回答は何通りあるのか知りたく、通常ペントミノの解放ソースを公開されている方を探していてたどり着きました。

形としては反転を切って「回転」だけにした後述のピース構成になると思っているのですが、このままだと例えばNo.86のzピースの形が回転だけでなく反転形も使われていたり思ったような結果となりませんでした。

アルゴリズム的に反転引数を1にしても判定形状が使われているように思うのですが、残念ながら当方の頭ではこちらのピース探索アルゴリズムを読み解けずw手詰まっております。

非効率でも構わないので、もし当該ピース構成での探索ができたらお願いしたいですが、お時間がないようでしたら以下2点のヒントだけでもお力をお借りしたいのです。

 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, 2, :F, 172),
Piece.new([[1,1,0], [0,1,0], [0,1,1]], 1, 2, :Z, 211),
Piece.new([[1,1,1], [1,1,0]], 1, 4, :P, 70),
Piece.new([[1,1,1,0], [0,0,1,1]], 1, 4, :N, 121),
Piece.new([[1,1,1,1], [0,1,0,0]], 1, 4, :Y, 170),
# 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]], 1, 4, :L, 3),
# 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)]

zariganitoshzariganitosh 2015/08/18 09:58 ledさん、
あまり検証できていませんが、試してみました。

> 2.うまく修正することで、反転を使わず回転のみだけ使用し解を出すことは出来ますでしょうか?

片面縛りにするなら、55行目のmの値を1に固定すると、線対称の反転を無視するようになります。
 -55: for i in (1..m)
 +55: for i in (1..1)
(あるいは、66行目のpp=に続く各ピースの左右反転の回数をすべて1に変更してもOKです)


> アルゴリズム的に反転引数を1にしても判定形状が使われているように思うのですが、

Zのピース原型データが最初から反転しているので、70行目を以下のように修正すると、本来のZと同じ向きになります。
 -70: Piece.new([[1,1,0], [0,1,0], [0,1,1]], 2, 2, :Z, 211),
 +70: Piece.new([[0,1,1], [0,1,0], [1,1,0]], 2, 2, :Z, 211),

ちなみに、このpentomino.rbにおいては、修正後のZのピース原型データは二次元で考えると以下のように解釈されます。
(注意:配列要素の先頭が下部、末尾が上部となります)
 [1,1,0]
 [0,1,0]
 [0,1,1]

ピース原型の配列データに続く引数の意味は、以下のようになっています。
 Piece.new(a=[ピース原型の配列データ], m=左右反転の回数, n=90度回転の回数, l=ピース名称, c=ピースの色)


> 1.利用している定義ピースの形状を描画する関数を作ることは可能でしょうか?

上記2箇所の修正をすると、片面縛りのペントミノを解くコードになると思います。
こちらで実行してみたところ、Zピースの反転を修正後の解は、58通りとなりました。
(修正前は86通りでした。表裏の向きによって解数が違うことに驚きました)

zariganitoshzariganitosh 2015/08/18 10:04 Zピース以外にも、表裏が違っているピースがあるかもしれません。
(NとYが怪しいかもしれません)
その場合は、上記の要領で修正してみてください。

ledled 2015/08/18 10:18 色々ご教授ありがとうございました!
試してみます。

この片面縛り異様に難しいです。
小学校の時購入し、この20数年パズル好きで意地っ張りの方に渡しているのですが、表向きで収まって返ってきたのは3人だけですw
途中の手順が全く解につながらないペントミノで、ここまで解が絞られるとやっぱり確率論的に苦しいのでしょうか・・・。

ledled 2015/08/18 14:01 ありがとうございます。
ピース見直して試してみました。

>(注意:配列要素の先頭が下部、末尾が上部となります)

これが解っていなかった(上部からだと思っていました)ので、後述のように修正しました。
あと、Fの値の回転数指定の所が2となっていたので4に変更しました。
その他の反転類のソースの所は第二引数のmを全て1にしているのでforのところはいじっておりません。

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([[0,1,0], [0,1,1], [1,1,0]], 1, 4, :F, 172), # Piece.new([[1,1,0], [0,1,1], [0,1,0]], 1, r, :F, 172)
Piece.new([[0,1,1], [0,1,0], [1,1,0]], 1, 2, :Z, 211), # Piece.new([[1,1,0], [0,1,0], [0,1,1]], 2, 2, :Z, 211)
Piece.new([[1,1,1], [0,1,1]], 1, 4, :P, 70), # Piece.new([[1,1,1], [1,1,0]], 2, 4, :P, 70)
Piece.new([[1,1,1,0], [0,0,1,1]], 1, 4, :N, 121), # Piece.new([[1,1,1,0], [0,0,1,1]], 2, 4, :N, 121)
Piece.new([[1,1,1,1], [0,0,1,0]], 1, 4, :Y, 170), # 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], [0,0,0,1]], 1, 4, :L, 3), # 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)]

これで実行すると256の解がでるのですが、重複が起こってしまうようです。
全部調べられてないのですが、とりあえず以下の2個が同じです。

・No. 6
・No. 190

片面縛りにすると、ボードの回転に対する重複解の除去アルゴリズムの部分に影響出てしまうのでしょうか?

zariganitoshzariganitosh 2015/08/18 15:07 この話題の最初の記事から読むと何か分かるかもしれません。

> 明治ミルクチョコーレートパズルの解をすべて探す
> http://d.hatena.ne.jp/zariganitosh/20150112/pentomino_programming#exclude_repeat

正しさの検証はしてませんが、Fピースの回転数を2回転に制限すると、6x10サイズで128通りの解数になりました。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/zariganitosh/20150123/making_of_pentomino_command
リンク元