슬라이딩 퍼즐 만들기

슬라이딩 퍼즐을 만들어보았습니다. 😀
상세 코드는 깃허브에서 확인하실 수 있습니다.

프로젝트 소개

• 슬라이딩 퍼즐 입니다.
• 이미지를 등록하여 퍼즐을 만들 수 있습니다.
• 등록한 이미지를 제거할 수 있습니다.
• 3x3, 4x4, 5x5 난이도를 선택할 수 있습니다.
• Reset 버튼을 통해 문제를 갱신할 수 있습니다.

---

---

어려웠던 점

처음에는 퍼즐에 사용될 요소들을 무작정 섞기만 하면 될 줄 알았습니다.

하지만 신나게 퍼즐을 풀다보니 도저히 풀 수 없는 녀석이 튀어나오더라구요 🥲

무슨 이유일까 궁금해서 검색을 해보니 슬라이딩 퍼즐에도 풀 수 있는 문제에 대한 조건이 있었습니다.

이 글은 해당 문제를 해결한 방법에 대해 작성했습니다.

슬라이드 퍼즐 알고리즘 해당 글을 보고 슬라이딩 퍼즐의 조건을 참고 했습니다.

---

변수

퍼즐을 풀수있는 조건을 알기 전에 각 변수에 대한 설명이 필요합니다.

1. inversion

inversion은 퍼즐의 변수를 1차원 배열로 초기화 했을때 요소 중 하나인 a와 a보다 뒤에있는 b를 비교했을 때 a>b가 참인 경우의 수를 말합니다.

즉, inversion을 세는 경우는 아래와 같습니다.

• a의 인덱스는 b의 인덱스보다 커야한다.
• a > b 가 참이다.

const puzzle = [1,2,3,4,5,9,6,7,8,10,12,11,13,14,15];

위의 경우 처럼 초기화 했을때

• 9는 뒤에 나오는 6,7,8 보다 크기 때문에 inversion을 3증가시킵니다.
• 12는 뒤에 나오는 11 보다 크기 때문에 inversion을 1증가시킵니다.
• 따라서 이 경우 inversion은 4입니다.

2. N

변수 N은 퍼즐의 너비입니다.

3x3 퍼즐의 경우 N은 3입니다.
4x4 퍼즐의 경우 N은 4입니다.

3. fromBottom

변수 fromBottom은 빈 타일이 바닥으로부터 얼마나 떨어져있는지를 나타냅니다.

• 퍼즐 A
  

퍼즐A의 경우 빈칸은 바닥으로부터 두 번째에 있습니다. 즉 fromBottom은 2입니다.

• 퍼즐 B
  
  퍼즐B의 경우 빈칸은 바닥으로부터 네 번째에 있습니다. 즉 fromBottom은 4입니다.

---

조건

풀 수 있는 퍼즐인지 아닌지를 판단하기 위해서는 다음과 같은 조건들이 필요했습니다.

• N이 홀수이면 inversion수가 짝수여야 한다.
• N이 짝수이면 다음과 같은 경우 풀수 있다.
  • fromBottom이 짝수이며 inversion은 홀수이다.
  • fromBottom이 홀수이며 inversion은 짝수이다.
• 다른 모든 경우에는 퍼즐을 풀 수 없다.
  
  

위의 조건을 달성하기 위해 아래와 같은 resetPuzzle 함수를 작성했습니다.

// difficulty는 난이도별 퍼즐의 배열 초기값 입니다.
const resetPuzzle = useCallback((difficulty) => {
    let ok = false;
    let randomSet;
  	// 풀 수 있는 퍼즐이 나올때까지 반복합니다.
    while (!ok) {
      let inversion = 0;
      // 퍼즐을 랜덤하게 섞습니다.
      randomSet = difficulty.tiles.sort(() => Math.random() - Math.random());
      // 각 퍼즐의 순서를 따라가며 inversion을 증가시킵니다.
      randomSet.forEach((item, index) => {
        for (let i = index; i < randomSet.length; i++) {
          if (item > randomSet[i]) {
            inversion++;
          }
        }
      });
      // difficulti.cut은 퍼즐의 너비입니다.
      const N = difficulty.cut;
      if (N % 2 !== 0) {
	      // N이 홀수일때
        if (inversion % 2 === 0) {
          // inversion이 짝수이기 때문에 풀수있다.
          ok = true;
        }
      } else {
        // N이 짝수일때
        const fromBottom =
          difficulty.cut - Math.floor(randomSet.indexOf(EMPTY_TILE) / 4);
        // fromBottom이 짝수이고 inversion이 홀수이면 풀수있다.
        if (fromBottom % 2 === 0 && inversion % 2 !== 0) {
          ok = true;
        }
        // fromBottom이 홀수이고 inversion이 짝수이면 풀수있다.
        if (fromBottom % 2 !== 0 && inversion % 2 === 0) {
          ok = true;
        }
      }
    }
    return randomSet;
  }, []);

---

위와 같은 코드를 통해 풀 수 있는 퍼즐만 표시 할 수 있게 되었습니다. 😀