6 * 6 퍼즐 알고리즘

Question

나는 임의의 순서로 35 개의 숫자 (1 ~ 35)를 가진 6 * 6 퍼즐을 가지고 있습니다. 빈칸을 '등록'으로 사용하고 순서대로 번호를 하나씩 옮깁니다. 3 * 3 퍼즐을 처리 할 수는 있지만 어떻게 6 * 6을 처리 할 수 ​​있습니까? 힌트를 좀 주시겠습니까?

Answer 1

아이디어는 동일하는 상태 graph으로 문제를 나타내며, shortest path 알고리즘를 실행합니다.

알고리즘의 효율성이 중요한 경우에는 admissible heuristic function과 함께 꽤 빠를 것으로 예상되는 정보 알고리즘 (예 : A* algorithm)이 필요할 수 있습니다.
더 간단하지만 더 느리지 만 BFS을 실행할 수 있습니다.

두 알고리즘 (A *, BFS)은 둘 완전한 및 최적의이 (최단 경로를 찾아) (있는 경우 항상하는 solutuion를 발견).

또한 매크로를 사용하면 알고리즘을보다 빠르게 얻기 위해 "좋은"일련의 동작을 알 수 있습니다. 작업 속도가 느리지 만 구현할 때까지는이 개선점을 무시하십시오.

---

편집 : 코딩 가이드 라인 : 그래프 등의 문제에서
봐 :이 그래프와 그래프는 이제 G=(V,E) 곳 V = { all possible states} 및

E = { (u,v) | can move from state u to state v within a single step } 될 것이다, - 있습니다 (시작 위치를 소스, 입력으로 제공됨) 및 대상 (정렬 된 퍼즐). 소스에서 목적지까지의 경로를 찾으려면 BFS 또는 A * (첨부 된 위키피디아 링크에서 가상 코드를보십시오)를 시작하십시오. BFS로 시작해야합니다 - 더 간단합니다.
최단 경로 알고리즘에 의해 반환 된 경로는 시작 보드에서 대상으로 이동하기 위해 수행해야하는 일련의 이동과 동일합니다.

참고 : 실제 그래프를 만들 필요가 없습니다. 시작 노드 (소스)를 잡고 꼭지점을 만들고 successors:V->2^V 함수가 있어야 각 꼭지점의 승계 자 (공식적으로 successors(v) = { (v,u) | (v,u) is in E })를 얻을 수 있습니다. 이렇게하면 그래프의 관련 부분을 즉시 작성할 수 있습니다.

Answer 2

이 게임의 간단한 전략은 맨 위 줄에 올바른 숫자를 넣는 것입니다 (다른 숫자는 신경 쓰지 않기 때문에 쉽습니다. 마지막 두 숫자는 올바른 위치에 넣기가 조금 더 어렵습니다. 이 두 가지를 같은 동작에 배치해야합니다.) 그런 다음 맨 위 행을 고정하고 왼쪽 열을 계속 한 다음 맨 위 행을 누른 다음 왼쪽 열을 계속 입력하십시오.

최적의 전략은 아니지만 작동하고 코드 작성이 간단합니다.

Answer 3

저는 대학 때와 똑같은 문제/퍼즐과 인공 지능과 휴리스틱 기술 및 그래프 이론이 포함 된 매우 흥미로운 문제를 연구했습니다. amit으로 명시된 바와 같이 A *, BFS 및 휴리스틱을 확인하는 것이 좋습니다.

여기 내 공헌입니다.이 문제를 해결할 때 나누기를 시도하여 전략을 정복하십시오.이 6x6 그리드는 서로 가깝게 연결된 네 개의 3x3 그리드라고 생각할 수 있으며 주어진 순서대로 각 경우를 분리 된 케이스로 풀려고합니다. (즉,이 작업 공간으로 사용됩니다)를 제외한, 왼쪽 상단 그리드는 조각을 모두 포함하는 방식으로 각 부분을 배열

1. ;

   예를 들어, 다음과 같은 알고리즘을 시도 할 수 있습니다

2. 왼쪽 위 격자를 해결하십시오.
3. 오른쪽 상단 그리드가 병목 오른쪽의 것을 제외한 모든 부분을 포함하는 방식으로 정렬합니다 (작업 공간으로 사용됨).
4. 오른쪽 위 격자를 해결하십시오.
5. ... 그리드 수와 독립적으로!

말을 마지막 문제는 당신해야 당신이 오른쪽 상단 그리드의 오른쪽 상단이 당신의 작업 공간 '이 될 수 있도록 할 수 없기 때문에 공간 작업으로 왼쪽 거하는 코너에 에주의 미래에 작품을 놓을 수 없으므로 "조각 부족"

Ps1 : 작업 공간은 일시적으로 조각을 놓칠 수있는 위치이며, 조각을 움직일 수있는 여유 공간을 가질 수 있습니다.

Ps2 :이 컨텍스트에서 그리드는 NxN 조각의 조합으로 모든 올바른 조각을 가져야하며 반드시 순서대로 정렬해야하는 것은 아닙니다.

나는 어떤면에서 도움이 되었길 바랍니다. :-)

Answer 4

우리는 전체 6 * 6 행렬을 순회 할 것이라고 생각합니다. 한 번에 하나의 작은 숫자 만 찾아서 다음 행렬로 옮깁니다. 이는 관련 솔루션이 아닙니다. 이 문제를 해결하는 가장 좋은 방법은 주어진 매트릭스에서 이진 검색을 사용하는 것입니다. 우리는 이진 검색을 적용하면 시간이 많이 걸릴 것입니다.이 문제를 해결하는 더 좋은 방법은 무엇입니까

Answer 5

위 해결했습니다 퍼즐 삽입 알고리즘을 사용하여 퍼즐. 위의 퍼즐을 해결하는 데 2 ​​일이 걸렸습니다. 그냥 .Net 코드를 실행하면 아무것도 묻지 않고 나에게 메시지를 남기면됩니다. 위의 문제를 해결하기 위해 C# inbuilt 클래스를 사용하지 않았습니다. 코드가 포함 된 순수한 c 로직 코드 솔루션

private static void MazePuzzle() 
     { 
      /**** 
     * A typical C Problem for Maze puzzle has been solved by prince.It took almost 3 days. 
     * Problem is about Sorting a 2D Matrix with any number of row and column 
     * This problem is also known as Rat Maze puzzle 
     * It is also be a typical Backtracking Problem 
     * ***/ 
      const int _row = 6; 
      const int _coloumn = 6; 
      //int _column1 = _coloumn; 

      int[,] _doubleArray = new int[_row, _coloumn] { { 19, 2, 4, 34, 23, 41 }, { 11, 63, 3, 93, 65, 98 }, { 12, 80, 15, 76, 71, 90 }, { 119, 32, 94, 84, 23, 41 }, { 129, 232, 124, 341, 253, 411 }, { 197, 289, 47, 343, 293, 401 } }; 
      int [] _StoringArray1D=new int[_row*_coloumn]; 
      int i = 0; 
      int j = 0; 
      int _comparingArrayElement = 0; 
      int _swipeTemp = 0; 


      for (; i < _row; i++) 
      { 
       int _trackrow = 0; 
       for (;j <_coloumn; j++) 
       { 
        _trackrow = 0; 
        if(i==0 && j==0) 
        { 
          _comparingArrayElement= _doubleArray[i, j + 1]; 
         if(_comparingArrayElement<_doubleArray[i,j]) 
         { 
          _swipeTemp = _doubleArray[i,j+1]; 
          _doubleArray[i, j + 1] = _doubleArray[i, j]; 
          _doubleArray[i, j] = _swipeTemp; 

         }//innerMost if 
        }//For First time 
         else 
         { 
          int k = 0; 
          do 
          { 
           if (_trackrow == i || _trackrow < i) 
           { 
            for (; k < _coloumn; k++) 
            { 
             if(k==j && i==_trackrow) 
             { 
              break; 
             } 
             else 
             { 
             if(_doubleArray[_trackrow,k]>_doubleArray[i,j]) 
             { 
              int _swipetempPrevious=_doubleArray[_trackrow,k]; 
              _doubleArray[_trackrow,k]=_doubleArray[i,j]; 
              _doubleArray[i, j] = _swipetempPrevious; 
             } 
             else 
             { 
              //do nothing just traverse 
             }//swipe else 
             }//k==j else 
            }//inner for do while 
            _trackrow++; 
            k = 0; 
           }//trackrow if 
           else 
           { 
            break; 
           }//trackrow else 
          } while (true); 
         }//else 
       }//innner for 
       j = 0; 
      }//outer for 
      Console.WriteLine("End of Program"); 
     }//Maze Puzzle Method