Update

The paper above proposed an algorithm to generate a maze in which the solution path reveals a hidden input (black-and-white) image. The key idea of the algorithm is to turn each pixel into a 2-by-2 set of pixels. This will allow us to find a solution path on the input image, and thus gives a desired maze.

The virtue of this algorithm is simplicity, and any connected raster image can be handled. However, there are a certain number of drawbacks.

1. We cannot specify the entrance and the exit arbitrarily. In particular, they need to be adjacent in the generated maze.
2. The solution path can be found by a right-hand walk without turning back at any deadend. Thus, solving the maze will not be fun.

Recently, these drawbacks have been resolved by three groups of people. Here, I'll summarize their approach.

• Ryohei Nakai and I (Yoshio Okamoto) from Tokyo Institute of Technology propose turning each pixel into a 4-by-4 set of pixels. This method can handle any connected input image. Certainly, the size of a generated maze will be big. This is a drawback.
• Kokolo Ikeda from Japan Advanced Institute of Science and Technology proposed turning each pixel into a 3-by-3 set of pixels. In this method, not all input images can be handled naturally, and so we need to modify the image a little bit. This looks to be a drawback, but he claims that this does not reduce the quality of the image. The size of a generated maze is smaller than the one by Nakai and me. He also proposes some other heuristic methods to improve the quality of the maze.
• Koki Hamada, who graduated from Kyoto University, proposed keeping a 2-by-2 set of pixels, as Okamoto and Uehara. But, by choosing the connections cleverly he is able to resolve the problems above. One drawback is that his method requires an input image to be 2-edge-connected.