DouKaku?

以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。

1. 格子状の迷路であること。
2. 経路の幅は均等であること。
3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。
   ループも認めません。
4. 出力の度にランダムな迷路であること。
   ランダムシードが同じ時に同じ迷路になってしまうのはよいです。

たとえば、n=4, m=5の迷路の出力は以下のようになります。

　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■　　　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　■　　　■　■
―■■■■■■■■■

こう言うのは、×の部分が3のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■×■　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■■■　■
４■　■×××■　■
―■　■×■■■　■
５■　■×××■　■
―■■■■■■■■■

このようなループも2のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　　　■　■
―■■■　■　■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　　　　　■　■
―■■■■■■■■■

できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。


難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を
どうやって作るのかを考えると答えが見えてくると思います。
ソースコードはJavaで150行程度になりました。

ルールについてよくわからないので質問します。
ルール１を満たさないのは、どういう場合ですか？
ルール２を満たさないのは、どういう場合ですか？
このプログラムがルールを満たしているということは、壁か、通路か未定の部分をあらかじめ
どちらかに固定した部分があってもよいということですか？
このプログラムを他の投稿プログラムと区別しているようにみえますが、ルール以外に
区別する「なにか」があるのですか？

私の方もうまく聞きたいことを伝えられないようで。
もうすこしだけ。下の例は、どうなりますか？
１　　　　　　　　　２　　　　　　　　　３
■■■■■　　■■■■■　　■■■■■
■□□□■　　■□■■■　　■□□□■
■■□■■　　■□■■■　　■□□□■
■□□□■　　■□□□■　　■□□□■
■■■■■　　■■■■■　　■■■■■

４
■■■■■■■■■■■
■□□□■□□□□□■
■□□□■□□□□□■
■□□□■□□□□□■
■□□□■■■□□□■
■□□□□□□□□□■
■□□□□□□□□□■
■□□□□□□□□□■
■■■■■■■■■■■

なんか空白にすると詰まってしまうので□にしました。