최근 수정 시각 : 2024-11-19 15:46:27

슬라이딩 퍼즐

파일:sliding_puzzle.jpg
샘 로이드의 15퍼즐[1]
1. 개요2. 상세
2.1. 예시
3. 공략4. 여담

[clearfix]

1. 개요

sliding puzzle

퍼즐 놀이의 일종.

2. 상세

슬라이딩 퍼즐은 조각판을 움직여서 순서대로 맞추는 퍼즐 놀이다. 일반적으로 직사각형 구조로 배열된 숫자 조각판들로 구성되어 있고 직사각형 틀 안에 조각판을 옮길 수 있는 빈 칸 하나가 존재한다. 단 하나의 빈 칸을 제외하면 조각판들끼리 서로의 움직임을 제한하기 때문에 모든 조각판을 순서대로 나열하기 위해서는 사고력이 필요하다. 조각판을 들어올리거나 틀을 분해하여 퍼즐을 해결하는 것은 금지되어 있다.

장난감으로 제작하기도 쉽고 저작권도 없기 때문에[2] 많은 제품들이 시중에 나와있다. 당장 주변의 완구점이나 완구코너에서 쉽게 구입할 수 있다. 비디오 게임으로도 제작하기 쉽기 때문에 슬라이딩 퍼즐은 앱이나 다운로드로도 쉽게 즐길 수 있다. 숫자뿐만 아니라 사진이나 그림을 그려넣어도 순서대로 맞추면 완성된 그림을 볼 수 있다는 점 때문에 여러가지 이미지를 사용하기도 좋다.

알고리즘 분석글에 따르면 원래 그림(목표)가 순서대로 나열한 것일 때 제시되는 퍼즐이 풀 수 있는 배치인지는 이하로 구분할 수 있다.

N×N의 형태로 배치하였고, '자신보다 큰 수가 자신의 앞에 있는 갯수'의 합계가 I이며, 빈칸에 해당하는 X가 있을 때 다음과 같다.
  • N이 홀수, I가 짝수이면 풀 수 있는 배치다.
  • N이 짝수, X가 맨 아래 짝수 칸, I가 홀수이면 풀 수 있는 배치다.
  • N이 짝수, X가 밴 아래 홀수 칸, I가 짝수이면 풀 수 있는 배치다.
  • 이외의 경우에는 전부 불가능하다.

그래서, 슬라이딩 퍼즐을 프로그래밍할 때에는 완전 무작위로 배치하는 것이 아니라, 처음부터 풀린(=완전히 정렬된) 상태로 배치해 놓고 무작위로 한 칸씩 움직이는 것을 반복해서 흐트러진 상태로 시작하는 방식으로 구현하는 것이 정석이다. 만약 완전 무작위로 배치하게 되면 풀 수 없는 배치가 나올 가능성이 생기기 때문이다. 만약 완전 무작위로 배치할 거라면, 무작위 배치 후 위의 알고리즘으로 검사해서 풀 수 없는 배치로 확인되면 마지막 두 조각의 순서만 서로 바꿔서 재배치하는 것으로 처리할 수도 있다.

2.1. 예시

1 3 5
7 4 2
8 6
이것을 1차원으로 전개해 보면 1, 3, 5, 7, 4, 2, 8, X, 6 순이다.
  • 3 뒤에 자신보다 작은 수가 1개(2) 있다.
  • 5 뒤에 자신보다 작은 수가 2개(4, 2) 있다.
  • 7 뒤에 자신보다 작은 수가 3개(4, 2, 6) 있다.
  • 4 뒤에 자신보다 작은 수가 1개(2) 있다.
  • 8 뒤에 자신보다 작은 수가 1개(6) 있다.
N의 값이 홀수(3)이며 I의 값이 짝수(8)이므로, 이 퍼즐은 풀 수 있다.
1 2 3 4
5 6 7 8
9 10 11 15
13 14 12
이것을 1차원으로 전개해 보면 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 15, 13, 14, 12, X 순이다.
  • 15 뒤에 자신보다 작은 수가 3개(13, 14, 12) 있다.
  • 14 뒤에 자신보다 작은 수가 1개(12) 있다.
N의 값이 짝수(4)이며 I의 값이 홀수(3)이다. 이 경우 빈 칸이 맨 아래 짝수 칸이면 풀 수 있지만 홀수(1)이므로, 이 퍼즐은 풀 수 없다.

만약 배치를 다음과 같이 바꾼다면,
1 2 3 4
5 6 7 8
9 10 11
15 13 14 12
이것을 1차원으로 전개해 보면 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, X, 15, 13, 14, 12 순이다. 빈 칸을 제외한 순서는 위와 동일하다.
  • 15 뒤에 자신보다 작은 수가 3개(13, 14, 12) 있다.
  • 14 뒤에 자신보다 작은 수가 1개(12) 있다.
N의 값이 짝수(4)이며 I의 값이 홀수(3)이다. 빈 칸이 맨 아래 짝수(2) 칸이므로, 이 퍼즐은 풀 수 있다.

3. 공략

루빅스 큐브보다는 쉽다. 루빅스 큐브는 한 면을 돌리면 8개의 블럭 위치가 바뀌고 블럭의 방향까지 생각해야 하지만, 슬라이딩 퍼즐은 블럭을 하나씩 움직이고 위치만 맞추면 되기 때문.[3] 보통 윗줄부터 한 줄씩 맞춘 다음 마지막 두 줄부터는 왼쪽부터 오른쪽으로 채워나가는 식으로 진행하면 된다.
14 15 10 9
8 11 13 3
6 4 2 7
5 12 1
우선 1과 2를 제자리에 갖다 놓자. 이건 쉽다.
1 2 14 9
15 10 13
8 11 6 3
5 4 12 7
3과 4가 문젠데, 다음과 같이 하면 둘을 한번에 맞출 수 있다.
1 2 9 3
15 6 14 4
8 10 13
5 12 11 7
3을 4의 위치에 갖다 놓고, 4를 3의 아래에 놓는다.
1 2 3
15 6 9 4
8 10 14 13
5 12 11 7
3이 들어가야 할 자리를 비운다. 그러면 3, 4가 한번에 맞춰진다.
1 2 3 4
5 6 7 8
9 10 14
13 12 15 11
같은 방법으로 5, 6은 그냥 갖다 놓고, (7, 8), (9, 13)은 한번에 맞추면 된다.
1 2 3 4
5 6 7 8
9 10 15 11
13 14 12
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
10, 14도 한번에 맞춘다. 정상적인 퍼즐은 남은 11, 12, 15를 계속 돌리면 끝나지만, 안 맞춰진다면? 축하한다. 맞출 수 없는 퍼즐이었다!
1 2 3 4
5 6 7 8
9 10 11 15
13 14 12
▲ 불가능한 퍼즐. 여기서 맨 위의 14-15 치환 퍼즐로는 맞출 수 있다.

4. 여담

[1] 참고로 위 퍼즐처럼 14, 15 두 블럭의 위치가 바뀐 퍼즐은 절대로 맞출 수 없다.문제적남자 여기서는 맨 아랫줄이 (14, 15, 13), (15, 13, 14)처럼 숫자가 루프식으로 연속된 상태일 때만 맞출 수 있다.[2] 무려 1880년에 처음 등장한 퍼즐이다.[3] 루빅스 큐브의 각 면에 슬라이딩 퍼즐이 결합되어 큐브 전체를 섞을 때마다 블럭의 색상과 방향까지 전부 바뀌는 변형 퍼즐도 있다.#

분류