What is the minimum number of lego pieces required to complete a NxN maze and also what is total nummber of corresponding configurations? There should be only one path between any two empty cells and any empty cell should be reachable from any other empty cell.
(in all of the following examples "x" denote lego position and "0" denote empty cell)
For example for N=2, minmum number of lego required is one
0 0
0 x

or
0 0
x 0

or
0 x
0 0

or
x 0
0 0

So for N=2, answer is  minimum of 1 lego and 4 configurations.
For N=3, some of the configurations are
0 0 0
0 x 0
0 0 x

or
0 0 0
0 x x
0 0 0

or
0 0 0
x 0 x
0 0 0

there are 7 more of such configurations in total(note the reflections and rotations of above 3 can generate the remaining 7 configurations).
So for N=3 answer is  minimum of 2 legos and 10 configurations.
What is the answer of N=13?
My initial thought was to find if there is any pattern in the series, the series for configurations generated for N=1 to 5 are 0,4,10,32,22 but searching OEIS didn't give me anything useful, on the other hand the series for minimum 0,1,2,4,6 is too common.
Edit - This is a computer science problem. The problem setter don't expect a $O(1)$ formula. An algorithmic approach better or equal to $O(N^6)$ time should suffice.
 A: I do not have an answer for all $N$, but I do have a provably optimal answer whenever $N$ is one more than a power of two, and some upper and lower bounds which are rather close.
Consider the graph whose vertices are the cells, where two cells are joined by an edge if they are orthogonally adjacent. Filling a cell with a Lego block removes one vertex, and removes all edges incident to that vertex. The goal is to remove enough vertices and edges so the graph that remains is a tree. Initially, the number of vertices and edges is given by
$$
|V|=N^2,\qquad |E|=2N(N-1),
$$
so initially the difference between $|E|$ and $|V|$ is $N^2-2N$. Furthermore, placing each block will decrease $|V|$ by exactly one, and decrease $|E|$ by at most $4$, so it will decrease $|E|-|V|$ by at most $3$. In order for a graph to be a tree, the difference $|E|-|V|$ must be exactly $-1$. Therefore, the number of blocks must be at least
$$
\frac{N^2-2N-(-1)}{3}=\frac{(N-1)^2}{3}
$$
In order to attain this, every block placed would have to decrease $|E|-|V|$ by $3$, meaning every block would need to be in the interior of the grid and not adjacent to any other blocks. However, there must always be at least one block on the exterior, else there would be a cycle around the perimeter. Therefore, we have shown that
$$
\text{# blocks}\ge \left\lceil \frac{(N-1)^2+1}{3}\right \rceil
$$
Furthermore, whenever $N$ is one more than a power of two, say $N=2^k+1$ for some $k\in \mathbb N$, then you can succeed using exactly $\left\lceil \frac{(N-1)^2+1}{3}\right \rceil$ blocks, using this strategy. Number the rows and columns from $1$ to $N$. A square at row $r$ and column $c$ will be filled as long as

*

*$2\le r\le N-1$,


*$2\le c\le N-1$, and


*The largest power of $2$ dividing $r-1$ equals the largest power of two dividing $c-1$.
This accounts for all but one of the blocks. You then need to place one additional block on the border, say at $(r,c)=(1,2)$. Here is an illustration of this construction when $N=17=2^4+1$.
. X . . . . . . . . . . . . . . .
. X . X . X . X . X . X . X . X .
. . X . . . X . . . X . . . X . .
. X . X . X . X . X . X . X . X .
. . . . X . . . . . . . X . . . .
. X . X . X . X . X . X . X . X .
. . X . . . X . . . X . . . X . .
. X . X . X . X . X . X . X . X .
. . . . . . . . X . . . . . . . .
. X . X . X . X . X . X . X . X .
. . X . . . X . . . X . . . X . .
. X . X . X . X . X . X . X . X .
. . . . X . . . . . . . X . . . .
. X . X . X . X . X . X . X . X .
. . X . . . X . . . X . . . X . .
. X . X . X . X . X . X . X . X .
. . . . . . . . . . . . . . . . .

Finally, we can show that
$$
\text{# blocks}\le \lfloor N^3/3\rfloor
$$
by generalizing the construction below. Namely, you take diagonal stripes of blocks regularly spaced at intervals of three, and then move some blocks around so that the regions between the stripes can access each other. Illustration when $N = 10$:
. . . . . . . . . .
X . X X . X X . X X
. . X . . X . . X .
. X . . X . . X . .
X . . X . . X . . X
. . X . . X . . X .
. X . . X . . X . .
X . . X . . X . . X
X . X X . X X . X .
. . . . . . . . . .

