2Dのルービックキューブ、loopoverのAIを作る

loopoverとは

ここから遊べる2Dのルービックキューブみたいなパズルゲームです。
https://www.openprocessing.org/sketch/580366/

比較的簡単に, しかも機械的に解くことができます。

AIを作ると自分で解くのがだるいような大きなパズルでも一瞬で解くことができます。
（私のPCでは2x2~30x30までそれぞれ３０回実行して３秒くらいですべて解き終わることができます。人間でこれをやると、、、やりません）!

解き方

これらのパズルゲームを解く前に遊びまくりましょう。
遊ぶことが解を見つけるための近道です。

とはいっても、実際遊んでみると、意外と難しいと思います。そこで、どんな感じにすればとけるのか、一緒に考えてみましょう。

1. 問題を小さな問題に分割せよ

いきなり全体を解こうとしても、なかなか解けません。
そこで、問題を部分に区切って方針を決めて解くことにします。

1.1 (n-1)x(n-1)を解く

最初に上の左側(n-1)x(n-1)を解きます。
これは比較的簡単に解けます。

ここで重要なのは、右一列と下一行をフリーにしておくことです。
フリーにすることで、その行を使って比較的容易に$(n-1)\times(n-1)$のパズルを解くことができます。

それでもわからない人は、空いている列を使って組み立てていくイメージでやれば解けると思います。

void solven_1(int x,int y){
  int idx=x+y*n;
  int from_x=0;
  int from_y=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(banmen[i][j]==idx){
	from_x=j;
	from_y=i;
	break;
      }
    }
  }
  //  printf("solve %c:%d%d from %d%d\n",idx+'a',x,y,from_x,from_y);
  int sameyflag=0;
  if(from_y==y){
    //    puts("samey1");
    sameyflag=1;
    from_y++;
    move(from_x,DOWN);
  }
  for(int i=from_x;i<n-1;i++){
    //    puts("move2");
    move(from_y,RIGHT);
  }
  if(from_x!=n-1&&sameyflag){
    //    puts("samey2");
    move(from_x,UP);
  }
  if(x!=0){
    for(int i=x;i<n-1;i++){
      //      puts("move3");
      move(y,RIGHT);
    }
  }
  if(0<from_y-y){
    for(int i=0;i<from_y-y;i++){
      move(n-1,UP);
    }
  }else{
    for(int i=0;i<y-from_y;i++){
      move(n-1,DOWN);
    }
  }
  for(int i=x;i<n-1;i++){
    move(y,LEFT);
  }
}

1.2 右側(n-2)行を解く

ここの解き方は、下のフリーラインを使ってCの次にHをつなげるイメージで行います。これもそこまで難しくはならないと思います。

void solven_2(int y){
  int idx=n-1+y*n;
  int from_x=-1;
  int from_y=-1;

  for(int j=0;j<n;j++){
    if(banmen[j][n-1]==idx){
      from_x=n-1;
      from_y=j;
      break;
    }
    else if(banmen[n-1][j]==idx){
      from_x=j;
      from_y=n-1;
      break;
    }
  }
  //  printf("solve2 %c:%d from %d%d\n",idx+'a',y,from_x,from_y);

  if(from_x==n-1){
    for(int i=from_y;i<n-1;i++){
      move(n-1,DOWN);
    }
    move(n-1,LEFT);
    for(int i=from_y;i<n-1;i++){
      move(n-1,UP);
    }
    from_y=n-1;
    from_x=n-1;
  }
  for(int i=from_x;i<n-2;i++){
    //    puts("move1");
    move(n-1,RIGHT);
  }
  for(int i=y;i<n-1;i++){
    //    puts("move2");
    move(n-1,DOWN);
  }
  move(n-1,RIGHT);
  for(int i=y;i<n-1;i++){
    //    puts("move3");
    move(n-1,UP);
  }
}

1.3 下側(n-1)列を解く

ここは、右下にある２行のフリースペースを使って並び替えを行うイメージで解きます。
注目しているマスをまず、右下の２ますの上のマスに入れます。
その後、入ってほしい場所まで下をシフトさせ、入れて戻してあげる感じです。

void solven_3(int x){
  int idx=n*(n-1)+x;
  //  printf("moving %c\n",idx+'a');
  //  print();
  if(banmen[n-2][n-1]!=idx){
    int from_x;
    for(int i=1;i<n;i++){
      if(idx==banmen[n-1][i]){
	from_x=i;
      }
    }
    if(from_x==n-1){
      //  printf("hit\n");
      move(n-1,RIGHT);
      move(n-1,DOWN);
      move(n-1,LEFT);
      move(n-1,UP);
    }
    else{
      move(n-1,DOWN);
      for(int i=from_x;i<n-1;i++){
	move(n-1,RIGHT);
      }
      move(n-1,UP);
      for(int i=from_x;i<n-1;i++){
	move(n-1,LEFT);
      }
    }
  }
  //  printf("ready\n");
  for(int i=x;i<n-1;i++){
    move(n-1,RIGHT);
  }
  move(n-1,DOWN);
  for(int i=x;i<n-1;i++){
    move(n-1,LEFT);
  }
  move(n-1,UP);
}

1.4 パリティーを解く

ここの２つが入れ替わっていると思います。これは少し解くのに頭を使います。
この場所と分かっている場合は、下の行、右の行に対して繰り返しシフトと往復をしていけばパリティを解消することができます。
右⇒下⇒左⇒下⇒右⇒下⇒左...を繰り返せば解消できるはずです。

このパリティはマップの大きさが偶数の時のみ発生し、仮に奇数の時に発生した場合はその盤面は解くことができません。どこかが間違っていることになります。

//only n is even
// parity swap
void swaplast2(){
  for(int i=0;i<n/2;i++){
    move(n-1,DOWN);
    move(n-1,RIGHT);
    move(n-1,UP);
    move(n-1,RIGHT);
  }
  move(n-1,DOWN);
  move(n-1,RIGHT);
  move(n-1,UP);
}

2. テストコードはしっかりと

各ステップにて、以前のステップですでに作られた構造が壊れていないかなどは注意深く見る必要があると思います。
また、テストは包括的に行うようにする必要があります。今回は大きさn=2~30をすべて30回ほどランダム生成してそれらを解かせています。

全体ソースコード

gistに置いておきます。
移動にかんしては無駄な移動が多く最適化の余地はありますが、面倒なのでこのままで。
https://gist.github.com/elect-gombe/767b2e1aed59e0812811b22fbba928ec

参考動画

原作者さんかな多分？　https://www.youtube.com/watch?v=95rtiz-V2zM