DouKaku?

棒倒し法の問題点は以下のようです。

1. 一行目に壁が少なくなってしまう。
2. 閉じた領域が出来てしまう。
3. 全ての道と連絡する抜け道ができてしまう。
4. 隙間だらけになってしまう。
5. 生成方向に逆行する経路ができない。

1～4の問題を克服した発散棒倒し法が紹介されていますが、
放射状に迷路を作るのでO(n)で実装するのは無理かもしれません。

参考
迷路自動生成アルゴリズム「発散棒倒し法」
http://aoyzsas.hp.infoseek.co.jp/maze/maze_hpillar.html