마지막으로 그래프에 대한 것으로 변환해 풀 수 있는 문제가 꽤 많이 있다. 그래프는 평면 위의 점과 점을 연결하는 선의 모음이라고 생각할 수 있다. 그래프에서 점과 선을 각각 꼭짓점(vertex)과 변(edge)이라고 부른다. 변에는 방향이 있거나 없을 수 있다. 변에 방향이 있으면 유향 그래프, 방향이 없으면 무향 그래프라고 부른다. 퍼즐이나 게임에서 꼭짓점은 문제의 특정 상태를 나타내고 변은 상태 사이에서 넘어갈 수 있는 경로를 나타낸다. 문제의 초기 상태에 해당하는 꼭짓점과 최종 목표에 해당하는 꼭짓점이 있는 그래프도 있다(최종 목표에 해당하는 여러 개의 꼭짓점이 있을 수도 있다). 이런 그래프를 상태 공간 그래프라고 부른다. 앞에서 설명한 변환은 방금 설명한 변환을 통해 문제를 초기 상태 꼭짓점에서 목표 상태 꼭짓점으로 이어지는 경로를 찾아내는 작업으로 바꿀 수 있다.

매우 오래되고 유명한 퍼즐 하나를 살펴보자.⁵

질투심 많은 두 남편 부부 두 쌍이 강을 건넌다. 배에는 최대 두 명까지만 탈 수 있다. 남편 둘 다 질투심이 강해 자기가 없을 때 아내가 다른 남자와 함께 있는 것을 참지 못한다. 이런 상황에서 네 명이 강을 건널 수 있을까?