I found a problem, but I think my solution is too slow. Please give me some advice or tutorials. QwQ

Here's the description of the problem：

You have a $$$3 \times 3$$$ grid, each cell containing a letter. You can swap two adjacent letters (up, down, left, or right). The question is, how many swaps are needed so that no two identical letters are adjacent in the grid? If it is impossible to achieve, return $$$-1$$$. A test case may contain multiple grid.

Sample input:

[["abc", "def", "ghi"], ["aaa", "aaa", "aaa"], ["abb", "aba", "efg"]]

Sample output:

[0, -1, 1]

I think it can be solved by memorizing the search, but the program needs to run for $$$9^7$$$ (except for the case where all letters are different and the case where there are two identical letters from $$$9^9$$$).

Thank you.