네, 일부 워터 소트와 볼 소트 퍼즐은 정말로 해결 불가능합니다. 당신이 얼마나 숙련되어 있든, 몇 수를 시도하든, 특정 색 구성에는 해결된 상태로 이어지는 유효한 수의 시퀀스가 없습니다. 이것은 난이도의 문제가 아니라 퍼즐 구조에 관한 수학적 사실입니다. 왜 해결 불가능한 퍼즐이 존재하는지, 어떻게 인식하는지, 그리고 마주쳤을 때 무엇을 해야 하는지 다음에서 설명합니다.
일부 퍼즐을 풀 수 없는 이유
컬러 소트 퍼즐은 상태 공간——모든 가능한 보드 배열의 집합——내에 시작 위치에서 목표 위치로의 경로가 존재할 때만 해결 가능합니다. 그러한 경로가 존재하지 않을 때 퍼즐은 해결 불가능합니다.
퍼즐이 해결 불가능해지는 가장 흔한 이유는 다음과 같습니다:
빈 공간 부족
빈 시험관은 분류를 가능하게 하는 작업 공간입니다. 그것들은 비켜야 하는 색의 임시 저장소 역할을 합니다. 빈 공간에 비해 색이 너무 많은 퍼즐에서는 색이 영구적으로 잠길 수 있습니다. 10개의 색과 0개의 빈 시험관이 있는 퍼즐은 거의 확실히 해결 불가능합니다.
막힌 색 배열
때때로 초기 배열이 순환 의존성을 만듭니다. 색 A가 색 B 아래에 갇혀 있고, B가 색 C 아래에 갇혀 있고, C가 색 A 아래에 갇혀 있습니다. 어떤 한 수도 그 순환을 깨지 못하고 빈 공간도 그것을 풀기에 충분하지 않습니다. 이러한 막힘은 미묘할 수 있습니다——3개의 색만이 아니라 많은 시험관에 걸친 상호 잠금된 의존 사슬 전체를 포함할 수 있습니다.
잘못된 색 개수
잘 만들어진 퍼즐은 각 색이 시험관 용량과 정확히 같은 횟수만큼 나타나야 합니다. 4 슬롯 시험관 퍼즐에서 색이 3번만 나타나면 그 색은 완전한 시험관을 채울 수 없으므로 퍼즐을 풀 수 없습니다. 이는 보통 생성 오류 또는 퍼즐 입력 시 실수를 나타냅니다.
ChromaOracle이 해결 불가능한 퍼즐을 어떻게 감지하는가
ChromaOracle의 솔버는 BFS(너비 우선 탐색)를 사용하여 초기 구성에서 시작해 도달 가능한 모든 보드 상태를 체계적으로 탐색합니다. 시작에서 1수 떨어진 모든 상태를 확인한 다음, 2수 떨어진 상태를, 그 다음 3수, 식으로 진행합니다.
BFS가 해결된 구성을 찾지 못하고 도달 가능한 모든 상태를 소진하면 해가 존재하지 않음을 증명한 것입니다. 이것은 시간 초과나 추측이 아닙니다. 알고리즘은 문자 그대로 모든 가능한 수의 시퀀스를 확인했고 어느 것도 작동하지 않음을 확인했습니다. ChromaOracle은 이 결과를 즉시 명확히 보고합니다.
이 철저한 접근법이 감지를 신뢰할 수 있게 만듭니다. 휴리스틱 솔버는 일정 횟수의 시도 후에 포기하고 퍼즐이 정말 불가능한지 단지 어려운지 모르게 만들 수 있습니다. BFS는 그 모호함을 완전히 제거합니다.
해결 불가능한 퍼즐을 직접 인식하는 방법
컴퓨터의 철저한 검색에 필적할 수는 없지만 퍼즐이 해결 불가능할 수 있음을 시사하는 경고 신호가 있습니다:
- 빈 시험관 없음, 즉각적인 일치 없음 —— 모든 시험관이 가득 차고 어떤 가장 위 색도 다른 시험관의 가장 위 색과 일치하지 않으면 유효한 첫 수조차 없습니다.
- 순환 함정 —— 어떤 색을 분류하려면 먼저 그 색 자체를 분류하지 않으면 움직일 수 없는 색을 옮겨야 한다고 알아차린다면 막힘을 보고 있을 수 있습니다.
- 반복되는 루프 —— 같은 수를 진전 없이 반복적으로 취소하고 다시 하고 있다면 상태 공간의 도달 가능한 부분에 해가 포함되지 않을 수 있습니다.
- 색 개수 불일치 —— 각 색을 세어보세요. 어떤 색이 시험관을 채우는 데 필요한 정확한 횟수만큼 나타나지 않으면 퍼즐이 잘못되었습니다.
이 신호 중 어느 것도 그 자체로 결정적이지 않으므로 솔버가 해결 가능성을 확인하는 결정적인 도구입니다.
막혔을 때 무엇을 해야 하나
진전 없이 몇 분간 퍼즐을 작업해 왔다면 다음 단계를 따르세요:
- 퍼즐을 ChromaOracle에 입력하세요. 화면에 보이는 대로 색을 입력합니다. 솔버는 최적 해를 반환하거나 퍼즐이 해결 불가능함을 확인할 것입니다.
- 색 입력을 확인하세요. 솔버가 해결 불가능하다고 말하면 입력한 색이 정확한지 다시 확인하세요. 한 색을 잘못 배치하면 퍼즐 전체가 변합니다.
- 수용하고 진행하세요. 퍼즐이 해결 불가능함이 확인되면 계속 진행해도 얻을 것이 없습니다. 많은 퍼즐 앱은 절차적 생성 오류로 인해 해결 불가능한 레벨을 포함합니다. 그 레벨을 건너뛰고 다음 레벨로 이동하세요.
- 취소 버튼 사용. 퍼즐이 해결 가능했지만 잘못된 수의 시퀀스를 만들었다면 대부분의 앱에 취소 기능이 있습니다. 작동 가능한 상태로 되돌리고 솔버가 추천하는 경로를 따르세요.
퍼즐 앱은 의도적으로 해결 불가능한 레벨을 포함하는가?
보통은 의도적이지 않습니다. 대부분의 퍼즐 앱은 알고리즘적으로 레벨을 생성하고 일부 생성 방법은 해결 가능성을 검증하지 않습니다. 결과적으로 생성된 레벨의 작은 비율이 불가능합니다. 일부 앱은 레벨을 게시하기 전에 해결 가능성을 테스트하지만 많은 앱은 그러지 않습니다.
이것이 ChromaOracle 같은 솔버가 존재하는 주된 이유 중 하나입니다. 벽에 부딪혔을 때 그 벽이 진짜인지 상상인지 알 자격이 있습니다.
자주 묻는 질문
인기 앱에서 해결 불가능한 퍼즐은 얼마나 흔한가요?
앱에 따라 다릅니다. 레벨 생성 중에 해결 가능성을 검증하는 잘 설계된 앱에는 해결 불가능한 레벨이 없습니다. 검사 없이 무작위로 레벨을 생성하는 앱은 레벨의 1~5%가 해결 불가능할 수 있습니다. 업계 표준이 없으므로 비율은 전적으로 개발자의 품질 관리에 달려 있습니다.
퍼즐에 빈 시험관이 있으면 항상 해결 가능한가요?
아니요. 빈 시험관은 해결 가능성을 더 가능하게 만들지만 보장하지는 않습니다. 빈 시험관이 있어도 색 배열이 사용 가능한 작업 공간으로도 해결할 수 없는 막힘을 만들면 퍼즐은 여전히 해결 불가능할 수 있습니다. 빈 시험관의 수, 색의 수, 특정 배열 모두 중요합니다.
빈 시험관을 추가해서 해결 불가능한 퍼즐을 해결 가능하게 만들 수 있나요?
많은 경우, 네. 빈 시험관을 추가하면 상태 공간이 확장되어 이전에 해결할 수 없던 막힘을 깨뜨릴 수 있습니다. 그러나 보장되지는 않습니다——색 배열이 깊이 잠겨 있으면 추가 빈 공간이 있어도 일부 퍼즐은 해결 불가능한 채로 남습니다. 확실히 알 수 있는 유일한 방법은 수정된 퍼즐을 솔버를 통해 실행하는 것입니다.