마지막으로 알고리즘을 적용할 방향을 제시하는 건설적인 역할을 하는 불변량의 예를 살펴보자. 아래 퍼즐은 역사상 가장 유명한 퍼즐 제작자라고 할 수 있는 Henry Ernest Dudeney[Dud02, p.95]와 Sam Loyd[Loy59, p.8]⁹가 만든 퍼즐이다(판 크기와 일부 표현은 수정했다).

옥수수밭의 닭 이 게임은 옥수수밭을 나타내는 5 × 8판에서 진행되며 농부와 부인을 나타내는 한 색의 두 말과 수탉과 암탉을 나타내는 다른 한 색의 두 말이 있다. 매 순서마다 사람과 닭이 옆에 있는 정사각형으로 이동하는데 위, 아래, 왼쪽, 오른쪽으로 움직일 수 있지만 대각선 방향으로는 움직이지 못한다. 그림 1-17 (a)에 표시된 위치에서 시작해 남편(M)과 아내(W)가 한 칸씩 움직인 후 수탉(r)과 암탉(h)이 한 칸씩 움직인다. 닭 두 마리를 모두 잡을 때까지 게임은 계속된다. 남편이나 아내가 닭이 들어 있는 칸으로 움직일 수 있으면 닭을 잡게 된다. 목표는 이동 횟수를 최소로 하면서 닭을 모두 잡는 것이다.

▲ 그림 1-17 (a) 옥수수밭의 닭 퍼즐 판. (b) 체스판처럼 색칠한 판