조금만 생각해보면 남편은 수탉을 잡을 수 없고 아내는 암탉을 잡을 수 없다는 것을 알 수 있다. 닭을 잡으려면 사람과 닭이 바로 옆 칸에 있어야 하는데 게임판을 체스판처럼 칠해놓고 나면(그림 1-17 (b)) 바로 옆 칸은 서로 색이 다르다. 남편과 수탉은 같은 색의 칸에서 출발하는데 각각 한 칸씩 이동하고 나도 칸의 색은 똑같으므로 몇 번 이동하든 남편과 수탉은 같은 색의 칸에 있을 수밖에 없다. 아내와 암탉에 대해서도 마찬가지다. 닭이 아무리 열심히 도망가도 둘 중 하나는 여덟 번 이동한 후, 나머지 하나는 아홉 번 이동한 후 잡힌다.

이 정도로 튜토리얼을 마치겠다. ‘어떤 퍼즐에 어떤 전략을 써야 하는가?’라는 질문에 대한 정답은 없다(정답이 있었다면 사람들은 애당초 퍼즐에 흥미를 느끼지도 않았을 것이다). 전략은 일반적인 도구에 불과하며 특정 문제에 잘 들어맞을 수 있지만 그렇지 않을 수도 있다. 문제를 많이 풀다 보면 어떤 도구가 잘 들어맞을지 알아채는 직관이 생길 수 있지만 그 직관이 항상 맞지 않을 수도 있다.

그렇더라도 지금까지 살펴본 전략과 기법은 알고리즘 문제를 푸는 유용한 도구로 써먹을 수 있다. 수학자들이 갖춘 도구보다 더 구체적이라는 장점도 있다. George Polya의 <어떻게 문제를 풀 것인가(How to Solve It)>(교우사, 2008)[Pol57]라는 책도 있지만 말이다.

물론 어떤 전략을 적용해야 할지 알더라도 일이 간단하지 않을 수 있다. 예를 들어 어떤 퍼즐에 해가 없다는 것을 증명할 때는 불변량을 활용하는 경우가 많다. 하지만 짝홀 특성을 활용하거나 판에 색을 적당히 칠하면 되겠다는 것을 알더라도 그 문제에 딱 맞는 불변량을 찾아내기 어려울 수 있다. 문제를 많이 풀다 보면 더 쉽게 찾아낼 수 있을지도 모르지만 원래 쉽지 않은 일이다.