[퍼즐풀이AI프로젝트] 3.퍼즐 풀이
완성한 코드는 총 355줄로 상당히 길다.
고작 84줄이었던 이전 코드를 글로 풀어 포스팅하니 한참 길어졌던 것을 생각하면
4배 이상 길어진 이번 코드는 어찌 설명해야 할지 엄두가 안 나니
그저 개발과정에 곁들어 살짝씩만 소개하기로 한다.
첫 작업은 가장 쉽다.
혹시나 어떤 줄의 텐트 숫자가 0개인 경우
그 줄에서 나무를 제외한 모든 빈칸을 잔디로 채운다.
그다음도 쉬운 편으로
지도의 모든 좌표를 하나씩 점검해서
빈칸 상하좌우에 나무가 존재하지 않으면
해당 좌표는 반드시 잔디가 된다.
여기까지 수월하게 마치고 나면 이제부터는 급격하게 복잡해진다.
이 퍼즐을 푸는 데 가장 기본은
각 줄에 들어갈 수 있는 텐트의 숫자가 지정되어 있다는 점이다.
그러므로 가로 세로 한 줄씩 떼어서 살펴보게 되는데
막상 손으로 풀 때 고려했던 것들을 하나하나 코드로 옮기다 보니
간단할 거란 당초의 예상과는 다르게 중간에 때려치울까 고민했던 적도 여러 번.
예를 들어 어떤 줄에 정해진 텐트의 숫자가 6개일 경우를 생각해보자.
1. 줄에 남은 빈칸이 6개라면 모든 빈칸은 텐트일 수밖에 없다.
2. 그보다 적게 남았다면 더 이전 단계에서 판단을 잘못한 것이니 처음부터 다시 검토.
3. 마지막으로 그보다 많이 남았을 경우가 문제인데
3-1. 남은 빈칸이 7개이고
3-1-1. 모든 빈칸이 서로 연속되지 않을 때는 사이 간격이 하나만 떨어진 곳을 찾는다.
둘 중 하나는 반드시 텐트가 존재하므로, 그 사이에 놓인 대각선 칸은 잔디일 수밖에 없다.
3-1-2. 오직 두 개의 빈칸이 서로 연속될 때는 연속된 빈칸을 제외한 나머지는 모두 텐트를 배치한다.
둘 중 하나는 반드시 텐트이므로 인접 좌표들 중 공통된 좌표는 잔디가 된다.
3-2. 남은 빈칸이 8개이고
3-2-1. 오직 두 개의 빈칸이 서로 연속될 때는 (생략)
3-2-2. 오직 세 개의 빈칸이 서로 연속될 때는 (생략)
3-2-3. (생략)
3-3. (생략)
3-4. (생략)
등등
고려해야 할 경우의 수가 끝없이 많아지는 데
각각의 경우마다 매번 if 분기를 작성해 따로 처리해야 하는 탓에
완전히 끝없는 개노가다였음을 뒤늦게 깨닫게 되었다.
뿐만 아니라 둘 이상의 줄을 한꺼번에 살펴야만 힌트를 얻을 수 있는 경우도 종종 발생하는데
그런 것까지 고려하려면 코드의 작성이 너무 복잡해져 아주 미칠 지경이었고
뭣보다 특정 상황에서만 유효하기에 대부분의 경우엔 무의미해지는 확인 작업이 계속 추가되는 것도
괜한 부하를 유발해 실행속도와 코드의 질을 떨어뜨리는 원인이 되어 썩 내키지 않았다.
최종적으로는 각각의 루틴에 상한을 설정해 둬서
1줄씩 확인하는 작업에서 연속된 빈칸은 최대 6개까지만 고려하도록 하고
2줄 이상을 확인하는 작업은 단 한 가지만 남기고 나머지는 배제했다.
또 다른 문제점이 하나.
이전 코드의 작성에서도 인지했지만 결국 해결법을 찾지 못해 이때까지 안고 온 문제인데
가로 줄을 확인하는 코드와 세로 줄을 확인하는 코드를 통합할 방법을 못 찾았다.
같은 작업을 좌표와 순서만 바꿔서 반복할 뿐인데 따로 기술할 수밖에 없으니
코드의 길이가 두 배로 늘어나는 것은 둘째 치더라도
수정할 때마다 두 곳 모두 변경해줘야 해서 여간 골치 아픈 일이 아니었다.
그래도 이전 코드는 짧으니까 큰 문제가 아니었지만 이번엔 코드도 훨씬 길어 더더욱 영향이 크다.
며칠을 더 고민한 끝에
for 구문을 여러 번 돌리면서 각각의 범위를 가변적으로 설정하는 것으로 해결했다.
파이썬을 다루기 전부터 종종 직면했던 문제인데 오랜 고민 끝에 10여 년 만에 해결하게 되니
스스로는 특허라도 내고 싶을 정도로 이것만으로도 대단한 성취감이 있었다.
혹시 검색을 제대로 활용했다면 이 방법 혹은 더 나은 방법을 찾을 수 있었을지도 모르지만
무슨 키워드를 써야 할지 전혀 짐작조차 안된다.
내가 고안한 방법이 이미 널리 알려지지 않았다면 언젠가는 자세히 공개할 기회가 있을지도.
여기까지만 해도 작은 크기의 퍼즐은 거의 다 풀리는 것을 확인했다. (미지수가 없는 경우만)
하지만 크기가 커지면 마지막 몇 개를 찾지 못한다.
2줄 이상을 고려해야 하는 것들만 남게 되니 당연한 결과.
해서, 시행작오를 통한 무작정 대입법을 도입했다.
일단 현재 상태를 다른 변수에 기록해두고
아무 좌표나 하나를 잡아 텐트로 가정한 뒤 계속해서 풀어본다.
문제가 없다면 좋은 일이고 문제가 있다면 처음 가정이 틀린 셈이므로
최초의 좌표는 반드시 잔디가 된다.
그리고 다른 좌표를 잡아서 위의 과정을 반복.
이 부분에서도 무려 두 차례나 큰 난관에 봉착했었는데
나중에 발견한 원인의 하나는 다차원 배열에서 단순 copy 명령이 완벽한 사본을 만들지 않는 탓이었고
또 하나는 너무 간단해서 오히려 한동안 못 찾았던 오타가 말썽이었다.
실행 과정에서 오류라고 잡아내질 않으니 한동안 눈치채지 못하고 고생했던 것.
거듭된 실패 끝에 결국 원인을 찾아내어
전자는 배열 안에 다시 for 구문을 사용한 계층별 copy로 해결했고
후자는 변수에 대입하는 과정에 등호 두 개를 썼던 곳에서 하나를 지움으로 해결했다.
일단 지금까지 시험해본 퍼즐들은 다 풀리는 것을 확인했고
시행착오법으로 안 풀리는 퍼즐이 존재한다는 것이 과연 가능할지 의문이기에
잠정적으로 완성이라 결론 내린다.
->12/25 추가: 스냅샷을 1회로 제한하고 있는 한계로, 거듭된 스냅샷 실행 후 최초의 스냅샷 지점으로 돌아갈 수 없기에 더 이상 풀이가 불가능해지는 시나리오가 이론상 존재할 수는 있다.
앱에 포함된 퍼즐 중 가장 큰 크기인 22x22 중에서 A1의 퍼즐로 테스트한 결과 스샷을 첨부한다.
가로 줄 검토 - 세로 줄 검토의 전환이 50번 있은 끝에 정답에 도달했다.
잠정적 완성.
작업 기간: 11월 하순 ~ 12월 12일
진정한 완성이라 확정 지으려면 충분한 검증이 필요한데
적어도 이전 글에서 소개한 코드로 작성한 퍼즐들은 몇 차례 테스트 결과 아무 문제가 없었다.
추가로 게임 앱에 포함된 퍼즐들도 테스트하고 싶은데
몇 가지는 손으로 받아 적어 이식하여 테스트에 성공했지만
아무래도 수작업에는 한계가 있다.
(22x22 크기를 받아 적으려면 530 글자를 받아써야 하는데 손이 너무 많이 가다 보니 인간이 할 짓이 아니었다)
해서 다음에 올라올 글은 퍼즐의 이식이 되겠지만
귀찮음은 점점 더해가는 반면 코딩 작업 도중에 흥미가 많이 식어버려
벌써 열흘 넘게 중단된 탓에 언제 작성하게 될지는 기약이 없다.