I a have project which consists on a group of numbers by increasing or decreasing one of their values. Imagine the following 3x2 grid:

1 1 1
2 2 2

We can only increase or decrease the value of any number by 2, which will increase/decrease adjacent (top, down, left and right) numbers by 1. For example, if we increase the value of the first number, the result would be:

3 2 1
3 2 2

The goal of this is to find the way to make all numbers equal in value in the fewest steps. To analyze all possible combinations of "moves", an algorithm has been created which goes through all the possible combinations from the lowest value (i.e. 0) to the highest. In this case, seven (7) is the highest value. The algorithm stops the moment it finds the solution.

However, this results in the program wastefuly analizing steps that it has already been through, for example, increasing its value and then decreasing it again, since both increasing and decreasing are steps which can be repeated as often as necessary. The pseudocode below takes 18,853,802 steps on a max depth of 7 values per cell to find the solution. Moreover, there are cells which can be empty, and thus generate more useless steps, since there would be nothing to read from them. For example:

1 X 1
2 3 4

How could it be done so that the algorithm skips the steps which would cause a state that has already been tried? The requirements are that it can also return the steps it used to find the answer, with any grid size.

The algorithm's pseudocode is the following:

function solve : x, y, direction, depth, currentSolution

//CurrentSolution is a copy
currentSolution.addTurn x, y, direction

//If move is not possible, return, all following turns are not necessary
if doTurn x, y, direction == false:
    return

depth++;

if maxDepth > MAX_DEPTH:
    return

if isSolved == true:
    solution.add(currentSolution)

foreach cell in gridCells:

    //If the previous turn was the same, just reversed, don't do anything
    if x != newX && y != newY && direction != Direction.DECREASE:
        //Do nothing
    else:
        solve newX, newY, Direction.INCREASE, depth

    if x != newX && y != newY && direction != Direction.INCREASE:
        //Do nothing
    else:
        solve newX, newY, Direction.DECREASE, depth

One optimization is to look at this problem as a shortest path problem in a graph.

The graph G=(V,E) is a states graph, where a vertex is a possible state: V = {all possible matrices}, and an edge is a possible move from one state to the other using a single operation: E= { (u,v) | can change matrix u to v in one op}.

Now, you can use a shortest path algorithm on an unweighted graph. BFS is one possible solution, which is very similar to your approach - but thanks to the visited set BFS maintains, it is guaranteed you don't revisit the same state twice.

Another approach is using A* Search Algorithm, with some heuristic function.

Please Note: The graph is symbolic, you don't actually need to calculate it before you start. You can just have a next(v) function, that returns a set of "next" vertices - that can be reached from v in a single step, and then use this next() function to mimic edges, and create only the part of your graph you need, on the fly.