Python 找出2维下自回避随机行走的所有结果

对于自回避随机行走的问题，可以使用回溯法解决。具体实现方法如下：

1. 定义一个二维数组来表示横纵坐标的位置，初始值为0；

2. 定义一个步长的数组，包含每个方向上的步长值，如{(1,0),(-1,0),(0,1),(0,-1)}表示向右、向左、向上、向下移动的步长；

3. 定义一个函数check_next(x, y)，用来检查当前位置能否进行下一步的移动，即判断当前位置是否在数组范围内且没有被访问过；

4. 定义一个函数backtracking(x, y, n)，用来进行回溯搜索，n表示当前已经走过的步数，当走过全部的n*n个格子时，返回True表示搜索成功；

5. 在backtracking函数中，首先检查当前位置(x, y)是否已经在之前遍历过，如果是则返回False；否则将当前位置标记为已访问。

6. 然后依次检查每个方向的位置，如果可以移动到该位置，则进行递归搜索，直到所有的位置都搜索过，并且搜索到了最后一个位置。如果搜索成功，则返回True，否则将当前位置标记为未访问，返回False。

7. 最后，可以调用backtracking函数来获取所有可能的结果。

代码示例如下：

visited = []
for i in range(n):
    visited.append([0] * n)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def check_next(x, y):
    if x < 0 or y < 0 or x >= n or y >= n or visited[x][y] == 1:
        return False
    return True

def backtracking(x, y, k):
    if k == n*n:
        return True
    if visited[x][y] == 1:
        return False
    visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if check_next(nx, ny):
            if backtracking(nx, ny, k+1):
                print('(%d,%d)' % (x, y), end=' ')
                return True
    visited[x][y] = 0
    return False

for i in range(n):
    for j in range(n):
        if backtracking(i, j, 1):
            print('(%d,%d)' % (i, j))

这段代码可以输出所有自回避随机行走的结果。注意，该算法的时间复杂度为O(4^n)，在n较大时可能会超时。