# 2022/05/28～06/05(9日)　AHC011(反面教師)

## はじめに
AHC011は方針を誤り提出まで至りませんでした。その反省を刻むためのメモであり反面教師にして下さい。

## 初見の印象
Nパズル問題。同種のタイルがあるから、その分短縮できるかも。

> N×N の盤面上に N^2 −1 枚のタイルが配置されている。 1タイル分の空きマスがあり、4方向に隣接するタイルを空きマスへスライド移動させることが出来る。 絵が各タイルに分割して描かれているので、スライド操作を繰り返すことでタイルを移動させ、絵を完成させよ。

必ず右下が空マスになるのと、木である事は保証されているらしい。
6 ≦ N ≦ 10 なので、マス目は 35～99。
操作回数 T = 2×N^3 なので、432～2000 回。
マスの種類は15種類+空マス。

## 1日目
■調査
全てつながった完全な解を出した方がいいのか？
→完全解を出した方がよい。
スコア比較
N=6、T=432
・K=Tで完成：500,000点
・K=1で1つだけずれ：500,000 * (431/432) < 完成の最低スコア
完全解の最短手数勝負であることがわかる。

データはchar配列でとりあえず。(16bitだから4倍ムダで済む)

完全解に対して近づけるようにスライドしていく。
※絶対に解けない解もある。どうやって検知するか？
→偶奇を見ればいいらしい。同種マスがあるので、これもDFSかな。
　https://manabitimes.jp/math/979
→空きマスが揃っている必要があるので、強制移動の上で確認。

通常のスライドパズルの解き方。
幅優先では、3×3が限界らしい。双方向探索の考えは使えそう。
http://www.nct9.ne.jp/m_hiroi/linux/cpp32.html
→双方向探索は使えないと決着が付いていた。
https://qiita.com/guicho271828/items/cf1e7fcb98b1f074eacb

反復深化で、下限値の工夫について詳しく書かれている。
https://computerpuzzle.net/puzzle/15puzzle/index.html

今回ゴールが複数あっていいので、各ゴールから反復深化で近づけるのが良さそう。
逆にスタートから双方向探索として、ゲーム木を作っておき、hitしたら終わる。

じろうさんのこれみたく、やはり解は複数存在。
https://twitter.com/Jiro_tech15/status/1530435632220508160

なので、やはり複数ゴールから逆算して、スタートに下限値で切りながら近づく反復深化(IDFS)が良さそう。
下限値で切る方法を工夫して、最短じゃなくてもそこそこの解を出すのがいいかも。
下限値はやはりWD (WalkingDistance)が賢そう
https://computerpuzzle.net/puzzle/15puzzle/index.html

とりあえず、スライド操作ではなく、任意配置で完全解が求まるか調べる。
DFSかな？
→調べた。山ほどある。
→適当にスタートから動かして、確定マスに対して完全解があるかをcheckするとか？

となると、やっぱりスタートからのビムサ系が良さそう。確定マスを評価していく方向で。
chokudaiサーチよりにして、IDFSで評価が進んだものを追加とか？
単純にゲーム木展開していったらだめかな？チェックポイント盤面のみ保存で。
→とりあえず全盤面保存でやってみる。
→先のWDを残コストとして、コスト最小化のサーチをやれば良さそう？
→ただ、ゴールが多すぎてWDを出せない。確定マスだけのサーチでいける？
→確定マスに対して完全解が見つかるかをcheck。
→端にしか置けないマスをcountすることで、ちょっと楽できそう。

暫定順位表は、maspyさんの38Mが1位。

## 2日目以降

(小さなケースで複数の完全解をゴールにDFSベースの探索を詰めていく。見るに耐えないので省略。最小ケースで運がいいと高い点は出るが。。。)

## 残り24時間
提出できるよう整えたいが、現状N=6も確実には終わらない。
seed0の解が出たら打ち切ってみると、45s/46sで完全解判定が支配的。
解が出たのはchokudaiサーチのloop4週目。全然回ってない。

N=7の解判定ですでに1s/回くらいかかってる。
→完全解が1つも出せない。
→ランダムに作った後、空マスを調整して空けるとかは？

ランダムで生成
10x10
ただ、N=7でもtile一致は見つけられない。
初期解からブラして近づけていく？
ブラして早くなったが、N=9で150sかかってる。

完全解を時間内に1つも求めることができない。

## 感想戦
小さいケースで楽に求まるからと完全解の調査を打ち切ったのが敗因。
大きなケースでの完全解をまず求めないと始まらなかった。
inputはランダムmoveで崩されているので、各辺周辺のtileから見ていけば確率的には見つかったんだろうか？
30M超えだと完全解は求まっていると思うので、導出方法が気になる。

他の人の解法を見る
・山登りで初期解を出したっぽい。あー。。。
・木を作るパートは枝狩りDFSで10msまじ！？
→G4ANPONさんより。大きいタイルからやるだったかぁ。。。
→phocomさんより、残りの手札意識。