[wvxvw]

Алгоритм, принципиально, похож на судоку, т.е. те же методы решения, только условие другое. Или, если сильно упростить - крестики-нолики. Т.е. принцип примерно следующий: перешли в первый квадрат, сделали случайный выбор из четрыех за вычетом уже опробованых направлений, куда идти дальше, если опробованы все направления, делаем еще шаг назад. Перешли в следующий, проверили решаемость лабиринта, если не решается, - идем шаг назад, и повторяем.
Так же как судоку можно абстрагировать до работы с сетами и функцией определенной на сете всех возможных переходов, последовательно "скармливая" такой функции возможные комбинации и проверяя решаемость - наверное будет оптимальный вариант.

EDIT: Еще подумалось о алгоритме: берем перлин шум, и с его помощью изначально заполняем доску, проверяем решаемость, если решается, добавляем еще шум, и так по кругу. Можно еще какую-инбудь логистику добавить, чтобы, например, если есть почти решаемый вариант, убирать ранее добавленный шум так, чтобы вариант становился решаемым, и добавлять шум еще раз.