슬라이딩 퍼즐 풀기 - 기본편

어렸을 때, 한번쯤은 다들 해보았을 법한 퍼즐입니다.

 

일반적으로 4x4 퍼즐이라고도 하고, 그림 퍼즐이라고도 합니다.  하지만 퍼즐이란 말은 무언가 풀어볼 수 있는 형태의 게임을 다 지칭하는 것이라서요.  슬라이딩 퍼즐이라고 한정지어서 이야기하는 것이 맞을 듯 합니다.

 

 

 

4x4 슬라이딩 퍼즐

 

보통 많이 있는 퍼즐은 4x4 퍼즐로 위와 같이 숫자가 1부터 15까지 써 있는 형태이거나 그림이 있는 경우입니다.

 

4x4 그림 퍼즐

 

퍼즐 자체가 어렵지 않기 때문에, 하다보면 퍼즐을 맞출 수가 있습니다.  보통은 빈칸이 있는 곳과 가장 먼 줄부터 맞추어 나가는 것이죠.  맨 마지막 두줄은 돌리면서 회전하는 것을 생각해서 위치를 맞추면 됩니다.

 

그런데 최적의 해를 구할려면 어떻게 될까요?

슬라이딩 퍼즐은 모든 경우의 수를 따져보면 상당히 많습니다.  슬라이딩 퍼즐은 아무렇게나 배열할 경우 50%는 맞출 수 없는 경우가 됩니다.  그것을 감안하더라도 총 경우의 수는 15! 정도에 육박합니다.  4x4라면 15! 만큼 경우의 수를 찾는 것은 우리가 허용할 수 있는 시간안에 계산이 됩니다.  그렇지만 5x5만 해도 24! 정도의 경우의 수를 찾아야 합니다.  경우의 수는 약 10의 23승 정도가 됩니다.  1초에 백만개씩 처리하더라도 몇십, 몇백년이 걸리는 작업입니다.

 

슬라이딩 퍼즐을 랜덤하게 배열하면 좋겠지만, 그러면, 퍼즐이 풀릴 수 있는지 아닌지를 검사해야 합니다.  퍼즐이 풀릴 수 있는지 아닌지는 숫자의 위치를 가지고 판가름할 수 있습니다.  그렇지만, 여기서는 랜덤하게 슬라이딩해서 무작위 퍼즐을 만들었습니다.

 

[Generate random puzzle]

void GenerateRandomPuzzle(PuzzleParams *param)
{
	param->squares = new char[param->rows*param->cols];
	for( int i = 1 ; i < param->rows*param->cols ; i++ )
		param->squares[i-1] = i;
	param->emptySquare = param->rows*param->cols-1;
	param->squares[param->emptySquare] = 0;

	for( int i = 0 ; i < param->rows*param->cols*10 ; i++ )
		Move(param, (eMove)(rand()%4));
}