Вот такая задачка есть у Столярова в третьем томе рядом с tcl/tk.
Как и положено, понял суть задачи только после написания первого решения.
Дело в том, что количество переборов выходит такое, что современный компьютер решает их даже не за 0.5мс. У меня программа работала минут 10 — признаков решения не видно.
По всей видимости, переборов нужно 64!, но я круглый электрик-гумантирай. Багов не обнаружил.
Умная оптимизация? Заблокированные угловые клеточки занимают на себя огромное количество переборов. Но ими, конечно, дело не ограничивается. Боюсь что рекурсивная проверка заблокированности каждой ячейки выйдет ещё одним таким приложением.
Как решить такую задачу?
Интересно что поиск для досок на
полей | занимает времени |
---|---|
5 | 0.019u |
6 | 0.559u |
7 | 0.502u |
Но при этом поиск для 8 и 9 может длиться десятки минут. Наверное, какой-то баг, но я его не вижу.
Перемещено leave из general