如何检查8字谜的一个实例是否可解？-yiteyi-C++库

什么是8字谜？ 给定一块3×3的板，有8块瓷砖（每个瓷砖有一个1到8之间的数字）和一个空白。目标是使用空白空间将数字按顺序放置在瓷砖上。我们可以将四块相邻的瓷砖（左、右、上、下）滑入空白区域

null

8puzzle1

如何确定给定的状态是否可解？ 下面是两个示例，第一个示例可以通过一系列幻灯片达到目标状态。第二个例子不能。

8puzzle

下面是一个简单的规则来检查一个8字谜是否是可解的。 如果输入状态中的倒数是奇数，则不可能解决8个谜题的实例。 在上图给出的例子中，第一个例子有10个反演，因此是可解的。第二个例子有11个倒数，因此不可解。

什么是倒置？ 如果瓷砖上的值与其在目标状态下的外观顺序相反，则一对瓷砖形成反转。例如，下面的8字谜有两个倒数，（8，6）和（8，7）。

   1   2   3   4   _   5   8   6   7

以下是检查8谜题的给定实例是否可解的实现。这个想法很简单，我们在给定的8个谜题中计算倒数。

C++

                         // C++ program to check if a given instance of 8 puzzle is solvable or not                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         // A utility function to count inversions in given array 'arr[]'                       
                         int                                     getInvCount(                                     int                                     arr[])                       
                         {                       
                                                 int                                     inv_count = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < 9 - 1; i++)                       
                                                 for                                     (                                     int                                     j = i+1; j < 9; j++)                       
                                                 // Value 0 is used for empty space                       
                                                 if                                     (arr[j] && arr[i] &&  arr[i] > arr[j])                       
                                                 inv_count++;                       
                                                 return                                     inv_count;                       
                         }                       
           
                         // This function returns true if given 8 puzzle is solvable.                       
                         bool                                     isSolvable(                                     int                                     puzzle[3][3])                       
                         {                       
                                                 // Count inversions in given 8 puzzle                       
                                                 int                                     invCount = getInvCount((                                     int                                     *)puzzle);                       
           
                                                 // return true if inversion count is even.                       
                                                 return                                     (invCount%2 == 0);                       
                         }                       
           
                         /* Driver program to test above functions */                       
                         int                                     main(                                     int                                     argv,                                     int                                     ** args)                       
                         {                       
                                                 int                                     puzzle[3][3] =  {{1, 8, 2},                       
                                                 {0, 4, 3},                                     // Value 0 is used for empty space                       
                                                 {7, 6, 5}};                       
                                                 isSolvable(puzzle)? cout <<                                     "Solvable"                                     :                       
                                                 cout <<                                     "Not Solvable"                                     ;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to check if a given                       
                         // instance of 8 puzzle is solvable or not                       
                         class                                     GFG                       
                         {                       
                                   
                         // A utility function to count                       
                         // inversions in given array 'arr[]'                       
                         static                                     int                                     getInvCount(                                     int                                     [][] arr)                       
                         {                       
                                                 int                                     inv_count =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i <                                     3                                     -                                     1                                     ; i++)                       
                                                 for                                     (                                     int                                     j = i +                                     1                                     ; j <                                     3                                     ; j++)                       
                                   
                                                 // Value 0 is used for empty space                       
                                                 if                                     (arr[j][i] >                                     0                                     &&                       
                                                 arr[j][i] > arr[i][j])                       
                                                 inv_count++;                       
                                                 return                                     inv_count;                       
                         }                       
           
                         // This function returns true                       
                         // if given 8 puzzle is solvable.                       
                         static                                     boolean                                     isSolvable(                                     int                                     [][] puzzle)                       
                         {                       
                                                 // Count inversions in given 8 puzzle                       
                                                 int                                     invCount = getInvCount(puzzle);                       
           
                                                 // return true if inversion count is even.                       
                                                 return                                     (invCount %                                     2                                     ==                                     0                                     );                       
                         }                       
           
                         /* Driver code */                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     [][] puzzle = {{                                     1                                     ,                                     8                                     ,                                     2                                     },{                                     0                                     ,                                     4                                     ,                                     3                                     },{                                     7                                     ,                                     6                                     ,                                     5                                     }};                       
                                                 if                                     (isSolvable(puzzle))                       
                                                 System.out.println(                                     "Solvable"                                     );                       
                                                 else                       
                                                 System.out.println(                                     "Not Solvable"                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed by chandan_jnu                       

Python3

                         # Python3 program to check if a given                       
                         # instance of 8 puzzle is solvable or not                       
           
                         # A utility function to count                       
                         # inversions in given array 'arr[]'                       
                         def                                     getInvCount(arr):                       
                                                 inv_count                                     =                                     0                       
                                                 empty_value                                     =                                     -                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,                                     9                                     ):                       
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     ,                                     9                                     ):                       
                                                 if                                     arr[j] !                                     =                                     empty_value                                     and                                     arr[i] !                                     =                                     empty_value                                     and                                     arr[i] > arr[j]:                       
                                                 inv_count                                     +                                     =                                     1                       
                                                 return                                     inv_count                       
           
                                   
                         # This function returns true                       
                         # if given 8 puzzle is solvable.                       
                         def                                     isSolvable(puzzle) :                       
           
                                                 # Count inversions in given 8 puzzle                       
                                                 inv_count                                     =                                     getInvCount([j                                     for                                     sub                                     in                                     puzzle                                     for                                     j                                     in                                     sub])                       
           
                                                 # return true if inversion count is even.                       
                                                 return                                     (inv_count                                     %                                     2                                     =                                     =                                     0                                     )                       
                                   
                                                 # Driver code                       
                         puzzle                                     =                                     [[                                     8                                     ,                                     1                                     ,                                     2                                     ],[                                     -                                     1                                     ,                                     4                                     ,                                     3                                     ],[                                     7                                     ,                                     6                                     ,                                     5                                     ]]                       
                         if                                     (isSolvable(puzzle)) :                       
                                                 print                                     (                                     "Solvable"                                     )                       
                         else                                     :                       
                                                 print                                     (                                     "Not Solvable"                                     )                       
                                   
                                                 # This code is contributed by vitorhugooli                       
                                                 # Fala meu povo desse Brasil varonil :winking_face:                       

C#

                         // C# program to check if a given                       
                         // instance of 8 puzzle is solvable or not                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // A utility function to count                       
                         // inversions in given array 'arr[]'                       
                         static                                     int                                     getInvCount(                                     int                                     [,] arr)                       
                         {                       
                                                 int                                     inv_count = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < 3 - 1; i++)                       
                                                 for                                     (                                     int                                     j = i + 1; j < 3; j++)                       
                                   
                                                 // Value 0 is used for empty space                       
                                                 if                                     (arr[j, i] > 0 && arr[j, i] > arr[i, j])                       
                                                 inv_count++;                       
                                                 return                                     inv_count;                       
                         }                       
           
                         // This function returns true                       
                         // if given 8 puzzle is solvable.                       
                         static                                     bool                                     isSolvable(                                     int                                     [,] puzzle)                       
                         {                       
                                                 // Count inversions in given 8 puzzle                       
                                                 int                                     invCount = getInvCount(puzzle);                       
           
                                                 // return true if inversion count is even.                       
                                                 return                                     (invCount % 2 == 0);                       
                         }                       
           
                         /* Driver code */                       
                         static                                     void                                     Main()                       
                         {                       
                                                 int                                     [,] puzzle =                                     new                                     int                                     [3,3]{{1, 8, 2},                       
                                                 {0, 4, 3},                                     // Value 0 is used for empty space                       
                                                 {7, 6, 5}};                       
                                                 if                                     (isSolvable(puzzle))                       
                                                 Console.WriteLine(                                     "Solvable"                                     );                       
                                                 else                       
                                                 Console.WriteLine(                                     "Not Solvable"                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed by chandan_jnu                       

PHP

                         <?php                       
                         // PHP program to check if                       
                         // a given instance of 8                       
                         // puzzle is solvable or not                       
           
                         // A utility function to                       
                         // count inversions in                       
                         // given array 'arr[]'                       
                         function                                     getInvCount(                                     $arr                                     )                       
                         {                       
                                                 $inv_count                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     < 9 - 1;                                     $i                                     ++)                       
                                                 for                                     (                                     $j                                     =                                     $i                                     + 1;                                     $j                                     < 9;                                     $j                                     ++)                       
                                                 $inv_count                                     ++;                       
                                                 return                                     $inv_count                                     ;                       
                         }                       
           
                         // This function returns true                       
                         // if given 8 puzzle is solvable.                       
                         function                                     isSolvable(                                     $puzzle                                     )                       
                         {                       
                                                 // Count inversions in                       
                                                 // given 8 puzzle                       
                                                 $invCount                                     = getInvCount(                                     $puzzle                                     );                       
           
                                                 // return true if                       
                                                 // inversion count is even.                       
                                                 return                                     (                                     $invCount                                     % 2 == 0);                       
                         }                       
           
                         // Driver Code                       
                         $puzzle                                     =                                     array                                     (                                     array                                     (1, 8, 2),                       
                                                 array                                     (0, 4, 3),                                     // Value 0 is used                       
                                                 array                                     (7, 6, 5));                                     // for empty space                       
                                   
                         if                                     (isSolvable(                                     $puzzle                                     ) == true)                       
                                                 echo                                     "Solvable"                                     ;                       
                                                 else                       
                                                 echo                                     "Not Solvable"                                     ;                       
                                   
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to check if a given                       
                         // instance of 8 puzzle is solvable or not                       
           
                         // A utility function to count inversions                       
                         // in given array 'arr[]'                       
                         function                                     getInvCount(arr)                       
                         {                       
                                                 let inv_count = 0 ;                       
                                                 for                                     (let i=0;i<2;i++){                       
                                                 for                                     (let j=i+1;j<3;j++){                       
                                   
                                                 // Value 0 is used for empty space                       
                                                 if                                     (arr[j][i] > 0 && arr[j][i] > arr[i][j])                       
                                                 inv_count += 1;                       
                                                 }                       
                                                 }                       
                                                 return                                     inv_count;                       
                         }                       
                         // This function returns true                       
                         // if given 8 puzzle is solvable.                       
                         function                                     isSolvable(puzzle)                       
                         {                       
                                                 // Count inversions in given 8 puzzle                       
                                                 let invCount = getInvCount(puzzle);                       
                                                 // return true if inversion count is even.                       
                                                 return                                     (invCount % 2 == 0);                       
                         }                       
           
                         // Driver code                       
           
                         // Value 0 is used for empty space                       
                         puzzle = [[1, 8, 2],[0, 4, 3],[7, 6, 5]] ;                       
                         if                                     (isSolvable(puzzle))                       
                                                 document.write(                                     "Solvable"                                     );                       
                         else                       
                                                 document.write(                                     "Not Solvable"                                     );                       
                                   
                         </script>                       

输出：

Solvable

时间复杂度：O（1）

辅助空间：O（1）

注意，上面的实现使用简单的算法进行反转计数。这样做是为了简单。可以使用基于合并排序的倒排计数算法 .

这是怎么回事？ 这个想法是基于这样一个事实：在一组移动之后，反转的奇偶性保持不变，即，如果反转计数在初始阶段是奇数，那么在任何移动序列之后它仍然是奇数，如果反转计数是偶数，那么在任何移动序列之后它仍然是偶数。在目标状态下，有0个反转。所以我们只能从一个倒数为偶数的状态到达目标状态。反转计数的奇偶性是如何不变的？当我们滑动瓦片时，我们要么行移动（向左移动或向右移动瓦片进入空白空间），要么使列移动（向上移动或向下移动到空白空间）。

（a） 行移动不会更改反转计数。参见下面的例子

   1   2   3    Row Move     1   2   3   4   _   5   ---------->   _   4   5    8   6   7                 8   6   7  Inversion count remains 2 after the move   1   2   3    Row Move     1   2   3   4   _   5   ---------->   4   5   _   8   6   7                 8   6   7  Inversion count remains 2 after the move

b）列移动执行以下三种操作之一。 …..（i）将反转计数增加2。参见下面的例子。

         1   2   3   Column Move     1   _   3         4   _   5   ----------->    4   2   5           8   6   7                   8   6   7      Inversion count increases by 2 (changes from 2 to 4)

…..（ii）将反转计数减少2

         1   3   4    Column Move     1   3   4         5   _   6   ------------>    5   2   6         7   2   8                    7   _   8      Inversion count decreases by 2 (changes from 5  to 3)

…..（iii）保持反转计数不变。

         1   2   3    Column Move     1   2   3         4   _   5   ------------>    4   6   5         7   6   8                    7   _   8        Inversion count remains 1 after the move

因此，如果移动将反转计数增加/减少2，或者使反转计数保持不变，则不可能通过任何行/列移动序列来更改状态的奇偶校验。

练习： 如何检查15个谜题的给定实例是否可解。在15个拼图中，我们有4×4的板，其中15个瓷砖有一个数字和一个空白。请注意，上述简单的反转计数规则并不直接适用于15个谜题，需要对15个谜题的规则进行修改。

相关文章： 如何检查15个谜题的一个实例是否可解？本文由伊山撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章