algorithm - 按照一些规则查找 3x3 矩阵中的所有组合

Question

给定一个 3x3 矩阵:

|1 2 3|  
|4 5 6|  
|7 8 9|  

我想通过按照以下规则连接此矩阵中的数字来计算所有组合:

• 组合宽度在3到9之间
• 一个号码只用一次
• 只能连接相邻的数字

一些示例:123、258、2589、123654 等
例如 1238 不是一个好的组合，因为 3 和 8 不相邻。 123和321的组合是不一样的。
我希望我的描述是清楚的。
如果有人有任何想法，请告诉我。其实我不知道如何开始 :D。谢谢

Answer 1

这是一个搜索问题。您可以使用直接的深度优先搜索和递归编程来快速解决问题。类似于以下内容:

func search(matrix[N][M], x, y, digitsUsed[10], combination[L]) {
    if length(combination) between 3 and 9 {
       add this combination into your solution
    }

    // four adjacent directions to be attempted
    dx = {1,0,0,-1}
    dy = {0,1,-1,0}
    for i = 0; i < 4; i++ {
       next_x = x + dx[i]
       next_y = y + dy[i]
       if in_matrix(next_x, next_y) and not digitsUsed[matrix[next_x][next_y]] {
           digitsUsed[matrix[next_x][next_y]] = true
           combination += matrix[next_x][next_y]
           search(matrix, next_x, next_y, digitsUsed, combination)

           // At this time, sub-search starts with (next_x, next_y) has been completed.
           digitsUsed[matrix[next_x][next_y]] = false
       }
   }
}

因此您可以为矩阵中的每个网格运行搜索功能，并且您的解决方案中的每个组合都彼此不同，因为它们从不同的网格开始。

此外，我们不需要记录矩阵中一个格子是否被遍历的状态，因为每个数字只能使用一次，所以已经遍历的格子将永远不会被再次遍历。数字已包含在组合中。