algorithm - 无法解决代码厨师难题？

Question

我正在尝试解决 this显然是初学者级别的问题。但甚至无法想出蛮力方法。

这里是问题陈述:

Johnny has some difficulty memorizing the small prime numbers. So, his computer science teacher has asked him to play with the following puzzle game frequently.

The puzzle is a 3x3 board consisting of numbers from 1 to 9. The objective of the puzzle is to swap the tiles until the following final state is reached:

1 2 3
4 5 6
7 8 9

At each step, Johnny may swap two adjacent tiles if their sum is a prime number. Two tiles are considered adjacent if they have a common edge.

Help Johnny to find the shortest number of steps needed to reach the goal state.

Input

The first line contains t, the number of test cases (about 50). Then t test cases follow. Each test case consists of a 3x3 table describing a puzzle which Johnny would like to solve.

The input data for successive test cases is separated by a blank line.

Output

For each test case print a single line containing the shortest number of steps needed to solve the corresponding puzzle. If there is no way to reach the final state, print the number -1.

Example

Input:

2
7 3 2 
4 1 5 
6 8 9 

9 8 5 
2 4 1 
3 7 6  

Output:

6
-1

Answer 1

这是 Python 的开始，用于查找从一开始就可以到达的所有板的距离。

start = '123456789'
needed_moves = {start: 0}
work_queue = [start]
while (len(work_queue)):
    board = work_queue.pop(0)
    for next_board in next_move(board):
        if next_board not in needed_moves:
            needed_moves[next_board] = needed_moves[board] + 1
            work_queue.append(next_board)

这是广度优先搜索的标准模式。只需为测试用例提供一个 next_move 函数和一些胶水就可以了。

对于深度优先搜索，只需将队列切换为堆栈。这实际上意味着 work_stack.pop() 弹出最后一个元素而不是 work_queue.pop(0) 获取第一个元素。