Как стать автором
Обновить

Решение японских кроссвордов одним запросом SQL

Ненормальное программирование *Oracle *SQL *
Привет хабр! Приближается день программиста, и я спешу поделиться своими ненормальными наработками.

Японский кроссворд — NP-полная задача, как и задача коммивояжёра, укладки рюкзака и др. Когда ее решает человек, следует последовательно определять гарантированно заполненные и пустые ячейки. Одну за другой вычеркивать колонки и строки, пока не сложится весь рисунок. Как же возможно запрограммировать решение подобной задачи на языке, который официально даже не является языком программирования, не содержит циклов и переменных? SQL — язык запросов, его главная задача — выбирать строки. Вот мы и будем генерировать множество всех возможных перестановок и, словно скульптор, отсекать все лишнее.

укусить себя за пятку
Всего голосов 172: ↑165 и ↓7 +158
Просмотры 59K
Комментарии 26