先日、地元のまつりがあった。そこの会場となっている区民館では子供用ボーリングやプラ板遊びなどの催しが開かれていたのだが、その中の一つに「ひとりぼっち」というゲームを行なっているのを見つけたので、一緒にいた小4の自分の娘に「このゲーム面白そうだね」と言ったところ、「ラストワンでしょ」と返され、よく知っているゲームとのことだった。遊び方は次の通り。全部で33のマスがあり、真ん中以外の32個のマスにコマを置く。コマは縦・横方向に隣のコマを一つ飛び越えて進むことができる。飛び越えられたコマは取り除かれる。これを繰り返して、最後のコマを真ん中のマスに置けばクリアとなる。32コマを使うステージ以外にもT字型やピラミッド型にコマを配置するなど、さまざまなバリエーションがある。
ネットで調べたところ、1985年にバンダイから同名の電子ゲームが出ていたようだ。リンク先では動画もあるのでそれを見てもらえば遊び方は一目瞭然だろう。普通に解いても面白そうだが、コンピュータを使って解かせたくなったので、早速プログラムを作ってみた。
余談だが、子供のころ、コンピュータは何でも解いてくれる魔法の箱だと思っていた。円周率を何桁まで解いたと聞いて、ワクワクしたものだ。ラストワンのようなゲームをコンピュータに解かせたいという気持ちは、子供のころのコンピュータに対する憧れから来るのかもしれない。
閑話休題。ラストワンは33マスあり、コマが「ある」「ない」の2状態のみを持つので、33ビットを使って盤面の状態を表すことができる。そして、ある状態から取り得る次の状態をすべて求めて、それを優先順位付きキューに入れて探索した。キューが空になるか、ゴールの状態が見つかるまで探索を行う。優先順位付きキューにしたのは探索を短縮するためにヒューリスティックな関数でスコアを決めようと思ったからなんだけど、32コマあるステージも含め、どれも一瞬で解けてしまうので、どうやら高度なヒューリスティック関数を用意しなくても問題なかったらしい。
上図のように初期配置としてT字型にコマを置く場合、以下に示すような入力データを用意して、これをプログラムに渡す。o (オー)でコマのあるマスを表し、. (ドット)で空のマスを表している。
lastone.dat
... ... ....... ..ooo.. ...o... .o. ...
入力データのファイル名が lastone.dat であれば、以下のように実行すればよい。
% ./lastone lastone.dat
実行結果は以下のようになる。
... ... ....... ..ooo.. ...o... .o. ... ... ... ....... .o..o.. ...o... .o. ... ... ... ....... .o.oo.. ....... ... ... ... ... ....... .oo.... ....... ... ... ... ... ....... ...o... ....... ... ...
最後に作成したコードを示す。
lastone.cpp
// Last One solver by nox, 14 Oct. 2011 #include <iostream> #include <fstream> #include <string> #include <vector> #include <queue> #include <algorithm> #include <utility> using namespace std; typedef unsigned long long state_t; typedef int score_t; const int N = 33; // number of cells class LastOne { private: vector<vector<pair<int, int> > > D; // table of directions state_t start, goal; vector<state_t> ans; // solution public: LastOne(const string datafile=""); ~LastOne() { } void read(const string datafile); int movable(state_t state); void next(state_t state, vector<state_t>& neighbors); bool search(); void show(state_t state); void answer(); }; // initialize and make table LastOne::LastOne(const string datafile) { if (!datafile.empty()) read(datafile); vector<pair<int, int> > v; v.push_back(make_pair(1, 2)); v.push_back(make_pair(3, 8)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 9)); D.push_back(v); v.clear(); v.push_back(make_pair(1, 0)); v.push_back(make_pair(5, 10)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 5)); v.push_back(make_pair(8, 15)); D.push_back(v); v.clear(); v.push_back(make_pair(9, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 3)); v.push_back(make_pair(10, 17)); D.push_back(v); v.clear(); v.push_back(make_pair(7, 8)); v.push_back(make_pair(13, 20)); D.push_back(v); v.clear(); v.push_back(make_pair(8, 9)); v.push_back(make_pair(14, 21)); D.push_back(v); v.clear(); v.push_back(make_pair(3, 0)); v.push_back(make_pair(7, 6)); v.push_back(make_pair(9, 10)); v.push_back(make_pair(15, 22)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 1)); v.push_back(make_pair(8, 7)); v.push_back(make_pair(10, 11)); v.push_back(make_pair(16, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(5, 2)); v.push_back(make_pair(9, 8)); v.push_back(make_pair(11, 12)); v.push_back(make_pair(17, 24)); D.push_back(v); v.clear(); v.push_back(make_pair(10, 9)); v.push_back(make_pair(18, 25)); D.push_back(v); v.clear(); v.push_back(make_pair(11, 10)); v.push_back(make_pair(19, 26)); D.push_back(v); v.clear(); v.push_back(make_pair(14, 15)); D.push_back(v); v.clear(); v.push_back(make_pair(15, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(8, 3)); v.push_back(make_pair(14, 13)); v.push_back(make_pair(16, 17)); v.push_back(make_pair(22, 27)); D.push_back(v); v.clear(); v.push_back(make_pair(9, 4)); v.push_back(make_pair(15, 14)); v.push_back(make_pair(17, 18)); v.push_back(make_pair(23, 28)); D.push_back(v); v.clear(); v.push_back(make_pair(10, 5)); v.push_back(make_pair(16, 15)); v.push_back(make_pair(18, 19)); v.push_back(make_pair(24, 29)); D.push_back(v); v.clear(); v.push_back(make_pair(17, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(18, 17)); D.push_back(v); v.clear(); v.push_back(make_pair(13, 6)); v.push_back(make_pair(21, 22)); D.push_back(v); v.clear(); v.push_back(make_pair(14, 7)); v.push_back(make_pair(22, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(15, 8)); v.push_back(make_pair(21, 20)); v.push_back(make_pair(23, 24)); v.push_back(make_pair(27, 30)); D.push_back(v); v.clear(); v.push_back(make_pair(16, 9)); v.push_back(make_pair(22, 21)); v.push_back(make_pair(24, 25)); v.push_back(make_pair(28, 31)); D.push_back(v); v.clear(); v.push_back(make_pair(17, 10)); v.push_back(make_pair(23, 22)); v.push_back(make_pair(25, 26)); v.push_back(make_pair(29, 32)); D.push_back(v); v.clear(); v.push_back(make_pair(18, 11)); v.push_back(make_pair(24, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(19, 12)); v.push_back(make_pair(25, 24)); D.push_back(v); v.clear(); v.push_back(make_pair(22, 15)); v.push_back(make_pair(28, 29)); D.push_back(v); v.clear(); v.push_back(make_pair(23, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(24, 17)); v.push_back(make_pair(28, 27)); D.push_back(v); v.clear(); v.push_back(make_pair(27, 22)); v.push_back(make_pair(31, 32)); D.push_back(v); v.clear(); v.push_back(make_pair(28, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(29, 24)); v.push_back(make_pair(31, 20)); D.push_back(v); } // read LastOne data void LastOne::read(const string datafile) { fstream fs(datafile.c_str(), ios_base::in); string line; goal = 0x10000; start = 0ULL; while (getline(fs, line)) { for (string::iterator p = line.begin(); p != line.end(); ++p) { if (*p == 'o') { start <<= 1; start |= 1ULL; } else if (*p == '.') start <<= 1; } } fs.close(); } // number of movable pieces int LastOne::movable(state_t state) { int s = 0; for (int i = 0; i < N; i++) if ((state >> i) & 1) for (vector<pair<int, int> >::iterator p = D[i].begin(); p != D[i].end(); ++p) s += ((state >> p->first) & 1) & !((state >> p->second) & 1); return s; } // next states void LastOne::next(state_t state, vector<state_t>& neighbors) { neighbors.clear(); for (int i = 0; i < N; i++) if ((state >> i) & 1) for (vector<pair<int, int> >::iterator p = D[i].begin(); p != D[i].end(); ++p) if (((state >> p->first) & 1) & !((state >> p->second) & 1)) neighbors.push_back(state ^ (1ULL << p->first) ^ (1ULL << p->second) ^ (1ULL << i)); } // search solution bool LastOne::search() { vector<state_t> checked(1, start); priority_queue<pair<score_t, vector<state_t> > > queue; queue.push(make_pair(1, checked)); vector<state_t> neighbors; while (!queue.empty()) { pair<score_t, vector<state_t> > q(queue.top()); queue.pop(); state_t last = q.second.back(); if (last == goal) { ans = q.second; return true; } next(last, neighbors); for (vector<state_t>::iterator p = neighbors.begin(); p != neighbors.end(); ++p) { if (binary_search(checked.begin(), checked.end(), *p)) continue; if (movable(*p) == 0 && *p != goal) continue; checked.insert(upper_bound(checked.begin(), checked.end(), *p), *p); vector<state_t> path(q.second); path.push_back(*p); queue.push(make_pair(static_cast<score_t>(path.size()), path)); } } return false; } // show state void LastOne::show(state_t state) { string line; while (state) { if (state & 1ULL) line.push_back('o'); else line.push_back('.'); state >>= 1; } int n = N - line.size(); for (int i = 0; i < n; i++) line.push_back('.'); reverse(line.begin(), line.end()); cout << " " << line.substr(0, 3) << endl; cout << " " << line.substr(3, 3) << endl; cout << line.substr(6, 7) << endl; cout << line.substr(13, 7) << endl; cout << line.substr(20, 7) << endl; cout << " " << line.substr(27, 3) << endl; cout << " " << line.substr(30, 3) << endl; } // show solution void LastOne::answer() { for (vector<state_t>::iterator p = ans.begin(); p != ans.end(); ++p) { show(*p); cout << endl; } } int main(int argc, char* argv[]) { if (argc < 2) { cerr << "Usage: " << argv[0] << " datafile" << endl; exit(1); } LastOne lastone(argv[1]); if (lastone.search()) lastone.answer(); else cout << "No solution." << endl; return 0; }
ネットで調べたところ、1985年にバンダイから同名の電子ゲームが出ていたようだ。リンク先では動画もあるのでそれを見てもらえば遊び方は一目瞭然だろう。普通に解いても面白そうだが、コンピュータを使って解かせたくなったので、早速プログラムを作ってみた。
余談だが、子供のころ、コンピュータは何でも解いてくれる魔法の箱だと思っていた。円周率を何桁まで解いたと聞いて、ワクワクしたものだ。ラストワンのようなゲームをコンピュータに解かせたいという気持ちは、子供のころのコンピュータに対する憧れから来るのかもしれない。
閑話休題。ラストワンは33マスあり、コマが「ある」「ない」の2状態のみを持つので、33ビットを使って盤面の状態を表すことができる。そして、ある状態から取り得る次の状態をすべて求めて、それを優先順位付きキューに入れて探索した。キューが空になるか、ゴールの状態が見つかるまで探索を行う。優先順位付きキューにしたのは探索を短縮するためにヒューリスティックな関数でスコアを決めようと思ったからなんだけど、32コマあるステージも含め、どれも一瞬で解けてしまうので、どうやら高度なヒューリスティック関数を用意しなくても問題なかったらしい。
上図のように初期配置としてT字型にコマを置く場合、以下に示すような入力データを用意して、これをプログラムに渡す。o (オー)でコマのあるマスを表し、. (ドット)で空のマスを表している。
lastone.dat
... ... ....... ..ooo.. ...o... .o. ...
入力データのファイル名が lastone.dat であれば、以下のように実行すればよい。
% ./lastone lastone.dat
実行結果は以下のようになる。
... ... ....... ..ooo.. ...o... .o. ... ... ... ....... .o..o.. ...o... .o. ... ... ... ....... .o.oo.. ....... ... ... ... ... ....... .oo.... ....... ... ... ... ... ....... ...o... ....... ... ...
最後に作成したコードを示す。
lastone.cpp
// Last One solver by nox, 14 Oct. 2011 #include <iostream> #include <fstream> #include <string> #include <vector> #include <queue> #include <algorithm> #include <utility> using namespace std; typedef unsigned long long state_t; typedef int score_t; const int N = 33; // number of cells class LastOne { private: vector<vector<pair<int, int> > > D; // table of directions state_t start, goal; vector<state_t> ans; // solution public: LastOne(const string datafile=""); ~LastOne() { } void read(const string datafile); int movable(state_t state); void next(state_t state, vector<state_t>& neighbors); bool search(); void show(state_t state); void answer(); }; // initialize and make table LastOne::LastOne(const string datafile) { if (!datafile.empty()) read(datafile); vector<pair<int, int> > v; v.push_back(make_pair(1, 2)); v.push_back(make_pair(3, 8)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 9)); D.push_back(v); v.clear(); v.push_back(make_pair(1, 0)); v.push_back(make_pair(5, 10)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 5)); v.push_back(make_pair(8, 15)); D.push_back(v); v.clear(); v.push_back(make_pair(9, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 3)); v.push_back(make_pair(10, 17)); D.push_back(v); v.clear(); v.push_back(make_pair(7, 8)); v.push_back(make_pair(13, 20)); D.push_back(v); v.clear(); v.push_back(make_pair(8, 9)); v.push_back(make_pair(14, 21)); D.push_back(v); v.clear(); v.push_back(make_pair(3, 0)); v.push_back(make_pair(7, 6)); v.push_back(make_pair(9, 10)); v.push_back(make_pair(15, 22)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 1)); v.push_back(make_pair(8, 7)); v.push_back(make_pair(10, 11)); v.push_back(make_pair(16, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(5, 2)); v.push_back(make_pair(9, 8)); v.push_back(make_pair(11, 12)); v.push_back(make_pair(17, 24)); D.push_back(v); v.clear(); v.push_back(make_pair(10, 9)); v.push_back(make_pair(18, 25)); D.push_back(v); v.clear(); v.push_back(make_pair(11, 10)); v.push_back(make_pair(19, 26)); D.push_back(v); v.clear(); v.push_back(make_pair(14, 15)); D.push_back(v); v.clear(); v.push_back(make_pair(15, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(8, 3)); v.push_back(make_pair(14, 13)); v.push_back(make_pair(16, 17)); v.push_back(make_pair(22, 27)); D.push_back(v); v.clear(); v.push_back(make_pair(9, 4)); v.push_back(make_pair(15, 14)); v.push_back(make_pair(17, 18)); v.push_back(make_pair(23, 28)); D.push_back(v); v.clear(); v.push_back(make_pair(10, 5)); v.push_back(make_pair(16, 15)); v.push_back(make_pair(18, 19)); v.push_back(make_pair(24, 29)); D.push_back(v); v.clear(); v.push_back(make_pair(17, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(18, 17)); D.push_back(v); v.clear(); v.push_back(make_pair(13, 6)); v.push_back(make_pair(21, 22)); D.push_back(v); v.clear(); v.push_back(make_pair(14, 7)); v.push_back(make_pair(22, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(15, 8)); v.push_back(make_pair(21, 20)); v.push_back(make_pair(23, 24)); v.push_back(make_pair(27, 30)); D.push_back(v); v.clear(); v.push_back(make_pair(16, 9)); v.push_back(make_pair(22, 21)); v.push_back(make_pair(24, 25)); v.push_back(make_pair(28, 31)); D.push_back(v); v.clear(); v.push_back(make_pair(17, 10)); v.push_back(make_pair(23, 22)); v.push_back(make_pair(25, 26)); v.push_back(make_pair(29, 32)); D.push_back(v); v.clear(); v.push_back(make_pair(18, 11)); v.push_back(make_pair(24, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(19, 12)); v.push_back(make_pair(25, 24)); D.push_back(v); v.clear(); v.push_back(make_pair(22, 15)); v.push_back(make_pair(28, 29)); D.push_back(v); v.clear(); v.push_back(make_pair(23, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(24, 17)); v.push_back(make_pair(28, 27)); D.push_back(v); v.clear(); v.push_back(make_pair(27, 22)); v.push_back(make_pair(31, 32)); D.push_back(v); v.clear(); v.push_back(make_pair(28, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(29, 24)); v.push_back(make_pair(31, 20)); D.push_back(v); } // read LastOne data void LastOne::read(const string datafile) { fstream fs(datafile.c_str(), ios_base::in); string line; goal = 0x10000; start = 0ULL; while (getline(fs, line)) { for (string::iterator p = line.begin(); p != line.end(); ++p) { if (*p == 'o') { start <<= 1; start |= 1ULL; } else if (*p == '.') start <<= 1; } } fs.close(); } // number of movable pieces int LastOne::movable(state_t state) { int s = 0; for (int i = 0; i < N; i++) if ((state >> i) & 1) for (vector<pair<int, int> >::iterator p = D[i].begin(); p != D[i].end(); ++p) s += ((state >> p->first) & 1) & !((state >> p->second) & 1); return s; } // next states void LastOne::next(state_t state, vector<state_t>& neighbors) { neighbors.clear(); for (int i = 0; i < N; i++) if ((state >> i) & 1) for (vector<pair<int, int> >::iterator p = D[i].begin(); p != D[i].end(); ++p) if (((state >> p->first) & 1) & !((state >> p->second) & 1)) neighbors.push_back(state ^ (1ULL << p->first) ^ (1ULL << p->second) ^ (1ULL << i)); } // search solution bool LastOne::search() { vector<state_t> checked(1, start); priority_queue<pair<score_t, vector<state_t> > > queue; queue.push(make_pair(1, checked)); vector<state_t> neighbors; while (!queue.empty()) { pair<score_t, vector<state_t> > q(queue.top()); queue.pop(); state_t last = q.second.back(); if (last == goal) { ans = q.second; return true; } next(last, neighbors); for (vector<state_t>::iterator p = neighbors.begin(); p != neighbors.end(); ++p) { if (binary_search(checked.begin(), checked.end(), *p)) continue; if (movable(*p) == 0 && *p != goal) continue; checked.insert(upper_bound(checked.begin(), checked.end(), *p), *p); vector<state_t> path(q.second); path.push_back(*p); queue.push(make_pair(static_cast<score_t>(path.size()), path)); } } return false; } // show state void LastOne::show(state_t state) { string line; while (state) { if (state & 1ULL) line.push_back('o'); else line.push_back('.'); state >>= 1; } int n = N - line.size(); for (int i = 0; i < n; i++) line.push_back('.'); reverse(line.begin(), line.end()); cout << " " << line.substr(0, 3) << endl; cout << " " << line.substr(3, 3) << endl; cout << line.substr(6, 7) << endl; cout << line.substr(13, 7) << endl; cout << line.substr(20, 7) << endl; cout << " " << line.substr(27, 3) << endl; cout << " " << line.substr(30, 3) << endl; } // show solution void LastOne::answer() { for (vector<state_t>::iterator p = ans.begin(); p != ans.end(); ++p) { show(*p); cout << endl; } } int main(int argc, char* argv[]) { if (argc < 2) { cerr << "Usage: " << argv[0] << " datafile" << endl; exit(1); } LastOne lastone(argv[1]); if (lastone.search()) lastone.answer(); else cout << "No solution." << endl; return 0; }
コメント