点Nの軌跡

競プロの話または日記

コンデンサ解法全列挙プログラム

ゲーム プログラミング

これのプログラムについて。

基本方針は全探索。

[0,1,2,3]

[4,5,6,7]

[8,9,10,11]

というふうに番号をふって考える。下線が引いてあるところは固定されている。ひとつ操作すると4近傍も同じように回る。固定されているやつは操作できないし、近傍が操作されても動かない。

操作できるやつは9個である。同じのを8回操作すると元に戻るので、そのようなことをするのは無駄である。それぞれ0回以上7回以下、合計89通りの操作を試してみて、正しい経路になっていればよい。12点通るので検証にそれに比例した時間がかかるとして、単純にやると89×12で16億回ぐらいの演算が必要になりそう。一般的なPCで実行してもすぐ終わりそうだけど、ちょっとだけ高速化を狙ってみたい。

よくみると、8番は最後に下を向いていなければならない。8番に影響するのは8番自身とその横の9番だけなので、8番と9番の操作回数は片方を決めるともう片方が同時に確定する。88×12で2億回ぐらいに落ちた。

同様に、0番3番11番も角なので最終的に向いている方向に強めの制約（半分以上許されない）がかかっている。ここに枝刈りを入れてあげることでもっと早くなりそうだったのでそうした。

経路の検証。スタートからたどって11回移動したときに、全部の場所を通っていてなおかつゴールにいたらOK（ゴール地点=8番の向きは下でなければならないが、二つ上の段落で解決しているので考慮する必要はない）。盤外に出たり既に来たところに戻ったらその時点で打ち切っている。

追記

ご指摘。

https://twitter.com/rustysapen/status/1476545306582208522

僕の実装だと0番の向き右を許容してるけど1番の入次数が2になってしまうのでこれは枝刈りできるポイント。ソースコードに反映してないですが、if文書き換えて実行してもらうと倍ぐらい速くなる気がします。

追記終わり

実行はこちら。

https://paiza.io/projects/Tog8_lnk1J8cQmuaApxc6w

ソースコードは以下にも。

#include <iostream>
#include <utility>
#include <chrono>

using namespace std;
using dir = pair<int,int>;
using pos = pair<int,int>;

constexpr int startid = 3;
constexpr int goalid = 8;

/*
int id[3][4] = {
  {0,1,2,3},
  {4,5,6,7},
  {8,9,10,11}
};
*/

pos id_pos(const int x){
  return {x>>2,x&3};
}
int pos_id(const pos p){
  return p.first*4+p.second;
}

constexpr bool lock[3][4] = {
  {0,0,1,0},
  {1,0,0,0},
  {0,0,1,0}
};

int in(const pos p){
  int y = p.first, x = p.second;
  return 0<=y && y<3 && 0<=x && x<4;
}
int out(const pos p){
  return !in(p);
}

pos add(const pos p, const dir d){
  return {p.first+d.first, p.second+d.second};
}

enum dirstr{
  U,UR,R,DR,D,DL,L,UL
};

constexpr dir dirs[8] = {
  {-1,0}, // U
  {-1,1}, // UR
  {0,1},  // R
  {1,1},  // DR
  {1,0},  // D
  {1,-1}, // DL
  {0,-1}, // L
  {-1,-1} // UL
};

constexpr int neighbor[4] = {U,R,D,L};

constexpr int initialpuzzle[3][4] = {
  {U,U,L,D},
  {U,D,UL,UL},
  {UL,R,L,U}
};
int getinitstate(const int x){
  return initialpuzzle[x>>2][x&3];
}

int state[3][4];
void resetstate(){
  for(int y=0;y<3;y++){
    for(int x=0;x<4;x++){
      state[y][x] = initialpuzzle[y][x];
    }
  }
}
void spin(const int id, const int t){
  if(lock[id>>2][id&3]) return;
  state[id>>2][id&3]+=t;
  state[id>>2][id&3]&=7;
}
void push(const int id, const int t){
  if(lock[id>>2][id&3]) return;
  spin(id,t);
  pos p = id_pos(id);
  for(int i=0;i<4;i++){
    pos nxt = add(p,dirs[neighbor[i]]);
    if(in(nxt)){
      spin(pos_id(nxt),t);
    }
  }
}

constexpr int fullbit = (1<<12)-1;

int path[12];
void resetpath(){
  for(int i=0;i<12;i++) path[i]=0;
}

int c[12];

int main(){
  chrono::system_clock::time_point start, end;
  start = chrono::system_clock::now();

  int cnt = 0;

  for(c[9]=0;c[9]<8;c[9]++){
    c[8] = D-((c[9]+getinitstate(8))&7); if(c[8]<0) c[8]+=8;
    for(c[0]=0;c[0]<8;c[0]++){
      for(c[1]=0;c[1]<8;c[1]++){
        int s0 = (getinitstate(0)+c[0]+c[1])&7;
        if(!(R<=s0 && s0<=DR)) continue;
        for(c[7]=0;c[7]<8;c[7]++){
          for(c[3]=0;c[3]<8;c[3]++){
            int s3 = (getinitstate(3)+c[3]+c[7])&7;
            if(!(D<=s3 && s3<=L)) continue;
            for(c[11]=0;c[11]<8;c[11]++){
              int s11 = (getinitstate(11)+c[7]+c[11])&7;
              if(UR<=s11 && s11<=DL) continue;
              for(c[5]=0;c[5]<8;c[5]++){
                for(c[6]=0;c[6]<8;c[6]++){
                  resetstate();
                  resetpath();
                  for(int i=0;i<12;i++) push(i,c[i]);
                  int id = startid;
                  pos nowpos = id_pos(id);
                  int check = 1<<id;
                  path[0] = id;
                  for(int p=1;p<12;p++){
                    nowpos = add(nowpos,dirs[state[id>>2][id&3]]);
                    if(out(nowpos)) break;
                    id = pos_id(nowpos);
                    path[p] = id;
                    if((check>>id)&1) break;
                    check|=(1<<id);
                  }
                  if(check==fullbit){
                    if(1){
                      cout << "solution found:\n";
                      cout << c[0] << ' ' << c[1] << ' ' << 'x' << ' ' << c[3] << '\n';
                      cout << 'x' << ' ' << c[5] << ' ' << c[6] << ' ' << c[7] << '\n';
                      cout << c[8] << ' ' << c[9] << ' ' << 'x' << ' ' << c[11] << '\n';
                    }
                    if(1){
                      int sum = 0, btn = 0;
                      for(int i=0;i<12;i++) sum+=c[i];
                      for(int i=0;i<12;i++) if(c[i]) btn++;
                      cout << sum  << " push, " << btn << " buttons\n";
                    }
                    if(1){
                      cout << "path:";
                      for(int i=0;i<12;i++) cout << ' ' << path[i];
                      cout << '\n';
                    }
                    cout << '\n';
                    cnt++;
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  cout << cnt << " solutions\n";
  end = chrono::system_clock::now();
  double ela = chrono::duration_cast<chrono::milliseconds> (end-start).count();
  cout << "solve time: " << ela << " ms\n";
  return 0;
}