모바일 퍼즐게임 Fill

격자 그래프에서 해밀턴 경로를 찾는 퍼즐게임. 구글 Play 스토어에 있음. 애플 앱스토어에도 아마 있을듯.

해밀턴 경로의 결정문제는 NP-완전임.

경로의 시작점은 이미 정해져있음. 게임의 난이도를 낮추기 위해서? 혹은 올리기 위해서인가? 모든 다른 노드와 인접한 새로운 노드를 하나 추가하면 되므로 경로의 시작점이 정해져 있어도 NP-완전인건 마찬가지임.

이전에 다른 모바일 퍼즐게임을 (우연적 요소가 없고 모든 정보가 공개되어 있는 결정론적 게임이었음; 애니팡이나 캔디크어러시 사가 같은 종류 말고) 자동으로 푸는 프로그램을 짠 적이 있는데, 그 퍼즐의 복잡도는 뭔지 모르겠다. 그냥 적당한 휴리스틱 및 탐색 트리 가지치기로 짠 거였는데.

그래픽이 단순하니 이것도 입출력 모듈을 구현하기는 어렵지 않을듯.

문제는 알고리즘인데, 해밀턴 경로 문제는 일반적 그래프에 관한 것이지만, 이 퍼즐은 그래프의 형태가 매우 제한되어 있음. 2차원 격자 그래프라고 하면 되나? 이 퍼즐의 복잡도 역시 NP-완전인가? 아마 증명되어 있을듯. 일단 평면 그래프 => 2차원 격자위의 그래프로 환원이 가능하니 평면 그래프가 NP-완전인 것만 알면 됨. 라고 생각했는데 아 이거 안 되는구나. 완전 멍청한 생각이었다.

비록 NP-완전이라더라도 적당한 휴리스틱을 고안할 수는 있을듯. 일단 쉽게 알 수 있는 건 degree 1 인 노드를 가장 마지막에 방문해야 한다는 것.

근데 이 퍼즐을 푼다는 건 결정문제를 푸는 것과는 다르다. 답이 있음은 보장되어 있다. 문제는 어떻게 경로를 찾느냐는 건데...

요즘 바쁜데 나중에 시간 나면 고민해봐야 하나. 아 근데 어차피 할 거 아무리 많아도 열심히 안 사는데. 요즘 그냥 간단한 모바일게임을 마구마구 하다보니까 별 걸 다 하게 되네. 이런 거 해서 뭐 하나. 내가 이런 한심한 게임이나 하면서 시간을 죽이기 위해 사나?

---------------------

아 이거 별로 안 어려운 (계산적으로든, 사람한테든) 문제인 것 같다. 다항시간에 풀리는 문제고, 그 알고리즘도 어렵지 않게 고안할 수 있을듯. 체스보드 모양으로 색칠한 다음에 parity를 이용해 잘 증명하면 될듯. 다음처럼 경우를 나누면 될 텐데

1. 흰 셀 수와 검은 셀 수가 2개 이상 차이남

해밀턴 경로 없음.

2. degree 1 인 노드가 3개 이상

해밀턴 경로 없음.

3. 그래프가 연결되지 않음

해밀턴 경로 없음.

4. 흰 셀 수와 검은 셀 수의 차에 따라, 시작 노드와 끝 노드의 색이 같은지 다른지가 결정됨. 그런데 degree 1 인 노드가 2개고, 따라서 시작 노드와 끝 노드가 정해져 있는데, 그 색이 적절하지 않다면?

해밀턴 경로 없음.

이렇게 잘 따져나가다 보면 할 수 있을 것 같음. 노드 수에 대해 적당한 invariant 를 유지해서 귀납법으로 하면 될듯. 귀납법이기 때문에 구성적이고 따라서 다항시간 알고리즘도 존재함. 선형시간에 될지는 잘 모르겠다. 아무튼 아직 엄밀히 증명한 건 아님. 어쩌면 안 될 수도.

------------------

아 저 조건 4개로는 부족하구나. 저 조건 4개에 모두 해당되지 않으면서 해밀턴 경로가 없는 반례가 있음. 7x7 칸에 들어가는 밭 전(田) 자 모양. 그래도 해밀턴 경로가 존재할 아주 복잡하지는 않은 필요충분조건이 있고 이 문제는 다항시간에 결정가능할 것 같은데... 검색을 하면 나오려나.

----------------

이 문제 NP완전임이 이미 증명되어 있음. grid graph hamiltonian 이라고 검색을 하니까 여러 가지 나옴. 검색을 열심히 하면 쉽게 설명되어 있는 증명을 찾을 수 있으려나... 이거 증명을 읽어봐야 하나? 어려우려나? 다른 할 것도 많은데. 그냥 검색을 통해 NP-완전임을 알았다는 것으로 충분할까.

NP 문제의 특징은 다항 시간 안에 답이 맞는지 틀린지 판단할 수 있는 certificate이 존재한다는 것. 이 문제의 경우 문제의 인스턴스 하나하나를 설계하기는 쉬움. 그냥 설계자가 직접 적당한 해밀턴 경로를 그리면 되니까. 나는 72개째 지금 풀고 있지만 문제가 굉장히 많던데, 문제 만들기 어렵지는 않을듯. 난이도 조절이 어려우려나?

아무튼 NP완전이라는 것을 알았으니 효율적인 알고리즘을 설계할 순 없음. 프로그램 짜서 자동으로 풀 거면 그냥 휴리스틱을 무지 집어넣어야겠네. 저 위에 말했던 조건 4개가 다 좋은 휴리스틱이죠 뭐. 트리 탐색으로 수많은 경로를 시도해보기 + 위 조건으로 트리 가지치기 하면 성능 꽤 잘 나올 것 같기도 하고. 애초에 문제 사이즈가 별로 안 커 보이는데. 사람이 푸는 것보다 빠른 알고리즘 짜기 별로 안 어려울 것 같다.

증명되지 않은 휴리스틱 구현해서 실험해보고 성능이 얼마나 나오나 측정해보고... 성능이 잘 나와도 왜 그런지 잘 이해할 수 없고 성능이 잘 나오지 않아도 왜 그런지 이해할 수 없고... 그런 거 별로 좋아하진 않았는데. 그래도 걍 취미로 하면 재미있을 것 같기도 하고. 근데 그 시간에 다른 이론 공부 하는 게 낫나?

그 짤 생각나네.

Theory is when you know everything but nothing works.

Practice is when everything works but no one knows why.

In our lab, theory and practice are combined: nothing works and no one knows why.

-----------------------

어릴 때 엄마 폰에 (피쳐폰) 저런 식으로 격자 그래프에서 해밀턴 경로를 찾는 게임이 있었음. 네모라이즈라는 게임이었는데, 특정 폰 모델 기본 탑재 게임이었던 것으로 기억함.

https://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE00629502&language=ko_KR#none

http://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE01612034&language=ko_KR

구글 검색 해보니까 어떤 사람이(이정림 경기대 석사과정, 권기현 경기대 교수) 이전에(2005년) 연구해놓은 내용이 나오네. 

모델 체킹을 통해서 푼다고 하네. 그게 정확히 뭐지? 난 그냥 트리 탐색+가지치기 휴리스틱으로 풀 생각밖에 못 했는데. 하긴 정형기법 쪽에서 형식논리학을 좀 쓴다고 들은 것 같다. 그래도 수리논리 쪽에서 쓰는 논리학과 정형기법 쪽에서 쓰는 논리학 사이에는 수학자들이 하는 해석학과 공학자들이 쓰는 미적분학 정도의 차이는 있겠지. 아무튼 재미있는 내용이고 읽어볼만할듯. 게다가 한글논문이고. ...... 읽어보는데 무슨 말인지 모르겠다. 모델 체킹을 모르는데 뭐.

그러고보니 전에 소코반(push push)도 모델 체킹으로 풀 수 있다고 들었는데. modal logic 으로 게임을 formulate 한다고 했나? 그게 모델 체킹 공부할 때 거쳐가는 중요한 연습문제정도 된다고 하던데. 프로그래밍 처음 배우는 거에 비유하면 테트리스 짜는 거 정도 되나.

그러고보니 모델론(model theory)로 P-NP 난제를 증명하려는 시도가 있다고 하던데, 관련이 있는 건가?

--------------------------------

아 이 얘기를 해도 되는지 모르겠는데... 저 사람은 전에 본 적이 있는 것 같다. (아마도) (기억이 확실하지 않음) (틀릴수도 있음) (사실 틀림) (틀렸다니까) 그 때 이런 말을 했던 것 같은데.

"제가 대학원생때 이거 공부하는데... 어휴... 책을 봐도 봐도 모르겠고... 책 보다가 이해 못해겠으면 집어던지고 교회 가서 하나님께 기도하고... 또 제가 크리스천이라... ㅎㅎㅎㅎ... 아무튼 이거 공부하는데 그냥 책만 보고 공부하면 모티베이션이 안 생기니까 게임 같은 거 풀어보면 좋습니다 ㅎㅎㅎㅎ"