최근 수정 시각 : 2024-11-29 13:56:23

슬라이딩 퍼즐

파일: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. 공략

트위스티 퍼즐보다는 쉽다. 트위스티 퍼즐은 한 면을 돌리면 블럭 위치가 전부 바뀌고 블럭의 방향까지 생각해야 하지만, 슬라이딩 퍼즐은 블럭을 하나씩 움직이고 위치만 맞추면 되기 때문.[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] 2x2나 3x3 큐브의 각 면에 슬라이딩 퍼즐이 결합되어 큐브 전체를 섞을 때마다 블럭의 색상과 방향까지 전부 바뀌는 변형 퍼즐도 있다.#

분류