Используем TSQL для игры в «Судоку»

После того как при помощи TSQL была успешна решена «Балда» (статья) я решил попробовать решить на нем «Судоку» (спасибо за идею shavluk).

Решение судоку получилось на удивление достаточно простым.

Базовая схема имеет следующий вид:


Описание таблиц:

• SudokuCell – описание и свойств (регион, строка, столбец) всех ячеек;
• SudokuValue – допустимые значения ячейки;
• SudokuField – поле, для задания известных цифр.

Скрипт для создания таблиц:

-- удаляем таблицы если они уже есть IF EXISTS (SELECT * FROM sysobjects WHERE name='SudokuField') DROP TABLE SudokuField; IF EXISTS (SELECT * FROM sysobjects WHERE name='SudokuCell') DROP TABLE SudokuCell; IF EXISTS (SELECT * FROM sysobjects WHERE name='SudokuValue') DROP TABLE SudokuValue;    ---------------------------------------------- -- описание ячеек и их свойств ---------------------------------------------- CREATE TABLE SudokuCell(   ID int NOT NULL,       -- ID ячейки   RegionID int NOT NULL, -- регион   RowID int NOT NULL,    -- строка   ColID int NOT NULL,    -- столбец CONSTRAINT PK_SudokuCell PRIMARY KEY(ID) ) GO  -- заполняем таблицу INSERT SudokuCell(ID,RegionID,RowID,ColID) SELECT   reg.ID*100+r.i*10+c.j,   reg.ID,   (reg.ID/10-1)*3+r.i,   (reg.ID-1)%10*3+c.j FROM (VALUES (11),(12),(13),(21),(22),(23),(31),(32),(33)) reg(ID) CROSS JOIN (VALUES(1),(2),(3)) r(i) CROSS JOIN (VALUES(1),(2),(3)) c(j) GO    ---------------------------------------------- -- цифры 1-9 (допустимые значения) ---------------------------------------------- CREATE TABLE SudokuValue(   Value char(1) NOT NULL, CONSTRAINT PK_SudokuValue PRIMARY KEY(Value) ) GO  -- заполняем таблицу INSERT SudokuValue(Value) VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9) GO    ---------------------------------------------- -- поле ---------------------------------------------- CREATE TABLE SudokuField(   CellID int NOT NULL,   Value char(1) NOT NULL, CONSTRAINT PK_SudokuField PRIMARY KEY(CellID), CONSTRAINT FK_SudokuField_CellID FOREIGN KEY(CellID) REFERENCES SudokuCell(ID), CONSTRAINT FK_SudokuField_Value FOREIGN KEY(Value) REFERENCES SudokuValue(Value) ) GO 

Заполнение поля известными цифрами производим следующим образом:

-- предварительная очистка поля, на тот случай если оно заполнено TRUNCATE TABLE SudokuField GO  -- заполнение поля известными цифрами INSERT SudokuField(CellID,Value)VALUES (1122,'3'),(1123,'4'), (1211,'1'),(1212,'5'), (1322,'8'),(1323,'9'),(1333,'3'),  (2112,'2'),(2122,'4'),(2123,'7'),(2133,'9'), (2212,'6'),(2223,'9'),(2232,'2'), (2311,'8'),(2333,'1'),  (3111,'1'), (3213,'2'),(3221,'9'), (3313,'5'),(3332,'7'),(3333,'4') GO 

Идентификатор ячейки (CellID) построен следующим образом:

• Первая и вторая цифра числа – указывают какой это регион (строка, столбец);
• Третья и четвертая цифра – номер строки и столбца в регионе.

Начальные варианты заполнения я брал со следующего сайта – ссылка.

Посмотрим, как выглядит поле:

-- вид поля до заполнения SELECT   ISNULL([1],'') [1],   ISNULL([2],'') [2],   ISNULL([3],'') [3],   ISNULL([4],'') [4],   ISNULL([5],'') [5],   ISNULL([6],'') [6],   ISNULL([7],'') [7],   ISNULL([8],'') [8],   ISNULL([9],'') [9] FROM   (     SELECT c.RowID,c.ColID,f.Value     FROM SudokuCell c     LEFT JOIN SudokuField f ON f.CellID=c.ID   ) q PIVOT(MAX(Value) FOR ColID IN([1],[2],[3],[4],[5],[6],[7],[8],[9])) p ORDER BY RowID 

Дальше идет алгоритм поиска решения с комментариями:

-- получаем допустимые цифры в пустых ячейках SELECT   -- формируем идентификатор варианта - укорачиваем его для более быстрого поиска   CONCAT('>',CAST(CellNo AS varchar(4)),CHAR(ASCII('a')+Value-1)) ID,   * INTO #SudokuVariant FROM   (     -- получаем все незаполненные ячейки     SELECT       ID CellID,RowID,ColID,RegionID,       -- нумеруем ячейки       CAST(DENSE_RANK()OVER(ORDER BY ID) AS int) CellNo     FROM SudokuCell     WHERE ID NOT IN(SELECT CellID FROM SudokuField)   ) e CROSS APPLY   (     -- получаем все цифры, которые могут быть вписаны в каждую пустую ячейку     SELECT v.Value     FROM SudokuCell c     JOIN SudokuField f ON f.CellID=c.ID AND (c.ColID=e.ColID OR c.RowID=e.RowID OR c.RegionID=e.RegionID)     RIGHT JOIN SudokuValue v ON v.Value=f.Value     WHERE c.ID IS NULL -- оставляем только цифры, которых нет в регионе/строке/столбце   ) v  --SELECT * FROM #SudokuVariant   -- вспомогательная таблица для построения деревьев решений CREATE TABLE #SudokuTree(   CellNo int NOT NULL,   VariantPath varchar(1000) NOT NULL,   PathLen int NOT NULL )  -- создаем корни деревьев из ячеек с CellNo=1 INSERT #SudokuTree(CellNo,VariantPath,PathLen) SELECT CellNo,ID,1 FROM #SudokuVariant WHERE CellNo=1  --SELECT * FROM #SudokuTree    -- это максимальная длина цепочки DECLARE @MaxCellNo int=(SELECT MAX(CellNo) FROM #SudokuVariant)  -- номера начальной и следующией ячеек DECLARE @CurrCellNo int=1 DECLARE @NextCellNo int=@CurrCellNo+1  -- строим дерево WHILE @CurrCellNo<@MaxCellNo BEGIN    -- добавление отростков   INSERT #SudokuTree(CellNo,VariantPath,PathLen)   SELECT     v.CellNo,     CONCAT(t.VariantPath,v.ID),     t.PathLen+1   FROM #SudokuTree t   JOIN #SudokuVariant v ON t.CellNo=@CurrCellNo AND v.CellNo=@NextCellNo   /*     в следующий узел дерева будут входить только значения, которых нет в регионе/строке/столбце     по сути эта проверка является самодостаточной, т.к. мы уже отсекли недопустимые значения     при формировании таблицы #SudokuVariant   */    WHERE NOT EXISTS(                 SELECT *                 FROM #SudokuVariant i                 WHERE t.VariantPath LIKE '%'+i.ID+'%'                   AND (i.RegionID=v.RegionID OR i.RowID=v.RowID OR i.ColID=v.ColID)                   AND i.Value=v.Value               )    /*     т.к. полный путь у нас сохраняется в VariantPath,     то данные предыдущего уровня можно удалить   */   DELETE #SudokuTree WHERE CellNo=@CurrCellNo     -- перемещаемся на уровень выше   SET @CurrCellNo+=1   SET @NextCellNo+=1  END  --SELECT * FROM #SudokuTree    -- заполняем поле найдеными значениями INSERT SudokuField(CellID,Value) SELECT v.CellID,v.Value FROM #SudokuVariant v JOIN   (     -- если решений получилось несколько, берем самое первое     SELECT TOP 1 *     FROM #SudokuTree   ) r ON r.VariantPath LIKE '%'+v.ID+'%'    -- удаляем временные таблицы DROP TABLE #SudokuTree DROP TABLE #SudokuVariant 

На моем компьютере решение находится в пределах 10-15 секунд (в зависимости от заданных начальных значений).

Посмотрим, на найденное решение:

-- вид поля после заполнения SELECT   ISNULL([1],'') [1],   ISNULL([2],'') [2],   ISNULL([3],'') [3],   ISNULL([4],'') [4],   ISNULL([5],'') [5],   ISNULL([6],'') [6],   ISNULL([7],'') [7],   ISNULL([8],'') [8],   ISNULL([9],'') [9] FROM   (     SELECT c.RowID,c.ColID,f.Value     FROM SudokuCell c     LEFT JOIN SudokuField f ON f.CellID=c.ID   ) q PIVOT(MAX(Value) FOR ColID IN([1],[2],[3],[4],[5],[6],[7],[8],[9])) p ORDER BY RowID 

Другие примеры решения:

Для задания начальных значений использовались следующие скрипты:

-- предварительная очистка поля, на тот случай если оно заполнено TRUNCATE TABLE SudokuField GO  -- заполнение поля известными цифрами INSERT SudokuField(CellID,Value)VALUES (1112,'7'),(1113,'1'),(1131,'4'),(1132,'9'), (1212,'9'),(1221,'3'),(1223,'6'), (1311,'8'),(1331,'7'),(1333,'5'),  (2112,'1'),(2121,'9'),(2123,'2'), (2211,'9'),(2233,'8'), (2321,'6'),(2323,'3'),(2332,'2'),  (3111,'8'),(3113,'5'),(3133,'7'), (3221,'6'),(3223,'7'),(3232,'4'), (3312,'7'),(3313,'6'),(3331,'3'),(3332,'5') GO 

-- предварительная очистка поля, на тот случай если оно заполнено TRUNCATE TABLE SudokuField GO  -- заполнение поля известными цифрами INSERT SudokuField(CellID,Value)VALUES (1132,'4'), (1221,'9'),(1223,'4'),(1231,'8'),(1233,'5'), (1311,'7'),(1321,'2'),(1323,'3'),  (2113,'7'),(2121,'9'),(2133,'3'), (2212,'1'), (2311,'6'),(2332,'5'),(2333,'2'),  (3111,'6'),(3112,'2'),(3121,'7'), (3223,'3'),(3233,'8'), (3323,'9') GO 

Собственно, все.

Полный скрипт можно скачать по следующей ссылке – скрипт.

Надеюсь, что статья была интересна.

Удачи и спасибо за внимание!

ссылка на оригинал статьи http://habrahabr.ru/post/272373/