何分でできるかな?
※ 空欄に一桁の数字を入れて、式を完成させなさい。ただし、最上桁に0は入らないものとする。
※ ヒント、解説、解答はありません。
下図の□に一桁の数字を入れて式を完成させなさい。(ただし、最上桁に0は入らないものとする)
解答は下の方
↓
↓
↓
↓
↓
4行目から5行目を引いたら余りが0になるのだから、4行目と5行目は同じ数。
すなわち、5行目は 2?4 だ。
で、5行目の値は除数に3を乗じたものだから、3で割り切れないといけない。
3で割り切れる数字は各桁の合計も3で割り切れるので、? は 0, 3, 6, 9 のいずれかとなる。
204/3 = 68, 234/3 = 78, 264/3 = 88, 294 = 99 なので、
除数は 68, 78, 88, 98 のいずれかということになる。いずれにしても1桁目は 8 だ。
3行目に注目すると、1桁目が2である。8に何かを乗じて1桁目が2になるのは 8*4 と 8*9 だけだ。
しかし、9 は大きすぎて 68*9 でも 612 となり、被除数の 1/10 を大きく越えてしまう。
*4 の場合でも 78*4 = 312 となり大きすぎる。
よって、商は 43, 除数は 68, 被除数は 43*68 = 2924 となる。
あとは、計算して空欄を埋めると下図のようになる。
玉:3*4 + 5*6 + 8*2 = 58
金:3*2 + 5 + 4*4 + 6*2 + 2*2 + 3 = 46
飛:2*4 + 3*6 + 4*2 = 34
角:1*4 + 2*6 + 4*2 = 24
歩:1*9 = 9
歩=100 とすれば、角=267、飛=378、金=511
全てのコマの合計:(100+267+378+511)*2 = 2512
通常の「どうぶつしょうぎ」では田中らによって後手必勝であることが求められているが、上図のように、ライオンとひよこだけの局面から双方が最善を尽くした場合は、先手必勝 or 後手必勝 or 引き分け のどれなのであろうか?
プログラムのチェックもかねて探索してみたところ、上図は先手必勝だった。
必勝手順の初手はライオンを斜め上に上がる手だった。ひよこをとっても良さそうだが、同ライオンとなった局面は後で出てくるが、先手必敗になる。どうやらライオンは相手陣地に近い方が有利なようだ。
H:0 Z:0 K:0 . *L . . *H . . H L . . . H:0 Z:0 K:0
ライオンが斜めにあがると、次はひよこをただで取られてしまうので、後手はひよこを取るよりない。
後手もライオンが斜めに上がると、先手ライオンに進まれてしまい、トライを阻止できなくなる。
なので、後手はひよこをとり、先手はライオンで取り返す。
この状態が最初に言及した局面と同じで、ライオンがひとつ進んだ方が勝ちの局面だ。
H:1 Z:0 K:0 . *L . . . . . L . . . . H:1 Z:0 K:0
ここで先手からライオンの頭にひよこを打たれると、後手ライオンが逃げ、先手ライオンがトライできるので、後手はライオンの頭にひよこを打つ一手。先手は横に逃げる。
H:0 Z:0 K:0 . *L . . *H . . . L . . . H:1 Z:0 K:0
後手のひよこが移動すると取られるし、後手ライオンが左に移動すると先手にトライされるので、後手ライオンが右による一手。
H:0 Z:0 K:0 . . *L . *H . . . L . . . H:1 Z:0 K:0
ここで先手が相手ライオン頭にひよこを打つと、ライオンに逃げられてしまい、あとが続かない。
正解は、下図のようにひよこを垂らす手。
H:0 Z:0 K:0 . . *L H *H . . . L . . . H:0 Z:0 K:0
放置しておくとニワトリを作られるので、後手は左に寄る一手。
H:0 Z:0 K:0 . *L . H *H . . . L . . . H:0 Z:0 K:0
先手ひよこはただ取られるだけに見えるが、成って相手ライオンを左に寄せるのが好手だ。
H:0 Z:0 K:0 N *L . . *H . . . L . . . H:0 Z:0 K:0
後手は取るしかない。
H:1 Z:0 K:0 *L . . . *H . . . L . . . H:0 Z:0 K:0
で、先手ライオンがひとつ前に進むと、後手は先手のトライを防ぐ手が無い。
H:1 Z:0 K:0 *L . . . *H L . . . . . . H:0 Z:0 K:0
というわけで、ひよこをたらして成り捨てるのが絶妙手で、13手で先手の必勝というわけだ。
縦長*5:19手
+--+--+--+--+ | 4| 4| 3| 3| +--+--+ + + | 3| 3| 3| 3| + + +--+--+ | 3| 3| 1 1| +--+--+ + + | 4| 3| 1 1| +--+ +--+--+ | | 3| 4| | +--+--+--+--+
横長*1, 縦長*4:93手
+--+--+--+--+ | | 1 1| 3| +--+ + + + | 4| 1 1| 3| +--+--+--+--+ | 3| 2 2| 3| + +--+--+ + | 3| 3| | 3| +--+ +--+--+ | 4| 3| 4| 4| +--+--+--+--+
横長*2, 縦長*3:138手
+--+--+--+--+ | 3| 4| 4| 4| + +--+--+--+ | 3| 3| 1 1| +--+ + + + | 3| 3| 1 1| + +--+--+--+ | 3| 2 2| 4| +--+--+--+--+ | | | 2 2| +--+--+--+--+
横長*3, 縦長*2:135手
+--+--+--+--+ | 1 1| 4| 3| + + +--+ + | 1 1| | 3| +--+--+--+--+ | | 3| 2 2| +--+ +--+--+ | 4| 3| 2 2| +--+--+--+--+ | 4| 4| 2 2| +--+--+--+--+
横長*4, 縦長*1:97手
+--+--+--+--+ | 4| 4| 1 1| +--+--+ + + | 2 2| 1 1| +--+--+--+--+ | | 4| 2 2| +--+--+--+--+ | 2 2| 3| | +--+--+ +--+ | 2 2| 3| 4| +--+--+--+--+
横長*5:56手
+--+--+--+--+ | 1 1| 4| 4| + + +--+--+ | 1 1| 2 2| +--+--+--+--+ | 2 2| 2 2| +--+--+--+--+ | 4| 2 2| 4| +--+--+--+--+ | 2 2| | | +--+--+--+--+
enum { // ピース種別 BLANK = 0, P2x2, P2x1, // width = 2, height = 1 P1x2, P1x1, MASK = 0x0f, F = 0x10, // 代表点意外の場合のフラグ P2x2F = P2x2|F, P2x1F = P2x1|F, P1x2F = P1x2|F, WALL = 255, // 盤面サイズ BD_WIDTH = 4, BD_HEIGHT = 5, ARY_WIDTH = (BD_WIDTH+1), ARY_HEIGHT = (BD_HEIGHT+2), ARY_SIZE = (ARY_WIDTH*ARY_HEIGHT), }; class Board { ..... private: byte m_board[ARY_SIZE];};
+--+--+--+--+ | | | | | +--+--+--+--+ | | | | | +--+--+--+--+ | | | | | +--+--+--+--+ | | | | | +--+--+--+--+
横線、縦線があるかどうかを bool 配列で表す。
bool horz[HT+1][WD]; bool vert[HT][WD+1];
端っこの処理をそれ以外と共通にするために、上下左右にひとマス分余計に要素を確保しておけばおkかな?
一つの頂点に接続する辺の数は、0, 2(90度のみ), 3, 4 ならOK
2*2 の場合でも、2*3*2 = 12 bit なので、2^12 = 4096
4*4 だと、4*5*2 = 40 bit にもなっちまうぞ
というわけで、マッチ棒の状態で回すのではなく、各マス目がマッチ棒で囲まれているかどうかで回すことにする。