3 개의 백돌과 3 개의 흑돌 그리고 중간에 빈 구멍을 가지는 퍼즐이 있다.
최초 상태: WWW_BBB 최종 상태: BBB_WWW이 퍼즐에서는 2 가지의 이동이 가능하다.
N 사이즈의 shuttle puzzle 은 N 개의 흑돌과 N개의 백돌 그리고 스페이스를 포함 2N+1 개의 구멍을 가진다.
아래는 사이즈 3에서의 최초, 중간 ,마지막 상태를 보여준다.
WWW BBB WW WBBB WWBW BB WWBWB B WWB BWB W BWBWB WBWBWB BW WBWB BWBW WB BWBWBW BWBWB W BWB BWW B BWBWW BB WBWW BBBW WW BBB WWW입력으로 N 을 입력으로 받아 최소한의 이동으로 최종 상태를 만드는 프로그램을 작성하는 것이 일이다.
입력 3 출력 3 5 6 4 2 1 3 5 7 6 4 2 3 5 4
출처 : usaco