상하좌우 중에서 3면 이상이 정위치에 있는 블럭 혹은 벽으로 막혀 있을 때 그 위치에 블럭을 넣으려면 반드시 이미 자리 잡은 블럭중 하나를 움직어야 됨.

그래서 3면 이상이 막힌 자리가 존재하지 않게 만들기 위해서 움직여야 하는 블럭의 갯수*2 를 맨하탄 휴리스틱에 더해도 admissible heuristic이 될거임.

위치를 옮겼다가 다시 제자리에 놓아야 하니까 *2를 하는거고.


문제는 linear conflict랑 같이 쓰려면 골아플듯.

linear conflict 자체도 여러개 있을때 서로 충돌하는것 때문에 카운팅 하기 어려워 보이던데.


그리고 당장 고쳐야될게 너무 많아 ㅋㅋ 이거 이번주 안으로 해보기 힘들것 같아.



(예시)

1 3 * *

8 6 * *

9 5 * *

* * * *


이렇게 되있으면 1, 6, 9를 움직이지 않고 8을 꺼낼 방법이 없잖아.

셋중에 적어도 2개는 움직여야 8을 꺼내고 그 자리에 5를 넣을 수 있음.

2개를 움직였다가 다시 제자리로 놓으려면 최소 2*2 = 4번을 더 움직여야 함.

따라서 (h_manhattan + 4)를 휴리스틱으로 쓸 수 있음.