Search algorithm with avoiding repeated states

What is the meaning of distinct states here.

The meaning of distinct state is a unique cell, you count each cell in the grid only once.

Crude upper bound to number of distinct states:

First, look at a subgrid of size 2d+1 X 2d+1, and you start from the node at the middle. It is easy to see that there are no cells outside of this subgrid that are reachable (from the center) within d steps. In addition, number of cells in this subgrid is (2d+1)*(2d+1) ~= 4d^2, so we found a simple upper bound which is significantly better than naive 4^d.

But there are many cells which are still unreachable (for example, you cannot get within d steps to (0,0) from the middle (which is index (d,d)), so we can get a tighter bound.

Approach 1: Combinatorics:

If we say we can move only "up and right", the number of reachable cells we can traverse through are sum { CC(i,2) | i=0,1,...,d }. In here, CC stands for stars and bars solution, and defined as:

CC(n,k) = Choose(n+k-1,k-1) = (n+k-1)!/(n!*(k-1)!)

When assigning the formula, we get:

sum{ (i+1)!/(i)!1! | i=1,...,d} = sum { (i+1) | i=1,...,d}

The above is sum of arithmetic progression that sums to (d)(d+1)/2

However, note that by allowing only "up and right" moves, we allowed reaching only to the upper-right quarter of the grid, and we want to allow it for the other quarters as well. From symmetry, for each quarter the number of attainable cells is identical to the above, and in addition - add the origin cell (one we started from) so at total we get:

#reachable_cells(d) = 4* (d)(d+1)/2 = 2d(d+1) + 1 ~= 2d^2

Approach 2 Geometrical:

Have a look on the following example matrix of size 7 X 7:

6 5 4 3 4 5 6
5 4 3 2 3 4 5
4 3 2 1 2 3 4
3 2 1 0 1 2 3
4 3 2 1 2 3 4
5 4 3 2 3 4 5
6 5 4 3 4 5 6

This matrix contains all nodes of distance at most 3 from the center.
If you look carefully, you can see that each distance is actually forming a square around the center, with an edge of length d. (so for d=1, there is a square around 0 with edges of length 1, for d=2, there is a square with edged of length 2, and so on)

In a square, the perimeter is 4a - where a is the length of the edge.
So, the number of unique cells which are reachable from the center with at most d steps, is the number of cells on any such rectangle.

Number of cells on a rectangle with edge length of i is 4i, and we need to sum that up for each possible rectangle where i<d, and we get:

#reachable_cells(d) = sum { 4i | i=1,....,d } = 4 sum{ i | i=1,...,d}

This is sum of arithmetic progression again (and add the origin again), and we get:

#reachable_cells(d) = 4 * d(d+1)/2 + 1 = 2d(d+1) + 1 ~= 2d^2

Examples:

6 5 4 3 4 5 6
5 4 3 2 3 4 5
4 3 2 1 2 3 4
3 2 1 0 1 2 3
2 3 2 1 2 3 4
5 4 3 2 3 4 5
6 5 4 3 4 5 6

In the above, you have 7X7 matrix, it contains all cells of of distance up to 3 from the center, as you can see - the number of reachable states by counting them and see it fits the forumla:

#reachable_cells(0) = 2*0*1 + 1 = 1
#reachable_cells(1) = 2*1*2 + 1 = 5
#reachable_cells(2) = 2*2*3 + 1 = 13
#reachable_cells(3) = 2*3*4 + 1 = 25