Let’s look at the problem from the opposite side. Suppose we already have a valid test maze. What then?
Well, the maze must have a solution. Let’s take one fixed solution that is as short as possible.
Now imagine that we turn all cells that are not visited by this particular solution into walls. What do we get? It’s easy to realize that we will still have a valid test maze. This is because the original solution still solves the maze – the cells we jumped over in each step were already all walls, and the solution we kept does contain all directions.
This observation should give you a clue how to look for the smallest valid maze: instead of examining all mazes, you can just look for a single path in the above sense.
There were multiple ways that could get you from here to the solution. For example, you could make the educated guess that the optimal path will contain each direction exactly once. This makes it really easy to take a fixed size maze, try all such paths, and for each of them run a simple BFS to verify that there are no unwanted shorter solutions. This approach does indeed produce the optimal solutions to both subproblems.
Obviously, when working on this problem we had to be a bit more careful and actually verify that for smaller mazes there are no other solutions either. Still, with the above observation the code is almost the same. In the attached brute-force solution we do two things differently:
Remember that if there is any valid maze for the given dimensions, there has to be a valid maze where the shortest solution visits all empty cells. And we can make this condition even more strict: out of all such mazes we are looking for the one where the number of empty cells (equivalently, the number of jumps in the solution) is as small as possible.
Thus, we only need to generate solutions that cannot be shortened. This means that as soon as the solution leaves a row/column/diagonal in J2, it cannot re-enter that line later – doing so would create a shortcut. Additionally, making multiple consecutive jumps in the same direction makes no sense either, as you can shorten the solution by merging them into one jump.
Hence, in our program, as soon as we enter a cell C1, we try all possibilities for the next cell C2, but before we recursively continue from C2 we mark all other cells directly reachable from C1 as banned. This makes the program fast enough to eliminate all smaller board sizes in a few seconds.
Here is the “lexicographically smallest” optimal solution for subproblem J1:
3 3
1##
#54
2#3And this is the solution for subproblem J2:
7 7
1######
2######
###5##6
#9#####
#####4#
####3##
#87####For added clarity we used a slightly different format: the digits represent the order in which the empty cells have to be visited. (Thus, 1 is A and the biggest number is B.)
The above observations about the shortest solution can also be easily turned into a mathematical proof that the solutions shown above are optimal. E.g., in the J2 case note that any path has to start somewhere and it has to make at least six non-horizontal jumps (each leading into a new row) and at least six non-vertical jumps (each leading into a new column). Thus, you cannot fit such a path into a grid with fewer than 7 rows or 7 columns.