게임 - n × n 정사각형 배열이 있다고 가정합니다. 이 중 일부 사각형은 비어 있고 일부는 솔리드이며 일부가 아닌 사각형은 정수 1, 2, 3, …으로 설정됩니다. 각 정수는 보드에서 정확히 두 개의 다른 사각형을 유지하거나 차지합니다. 플레이어의 임무는 수평 및 수직 이동만을 구현하는 간단한 경로의 도움으로 보드에서 각 정수의 두 발생을 연결하는 것입니다. 두 개의 다른 경로가 서로 교차하는 것은 허용되지 않습니다. 경로에는 실선 정사각형이 포함될 수 없습니다(단색 정사각형은 경로에 표시할 수 없습니다). 마지막으로 솔리드가 아닌 모든 사각형은 경로로 채워져야 합니다.
알고리즘 - 주어진 보드 크기 n × n으로 유효한 무작위 퍼즐을 구성하려면 먼저 보드에 서로 교차하지 않는 임의의 단순 경로를 생성합니다. 생성된 모든 경로 외부에 몇 개의 격리된 사각형이 남아 있으면 이러한 격리된 사각형을 솔리드(금지)로 표시합니다. 다음으로 경로의 끝점과 실선 사각형 목록을 퍼즐로 제공합니다.
따라서 우리는 먼저 솔루션을 생성하고 다음으로 솔루션에서 퍼즐을 해결합니다. 경로와 솔리드 사각형은 n × n 보드를 분할하거나 분할합니다. 우리는 이 파티션을 생성하기 위해 union-find 데이터 구조를 구현합니다. 데이터 구조는 보드에 있는 n^2 정사각형 세트의 하위 집합으로 처리됩니다.
의사 코드
-
다음과 같이 보드에서 무작위로 사각형 (a, b) 및 (c, d)를 찾습니다.
-
(a, b) 및 (c, d)는 서로 이웃하고
-
(a, b)도 (c, d)도 지금까지 생성된 경로에 속하지 않습니다. 전체 보드에서 이러한 사각형 쌍이 발견되지 않으면 FAILURE를 반환합니다. /* 여기서 (a, b) 및 (c, d)는 구성할 새 경로의 처음 두 사각형입니다. */
-
-
(a, b) 및 (c, d)를 포함하는 두 개의 union-find 트리의 합집합을 만듭니다.
-
현재 경로가 확장될 수 있을 때까지 반복하십시오 -
-
이름 바꾸기 (a, b) =(c, d).
-
-
−
가 되도록 (a, b)의 임의의 이웃 정사각형(c, d)을 찾습니다.-
(c, d) 지금까지 생성된 경로(현재 경로 포함)에 속하지 않습니다.
-
부분적으로 구성된 현재 경로에서 유일한 이웃(c, d)은 (a, b)입니다.
-
-
그러한 이웃(c, d)을 찾을 수 없으면 경로를 더 이상 확장할 수 없으므로 루프를 끊습니다.
-
그렇지 않으면 (a, b) 및 (c, d)가 속한 두 개의 union-find 트리의 합집합을 만듭니다.
-
새로운 경로의 시작점과 끝점에 있는 두 개의 사각형의 끝점 플래그를 설정합니다.
-
반환 성공