ChromaOracle 퍼즐 솔버 작동 원리:BFS 알고리즘 설명

ChromaOracle은 BFS(너비 우선 탐색)라는 알고리즘을 사용하여 어떤 컬러 소트 퍼즐의 가장 짧은 가능 해도 찾습니다. 솔버는 추측하거나 휴리스틱을 따르지 않고, 가장 짧은 시퀀스부터 시작하여 모든 가능한 수의 시퀀스를 체계적으로 탐색하다가 퍼즐을 푸는 것을 찾을 때까지 계속합니다. 이는 반환되는 해가 가능한 한 적은 수의 수를 사용함을 보장합니다. 호기심 많은 플레이어와 기술 지향 독자 모두를 위해 작동 원리를 설명합니다.

퍼즐을 검색 문제로 보기

모든 컬러 소트 퍼즐——워터 소트, 볼 소트, 또는 어떤 변형이든——은 검색 문제로 기술될 수 있습니다. 임의 시점의 퍼즐 보드는 "상태"입니다: 모든 시험관에 걸친 특정 색 배열입니다. 모든 유효한 부음이나 이동은 한 상태를 다른 상태로 변환합니다. 퍼즐을 푸는 것은 시작 상태를 목표 상태——각 시험관이 한 가지 색만 담거나 비어 있는 상태——로 변환하는 수의 시퀀스를 찾는 것을 의미합니다.

지도처럼 상상해보세요. 각 교차로가 상태입니다. 교차로 사이의 각 도로가 수입니다. 시작 상태는 지금 있는 곳입니다. 목표 상태가 목적지입니다. 솔버의 일은 가장 짧은 경로를 찾는 것입니다.

너비 우선 탐색이란?

너비 우선 탐색은 매우 특정한 순서로 이 상태 지도를 탐색하는 방법입니다: 시작에서 1수 떨어진 모든 상태를 먼저 확인하고, 그 다음 2수 떨어진 모든 상태를, 그 다음 3수, 식으로 진행합니다. 모든 방향으로 층별로 균등하게 펼쳐집니다.

이 층화된 접근법이 최적성을 보장합니다. BFS는 어떤 6수 해를 탐색하기 전에 모든 5수 해를 탐색하기 때문에 목표 상태에 처음 도달하면 반드시 최단 경로를 통해 도달한 것입니다. 더 짧은 경로를 놓칠 수 없습니다——모든 짧은 가능성은 이미 확인되었습니다.

프로세스는 다음과 같이 작동합니다:

1. 초기 보드 상태에서 시작합니다.
2. 그 상태에서 모든 유효한 수를 생성합니다. 각 수는 새 보드 상태를 생성합니다.
3. 이 새 상태 중 어떤 것이 해결된 상태인지 확인합니다. 그렇다면 수의 시퀀스를 반환합니다.
4. 그렇지 않으면 모든 새 상태를 큐에 추가하고 큐의 다음 상태로 2단계부터 반복합니다.
5. 목표를 찾거나 모든 도달 가능한 상태가 탐색될 때까지 계속합니다.

큐가 해를 찾지 못하고 비어지면 퍼즐은 해결 불가능합니다——솔버가 즉시 보고합니다.

상태 공간 표현

BFS가 효율적으로 작동하려면 솔버가 각 보드 상태를 간결하게 표현하고 이미 방문한 상태를 감지하는 방법이 필요합니다. ChromaOracle은 각 시험관을 색의 스택으로 표현하고 전체 보드를 이러한 스택의 컬렉션으로 표현합니다.

같은 상태를 두 번 탐색하지 않기 위해——시간과 메모리를 낭비하기 때문——솔버는 각 상태에 대한 정규 키를 생성합니다. 이 키는 시험관 순서에 관계없이 동일한 배열을 같은 상태로 취급하는 보드의 정규화된 문자열 표현입니다. 두 보드가 같은 시험관 내용을 가지고 있지만 좌우 순서만 다르다면 같은 키를 생성하고 중복으로 인식됩니다.

이 중복 제거는 중요합니다. 그것 없이는 솔버가 같은 위치를 수백만 번 재방문하여 사용 불가능할 정도로 느려질 것입니다. 그것이 있으면 솔버는 각 고유 상태를 한 번만 처리합니다.

왜 BFS가 최단 해를 보장하는가

보장은 탐색 순서에서 옵니다. BFS는 시작에서의 거리(수의 수로 측정)에 따라 엄격히 상태를 처리합니다. 거리가 N인 모든 상태는 거리가 N+1인 어떤 상태보다 먼저 처리됩니다. 따라서 솔버가 목표 상태에 처음 도달하면 길이 N의 경로를 통해 도달한 것이며, 길이가 N 미만인 경로는 존재하지 않습니다——모든 짧은 경로는 이미 완전히 탐색되었기 때문입니다.

이는 알고리즘의 수학적 속성이며 휴리스틱이나 근사가 아닙니다. BFS가 반환하는 해는 증명 가능하게 최적입니다.

BFS와 DFS

ChromaOracle은 대안 알고리즘으로 DFS(깊이 우선 탐색)도 지원합니다. DFS는 다르게 작동합니다: 층별로 탐색하는 대신 백트래킹하기 전에 가능한 한 깊게 단일 경로를 따라갑니다.

장단점은 다음과 같습니다:

• BFS는 최단 해를 찾지만, 현재 깊이 수준의 모든 상태를 동시에 저장해야 하므로 더 많은 메모리를 사용합니다.
• DFS는 많은 경우 더 빠르게 해를 찾고 더 적은 메모리를 사용하지만 해가 최단이 아닐 수 있습니다. 만난 첫 번째 유효한 경로를 반환하며 필요한 것보다 훨씬 길 수 있습니다.

대부분의 플레이어에게 BFS가 올바른 선택입니다——최소 수의 수를 원하기 때문입니다. DFS는 단지 어떤 해라도 빨리 원할 때 또는 퍼즐이 BFS가 메모리 부족에 빠질 정도로 클 때 유용합니다.

미스터리 모드 작동 원리

ChromaOracle의 가장 독특한 기능 중 하나는 숨겨진 또는 알 수 없는 색을 포함하는 퍼즐용으로 설계된 미스터리 모드입니다. 많은 퍼즐 게임에서 일부 시험관 슬롯은 색 대신 물음표를 표시하며, 실제 색은 그 층이 시험관 가장 위가 될 때만 드러납니다.

ChromaOracle은 순열 분석을 통해 이를 처리합니다:

1. 솔버가 알 수 없는 것으로 표시된 모든 위치를 식별합니다.
2. 퍼즐의 규칙과 일치하는——각 색이 정확한 횟수만큼 나타나야 하는——그 위치에 대한 모든 가능한 색 할당을 생성합니다.
3. 결과로 나오는 각 퍼즐을 BFS를 사용해 독립적으로 풀어냅니다.
4. 모든 해 집합을 분석하여 숨겨진 색이 무엇이든 안전한 수를 찾습니다.

이를 "공통 접두사" 찾기라고 합니다——모든 가능한 색 할당의 해 시작에 나타나는 가장 긴 수의 시퀀스. 이 수들은 알 수 없는 것이 무엇으로 드러나든 정확함이 보장됩니다.

이 접근법은 불확실성의 문제를 철저한 분석의 문제로 변환합니다. 솔버는 추측하는 대신 모든 가능성을 고려하고 어떤 수가 위험 없는지 알려줍니다.

성능과 실제 한계

컬러 소트 퍼즐의 상태 공간은 시험관과 색의 수에 따라 기하급수적으로 커집니다. 5개 색의 단순한 퍼즐은 수천 개의 도달 가능한 상태를 가질 수 있습니다. 12개 색의 복잡한 퍼즐은 수백만 개를 가질 수 있습니다.

ChromaOracle은 브라우저에서 TypeScript를 사용하여 완전히 실행됩니다. 대부분의 퍼즐——약 10개 색까지——은 BFS가 1초 미만에 완료됩니다. 더 큰 퍼즐은 몇 초가 걸릴 수 있습니다. 매우 큰 구성은 브라우저 메모리 한계를 초과할 수 있으며 그 시점에서 DFS가 더 나은 옵션이 됩니다.

솔버는 순수 계산이며 네트워크 호출이 없습니다. 퍼즐 데이터는 디바이스를 떠나지 않으며 풀이 속도는 디바이스의 처리 능력에만 의존합니다.

엔진 아키텍처

기술 구현에 관심 있는 독자를 위해, ChromaOracle의 솔버 엔진은 집중된 모듈로 구성됩니다:

• Container(컨테이너) —— 단일 시험관을 색의 스택으로 표현하며 push, pop, 가장 위 색 쿼리를 처리합니다.
• Collection(컬렉션) —— 전체 보드를 표현하며 현재 상태에서 모든 유효한 수를 생성하고 중복 제거를 위한 정규 키를 생성합니다.
• Search(탐색) —— BFS와 DFS 모두 구현하며 큐 또는 스택과 방문된 상태 집합을 관리합니다.
• Strategy(전략) —— 다중 해 분석을 조정하며 모든 해를 찾고 미스터리 모드용 공통 접두사를 계산합니다.
• Validation(검증) —— 풀이가 시작되기 전에 퍼즐 구성이 잘 형성되었는지 확인합니다.

엔진은 프레임워크 의존성이 없습니다. 순수 TypeScript이며 독립적으로 테스트 가능하고 어떤 JavaScript 런타임에도 이식 가능합니다.

자주 묻는 질문

ChromaOracle이 특정 퍼즐에서 더 오래 걸리는 이유는?

풀이 시간은 상태 공간의 크기에 의존하며 이는 색, 시험관, 빈 슬롯의 수에 의해 결정됩니다. 색이 많고 빈 시험관이 적을수록 탐색할 가능한 상태가 더 많습니다. 빈 시험관이 1개인 12색 퍼즐은 빈 시험관이 3개인 4색 퍼즐보다 훨씬 큰 상태 공간을 가집니다.

솔버가 해를 찾지 못할 수 있나요?

해가 존재하면 BFS는 항상 그것을 찾습니다. BFS가 해를 찾지 못하고 완료되면 퍼즐은 수학적으로 해결 불가능합니다——유효한 수의 시퀀스가 목표 상태에 도달할 수 없습니다. ChromaOracle은 이를 명확하게 보고하므로 퍼즐이 단지 어려운 것이 아니라 불가능함을 알 수 있습니다.

BFS 해는 항상 최선인가요?

네. BFS는 수의 수 측면에서 최단 해를 보장합니다. BFS가 반환하는 해보다 적은 수의 유효한 해는 존재하지 않습니다. 이는 알고리즘의 수학적 속성입니다.

미스터리 모드는 어떤 수가 안전한지 어떻게 아나요?

미스터리 모드는 숨겨진 색의 모든 가능한 할당에 대해 퍼즐을 풀어내고 모든 해를 비교합니다. 수가 모든 가능성의 최적 해에 나타날 때만 안전한 것으로 표시됩니다. 이는 그 수가 숨겨진 색이 무엇이든 정확함을 의미합니다.