Hatena::ブログ(Diary)

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

2015-01-15

RubyとC言語でもペントミノバズルを解いてみる

前回からの続き。

ペントミノパズルを解くPythonコードは、順調に高速化の道を歩んできた。

  • 3時間以上 → 50分 → 20分 → 3分。

ところで、現在はnumpyにほとんど依存しないコードになっている。ならば、他のプログラミング言語でも同じアルゴリズムでペントミノパズルを解けるはず。ふと、使い慣れているRubyで書いてみたらどうなるのだろう?と思った。やってみた。

Rubyで解く

  • 完全にPython脳になっていたので、endが必要な書き方に激しく無駄を感じてしまった。
  • いくつかのエラーに悩まされながら、どうにか以下の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}"

1分切ってる!

$ time ruby pentomino.rb

解合計: 2339
操作数: 10385817

real	0m59.035s
user	0m58.632s
sys	0m0.285s
  • なんと!同じアルゴリズムをRubyで書いたら、3倍も高速化されてしまった!
  • 昔からPythonは早くて、Rubyはノロマな子、と思い込んでいたので驚いた。
  • ちなみに、各言語のバージョン。
$ python --version
Python 2.7.6

$ ruby --version
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-darwin12.2.0]

C言語で解く

  • 高速化の話はもう終わりと思っていたのに。
  • Rubyで書き直した途端3倍も早くなってしまった!
  • こうなったらC言語で最速を狙いたい気分になる。
  • 完全なスクリプト言語な脳でC言語を触り始めると、もうエラーと警告が嵐のように出まくる。
    • メモリ構造を想像しながら構造体を定義して、
    • 可変長な要素の配列を作ることをあきらめつつ、配列を定義する。
    • 変数や関数は事前にすべて宣言しておかなければならない。
  • いくつもの試練を乗り越えて、ようやく以下のコードが完成する。
  • コンパイルして、実行してみると...
#include  <stdio.h>

typedef struct {
  int       pos[5];
} MinoPos;

typedef struct {
  char      name;
  int       used;
  int       formsize;
  MinoPos   form[8];
} Piece;

Piece pieces[] =
{
    {'X', 0, 1, {{0,6,7, 8,14}}},
    {'U', 0, 4, {{0,1,2, 7, 9},{0,1, 7,14,15},{0,2, 7, 8, 9},{0,1, 8,14,15}}},
    {'W', 0, 4, {{0,1,8, 9,16},{0,1, 6, 7,13},{0,7, 8,15,16},{0,6, 7,12,13}}},
    {'F', 0, 2, {{0,1,8, 9,15},{0,6, 7, 8,13}}},
    {'Z', 0, 4, {{0,1,8,15,16},{0,5, 6, 7,12},{0,1, 7,13,14},{0,7, 8, 9,16}}},
    {'P', 0, 8, {{0,1,2, 7, 8},{0,7, 8,14,15},{0,1, 6, 7, 8},{0,1, 7, 8,15},{0,1,2,8, 9},{0,1, 7, 8,14},{0,1,7,8, 9},{0,6, 7,13,14}}},
    {'N', 0, 8, {{0,1,2, 9,10},{0,6, 7,13,20},{0,1, 8, 9,10},{0,7,13,14,20},{0,1,2,6, 7},{0,7,14,15,22},{0,1,5,6, 7},{0,7, 8,15,22}}},
    {'Y', 0, 8, {{0,1,2, 3, 8},{0,7,14,15,21},{0,5, 6, 7, 8},{0,6, 7,14,21},{0,1,2,3, 9},{0,7, 8,14,21},{0,6,7,8, 9},{0,7,13,14,21}}},
    {'T', 0, 4, {{0,1,2, 8,15},{0,7, 8, 9,14},{0,7,13,14,15},{0,5, 6, 7,14}}},
    {'L', 0, 8, {{0,1,2, 3, 7},{0,7,14,21,22},{0,4, 5, 6, 7},{0,1, 8,15,22},{0,1,2,3,10},{0,1, 7,14,21},{0,7,8,9,10},{0,7,14,20,21}}},
    {'V', 0, 4, {{0,1,2, 7,14},{0,7,14,15,16},{0,7,12,13,14},{0,1, 2, 9,16}}},
    {'I', 0, 2, {{0,1,2, 3, 4},{0,7,14,21,28}}},
};

int board[77];
int counter, try_counter;

void init_board(void);
void print_board(void);
void try_piece(int level);
int board_index(int find_num);



void init_board(void)
{
  int i;

  for(i=0; i<77; i++){
    if(((i + 1) % 7) == 0 || i >= 70){
      board[i] = 100;
    }
  }
}

void print_board(void)
{
  int row, col;

  printf("No. %d\n", counter);
  for(row=0; row<6; row++){
    for(col=0; col<70; col += 7){
      printf(" %c", pieces[board[row + col] - 1].name);
    }
    printf("\n");
  }
  printf("\n");
}

int board_index(int find_num)
{
  int i;

  for(i=0; i<77; i++){
    if(board[i] == find_num){
      return i;
    }
  }
  return 0;
}

void try_piece(int level)
{
  int i, j, k, x;

  try_counter++;
  x = board_index(0);
  for(i=0; i<12; i++){
    if(pieces[i].used == 1){continue;}
    for(j=0; j<pieces[i].formsize; j++){
      if(board[x + pieces[i].form[j].pos[0]] ||
         board[x + pieces[i].form[j].pos[1]] ||
         board[x + pieces[i].form[j].pos[2]] ||
         board[x + pieces[i].form[j].pos[3]] ||
         board[x + pieces[i].form[j].pos[4]]){continue;}
      // ピースを置く
      for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = i + 1;}
      pieces[i].used = 1;
      // すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
      if(level == 11){
        counter++;
        print_board();
        // ピースを戻す
        for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = 0;}
        pieces[i].used = 0;
        return;
      }
      // 次のピースを試す
      try_piece(level + 1);
      // ピースを戻す
      for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = 0;}
      pieces[i].used = 0;
    }
  }
}

int main(int argc, char **argv)
{
  init_board();
  try_piece(0);
  printf("解合計: %d\n", counter);
  printf("操作数: %d\n", try_counter);
}

わずか1.2秒で完了した!

  • Rubyの1分からC言語1.2秒へ桁違いの高速化。
$ gcc -O2 pentomino.c
$ time ./a.out
解合計: 2339
操作数: 10385817

real	0m1.256s
user	0m1.237s
sys	0m0.017s
なしreal 0m2.789s
-O1real 0m1.276s
-O2real 0m1.249s
-O3real 0m1.292s

-O2が最速だ!


1秒切りたい

  • ここまで来ると、どうしても1秒を切りたくなる。
  • 工夫すべきところは、以下のコード部分だと思う。
...中略...
int board_index(int find_num)
{
  int i;

  for(i=0; i<77; i++){
    if(board[i] == find_num){
      return i;
    }
  }
  return 0;
}

void try_piece(int level)
{
  int i, j, k, x;

  try_counter++;
  x = board_index(0);
  for(i=0; i<12; i++){
    if(pieces[i].used == 1){continue;}
    for(j=0; j<pieces[i].formsize; j++){
      if(board[x + pieces[i].form[j].pos[0]] ||
         board[x + pieces[i].form[j].pos[1]] ||
         board[x + pieces[i].form[j].pos[2]] ||
         board[x + pieces[i].form[j].pos[3]] ||
         board[x + pieces[i].form[j].pos[4]]){continue;}
      // ピースを置く
...中略...
  • この部分はtry_counterが示すとおり1000万回以上も繰り返すのだ。
  • わずかな無駄も1000万回繰り返すと、結構な時間になってしまう...。
board_index()関数の修正
  • まず、board_index()関数の動きに注目してみる。
  • 次にピースを置く場所を決めるために、board配列の先頭から検索して、最初に0が出現するインデックス値を返している。
  • しかし、毎回board配列の先頭から検索するのは無駄である。
  • 少なくとも前回のインデックスxまでは、Pentominoピースで埋まっているはずなので、
  • 次回の検索位置は x+1 から探し始めた方が無駄がないはず。
  • 以下の修正をして、コンパイルして、実行してみると...

 @@ -32,8 +32,8 @@ int counter, try_counter;
  
  void init_board(void);
  void print_board(void);
 -void try_piece(int level);
 -int board_index(int find_num);
 +void try_piece(int x, int level);
 +int board_index(int find_num, int start_pos);
  
  
  
 @@ -62,11 +62,11 @@ void print_board(void)
    printf("\n");
  }
  
 -int board_index(int find_num)
 +int board_index(int find_num, int start_pos)
  {
    int i;
  
 -  for(i=0; i<77; i++){
 +  for(i=start_pos; i<77; i++){
      if(board[i] == find_num){
        return i;
      }
 @@ -74,12 +74,12 @@ int board_index(int find_num)
    return 0;
  }
  
 -void try_piece(int level)
 +void try_piece(int x, int level)
  {
 -  int i, j, k, x;
 +  int i, j, k;
  
    try_counter++;
 -  x = board_index(0);
 +  x = board_index(0, x);
    for(i=0; i<12; i++){
      if(pieces[i].used == 1){continue;}
      for(j=0; j<pieces[i].formsize; j++){
 @@ -101,7 +101,7 @@ void try_piece(int level)
          return;
        }
        // 次のピースを試す
 -      try_piece(level + 1);
 +      try_piece(x + 1, level + 1);
        // ピースを戻す
        for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k = 0;}
        pieces[i].used = 0;
 @@ -112,7 +112,7 @@ void try_piece(int level)
  int main(int argc, char **argv)
  {
    init_board();
 -  try_piece(0);
 +  try_piece(0, 0);
    printf("解合計: %d\n", counter);
    printf("操作数: %d\n", try_counter);
  }

ほぼ1秒で完了した!

$ gcc -O2 pentomino.c
$ time ./a.out
解合計: 2339
操作数: 10385817

real	0m1.066s
user	0m1.049s
sys	0m0.016s
ループで回す
  • でもまだ1秒切れてない...。
  • あともう少しなんだけど。
  • board_index()関数を最適化してしまったので、
  • 工夫の余地が残るのは、以下の部分しかない。
  • しかしどう考えても、(A)から(B)まで、これ以上効率的な書き方は想像できない...。
...中略...
void try_piece(int x, int level)
{
  int i, j, k;

  try_counter++; // ......(A)
  x = board_index(0, x);
  for(i=0; i<12; i++){
    if(pieces[i].used == 1){continue;}
    for(j=0; j<pieces[i].formsize; j++){ // ......(B)
      if(board[x + pieces[i].form[j].pos[0]] || // ......(C)
         board[x + pieces[i].form[j].pos[1]] ||
         board[x + pieces[i].form[j].pos[2]] ||
         board[x + pieces[i].form[j].pos[3]] ||
         board[x + pieces[i].form[j].pos[4]]){continue;}
      // ピースを置く
...中略...
  • 残る部分は、(C)の長い条件判定のコード。
  • ピースが置けるかどうかを判定している。
  • 高速化を狙って、あえてループを使わずに展開したのだけど、試しにループで処理してみる。(半分ヤケクソ)
  • 以下の修正をして、コンパイルして、実行してみると...

 @@ -77,17 +77,16 @@ int board_index(int find_num, int start_pos)
  void try_piece(int x, int level)
  {
    int i, j, k;
 +  int sum;
  
    try_counter++;
    x = board_index(0, x);
    for(i=0; i<12; i++){
      if(pieces[i].used == 1){continue;}
      for(j=0; j<pieces[i].formsize; j++){
 -      if(board[x + pieces[i].form[j].pos[0 ||
 -         board[x + pieces[i].form[j].pos[1 ||
 -         board[x + pieces[i].form[j].pos[2 ||
 -         board[x + pieces[i].form[j].pos[3 ||
 -         board[x + pieces[i].form[j].pos[4){continue;}
 +      sum = 0;
 +      for(k=0; k<5; k++){sum += board[x + pieces[i].form[j].pos[k;}
 +      if(sum){continue;}
        // ピースを置く
        for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k = i + 1;}
        pieces[i].used = 1;

1秒切った!

$ gcc -O2 pentomino.c
$ time ./a.out
解合計: 2339
操作数: 10385817

real	0m0.974s
user	0m0.958s
sys	0m0.014s

  • 高速化の経過: 3時間以上 → 50分 → 20分(Python) → 3分(Python) → 1分(Ruby) → 1.2秒(C) → 1秒(C) → 0.97秒(C)!
  • 教訓: 場合によっては、コード展開するより、ループ回した方が早い!
    • ループ処理で高速化したわけではなく、条件判定から加算命令に変更した効果であった。
    • その証拠にループを展開した加算命令の方がさらに高速化された。(わずか0.02秒だけど)

 -      sum = 0;
 -      for(k=0; k<5; k++){sum += board[x + pieces[i].form[j].pos[k;}
 -      if(sum){continue;}
 +      if(board[x + pieces[i].form[j].pos[0 +
 +         board[x + pieces[i].form[j].pos[1 +
 +         board[x + pieces[i].form[j].pos[2 +
 +         board[x + pieces[i].form[j].pos[3 +
 +         board[x + pieces[i].form[j].pos[4){continue;}

$ gcc -O2 pentomino.c
$ time ./a.out
解合計: 2339
操作数: 10385817

real	0m0.949s
user	0m0.933s
sys	0m0.014s

  • さらなる高速化に気付いた。
  • board[ x + pieces[i].form[j].pos[0] ] が0であることは明白なので、計算を省略できる。

 @@ -83,8 +83,7 @@
    for(i=0; i<12; i++){
      if(pieces[i].used == 1){continue;}
      for(j=0; j<pieces[i].formsize; j++){
 -      if(board[x + pieces[i].form[j].pos[0 +
 -         board[x + pieces[i].form[j].pos[1 +
 +      if(board[x + pieces[i].form[j].pos[1 +
           board[x + pieces[i].form[j].pos[2 +
           board[x + pieces[i].form[j].pos[3 +
           board[x + pieces[i].form[j].pos[4){continue;}

$ gcc -O2 pentomino.c
$ time ./a.out
解合計: 2339
操作数: 10385817

real	0m0.909s
user	0m0.884s
sys	0m0.014s

最終的なC言語コード

#include  <stdio.h>

typedef struct {
  int       pos[5];
} MinoPos;

typedef struct {
  char      name;
  int       used;
  int       formsize;
  MinoPos   form[8];
} Piece;

Piece pieces[] =
{
    {'X', 0, 1, {{0,6,7, 8,14}}},
    {'U', 0, 4, {{0,1,2, 7, 9},{0,1, 7,14,15},{0,2, 7, 8, 9},{0,1, 8,14,15}}},
    {'W', 0, 4, {{0,1,8, 9,16},{0,1, 6, 7,13},{0,7, 8,15,16},{0,6, 7,12,13}}},
    {'F', 0, 2, {{0,1,8, 9,15},{0,6, 7, 8,13}}},
    {'Z', 0, 4, {{0,1,8,15,16},{0,5, 6, 7,12},{0,1, 7,13,14},{0,7, 8, 9,16}}},
    {'P', 0, 8, {{0,1,2, 7, 8},{0,7, 8,14,15},{0,1, 6, 7, 8},{0,1, 7, 8,15},{0,1,2,8, 9},{0,1, 7, 8,14},{0,1,7,8, 9},{0,6, 7,13,14}}},
    {'N', 0, 8, {{0,1,2, 9,10},{0,6, 7,13,20},{0,1, 8, 9,10},{0,7,13,14,20},{0,1,2,6, 7},{0,7,14,15,22},{0,1,5,6, 7},{0,7, 8,15,22}}},
    {'Y', 0, 8, {{0,1,2, 3, 8},{0,7,14,15,21},{0,5, 6, 7, 8},{0,6, 7,14,21},{0,1,2,3, 9},{0,7, 8,14,21},{0,6,7,8, 9},{0,7,13,14,21}}},
    {'T', 0, 4, {{0,1,2, 8,15},{0,7, 8, 9,14},{0,7,13,14,15},{0,5, 6, 7,14}}},
    {'L', 0, 8, {{0,1,2, 3, 7},{0,7,14,21,22},{0,4, 5, 6, 7},{0,1, 8,15,22},{0,1,2,3,10},{0,1, 7,14,21},{0,7,8,9,10},{0,7,14,20,21}}},
    {'V', 0, 4, {{0,1,2, 7,14},{0,7,14,15,16},{0,7,12,13,14},{0,1, 2, 9,16}}},
    {'I', 0, 2, {{0,1,2, 3, 4},{0,7,14,21,28}}},
};

int board[77];
int counter, try_counter;

void init_board(void);
void print_board(void);
void try_piece(int x, int level);
int board_index(int find_num, int start_pos);



void init_board(void)
{
  int i;

  for(i=0; i<77; i++){
    if(((i + 1) % 7) == 0 || i >= 70){
      board[i] = 100;
    }
  }
}

void print_board(void)
{
  int row, col;

  printf("No. %d\n", counter);
  for(row=0; row<6; row++){
    for(col=0; col<70; col += 7){
      printf(" %c", pieces[board[row + col] - 1].name);
    }
    printf("\n");
  }
  printf("\n");
}

int board_index(int find_num, int start_pos)
{
  int i;

  for(i=start_pos; i<77; i++){
    if(board[i] == find_num){
      return i;
    }
  }
  return 0;
}

void try_piece(int x, int level)
{
  int i, j, k;

  try_counter++;
  x = board_index(0, x);
  for(i=0; i<12; i++){
    if(pieces[i].used == 1){continue;}
    for(j=0; j<pieces[i].formsize; j++){
      if(board[x + pieces[i].form[j].pos[1]] +
         board[x + pieces[i].form[j].pos[2]] +
         board[x + pieces[i].form[j].pos[3]] +
         board[x + pieces[i].form[j].pos[4]]){continue;}
      // ピースを置く
      for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = i + 1;}
      pieces[i].used = 1;
      // すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
      if(level == 11){
        counter++;
        print_board();
        // ピースを戻す
        for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = 0;}
        pieces[i].used = 0;
        return;
      }
      // 次のピースを試す
      try_piece(x + 1, level + 1);
      // ピースを戻す
      for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = 0;}
      pieces[i].used = 0;
    }
  }
}

int main(int argc, char **argv)
{
  init_board();
  try_piece(0, 0);
  printf("解合計: %d\n", counter);
  printf("操作数: %d\n", try_counter);
}

2015-01-14

ペントミノの解を求めるプログラム高速化

前回までにペントミノの解をすべて、求められるようになった。実行してみると、完了するまでに20分くらいかかる。当初に比べればこれでもかなり高速化したのだけど、まだまだ高速化の余地はありそう。チャレンジしてみる。

  • 最初は、6行10列のボードに敷き詰めようとして、3時間15分経過しても800解しか出力できなかった。
  • つぎに、ボードの縦横を入れ替えて10行6列にし、50分で9356解を出力した。
  • 現状は、重複解を排除するように変更し、20分で2339解を出力する。
$ time python pentomino.py
...中略...
解合計 2339
操作数 10385817

real	18m56.501s
user	18m47.271s
sys	0m1.475s

現状のコード

# coding: utf-8
import numpy as np



# すべてピース形状をPieceオブジェクトの配列に保存する
class Piece:
    def __init__(self, s, h,m,n):
        a = np.array(map(int, s)).reshape(h, -1)
        self.used = False
        self.form = []
        for i in range(m):
            for j in range(n):
                self.form.append((a, a.argmax()))
                a = np.rot90(a)
            a = np.fliplr(a)

pp = [Piece('010111010', 3,1,1),
      Piece('111101',    2,1,4),
      Piece('110011001', 3,1,4),
      Piece('110011010', 3,1,2),
      Piece('110010011', 3,2,2),
      Piece('111110',    2,2,4),
      Piece('11100011',  2,2,4),
      Piece('11110100',  2,2,4),
      Piece('111010010', 3,1,4),
      Piece('11111000',  2,2,4),
      Piece('111100100', 3,1,4),
      Piece('11111',     1,1,2)]



# パズルの解を求める
def try_piece(board, pp, x, y, lvl):
    global counter
    global try_counter
    try_counter += 1
    board_h, board_w = board.shape
    for i, piece in enumerate(pp):
        if not piece.used:
            for form in piece.form:
                piece_matrix, piece_origin = form
                h, w = piece_matrix.shape
                ox = x - piece_origin
                # ピースが飛び出したらそこから先は見ない
                if ox < 0 or ox + w > board_w or y + h > board_h: continue
                board_section = board[y:y + h, ox:ox + w]
                # ピースがかぶったらそこから先は見ない
                if (board_section * piece_matrix).any(): continue
                # ピースを置く
                board_section += piece_matrix * (i + 1)
                pp[i].used = True
                # すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
                if lvl == 11:
                    counter += 1
                    print 'No', counter
                    print np.rot90(board)
                    print
                    # ピースを戻す
                    board_section -= piece_matrix * (i + 1)
                    pp[i].used = False
                    return True
                # 次のピースを試す
                k = board.argmin()
                try_piece(board, pp, k % board_w, k // board_w, lvl + 1)
                # ピースを戻す
                board_section -= piece_matrix * (i + 1)
                pp[i].used = False
    return False

counter = 0
try_counter = 0
board = np.zeros((10, 6))
try_piece(board, pp, 0, 0, 0)
print '解合計', counter
print '操作数', try_counter

1次元配列化

  • 2次元配列を扱うnumpyは素晴らしい使い心地なのだけど、たぶん処理の負荷は高いのだと思う。
  • 各ピースはすべて5つの正方形の組み合わせで構成されている。
  • ところがピースの形状データは、最大3×3=9つの要素を持つ2次元配列で表現している。
  • ブロック数の倍近い要素数で、行列演算で重なり判定や置き換えを常に処理することになる。
  • また、2次元配列といってもメモリ中では常に1次元の状態で保存されているはず。
  • 単にコードが2次元配列的な表現になっているだけで、内部ではnumpyが1次元配列に変換して処理しているのだと思う。
  • numpyは人間の思考に楽をさせてくれるけど、それに甘えていると高速化できない。
  • 高速化を求めるならnumpyを使わずに、自分の思考をフル回転させる必要がある。
board配列の1次元化
  • まず、11行×7列の以下のような配列をイメージする。

f:id:zariganitosh:20150114094748p:image:h264

  • イメージとしては2次元で書いているけど、配列は1次元である。
  • 各マスの数字は、1次元配列のインデックスである。
  • グレーの部分は、行の末尾と列の末尾を区別するために追加している。
    • 例えばインデックス6は、1行ずれて両サイドに表現しているが、
    • 実際の1次元配列内部が以下のように連続したものであるため。

f:id:zariganitosh:20150114100345p:image:w450

    • インデックス5の次はインデックス6であり、インデックス7の手前はインデックス6なのである。
    • それを2次元的に補うため、両サイドに表現しているのだ。
  • 1次元配列で2次元的な空間を表現する工夫である。

  • board配列は0で初期化するのだけど、グレー要素には100を設定しておく。
    • board配列はいずれpiece番号で埋まっていくので、piece番号と区別できる必要がある。
    • 100に限らずpiece番号より大きい数値であれば、何でもいい。
>>> board = np.zeros(11 * 7)
>>> for i, b in enumerate(board):
...     if (i + 1) % 7 == 0 or i >= 70: board[i] = 100
... 
>>> board
array([   0.,    0.,    0.,    0.,    0.,    0.,  100.,    0.,    0.,
          0.,    0.,    0.,    0.,  100.,    0.,    0.,    0.,    0.,
          0.,    0.,  100.,    0.,    0.,    0.,    0.,    0.,    0.,
        100.,    0.,    0.,    0.,    0.,    0.,    0.,  100.,    0.,
          0.,    0.,    0.,    0.,    0.,  100.,    0.,    0.,    0.,
          0.,    0.,    0.,  100.,    0.,    0.,    0.,    0.,    0.,
          0.,  100.,    0.,    0.,    0.,    0.,    0.,    0.,  100.,
          0.,    0.,    0.,    0.,    0.,    0.,  100.,  100.,  100.,
        100.,  100.,  100.,  100.,  100.])
piece形状の1次元化
  • 各ピース形状の左上のブロックをインデックス0に合わせて置いてみる。
  • 例えばFピースなら、以下のようになる。

f:id:zariganitosh:20150114103228p:image:h264

  • [0, 1, 6, 7, 14]という座標は、board配列内でFピースを描くための情報となる。
  • 上記座標を覚えておけば、board配列の任意の位置にFピースを復元できるのだ!
  • すべてのピースを左上原点に合わせて、1次元座標を求めておく。

f:id:zariganitosh:20150114104429p:image:h450

>>> # coding: utf-8
... import numpy as np
>>> 
>>> # すべてのピース形状をPieceオブジェクトの配列に保存する
... class Piece:
...     def __init__(self, s, h,m,n):
...         a = np.array(map(int, s)).reshape(h, -1)
...         self.used = False
...         self.form = []
...         for i in range(m):
...             for j in range(n):
...                 self.form.append((a, a.argmax()))
...                 a = np.rot90(a)
...             a = np.fliplr(a)
... 
>>> pp = [Piece('010111010', 3,1,1),
...       Piece('111101',    2,1,4),
...       Piece('110011001', 3,1,4),
...       Piece('110011010', 3,1,2),
...       Piece('110010011', 3,2,2),
...       Piece('111110',    2,2,4),
...       Piece('11100011',  2,2,4),
...       Piece('11110100',  2,2,4),
...       Piece('111010010', 3,1,4),
...       Piece('11111000',  2,2,4),
...       Piece('111100100', 3,1,4),
...       Piece('11111',     1,1,2)]
>>> 
>>> for i, piece in enumerate(pp):
...     piece.loc_form = []
...     for form in piece.form:
...         a = []
...         for r, row in enumerate(form[0]):
...             for c, col in enumerate(row):
...                 if col: a.append(r * 7 + c - form[1])
...         piece.loc_form.append(a)
... 
>>> pp[0].loc_form
[[0, 6, 7, 8, 14]]

>>> pp[1].loc_form
[[0, 1, 2, 7, 9], [0, 1, 7, 14, 15], [0, 2, 7, 8, 9], [0, 1, 8, 14, 15]]
1次元配列を利用して解を求める
  • 以上の1次元配列を使ってパズルの解を求めるコードに修正してみた。
  • numpyを利用するのは解を出力する時だけとなった。
  • ピースが置けるかどうかの判定やピースを置く・戻す処理は、単純な変数同士の演算で処理している。
  • try_peiceの呼び出し回数は、1000万回を超えている!
  • try_pieceの書き方が高速化に大きな影響を及ぼすはず。

 # パズルの解を求める
 -def try_piece(board, pp, x, y, lvl):
 +def try_piece(board, pp, lvl):
      global counter
      global try_counter
      try_counter += 1
 -    board_h, board_w = board.shape
 +    x = board.argmin()
      for i, piece in enumerate(pp):
          if not piece.used:
 -            for form in piece.form:
 -                piece_matrix, piece_origin = form
 -                h, w = piece_matrix.shape
 -                ox = x - piece_origin
 -                # ピースが飛び出したらそこから先は見ない
 -                if ox < 0 or ox + w > board_w or y + h > board_h: continue
 -                board_section = board[y:y + h, ox:ox + w]
 -                # ピースがかぶったらそこから先は見ない
 -                if (board_section * piece_matrix).any(): continue
 +            for blocks in piece.loc_form:
 +                if board[x + blocks[0 or board[x + blocks[1 or board[x + blocks[2 or board[x + blocks[3 or board[x + blocks[4: continue
                  # ピースを置く
 -                board_section += piece_matrix * (i + 1)
 -                pp[i].used = True
 +                for b in blocks: board[x + b] = i + 1
 +                piece.used = True
                  # すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
                  if lvl == 11:
                      counter += 1
                      print 'No', counter
 -                    print np.rot90(board)
 +                    print np.rot90(board.reshape((11, -1))[0:10, 0:6])
                      print
                      # ピースを戻す
 -                    board_section -= piece_matrix * (i + 1)
 -                    pp[i].used = False
 +                    for b in blocks: board[x + b] = 0
 +                    piece.used = False
                      return True
                  # 次のピースを試す
 -                k = board.argmin()
 -                try_piece(board, pp, k % board_w, k // board_w, lvl + 1)
 +                try_piece(board, pp, lvl + 1)
                  # ピースを戻す
 -                board_section -= piece_matrix * (i + 1)
 -                pp[i].used = False
 +                for b in blocks: board[x + b] = 0
 +                piece.used = False
      return False
  
  counter = 0
  try_counter = 0
 -board = np.zeros((10, 6))
 -try_piece(board, pp, 0, 0, 0)
 +try_piece(board, pp, 0)
  print '解合計', counter
  print '操作数', try_counter

修正後のコード

  • boardサイズを可変できるように変数browとbcolで一般化して、以下のようなコードが完成。
# coding: utf-8
import numpy as np

# 参照だけならメソッド定義内でも常にグローバルスコープ
# 書き込みする場合はメソッド定義内でglobal宣言が必要
brow, bcol = 10, 6



# すべてのピース形状をPieceオブジェクトの配列に保存する
class Piece:
    def __init__(self, s, h,m,n):
        a = np.array(map(int, s)).reshape(h, -1)
        self.used = False
        self.form = []
        for i in range(m):
            for j in range(n):
                self.form.append((a, a.argmax()))
                a = np.rot90(a)
            a = np.fliplr(a)

pp = [Piece('010111010', 3,1,1),
      Piece('111101',    2,1,4),
      Piece('110011001', 3,1,4),
      Piece('110011010', 3,1,2),
      Piece('110010011', 3,2,2),
      Piece('111110',    2,2,4),
      Piece('11100011',  2,2,4),
      Piece('11110100',  2,2,4),
      Piece('111010010', 3,1,4),
      Piece('11111000',  2,2,4),
      Piece('111100100', 3,1,4),
      Piece('11111',     1,1,2)]

for i, piece in enumerate(pp):
    piece.loc_form = []
    for form in piece.form:
        a = []
        for r, row in enumerate(form[0]):
            for c, col in enumerate(row):
                if col: a.append(r * (bcol + 1) + c - form[1])
        piece.loc_form.append(a)



# boardの初期化
board = np.zeros((brow + 1) * (bcol + 1))
for i, b in enumerate(board):
    if ((i + 1) % (bcol + 1)) == 0 or i >= ((bcol + 1) * brow): board[i] = 100



# パズルの解を求める
def try_piece(board, pp, lvl):
    global counter, try_counter
    try_counter += 1
    x = board.argmin()
    for i, piece in enumerate(pp):
        if not piece.used:
            for blocks in piece.loc_form:
                if board[x + blocks[0]] or board[x + blocks[1]] or board[x + blocks[2]] or board[x + blocks[3]] or board[x + blocks[4]]: continue
                # ピースを置く
                for b in blocks: board[x + b] = i + 1
                piece.used = True
                # すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
                if lvl == 11:
                    counter += 1
                    print 'No', counter
                    print np.rot90(board.reshape((brow + 1, -1))[0:brow, 0:bcol])
                    print
                    # ピースを戻す
                    for b in blocks: board[x + b] = 0
                    piece.used = False
                    return True
                # 次のピースを試す
                try_piece(board, pp, lvl + 1)
                # ピースを戻す
                for b in blocks: board[x + b] = 0
                piece.used = False
    return False

counter = 0
try_counter = 0
try_piece(board, pp, 0)
print '解合計', counter
print '操作数', try_counter

実行すると...

$ time python pentomino.py
解合計 2339
操作数 10385817

real	2m58.318s
user	2m56.990s
sys	0m0.304s

3分切った!

参考ページ

以下のページがたいへん参考になりました!感謝です!

2015-01-12

明治ミルクチョコーレートパズルの解をすべて探す

今年の正月明けは、明治ミルクチョコレートパズルの問題に夢中になった...。

このパズルはチョコレートシリーズの中では甘めらしいのだが、各ピースがチョコレートで出来ている訳ではなく、食べられない。甘めというのは難易度のこと。これはABS樹脂で作られたチョコレート風デザインのパズルなのだ。写真で見ると、思わず食べてみたい衝動にかられる。

  • 1ピースは正方形5個の組み合わせで構成される。
  • その組み合わせは全部で12通りある。よって全部で12ピースある。
  • 各ピースにはアルファベットをイメージした名前が付けられている。

  • この12ピースをうまく組み合わせて、6×10(=正方形60個)の箱に収めるのだ。

f:id:zariganitosh:20150110083608p:image:w250

これは紛れもないペントミノ(pentomino)パズルのなのだ!このペントミノパズルをコンピューターに解かせる、という試み。こうゆう試みは大好き。さっそく自分でもやってみよう!

難解

  • 思い立ったはいいけど、何をどうやって問題を処理していいのか?さっぱり分からない...。
  • パズルを配置してその解を見つける処理というのは、自分の中では相当難易度が高い。
  • しかし、今回はブロックの配置もプログラミングする必要がある。
  • テトロミノ5ピースに対して、ペントミノ12ピース。その組み合わせも膨大になる。
  • どうやって、無駄なく、最適な場所を見つけていくのか?
  • どうやって、すべての配置を網羅すべきなのか?

さっぱり分からない...。

拝借

  • 分からない時は、素直に先達の知恵に頼ることにする。
  • 上記記事に登場するパズルの達人は、たった54行のコードでペントミノパズルを解いてしまっている。
  • しかも、正月中の突然の問い合わせにもかかわらず、明快に回答。
  • おそらく、アドリブ的なコーディングであり、フルスクラッチ*1

素晴らしい!(自分もいつかは難問でも自力で考え抜いて、素早くコーディングできる人になりたい)


  • 環境に合わせて若干の修正をした。
    • 日本語コメントがあるのでエンコーディング宣言が必要だった。
    • ピースの形状データを配列として取得するように修正してみた。
+# coding: utf-8
 import numpy as np
 class Piece:
     def __init__(self, s, t):
         h = t // 100 # 縦
         m = (t // 10) % 10 # 反転する(2)/しない(1)
         n = t % 10 # 回転数
-        a = np.array(1).reshape(h, -1)
+        a = np.array(map(int, s)).reshape(h, -1)
         self.pos = -1
         self.sel = 0
         self.cand = []

  • 修正したコードを実行してみると...
# coding: utf-8
import numpy as np
class Piece:
    def __init__(self, s, t):
        h = t // 100       # 縦
        m = (t // 10) % 10 # 反転する(2)/しない(1)
        n = t % 10         # 回転数
        a = np.array(map(int, s)).reshape(h, -1)
        self.pos = -1
        self.sel = 0
        self.cand = []
        for i in range(m):
            for j in range(n):
                self.cand.append((a, a.argmax()))
                a = np.rot90(a)
            a = np.fliplr(a)
pp = [Piece('010111010', 311),
      Piece('111101', 214),
      Piece('110011001', 314),
      Piece('110011010', 324),
      Piece('110010011', 322),
      Piece('111110', 224),
      Piece('11100011', 224),
      Piece('11110100', 224),
      Piece('111010010', 314),
      Piece('11111000', 224),
      Piece('111100100', 314),
      Piece('11111', 112)]
def allp(pp):
    for i, p in enumerate(pp):
        if p.pos < 0:
            for j, c in enumerate(p.cand):
                yield i, j, c[0], c[1]

board = np.array([False] * 60).reshape(6, 10)
def chk(board, pp, x, y, lvl):
    for i, j, p, d in allp(pp):
        h, w = p.shape
        # ピースが飛び出したらそこから先は見ない
        if x - d < 0 or x - d + w > 10 or y + h > 6: continue
        b = board[y:y + h, x - d:x - d + w]
        # ピースがかぶったらそこから先は見ない
        if (b & p).any(): continue
        pp[i].sel = j
        pp[i].pos = y * 10 + x - d
        # すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
        if lvl == 11: return True
        b += p
        k = board.argmin()
        # ここまで成功したら次のピースを試す
        if chk(board, pp, k % 10, k // 10, lvl + 1): return True
        # 失敗したら巻き戻して別の手を試す
        b -= p
        pp[i].pos = -1
    return False
chk(board, pp, 0, 0, 0)
l = np.zeros((6, 10))
for i, p in enumerate(pp):
    x, y, z = p.pos % 10, p.pos // 10, p.cand[p.sel][0]
    l[y:y + z.shape[0], x:x + z.shape[1]] += z * i

print('\n'.join(''.join(chr(int(j) + 65) for j in i) for i in l))
正月の酔っ払い物理学者が数学者の皮を被った天使に出会うお話 | カメリオ開発者ブログ

  • 見事に解が出力された!
$ python pentamino.py
BBBCCDDIII
BGBACCDDIL
GGAAACDJIL
GEEAJJJJKL
GEFFHHHHKL
EEFFFHKKKL

一体どのように解を見つけているのか?コードを追ってみた。

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

  • まず前半のコードで、すべてのピース形状をPieceオブジェクトの配列として保存している。
$ python
>>> import numpy as np
>>> class Piece:
...     def __init__(self, s, t):
...         h = t // 100       # 縦
...         m = (t // 10) % 10 # 反転する(2)/しない(1)
...         n = t % 10         # 回転数
...         a = np.array(map(int, s)).reshape(h, -1)
...         self.pos = -1
...         self.sel = 0
...         self.cand = []
...         for i in range(m):
...             for j in range(n):
...                 self.cand.append((a, a.argmax()))
...                 a = np.rot90(a)
...             a = np.fliplr(a)
... 
>>> pp = [Piece('010111010', 311),
...       Piece('111101', 214),
...       Piece('110011001', 314),
...       Piece('110011010', 324),
...       Piece('110010011', 322),
...       Piece('111110', 224),
...       Piece('11100011', 224),
...       Piece('11110100', 224),
...       Piece('111010010', 314),
...       Piece('11111000', 224),
...       Piece('111100100', 314),
...       Piece('11111', 112)]
  • 試しにPiece('010111010', 311)を実行してみると...
  • 以下のようなPieceオブジェクトが生成されるのだ!
    • '010111010'は、ピース形状のデータ。
    • 311にはそれぞれの桁数ごとに意味があって、3行・反転ポジション1つ・回転ポジション1つ、という意味。
      • 例:
      • +形状は、3行のデータを持つ。反転しても・90度回転しても形状が変化しないので、反転ポジション1つ・回転ポジション1つとなる。(311)
      • P形状は、3行のデータを持つ。反転変化あり・0・90・180・270度回転して異なる形状になるので、反転ポジション2つ・回転ポジション4つとなる。(324)
      • −形状は、1行のデータを持つ。反転変化なし・0・90度回転のみ異なる形状になるので、反転ポジション1つ・回転ポジション2つとなる。(112)
>>> p = Piece('010111010', 311)
>>> p
<__main__.Piece instance at 0x109bbda28>

>>> p.pos
 -1

>>> p.sel
 0

>>> p.cand
[(array([[0, 1, 0],
         [1, 1, 1],
         [0, 1, 0]]), 1)]
  • p.candの配列データはピース形状を表現している。(ブロックあり=1・なし=0)
  • 配列に続く数値は、ピース形状の先頭が何番目の配列要素から始まるかを表現している。
    • 上記の例では+形状なので、先頭のブロックは2番目の要素から始まっている。
    • 配列のインデックスは0、1、2...と続くので、2番目のインデッス値=1が設定されているのだ。
  • この数値は、ピースを配置する時に、隙間なく置くための重要な情報となる!

素晴しきnumpy!

ここで...

  • このコードをより詳しく理解するには、numpyの挙動を理解する必要があると気付いた。
  • Pieceクラスでは('010111010', 311)という引数から2次元配列に変換しているのだけど、
  • これはもう、numpy(数値演算ライブラリ)の行列演算能力から絶大な恩恵を受けている。
  • さらに、ピースの回転・反転、ピース同士の重なり判定、ボードにピースを並べたり、面倒と思える処理をnumpyは一瞬で解決してくれるのだ。
  • 自分はpythonをほとんど使ったことがなかったが、

numpyがあるならpython使いたい!と思わせるレベルの魅力がある。

  • コード中に使われているnumpyの技を探ってみた。
行列の組み替え
  • np.arrayのreshapeは、配列をお好みの行列に組み替えてくれるのだ。
    • reshape(3, 2)なら、3行×2列。
    • reshape(2, 3)なら、2行×3列。
  • どちらかがマイナスの指定は、プラスの指定に対応した値で組み替えてくれる。
    • reshape(3, -1)なら、3行×全要素数÷3列。
>>> import numpy as np
>>> list = map(int, '010111010')
>>> list
[0, 1, 0, 1, 1, 1, 0, 1, 0]

>>> np.array(list).reshape(3, -1)
array([[0, 1, 0],
       [1, 1, 1],
       [0, 1, 0]])
最大値・最小値の位置を調べる
  • argmaxは、配列中の最大値のインデックス値を返す。
  • インデックス値は一次元配列に変換された値になる。
>>> a = np.array([1,2,3,4,2,1]).reshape(2, -1)
>>> a
array([[1, 2, 3],
       [4, 2, 1]])

>>> a.argmax()
3
  • この仕組みを利用して、ピース形状の先頭ブロックの場所を特定しているのだ。
>>> list = map(int, '010111010')
>>> a = np.array(list).reshape(3, -1)
>>> a
array([[0, 1, 0],
       [1, 1, 1],
       [0, 1, 0]])

>>> a.argmax()
1
  • 同様にa.argmin()は、配列中の最小値のインデックス値を返す。
  • この仕組みを利用して、boardの中で次にピースを置く位置を素早く見つけているのだ。
>>> a.argmin()
0
行列の回転・反転
  • np.rot90(a)は、反時計回りに90度回転する。
>>> a
array([[1, 1, 1],
       [1, 1, 0]])

>>> np.rot90(a)
array([[1, 0],
       [1, 1],
       [1, 1]])
  • 180度・270度回転したい時は、回数を指定する。
>>> np.rot90(a, 2)
array([[0, 1, 1],
       [1, 1, 1]])

>>> np.rot90(a, 3)
array([[1, 1],
       [1, 1],
       [0, 1]])

  • np.fliplr(a)は、左右方向に反転する。(裏返す)
>>> a
array([[1, 1, 1],
       [1, 1, 0]])

>>> np.fliplr(a)
array([[1, 1, 1],
       [0, 1, 1]])

  • np.flipup(a)は、上下方向に反転する。(裏返す)
>>> a
array([[1, 1, 1],
       [1, 1, 0]])

>>> np.flipud(a)
array([[1, 1, 0],
       [1, 1, 1]])
配列の任意の範囲を切り出す
  • 大きな配列から範囲指定による切り出し。
>>> board = np.array(range(60)).reshape(6, 10)
>>> board
array([[ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9],
       [10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
       [20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
       [30, 31, 32, 33, 34, 35, 36, 37, 38, 39],
       [40, 41, 42, 43, 44, 45, 46, 47, 48, 49],
       [50, 51, 52, 53, 54, 55, 56, 57, 58, 59]])

>>> board[1:3, 2:6]
array([[12, 13, 14, 15],
       [22, 23, 24, 25]])
  • 範囲指定は、配列要素の境界を指定していると考えることにした。
配列の演算
  • 配列と数値の演算
>>> board * 10
array([[120, 130, 140, 150],
       [220, 230, 240, 250]])

  • 配列同士の演算
>>> board = np.array(range(60)).reshape(6, 10)
>>> board
array([[ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9],
       [10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
       [20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
       [30, 31, 32, 33, 34, 35, 36, 37, 38, 39],
       [40, 41, 42, 43, 44, 45, 46, 47, 48, 49],
       [50, 51, 52, 53, 54, 55, 56, 57, 58, 59]])

>>> b = board[1:3, 2:6]
>>> b
array([[12, 13, 14, 15],
       [22, 23, 24, 25]])

>>> z = np.zeros((2, 4))
>>> z
array([[ 0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.]])
  • コピーする演算
  • b = b * zは、新たな配列bとしてコピーしてから演算するようだ。
  • そのため、取り出し元のboard配列に影響しない。
>>> b = b * z
>>> b
array([[ 0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.]])

>>> board
array([[ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9],
       [10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
       [20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
       [30, 31, 32, 33, 34, 35, 36, 37, 38, 39],
       [40, 41, 42, 43, 44, 45, 46, 47, 48, 49],
       [50, 51, 52, 53, 54, 55, 56, 57, 58, 59]])
  • 置き換える演算
  • b *= zは、演算結果を元の配列bに上書きする。
  • よって、取り出し元のboard配列に影響を与える。
>>> b = board[1:3, 2:6]
>>> b
array([[12, 13, 14, 15],
       [22, 23, 24, 25]])

>>> b *= z
>>> b
array([[0, 0, 0, 0],
       [0, 0, 0, 0]])

>>> board
array([[ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9],
       [10, 11,  0,  0,  0,  0, 16, 17, 18, 19],
       [20, 21,  0,  0,  0,  0, 26, 27, 28, 29],
       [30, 31, 32, 33, 34, 35, 36, 37, 38, 39],
       [40, 41, 42, 43, 44, 45, 46, 47, 48, 49],
       [50, 51, 52, 53, 54, 55, 56, 57, 58, 59]])
  • b = b * zとb *= zになぜこのような違いが生まれるのか、正確なところはわからないが...
    • b = b * zのような書き方を利用することで、ピースの衝突判定が簡単にできる!
    • また、b *= zのような書き方を利用することで、boardにピースを素早く並べるられる!

素晴しきnumpy!(惚れた)

パズルの解を求める

いよいよ、パズルの解を求める処理が始まる。

>>> def allp(pp):
...     for i, p in enumerate(pp):
...         if p.pos < 0:
...             for j, c in enumerate(p.cand):
...                 yield i, j, c[0], c[1]
... 
>>> def chk(board, pp, x, y, lvl):
...     for i, j, p, d in allp(pp):
...         h, w = p.shape
...         # ピースが飛び出したらそこから先は見ない
...         if x - d < 0 or x - d + w > 10 or y + h > 6: continue
...         b = board[y:y + h, x - d:x - d + w]
...         # ピースがかぶったらそこから先は見ない
...         if (b & p).any(): continue
...         pp[i].sel = j
...         pp[i].pos = y * 10 + x - d
...         # すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
...         if lvl == 11: return True
...         b += p
...         k = board.argmin()
...         # ここまで成功したら次のピースを試す
...         if chk(board, pp, k % 10, k // 10, lvl + 1): return True
...         # 失敗したら巻き戻して別の手を試す
...         b -= p
...         pp[i].pos = -1
...     return False
... 
>>> board = np.array([False] * 60).reshape(6, 10)
>>> chk(board, pp, 0, 0, 0)
False
  • allp(pp)は、すべてのピース形状(反転・回転による変化も含む)を網羅した順序リスト(のようなもの)を返す関数。
  • Pieceオブジェクトの配列から、i=ピースNo.(0-11)、j=形状No.(0-7)、c[0]=形状データの配列、c[1]=ピース形状の先頭ブロックの位置、を順に渡してくれるのだ。
  • 以上の準備をして、chk(board, pp, x, y, lvl)で一つずつ、すべてのピース形状が置けるかどうかを試すのだ。
    • board=ピースが存在するかしないかを記録した6×10の配列。(最初はFalseで満たされた状態)
    • pp=Pieceオブジェクトの配列。
    • x, y=ピースを置く場所。ボード内の座標。
    • lvl=何個目のピースを試しているかという情報。
  • ピースを置く位置は、10×6のboard配列の左上から右側に向かって、1行ずつ順に試すことになる。
  • このとき重要になるのがピースの置き方。
  • 例えば、最初のピース形状の配列データをそのまま配置すると、以下のような状態となる。

f:id:zariganitosh:20150110110620p:image:w250

  • しかし、このように配置してしまうと、左上の1ブロックの隙間が永遠に解決できない隙間として残ってしまう...。
  • そこで、形状データを作成する時に保存した、先頭のブロックが何番目から始まるのか?という情報を利用して、以下のように配置している。

f:id:zariganitosh:20150110111135p:image:w250

  • しかし、残念ながら上記の配置では外枠にはみ出ているので、置き方としては失敗である。
  • そのような失敗を「# ピースが飛び出したらそこから先は見ない」下側のでif文判定している。
      • if x - d < 0 or x - d + w > 10 or y + h > 6: continue

  • また、枠からはみ出さなくても、ピース同士が重なってしまう状況も考えられる。

f:id:zariganitosh:20150110112655p:image:w250

  • 上記のような失敗を「# ピースがかぶったらそこから先は見ない」下側のif文で判定している。
      • if (b & p).any(): continue
    • pには、ピース形状の配列が代入されている。
    • bには、ピースを置く部分のboard配列の範囲が切り抜かれた内容が代入されている。
      • b = board[y:y + h, x - d:x - d + w]

  • 以上のチェックをくぐり抜けると、とりあえずピースが置けたことになる。(仮置き状態)

f:id:zariganitosh:20150110125748p:image:w250

  • とりあえずピースが置けた場合は...
    • Pieceオブジェクトに、その時の形状とボード内の位置を記録しておく。
      • pp[i].sel = j
      • pp[i].pos = y * 10 + x - d
    • と同時に、重なりチェック用のboard配列に、形状データを書き込んで次の重なりチェックに備える。
      • b += p

  • 以上の処理をして、次のピースを試す。
  • 次にピースを置く場所は、board配列内の一番小さな値を探して決める。
      • k = board.argmin()
    • 左上から1行ずつ、左から右に検索する。
    • 最小値が複数のある時は、最初に出現する位置となる。
    • kには、左上先頭からn個目という数値nが代入される。(1次元の位置情報)
  • Falseは0とみなされるので、以下の状況では黒枠の位置がその場所になる。

f:id:zariganitosh:20150110132450p:image:w250

  • 上記位置を引数にセットして、chk()関数自身を再帰呼び出しするのだ。
      • if chk(board, pp, k % 10, k // 10, lvl + 1): return True
    • k%10、k//10、によって1次元の位置情報を、2次元の位置情報に変換している。
    • lvl(レベルの略?)は、何個目のピースを試しているかという情報。

  • 以上の再帰呼び出しを繰り返して、すべてのピースが置けた場合は、その時の状態がパズルの解となるのだ!
  • すべてのピースが置けた場合はlvlが11となるので、それが再帰呼び出しを終了するきっかけとなる。
      • if lvl == 11: return True
  • しかし、lvlが11となる前にすべてのピース形状を試して何も置けなくなるとFalseが返り、それは失敗の合図。
  • とりあえず仮置きしたピースを取り除いて、次のピースを試す。
      • b -= p
      • pp[i].pos = -1
    • Pieceオブジェクトの位置情報は、使用済みのピースかどうか判定する情報にもなっているので-1に戻すのだ。
    • 使用済みのピースかどうかは、allp(pp)関数内で判定している。
      • if p.pos < 0:

パズルの解を出力する

最後に解を出力する処理。

>>> l = np.zeros((6, 10))
>>> for i, p in enumerate(pp):
...     x, y, z = p.pos % 10, p.pos // 10, p.cand[p.sel][0]
...     l[y:y + z.shape[0], x:x + z.shape[1]] += z * i
... 
>>> print('\n'.join(''.join(chr(int(j) + 65) for j in i) for i in l))
BBBCCDDIII
BGBACCDDIL
GGAAACDJIL
GEEAJJJJKL
GEFFHHHHKL
EEFFFHKKKL
  • 現状のパズルの解は、Pieceオブジェクトに保存された一次元の位置情報の座標でしかない。
  • 座標情報から、各ピースをAからLの文字で表現し、ボードに詰めた状態に変換しているのだ。

なるほど、ようやくコードの流れを見切った!

すべての解を求めたい

  • コードの流れを見切ると、自分流にコードを修正したくなる。
  • どうせなら、ペントミノパズルのすべての解を求めてみたくなった。

やってみた。

分かりやすい表現に修正
  • まずは、より自分が理解しやすいコードにするため、変数名や関数名のネーミングを分かりやすい名前に変更しておく。
  • また、行数、反転する・しない、回転数を3桁にまとめた引数を、3つの引数に分解しておいた。
  • さらに、board(10×6)を重なり判定だけに利用するのはもったいないので、ピースの番号を書き込むようにしてみた。
# coding: utf-8
import numpy as np



# すべてのピース形状をPieceオブジェクトの配列に保存する
class Piece:
    def __init__(self, s, h,m,n):
        a = np.array(map(int, s)).reshape(h, -1)
        self.used = False
        self.form = []
        for i in range(m):
            for j in range(n):
                self.form.append((a, a.argmax()))
                a = np.rot90(a)
            a = np.fliplr(a)

pp = [Piece('010111010', 3,1,1),
      Piece('111101',    2,1,4),
      Piece('110011001', 3,1,4),
      Piece('110011010', 3,2,4),
      Piece('110010011', 3,2,2),
      Piece('111110',    2,2,4),
      Piece('11100011',  2,2,4),
      Piece('11110100',  2,2,4),
      Piece('111010010', 3,1,4),
      Piece('11111000',  2,2,4),
      Piece('111100100', 3,1,4),
      Piece('11111',     1,1,2)]



# パズルの解を求める
def piece_all(pp):
    for piece_i, piece in enumerate(pp):
        if not piece.used:
            for form_j, form in enumerate(piece.form):
                piece_matrix, piece_origin = form
                yield piece_i, form_j, piece_matrix, piece_origin

def chk(board, pp, x, y, lvl):
    for i, j, piece_matrix, piece_origin in piece_all(pp):
        h, w = piece_matrix.shape
        ox = x - piece_origin
        # ピースが飛び出したらそこから先は見ない
        if ox < 0 or ox + w > 10 or y + h > 6: continue
        board_section = board[y:y + h, ox:ox + w]
        # ピースがかぶったらそこから先は見ない
        if (board_section * piece_matrix).any(): continue
        board_section += piece_matrix * (i + 1)
        pp[i].used = True
        # すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
        if lvl == 11: return True
        k = board.argmin()
        # ここまで成功したら次のピースを試す
        if chk(board, pp, k % 10, k // 10, lvl + 1): return True
        # 失敗したら巻き戻して別の手を試す
        board_section -= piece_matrix * (i + 1)
        pp[i].used = False
    return False

board = np.zeros((6, 10))
chk(board, pp, 0, 0, 0)
print board
すべての解を求める
  • 現状は、最初の解を見つけると、return Trueの連鎖でパズルを解くことをやめてしまう...。
  • すべての解を求めるには、解を見つけた時もパズルをやめずに、次の解を求めて検索する必要がある。
  • まず、return Trueの連鎖を断ち切るために、以下のコードを修正した。

 -        if chk(board, pp, k % 10, k // 10, lvl + 1): return True
 +        chk(board, pp, k % 10, k // 10, lvl + 1)


  • 次に、解を見つけた時の処理。解を見つけたら...
    • 解を出力する。
    • そして、pieceを元に戻して、(次の解を見つける準備)
    • returnする。

 @@ -50,7 +50,11 @@ def chk(board, pp, x, y, lvl):
          board_section += piece_matrix * (i + 1)
          pp[i].used = True
          # すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
 -        if lvl == 11: return True
 +        if lvl == 11:
 +            print board
 +            board_section -= piece_matrix * (i + 1)
 +            pp[i].used = False
 +            return True
          k = board.argmin()
          # ここまで成功したら次のピースを試す
          chk(board, pp, k % 10, k // 10, lvl + 1)
 @@ -63,4 +67,3 @@ def chk(board, pp, x, y, lvl):
  
  board = np.zeros((6, 10))
  chk(board, pp, 0, 0, 0)
 -print board


  • 何個目の解か分かるようにカウンターも追加してみた。

 @@ -39,6 +39,7 @@ def piece_all(pp):
                  yield piece_i, form_j, piece_matrix, piece_origin
  
  def chk(board, pp, x, y, lvl):
 +    global counter
      for i, j, piece_matrix, piece_origin in piece_all(pp):
          h, w = piece_matrix.shape
          ox = x - piece_origin
 @@ -51,7 +52,10 @@ def chk(board, pp, x, y, lvl):
          pp[i].used = True
          # すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
          if lvl == 11:
 +            counter += 1
 +            print 'No', counter
              print board
 +            print
              board_section -= piece_matrix * (i + 1)
              pp[i].used = False
              return True
 @@ -65,5 +69,7 @@ def chk(board, pp, x, y, lvl):
  
 +counter = 0
  board = np.zeros((6, 10))
  chk(board, pp, 0, 0, 0)
 +print '解合計', counter


  • 以上の修正コードを実行してみると、目論見どおり解を次々と出力し始めた!
$ python pentomino.py
No. 1
  2.   2.   2.   3.   3.   4.   4.   9.   9.   9.]
 [  2.   7.   2.   1.   3.   3.   4.   4.   9.  12.]
 [  7.   7.   1.   1.   1.   3.   4.  10.   9.  12.]
 [  7.   5.   5.   1.  10.  10.  10.  10.  11.  12.]
 [  7.   5.   6.   6.   8.   8.   8.   8.  11.  12.]
 [  5.   5.   6.   6.   6.   8.  11.  11.  11.  12.

No. 2
  2.   2.   2.   3.   3.   4.   4.   9.   9.   9.]
 [  2.   8.   2.   1.   3.   3.   4.   4.   9.  12.]
 [ 10.   8.   1.   1.   1.   3.   4.   7.   9.  12.]
 [ 10.   8.   8.   1.   5.  11.   7.   7.   6.  12.]
 [ 10.   8.   5.   5.   5.  11.   7.   6.   6.  12.]
 [ 10.  10.   5.  11.  11.  11.   7.   6.   6.  12.

No. 3
  2.   2.   2.   3.   3.   4.   4.   9.   9.   9.]
 [  2.   8.   2.   1.   3.   3.   4.   4.   9.  12.]
 [ 10.   8.   1.   1.   1.   3.   4.   7.   9.  12.]
 [ 10.   8.   8.   1.   5.  11.   6.   7.   7.  12.]
 [ 10.   8.   5.   5.   5.  11.   6.   6.   7.  12.]
 [ 10.  10.   5.  11.  11.  11.   6.   6.   7.  12.
...中略...
  • しかし、3時間16分経過してもNo. 335までしか求められない...。時間かかり過ぎ。
高速化を求める
  • そこで、高速化を求めて6行×10列のboardを、10行×6列に変更してみた。
  • boardサイズを可変できるように、行数と列数を変数に代入しておいた。
  • 解を出力する時だけ、90度回転させて本来の6行×10列に変換している。

 @@ -40,11 +40,12 @@ def piece_all(pp):
  
  def chk(board, pp, x, y, lvl):
      global counter
 +    board_h, board_w = board.shape
      for i, j, piece_matrix, piece_origin in piece_all(pp):
          h, w = piece_matrix.shape
          ox = x - piece_origin
          # ピースが飛び出したらそこから先は見ない
 -        if ox < 0 or ox + w > 10 or y + h > 6: continue
 +        if ox < 0 or ox + w > board_w or y + h > board_h: continue
          board_section = board[y:y + h, ox:ox + w]
          # ピースがかぶったらそこから先は見ない
          if (board_section * piece_matrix).any(): continue
 @@ -54,14 +55,14 @@ def chk(board, pp, x, y, lvl):
          if lvl == 11:
              counter += 1
              print 'No', counter
 -            print board
 +            print np.rot90(board)
              print
              board_section -= piece_matrix * (i + 1)
              pp[i].used = False
              return True
          k = board.argmin()
          # ここまで成功したら次のピースを試す
 -        chk(board, pp, k % 10, k // 10, lvl + 1)
 +        chk(board, pp, k % board_w, k // board_w, lvl + 1)
          # 失敗したら巻き戻して別の手を試す
          board_section -= piece_matrix * (i + 1)
          pp[i].used = False
 @@ -70,6 +71,6 @@ def chk(board, pp, x, y, lvl):
  
  counter = 0
 -board = np.zeros((6, 10))
 +board = np.zeros((10, 6))
  chk(board, pp, 0, 0, 0)
  print '解合計', counter

  • すると、わずか5分程度でNo. 800の解まで出力された!

劇的な高速化!

  • どうやら、左から右、上から下にpieceの置き方を検索する場合、boardの横幅となる列幅が狭いほど高速に検索できるようだ。
  • おそらく「# ピースが飛び出したらそこから先は見ない」の条件によって、列数が狭い方が早いうちに失敗を確定できるからと思われる。

  • 待つこと50分、とうとうすべての解が出力されたようだ!
$ python pentomino.py
...中略...
No 9354
  2.   2.   2.  10.  10.  10.  10.   7.   7.   3.]
 [  2.   6.   2.  10.   1.   7.   7.   7.   3.   3.]
 [  6.   6.  11.   1.   1.   1.   4.   3.   3.   9.]
 [  6.   6.  11.   5.   1.   4.   4.   9.   9.   9.]
 [ 11.  11.  11.   5.   5.   5.   4.   4.   8.   9.]
 [ 12.  12.  12.  12.  12.   5.   8.   8.   8.   8.

No 9355
 10.  10.   7.   2.   2.   2.   3.   6.   6.   6.]
 [ 10.   7.   7.   2.   1.   2.   3.   3.   6.   6.]
 [ 10.   7.  11.   1.   1.   1.   4.   3.   3.   9.]
 [ 10.   7.  11.   5.   1.   4.   4.   9.   9.   9.]
 [ 11.  11.  11.   5.   5.   5.   4.   4.   8.   9.]
 [ 12.  12.  12.  12.  12.   5.   8.   8.   8.   8.

No 9356
 10.  10.   7.   2.   2.   2.   6.   6.   6.   3.]
 [ 10.   7.   7.   2.   1.   2.   6.   6.   3.   3.]
 [ 10.   7.  11.   1.   1.   1.   4.   3.   3.   9.]
 [ 10.   7.  11.   5.   1.   4.   4.   9.   9.   9.]
 [ 11.  11.  11.   5.   5.   5.   4.   4.   8.   9.]
 [ 12.  12.  12.  12.  12.   5.   8.   8.   8.   8.

解合計 9356

重複を排除する
  • すべての解が出力されたと喜んだのも束の間、Webを検索してみると、ペントミノの解は2339通りらしい。
  • しかし、上記で出力された解は9356通りもある。

なぜ?

  • 実は、9356 = 2339 × 4なのである。
  • どうやら、ある一つのオリジナル解に対して、左右対称・上下対称・180度回転対称な配置もカウントしているためらしい。

f:id:zariganitosh:20150112151422p:image:w450

  • だから、ちょうど4倍の解が出力されてしまうのだ。
  • 対称解は、除外する必要があるらしい。

  • 対称解を除外する正攻法は...
    • 求めた解を保存しておいて、
    • 新たな解を見つけたら、
      • 過去に保存した解と対称でないかチェックする必要がある。
  • しかし、非常に手間と負担のかかる処理となりそう...。

  • そこで、もっと簡単な方法でチェックできないのか調べてみると...

対称解を発生させない検索方法が紹介されていた!

  • フリップあり、90度4回転する(8通りの形状がある)ピースに注目してみると、
  • 例えばFピースは、対称解でも上下対称・左右対称・180度回転対称な形状が現れている。

f:id:zariganitosh:20150112154200p:image:w450

  • 仮に、Fピースの形状をオリジナルと90度回転のみに制限できれば、対称解は発生しない、という考え方。
      • F形状に限らず、8通りの形状があるP・N・Y・L形状のどれか一つを制限しても同様の効果があるはず。

 -      Piece('110011010', 3,2,4),
 +      Piece('110011010', 3,1,2),

  • たったこれだけの修正をして、実行してみると...
$ python pentomino.py

No 2337
  2.   2.   2.  10.  10.  10.  10.   7.   7.   3.]
 [  2.   6.   2.  10.   1.   7.   7.   7.   3.   3.]
 [  6.   6.  11.   1.   1.   1.   4.   3.   3.   9.]
 [  6.   6.  11.   5.   1.   4.   4.   9.   9.   9.]
 [ 11.  11.  11.   5.   5.   5.   4.   4.   8.   9.]
 [ 12.  12.  12.  12.  12.   5.   8.   8.   8.   8.

No 2338
 10.  10.   7.   2.   2.   2.   3.   6.   6.   6.]
 [ 10.   7.   7.   2.   1.   2.   3.   3.   6.   6.]
 [ 10.   7.  11.   1.   1.   1.   4.   3.   3.   9.]
 [ 10.   7.  11.   5.   1.   4.   4.   9.   9.   9.]
 [ 11.  11.  11.   5.   5.   5.   4.   4.   8.   9.]
 [ 12.  12.  12.  12.  12.   5.   8.   8.   8.   8.

No 2339
 10.  10.   7.   2.   2.   2.   6.   6.   6.   3.]
 [ 10.   7.   7.   2.   1.   2.   6.   6.   3.   3.]
 [ 10.   7.  11.   1.   1.   1.   4.   3.   3.   9.]
 [ 10.   7.  11.   5.   1.   4.   4.   9.   9.   9.]
 [ 11.  11.  11.   5.   5.   5.   4.   4.   8.   9.]
 [ 12.  12.  12.  12.  12.   5.   8.   8.   8.   8.

解合計 2339
  • 待つこと20分、

見事、2339通りの解になった!

最終コード

  • 以下、コメントを修正したここまでのコード。
# coding: utf-8
import numpy as np



# すべてのピース形状をPieceオブジェクトの配列に保存する
class Piece:
    def __init__(self, s, h,m,n):
        a = np.array(map(int, s)).reshape(h, -1)
        self.used = False
        self.form = []
        for i in range(m):
            for j in range(n):
                self.form.append((a, a.argmax()))
                a = np.rot90(a)
            a = np.fliplr(a)

pp = [Piece('010111010', 3,1,1),
      Piece('111101',    2,1,4),
      Piece('110011001', 3,1,4),
      Piece('110011010', 3,1,2),
      Piece('110010011', 3,2,2),
      Piece('111110',    2,2,4),
      Piece('11100011',  2,2,4),
      Piece('11110100',  2,2,4),
      Piece('111010010', 3,1,4),
      Piece('11111000',  2,2,4),
      Piece('111100100', 3,1,4),
      Piece('11111',     1,1,2)]



# パズルの解を求める
def piece_all(pp):
    for piece_i, piece in enumerate(pp):
        if not piece.used:
            for form_j, form in enumerate(piece.form):
                piece_matrix, piece_origin = form
                yield piece_i, form_j, piece_matrix, piece_origin

def chk(board, pp, x, y, lvl):
    global counter
    board_h, board_w = board.shape
    for i, j, piece_matrix, piece_origin in piece_all(pp):
        h, w = piece_matrix.shape
        ox = x - piece_origin
        # ピースが飛び出したらそこから先は見ない
        if ox < 0 or ox + w > board_w or y + h > board_h: continue
        board_section = board[y:y + h, ox:ox + w]
        # ピースがかぶったらそこから先は見ない
        if (board_section * piece_matrix).any(): continue
        # ピースを置く
        board_section += piece_matrix * (i + 1)
        pp[i].used = True
        # すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
        if lvl == 11:
            counter += 1
            print 'No', counter
            print np.rot90(board)
            print
            # ピースを戻す
            board_section -= piece_matrix * (i + 1)
            pp[i].used = False
            return True
        # 次のピースを試す
        k = board.argmin()
        chk(board, pp, k % board_w, k // board_w, lvl + 1)
        # ピースを戻す
        board_section -= piece_matrix * (i + 1)
        pp[i].used = False
    return False

counter = 0
board = np.zeros((10, 6))
chk(board, pp, 0, 0, 0)
print '解合計', counter

*1:何もない0から開発すること