Depth-First Search for Matrix Outcomes

grid = [[0, 1, 0],
        [1, 0, 1],
        [1, 0, 0]]


def new_grid(grid):
    new_grid = []
    for line in grid:
        new_grid.append(list(line))
    return new_grid


reverse_dct = {0: 1, 1: 0}

possible_grid = [[new_grid(grid), ""]]
possible_move = {"x1": [[0,0], [0, 1], [0,2]], "x2": [[1,0], [1, 1], [1,2]], "x3": [[2,0], [2, 1], [2,2]], "x4": [[0,0], [1, 0], [2, 0]], "x5": [[0,1], [1, 1], [2, 1]], "x6": [[0, 2], [1, 2], [2, 2]]}


def print_grid(grid):
    for line in grid:
        print(line)
    print()


def transform(grid, move):
    # print(move)
    temp_grid = new_grid(grid)
    global possible_move, reverse_dct
    for x, y in possible_move[move]:
        temp_grid[x][y] = reverse_dct[temp_grid[x][y]]
    # print_grid(temp_grid)
    return new_grid(temp_grid)


print_grid(grid)
index = 0
while index < len(possible_grid):
    # print(len(possible_grid))
    current_grid = new_grid(possible_grid[index][0])
    for i in range(1, 7):
        # print("current")
        # print_grid(current_grid)
        _new_grid = new_grid(transform(new_grid(current_grid), "x" + str(i)))
        # print_grid(_new_grid)
        repeated = False
        for j in range(len(possible_grid)):
            if _new_grid == possible_grid[j][0]:
                # print("this grid")
                # print_grid(_new_grid)
                # print("Got repeated")
                # print_grid(possible_grid[i][0])
                repeated = True
                break
        if not repeated:
            # print("Found new grid")
            possible_grid.append([new_grid(_new_grid), possible_grid[index][1] + "->x" + str(i)])
            # print(len(possible_grid))
    index += 1

for item in possible_grid:
    print(item[1])
    print_grid(item[0])
print("Done computing")
print(len(possible_grid))
while True:
    command = input()
    if command == "exit":
        break
    arr = list(map(int, command.split()))
    input_grid = [[arr[0], arr[1], arr[2]], [arr[3], arr[4], arr[5]], [arr[6], arr[7], arr[8]]]
    for i in range(len(possible_grid)):
        if input_grid == possible_grid[i][0]:
            print(possible_grid[i][1])