3x3 격자 퍼즐 풀기 (JS)

Question

이미지를 3x3 격자로 분리했습니다. 그리드는 배열로 표시됩니다. 각 열 또는 행은 회전 할 수 있습니다. 그것은 항상 풀 수있을 것

[5,3,9] 
[7,1,4] 
[8,6,2] 

:

[1,2,3] 
[4,5,6] 
[7,8,9] 

과 같은에서 시작할 것 : 예를 들면, 맨 윗줄 [1,2,3]는 [3,1,2] 등

이

배열과 같이 끝낼 필요가 될 수 그래서 이것을 검사 할 필요가 없습니다.

나는 '1'을 찾고 왼쪽으로 그 다음 올바른 위치로 이동하는 장시간의 접근법을 시도했다. 2, 3, ...에 대해서도 그렇다. 그러나 영원히 원으로 돌아 간다.

아무런 도움이 필요하지 않겠지 만, 나에게 출발점/참조를 줄 수 있다고해도 ... 나는이 것을 생각할 수 없다.

Answer 1

문제는 한 값을 이동하면 다른 값이 바뀌기 때문입니다. 나는 충분한 이론으로 당신이 정확한 해결책을 찾을 수 있다고 생각하지만 여기에는 일할 기회가 더 많은 경험적 방법이 있습니다.

먼저 행에있는 모든 숫자가 해당 행에 속하면 문제를 풀거나 사소한 값을 교환해야합니다. [2,3,1]은 예를 들어 [3,2,1]이 바뀌는 반면 간단합니다.

그래서 왼쪽 위 1 개를 배치하는 것보다 "쉬운"목표는 모든 행을 그 상태로 가져 오는 것입니다. 우리가 어떻게 할 수 있을까? 열을 살펴 봅시다 ...

열에 각 행에서 하나의 숫자가 포함되어 있으면 위와 비슷한 상태입니다 (숫자가 올바른 행에 있거나 너무 바뀌기 때문에 너무 간단합니다).

그럼, 내가 제안하는 것은입니다 :

for column in columns: 
     if column is not one value from each row: 
      pick a value from column that is from a duplicate row 
      rotate that row 
    for column in columns: 
     as well as possible, shift until each value is in correct row 
    for row in rows: 
     as well as possible, shift until each value is in correct column 

지금, 그이 그것을 가까이하는 경향이 있지만, 작동하지 않을 수 있으며, "거의 바로"계약의 일부 세트를 해결할 수 있습니다.

그래서 루프에 넣고 각 실행마다 상태의 "해시"(예 : 행별로 읽는 값이 들어있는 문자열)를 기록합니다. 그런 다음 각 호출마다 상태가 이미 발생했기 때문에 해시가 이미 있었는지 확인하여 (우리가 스스로를 반복하므로) 일을 혼합하는 "임의의 셔플"을 호출합니다.

그래서 우리는 일단 우리가 가까워지면 일할 수있는 기회를 가지며, 우리가 그 일에 매달려있을 때 휴식을 취할 수있는 생각을 갖고 있습니다.

내가 말했듯이, 나는 이것을 할 수있는 더 똑똑한 방법이 있다고 확신하지만, 필자는 필사적으로 구글에서 아무 것도 찾을 수 없다면 그것은 내가 시도 할만한 발견 적 방법 일 것이다.난 확실하지 않다 위의 권리이지만,보다 일반적인 전술은 다음과 같습니다

• (퍼즐은 "선형"이고, 찾아 의미에서)
• 시도를 매우 가까운 솔루션을 해결할 것을 확인 이

을 반복하고 내가 여기서 말하고 정말로 있다면 그

셔플을 반복.

Answer 2

격자가 3x3이므로 솔루션을 찾을 수있을뿐만 아니라 이 (가)으로 가장 작은 숫자로 문제를 해결할 수 있습니다.

이 목적으로 Breadth First Search을 사용해야합니다.

각 구성을 9 개의 요소로 구성된 선형 배열로 나타냅니다. 이동할 때마다 다른 구성을 갖게됩니다. 배열은 본질적으로 1-9 사이의 수의 순열이므로, 단지 9 일 것입니다! = 362,880 개의 서로 다른 구성이 가능합니다.

각 구성을 노드로 간주하고 각 이동을 에지로 간주하는 경우 O (n)의 전체 그래프를 탐색 할 수 있습니다. 여기서 n은 구성의 수입니다. 우리는 이전에 보았던 구성을 다시 풀지 않으므로 이 어레이를 방문해야합니다.이 배열은 각 구성을 방문한 것으로 표시합니다.

'해결 된'구성에 도달하면 사용자가 보낸 구성을 저장하는 '상위'배열을 사용하여 수행 한 이동을 추적 할 수 있습니다.

또한 4x4 격자 인 경우 n은 (4x4)와 같으므로 문제는 해결하기 어려울 것입니다. = 16! = 2.09227899 × 10^13이다. 그러나 이와 같은 작은 문제의 경우 솔루션을 매우 빨리 찾을 수 있습니다.

편집 :

TL; DR :

• 꽤 빨리 그에서 작동하도록 보장합니다. 362,880은 오늘날의 컴퓨터에서 꽤 작은 숫자입니다.
• 가장 짧은 동작 순서를 찾을 수 있습니다.