이 퍼즐에 대한 상태 공간 그래프를 그림 1-5에 그려봤다. H_i, W_i는 각각 i번째 부부(i = 1, 2)의 남편과 아내를 나타낸다. 막대 두 개는 강, 회색 타원은 보트 위치를 나타내며 다음 이동 방향은 현재 위치로부터 알 수 있다(지면관계상 첫 번째 부부 H₁W₁이 강을 건너는 대신 두 번째 부부 H₂W₂가 강을 건너는 식으로 차이가 나는 부분은 그래프에 포함하지 않았다). 초기 상태와 최종 상태에 해당하는 꼭짓점은 굵게 표시했다.

이 그래프에서 초기 상태 꼭짓점에서 최종 상태 꼭짓점으로 이어지는 최단 경로는 네 가지로, 모두 네 개의 변으로 이어진다. 각 변으로 이어지는 네 경로는 다음과 같은 식으로 표현할 수 있다.

W₁W₂   W₁   H₁H₂   H₁   H₁W₁

W₁W₂   W₁   H₁H₂   W₂   W₁W₂

H₂W₂    H₂   H₁H₂   H₁   H₁W₁

H₂W₂    H₂   H₁H₂   W₂   W₁W₂

▲ 그림 1-5 질투심 많은 두 남편 문제의 상태 공간 트리