절차 퍼즐의 소개

  요리를 하는 데 있어서 레시피(recipe, 요리법)를 따르는 것은 매우 중요하다. 먼저 물을 끓이는 동안 재료들을 썰고 프라이 팬을 달구다가 물이 끓으면 갖은 양념 육수를 만드는 동시에 재료들을 볶는 등 이리저리 요리법을 따라서 음식을 만들어 낸다. 만일 시간이 엄수되지 못하거나 순서를 무시하고 요리하다가는 완성된 음식이 사람 입에 차마 못 들어가는 일이 생길 수 도 있다.

 비단 요리 뿐만이 아니라, 청소, 운전등 일의 순서를 지켜야 하는 일은 꽤 많다.

 

 

 절차 퍼즐에서는 이런 일의 순서나 절차를 따지는 일을 할 것이다. 어떤 과제를 해내는 데에 있어서 가장 짧은 절차, 혹은 알고리즘(Algorithm)을 찾아내거나, 아니면 주어진 제약, 예를 들어 A라는 일이 반드시 B보다 먼저 해야 한다든지하는 그런 상황속에서의 올바른 절차를 찾는 것이다. 주어진 환경이 클 수록 가능한 일의 순서가 순식간에 불어나기 때문에 문제는 더욱 복잡해진다. (참고로, 어떤 n 개의 일을 나열할 수 있는 경우의 수는 n의 계승(factrial, n!=n*(n-1)*...*2*1)으로, 대단히 빨리 솟구치는 함수이다.)

 

 

 절차퍼즐의 종류로는 대표적으로 강건너기문제와 저울질문제가 있다.

 강건너기 문제에는 여러 사람들이 등장한다. 보트는 한정된 사람만 탈 수 있어서 모든 사람들을 실어 나르려면 여러번 움직여야 한다. 그런데, 이 움직임에 제약이 있어서 누구는 누구랑 타면 되니 안되니, 누구는 노를 저을 수 있니 없니 하면서 상황이 꼬이게 된다. 그런 어찌 보면 답답한 상황속에서 모든 사람들을 강 건너편으로 보내는 것이 임무이다. 주로 알려진 것은 선교사와 식인종 퍼즐, 그리고 콩가루 가족의 강 건너기 문제이다.

 저울질 문제에는 양팔 저울이 등장한다. 양팔저울의 특징은 잘 알다싶이 저울 양 팔에 걸린 물체의 무게 비교이고, 직접적인 무게를 아는 것은 불가능하다는 것이다. 하다봇해 분동이라도 있으면 무게를 얼추 잴 수 있겠으나, 대부분의 퍼즐은 쉬운 길을 늘 막아버린다. 결국 여러번의 저울질을 통해 주어진 물체들의 무게비교를 해야 한다. 주로 알려진 것은 불량품찾기 문제.(하나가 무겁거나, 혹은 가볍거나.)

 

 

 이 이외에도 식빵 빨리 굽기, 케이크 나누기 등 다소 복잡한 문제들을 다루어본다.