Solving SUDOKU using PostgreSQL – Part 2

作者

上一篇文章的解法，是按照正向解题的思路去尝试解决。然而这种解法只能解决简单难度的数独，如果是大师级难度，则会遇到阻塞。比如下图中的这个大师级难度的数独：

运行SQL后，由于无法找到唯一候选，只能解决到如下图中的阶段

因此这里可以采用暴力的穷举方式，来找到最终的解。

穷举法

将所有数字合并到一起，形成一个大的字符串。每次迭代都寻找下一个为0的位置，并从1-9的数字逐个尝试替换，直到所有的0都被替换为1-9的数字为止。

因此数独初始有多少个空位，就需要迭代多少次。每次迭代产出的记录数也是指数增长，所以需要每次迭代都过滤掉无效记录。无效记录就是违反数独的行、列、方格的数字唯一性。

1
2
3
4
5
SELECT substring(all_rows from 1 for last_index - 1)
      || m.x ||
      substring(all_rows from last_index + 1) as all_rows,
      position('0' in substring(all_rows from last_index + 1)) + last_index as last_index
FROM sudoku_result, all_num m

过滤记录

根据last_index，找出该空位所在的行、列、方格，并寻找同行、同列、同方格中是否有数字相同的记录，如果有，则说明该记录无效，直接过滤掉即可。

行过滤

行过滤比较简单，根据last_index求出所在行的起点index，再加上[1-9]，就是所在行的所有位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
substring(all_rows from (floor((last_index - 1) / 9.0) * 9 + n.x) :: INTEGER for 1) :: INTEGER
 
postgres=> select floor((29 - 1) / 9.0) * 9 + n.x from (select unnest('{1,2,3,4,5,6,7,8,9}'::integer[]) as x) n;
 ?column?
----------
       28
       29
       30
       31
       32
       33
       34
       35
       36
(9 rows)

列过滤

列过滤也比较简单，根据last_index mod 9求出第几列，再加上[1-9]行，就是所在列的所有位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
substring(all_rows from (mod(last_index - 1, 9) + (n.x - 1) * 9 + 1) :: INTEGER for 1) :: INTEGER
 
postgres=> select mod(57 - 1, 9) + (n.x - 1) * 9 + 1 from (select unnest('{1,2,3,4,5,6,7,8,9}'::integer[]) as x) n;
 ?column?
----------
        3
       12
       21
       30
       39
       48
       57
       66
       75
(9 rows)

方格过滤

3*3的方格过滤比较复杂，其index是不连续的，如下图所示：

因此第一步需要找到3*3方格的起始位置，[1, 4, 7, 28, 31, 34, 55, 58, 61]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
floor((last_index - 1) / 27.0) * 27 + mod(floor((last_index - 1) / 3.0), 3) * 3 + 1
 
postgres=> select floor((41 - 1) / 27.0) * 27 + mod(floor((41 - 1) / 3.0), 3) * 3 + 1;
 
 ?column?
----------
       31
(1 row)
 
postgres=>
postgres=> select floor((80 - 1) / 27.0) * 27 + mod(floor((80 - 1) / 3.0), 3) * 3 + 1;
 
 ?column?
----------
       61
(1 row)

再加上[1-9]，每三个就要换一行，因此得出如下最终的公式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
floor((last_index - 1) / 27.0) * 27 + mod(floor((last_index - 1) / 3.0), 3) * 3 + floor((n.x - 1) / 3.0) * 9 +  mod((n.x - 1), 3) + 1
 
postgres=> select floor((42 - 1) / 27.0) * 27 + mod(floor((42 - 1) / 3.0), 3) * 3 + floor((n.x - 1) / 3.0) * 9 +  mod((n.x - 1), 3) + 1 from (select unnest('{1,2,3,4,5,6,7,8,9}'::integer[]) as x) n;
 ?column?
----------
       31
       32
       33
       40
       41
       42
       49
       50
       51
(9 rows)

最终SQL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
WITH RECURSIVE sudoku_result(all_rows, last_index) AS (
-- original problem
SELECT string_agg(c :: text, '') as all_rows, position('0' in string_agg(c :: text, '')) as last_index
FROM sudoku
 
UNION ALL
 
SELECT substring(all_rows from 1 for last_index - 1)
      || m.x ||
      substring(all_rows from last_index + 1) as all_rows,
      position('0' in substring(all_rows from last_index + 1)) + last_index as last_index
FROM sudoku_result, all_num m
WHERE last_index > 0
AND NOT EXISTS (
  SELECT x
  FROM all_num n
  WHERE substring(all_rows from (floor((last_index - 1) / 9.0) * 9 + n.x) :: INTEGER for 1) :: INTEGER = m.x
  OR substring(all_rows from (mod(last_index - 1, 9) + (n.x - 1) * 9 + 1) :: INTEGER for 1) :: INTEGER = m.x
  OR substring(all_rows from (floor((last_index - 1) / 27.0) * 27 + mod(floor((last_index - 1) / 3.0), 3) * 3 + floor((n.x - 1) / 3.0) * 9 +  mod((n.x - 1), 3) + 1) :: INTEGER for 1) :: INTEGER = m.x
  )
),
 
-- all numbers as integer array
all_arr(x) AS (
  SELECT '{1,2,3,4,5,6,7,8,9}' :: integer[]
),
 
-- all numbers as multiple rows
all_num(x) AS (
  SELECT unnest(x) from all_arr
)
SELECT * FROM sudoku_result;

最终计算出了结果，但是代价还是比较大的，迭代了58次，产生了11w条记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
postgres=> select count(*) from sudoku_all;
 count 
--------
 116326
(1 row)
 
postgres=> select count(distinct last_index) from sudoku_all;
 count
-------
    58
(1 row)
 
postgres=> select * from sudoku_all limit 10 offset 116320;
                                     all_rows                                      | last_index
-----------------------------------------------------------------------------------+------------
 485796321172348569639521478728914653546283917391657284964175832813462795257800000 |         77
 485796321172348569639521478728914653546283917391657284964175832813462795257830000 |         78
 485796321172348569639521478728914653546283917391657284964175832813462795257839000 |         79
 485796321172348569639521478728914653546283917391657284964175832813462795257839100 |         80
 485796321172348569639521478728914653546283917391657284964175832813462795257839140 |         81
 485796321172348569639521478728914653546283917391657284964175832813462795257839146 |         81
(6 rows)

发表评论