There are only 7280 different positions, you could easily make an index of all of them. Then you could build a solution tree, start from the legal solutions, work out all possible previous positions, put the move required in the index, then from these positions work out the previous positions, register the move in the index etc. It is important that when a position already has a registered move you do not overwrite it but instead just drop that branch.
This way your index will contain the optimal move for every possible position.
Assuming that there is plenty space you could solve the "puzzle" by choosing a solution where there is at least a double wide edge of 0's on the bottom and right side of the figure, then you can systematically build it starting from the upper left corner and working you way towards the bottom right.