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