カテゴリー別アーカイブ: パズル

虫食い算 今日の問題

何分でできるかな？

乗算 入門：
temp

除算 入門：
temp

乗算 初級：
temp

除算 初級：
temp

※ 空欄に一桁の数字を入れて、式を完成させなさい。ただし、最上桁に０は入らないものとする。
※ ヒント、解説、解答はありません。

虫食い算 今日の問題【初級 除算】

下図の□に一桁の数字を入れて式を完成させなさい。（ただし、最上桁に０は入らないものとする）
temp

解答は下の方

↓

↓

↓

↓

↓

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 となる。
あとは、計算して空欄を埋めると下図のようになる。

temp

虫食い算 今日の問題【初級 乗算】

下図の□に一桁の数字を入れて式を完成させなさい。（ただし、最上桁に０は入らないものとする）

temp

解答は下の方

↓

↓

↓

↓

↓

４行目に注目。7? × 6 = ??8 だが、何かに6を乗じて一桁目が 8 になるのは、3 か 8 のみ。
よって、1行目は 73 または 78 ということになる。
次いで3行目に注目。8に何を乗じても一桁目は5にはならない。
3に何かを乗じて一桁目が5になるのは5のみである。
よって1行目は 73, 2行目は65が確定する。
あとは計算をするだけだ。
答えは下図のようになる。

temp

どうぶつしょうぎ＞ひよこだけの場合

temp

通常の「どうぶつしょうぎ」では田中らによって後手必勝であることが求められているが、上図のように、ライオンとひよこだけの局面から双方が最善を尽くした場合は、先手必勝 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];};
  • ２次元盤面を番人付き１次元配列で表す
  • 1×1 以外は左上のピース位置を代表ピースとし、それ以外は非代表ピースフラグを立てておく

自分用メモ：マッチ棒パズル ソルバー

  • ２本移動の場合、必ず２本移動しなくてはいけない
  • ので、反復深化の浅い探索は不要
  • ただし、既に移動済みの場合は、手数リミットを減らして反復深化を行う
  • 余計な移動を行っている場合があるので、手数リミット以上も探索する
  • ただし、処理時間を食うので、３手までを上限とする？

自分用メモ 

+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+

横線、縦線があるかどうかを bool 配列で表す。

bool horz[HT+1][WD];
bool vert[HT][WD+1];

端っこの処理をそれ以外と共通にするために、上下左右にひとマス分余計に要素を確保しておけばおｋかな？
一つの頂点に接続する辺の数は、0, 2（90度のみ）, 3, 4 ならOK

2*2 の場合でも、2*3*2 = 12 bit なので、2^12 = 4096
4*4 だと、4*5*2 = 40 bit にもなっちまうぞ

というわけで、マッチ棒の状態で回すのではなく、各マス目がマッチ棒で囲まれているかどうかで回すことにする。

箱入り娘に関するメモ

temp

  • 図１ は標準的な「箱入り娘」の初期状態だ。
  • マス目の数は 4×5 = 20
  • 各ピースの種別を８ビットで表せば、合計20byteとなる
  • 各ピースを32bit ビットボードで表せば、4*10 = 40 byte となる
  • 状態をハッシュ化するには、左上から順にピース番号を並べるとよい
    • （空欄を含めた）１１桁のタイプ列で充分
    • 3bit * 11 = 33bit , または 5^11 = 4.88 * 10^7