ITPUB第2届“盛拓传媒杯”SQL数据库编程大赛第二期参考思路

〇〇

newkid 发表于 2013-12-4 06:41
25楼和31楼都有同样的错，在WHERE里面判断第二号邻居的条件有一个OR错写成为了AND, 现在改过来了。

31楼好了

ID             1     2     3     4     5     6     7     8     9    10    11    12    13    14    15   100
---------- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
146          .12   .03     0   .01     0   .01   .08   .14   .11   .13   .07   .28   .28   .17     0 21.45

newkid

改良后的递归法，推理过程简单多了，但最后的校验还是有点啰嗦。

WITH cells AS (                      ------- 构造所有单元格及其坐标
    SELECT LEVEL cell_id              -------- 从左上角开始，从左到右从上到下从1开始编号
          ,CEIL(LEVEL/:v_width) r     -------- 行号，1~v_height
          ,MOD(LEVEL-1,:v_width)+1 c  -------- 列号，1~v_width
          ,SUBSTR(:v_str,LEVEL,1) cnt -------- 该单元格周围的地雷数目
      FROM DUAL CONNECT BY LEVEL<=:v_width*:v_height
)
,cells2 AS (
SELECT cell_id,r,c,DECODE(cnt,' ',0,TO_NUMBER(cnt)) AS cnt
       ,CASE WHEN r>1 AND c>1         THEN cell_id-:v_width-1   ---- 左上方邻居的id
             WHEN r>1                 THEN cell_id-:v_width     ---- 正上方邻居的id
             WHEN c>1                 THEN cell_id-1            ---- 左边邻居的id
        END AS n_id   ----- 参照邻居的id
       ,CASE WHEN r>1                 THEN r-1 ELSE r END AS n_r ----参照邻居的行数
       ,CASE WHEN c>1                 THEN c-1 ELSE c END AS n_c ----参照邻居的列数
   from cells
)
,empty_cells AS (
SELECT  --------- 找出所有空位及其邻居位置, 空位是未标数字的单元格，可能有地雷也可能没有               
        cc.*
       ,ROWNUM empty_id ---------- 按顺序为空位取编号，递归的时候每层编号递增，按序猜测每个空位
        ------ 如果某个方位的邻居不存在，比如边界上，把该邻居的id设为大数999999, 这样SUBSTR不报错只是返回NULL
       ,CASE WHEN n_r>1 AND n_c>1         THEN n_id-:v_width-1  ELSE 999999 END AS n1  ----- 参照邻居的左上角
       ,CASE WHEN n_r>1                   THEN n_id-:v_width    ELSE 999999 END AS n2  ----- 参照邻居的正上方
       ,CASE WHEN n_r>1 AND n_c<:v_width  THEN n_id-:v_width+1  ELSE 999999 END AS n3  ----- 参照邻居的右上角
       ,CASE WHEN n_c>1                   THEN n_id-1           ELSE 999999 END AS n4  ----- 参照邻居的左侧
       ,CASE WHEN n_r<:v_height AND n_c>1 THEN n_id+:v_width-1  ELSE 999999 END AS n6  ----- 参照邻居的左下角
       ,NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n_id,1))),0)  n_cnt
   FROM (SELECT * FROM cells2
          WHERE cnt=0          ------- 空位
         ORDER BY CASE WHEN cell_id<=2*:v_width THEN c ELSE 9999 END  -------------- 霹雳火思路
                           ,CASE WHEN cell_id<=2*:v_width THEN r ELSE 9999 END
                           ,cell_id
        ) cc
)
,guess AS (SELECT 0 AS mine FROM DUAL UNION ALL SELECT 1 FROM DUAL)
,t(m_cnt     ---- 到目前为止猜测为地雷的总数, 达到:V_CNT时就结束
   ,empty_id  ---- 目前要猜测哪个空位
   ,res       ---- 最后输出的结果。每猜出一个雷就拼一个 * 进去
   ) AS (
SELECT 0   ------- 未猜测之前总雷数为0   
       ,1   ------- 从第一个空位开始遍历
       ,CAST(:v_str AS VARCHAR2(1000))  -------- 输出初始为原分布，在递归过程中嵌入地雷
   FROM DUAL
UNION ALL
SELECT m_cnt + guess.mine ---- 总雷数递增或不变，取决于当前猜测
       ,t.empty_id+1  ------- 空单元格编号推进
       ,SUBSTR(res,1,e.cell_id-1)||CASE WHEN guess.mine=1 THEN '*' ELSE ' ' END||SUBSTR(t.res,e.cell_id+1) ---在输出结果中嵌入地雷
   FROM t
       ,empty_cells e
       ,guess  ---和两种猜测做笛卡尔积：0:没有地雷，1:有地雷
WHERE t.empty_id<=(SELECT MAX(empty_id) FROM empty_cells)   ------- 空位编号推进直至最大
        AND t.empty_id=e.empty_id   ------连接到empty_cells表，取当前猜测空位的坐标、邻居等信息
        AND  t.m_cnt<:v_cnt  ---- 总雷数不能溢出
        AND (e.cell_id=1 OR
             CASE WHEN e.n_cnt=0 THEN
                       DECODE(SUBSTR(t.res,e.n_id,1),'*',1,0)
                  WHEN DECODE(SUBSTR(t.res,e.n1,1),'*',1,0)
                      +DECODE(SUBSTR(t.res,e.n2,1),'*',1,0)                  
                      +DECODE(SUBSTR(t.res,e.n3,1),'*',1,0)                  
                      +DECODE(SUBSTR(t.res,e.n4,1),'*',1,0)                  
                      +DECODE(SUBSTR(t.res,e.n6,1),'*',1,0)
                      <e.n_cnt THEN 1
                  ELSE 0
             END = guess.mine                  
             )
)
,t2 AS (
SELECT ROWNUM id,res, TRANSLATE(res,'12345678','        ') as S
FROM t
WHERE m_cnt=:v_cnt ---------- 总雷数必须符合
)
SELECT res FROM (
SELECT res
FROM ( SELECT t2.id
              ,cells.cell_id
              ,t2.res
              ,CASE WHEN SUBSTR(t2.res,cell_id,1) = '*' THEN ' '
                    ELSE TO_CHAR(CASE WHEN r>1 THEN ---- 不是第一行
                                           ----也不是第一列，那么可以取左上邻居
                                           CASE WHEN c>1 THEN DECODE(SUBSTR(s,cell_id-:v_width-1,1),'*',1,0) ELSE 0 END
                                           ----再取正上邻居
                                           +DECODE(SUBSTR(s,cell_id-:v_width,1),'*',1,0)
                                           ----如果非最右一列，还可以取右上邻居
                                           +CASE WHEN c<:v_width THEN DECODE(SUBSTR(s,cell_id-:v_width+1,1),'*',1,0) ELSE 0 END
                                      ELSE 0 ---- 如果是第一行，那么上述三个邻居都不存在
                                 END
                                +CASE WHEN c>1 THEN DECODE(SUBSTR(s,cell_id-1,1),'*',1,0) ELSE 0 END --- 如果非第一列则取左方邻居
                                +CASE WHEN c<:v_width THEN DECODE(SUBSTR(s,cell_id+1,1),'*',1,0) ELSE 0 END --- 如果非最后一列则取右方邻居
                                +CASE WHEN r<:v_height THEN ---- 如果不是最后一行
                                            ----也不是第一列，那么可以取左下邻居
                                            CASE WHEN c>1 THEN DECODE(SUBSTR(s,cell_id+:v_width-1,1),'*',1,0) ELSE 0 END
                                            ----再取正下邻居
                                           +DECODE(SUBSTR(s,cell_id+:v_width,1),'*',1,0)
                                            ----如果非最右一列，还可以取右下邻居
                                           +CASE WHEN c<:v_width THEN DECODE(SUBSTR(s,cell_id+:v_width+1,1),'*',1,0) ELSE 0 END
                                      ELSE 0 ---- 如果是最后一行，那么上述三个邻居都不存在
                                 END
                                 )
               END str
           FROM t2, cells
        )
GROUP BY id,res
HAVING REPLACE(LISTAGG(str) WITHIN GROUP (ORDER BY cell_id) ,'0',' ')=:v_str
)
;

newkid

加强递归过程中的空位互相校验，比起事后校验的代码少一些：

WITH cells AS (                      ------- 构造所有单元格及其坐标
    SELECT LEVEL cell_id              -------- 从左上角开始，从左到右从上到下从1开始编号
          ,CEIL(LEVEL/:v_width) r     -------- 行号，1~v_height
          ,MOD(LEVEL-1,:v_width)+1 c  -------- 列号，1~v_width
          ,SUBSTR(:v_str,LEVEL,1) cnt -------- 该单元格周围的地雷数目
      FROM DUAL CONNECT BY LEVEL<=:v_width*:v_height
)
,cells2 AS (
SELECT cell_id,r,c,DECODE(cnt,' ',0,TO_NUMBER(cnt)) AS cnt
       ,CASE WHEN r>1 AND c>1         THEN cell_id-:v_width-1   ---- 左上方邻居的id
             WHEN r>1                 THEN cell_id-:v_width     ---- 正上方邻居的id
             WHEN c>1                 THEN cell_id-1            ---- 左边邻居的id
        END AS n_id   ----- 参照邻居的id
       ,CASE WHEN r>1                 THEN r-1 ELSE r END AS n_r ----参照邻居的行数
       ,CASE WHEN c>1                 THEN c-1 ELSE c END AS n_c ----参照邻居的列数
   from cells
)
,empty_cells AS (
SELECT  --------- 找出所有空位及其邻居位置, 空位是未标数字的单元格，可能有地雷也可能没有               
        cc.*
       ,ROWNUM empty_id ---------- 按顺序为空位取编号，递归的时候每层编号递增，按序猜测每个空位
        ------ 如果某个方位的邻居不存在，比如边界上，把该邻居的id设为大数999999, 这样SUBSTR不报错只是返回NULL
       ,CASE WHEN n_r>1 AND n_c>1         THEN n_id-:v_width-1  ELSE 999999 END AS n1  ----- 参照邻居的左上角
       ,CASE WHEN n_r>1                   THEN n_id-:v_width    ELSE 999999 END AS n2  ----- 参照邻居的正上方
       ,CASE WHEN n_r>1 AND n_c<:v_width  THEN n_id-:v_width+1  ELSE 999999 END AS n3  ----- 参照邻居的右上角
       ,CASE WHEN n_c>1                   THEN n_id-1           ELSE 999999 END AS n4  ----- 参照邻居的左侧
       ,CASE WHEN n_r<:v_height AND n_c>1 THEN n_id+:v_width-1  ELSE 999999 END AS n6  ----- 参照邻居的左下角
       ,NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n_id,1))),0)  n_cnt
       ,CASE WHEN r>1 AND c>1 AND SUBSTR(:v_str,cell_id-:v_width-1,1)=' '  THEN cell_id-:v_width-1 ELSE 0 END AS en1  ---- 左上方邻居的id
       ,CASE WHEN r>1 AND SUBSTR(:v_str,cell_id-:v_width,1)=' '            THEN cell_id-:v_width   ELSE 0 END AS en2  ---- 正上方邻居的id
       ,CASE WHEN c>1 AND SUBSTR(:v_str,cell_id-1,1)=' '                   THEN cell_id-1          ELSE 0 END AS en4  ---- 左边邻居的id
   FROM (SELECT * FROM cells2
          WHERE cnt=0          ------- 空位
         ORDER BY CASE WHEN cell_id<=2*:v_width THEN c ELSE 9999 END  -------------- 霹雳火思路
                           ,CASE WHEN cell_id<=2*:v_width THEN r ELSE 9999 END
                           ,cell_id
        ) cc
)
,guess AS (SELECT 0 AS mine FROM DUAL UNION ALL SELECT 1 FROM DUAL)
,t(m_cnt     ---- 到目前为止猜测为地雷的总数, 达到:V_CNT时就结束
   ,empty_id  ---- 目前要猜测哪个空位
   ,res       ---- 最后输出的结果。每猜出一个雷就拼一个 * 进去
   ) AS (
SELECT 0   ------- 未猜测之前总雷数为0   
       ,1   ------- 从第一个空位开始遍历
       ,CAST(:v_str AS VARCHAR2(1000))  -------- 输出初始为原分布，在递归过程中嵌入地雷
   FROM DUAL
UNION ALL
SELECT m_cnt + guess.mine ---- 总雷数递增或不变，取决于当前猜测
       ,t.empty_id+1  ------- 空单元格编号推进
       ,SUBSTR(res,1,e.cell_id-1)||CASE WHEN guess.mine=1 THEN '*' ELSE ' ' END||SUBSTR(t.res,e.cell_id+1) ---在输出结果中嵌入地雷
   FROM t
       ,empty_cells e
       ,guess  ---和两种猜测做笛卡尔积：0:没有地雷，1:有地雷
WHERE t.empty_id<=(SELECT MAX(empty_id) FROM empty_cells)   ------- 空位编号推进直至最大
        AND t.empty_id=e.empty_id   ------连接到empty_cells表，取当前猜测空位的坐标、邻居等信息
        AND  t.m_cnt<:v_cnt  ---- 总雷数不能溢出
        AND (e.cell_id=1 OR
             CASE WHEN e.n_cnt=0 THEN
                       DECODE(SUBSTR(t.res,e.n_id,1),'*',1,0)
                  WHEN DECODE(SUBSTR(t.res,e.n1,1),'*',1,0)
                      +DECODE(SUBSTR(t.res,e.n2,1),'*',1,0)                  
                      +DECODE(SUBSTR(t.res,e.n3,1),'*',1,0)                  
                      +DECODE(SUBSTR(t.res,e.n4,1),'*',1,0)                  
                      +DECODE(SUBSTR(t.res,e.n6,1),'*',1,0)
                      <e.n_cnt THEN 1
                  ELSE 0
             END = guess.mine                  
             AND CASE WHEN e.en1>0 THEN DECODE(SUBSTR(t.res,e.en1,1),'*',1,0) ELSE guess.mine END = guess.mine
             AND CASE WHEN e.en2>0 THEN DECODE(SUBSTR(t.res,e.en2,1),'*',1,0) ELSE guess.mine END = guess.mine
             AND CASE WHEN e.en4>0 THEN DECODE(SUBSTR(t.res,e.en4,1),'*',1,0) ELSE guess.mine END = guess.mine
             )
)
SELECT res
  FROM t
WHERE m_cnt=:v_cnt ---------- 总雷数必须符合
;

〇〇

42楼47 43楼48
怎么差距这么大，又是优化器bug?
48这么快，都不象递归了，但第2个用例居然出错，（31*31的100个用例都全对）
147          .31  1.14    .3   .14   .34   .21   .27   .28 61.44  1.17 16.64
148          .16         .18   .13   .24   .09   .19   .18   .32    .2   .19   .41   .51   .29 29.29

已选择34行。

SQL> select width,height,cnt,cast(outs as varchar(100)) from dlz where qn=2;

WIDTH HEIGHT   CNT CAST(OUTSASVARCHAR(100))
----- ------ ----- ----------------------------------------------------------------------------------------------------
[   10     10    10        1 2       12   111   11  1 1       111   11  111   1   1 111122  1111 11 1221 112221  1   1 1]

newkid

再增强校验条件:
WITH cells AS (                      ------- 构造所有单元格及其坐标
    SELECT LEVEL cell_id              -------- 从左上角开始，从左到右从上到下从1开始编号
          ,CEIL(LEVEL/:v_width) r     -------- 行号，1~v_height
          ,MOD(LEVEL-1,:v_width)+1 c  -------- 列号，1~v_width
          ,SUBSTR(:v_str,LEVEL,1) cnt -------- 该单元格周围的地雷数目
      FROM DUAL CONNECT BY LEVEL<=:v_width*:v_height
)
,cells2 AS (
SELECT cell_id,r,c,DECODE(cnt,' ',0,TO_NUMBER(cnt)) AS cnt
       ,CASE WHEN r>1 AND c>1         THEN cell_id-:v_width-1   ---- 左上方邻居的id
             WHEN r>1                 THEN cell_id-:v_width     ---- 正上方邻居的id
             WHEN c>1                 THEN cell_id-1            ---- 左边邻居的id
        END AS n_id   ----- 参照邻居的id
       ,CASE WHEN r>1                 THEN r-1 ELSE r END AS n_r ----参照邻居的行数
       ,CASE WHEN c>1                 THEN c-1 ELSE c END AS n_c ----参照邻居的列数
   from cells
)
,empty_cells AS (
SELECT  --------- 找出所有空位及其邻居位置, 空位是未标数字的单元格，可能有地雷也可能没有               
        cc.*
       ,ROWNUM empty_id ---------- 按顺序为空位取编号，递归的时候每层编号递增，按序猜测每个空位
        ------ 如果某个方位的邻居不存在，比如边界上，把该邻居的id设为大数999999, 这样SUBSTR不报错只是返回NULL
       ,CASE WHEN n_r>1 AND n_c>1         THEN n_id-:v_width-1  ELSE 999999 END AS n1  ----- 参照邻居的左上角
       ,CASE WHEN n_r>1                   THEN n_id-:v_width    ELSE 999999 END AS n2  ----- 参照邻居的正上方
       ,CASE WHEN n_r>1 AND n_c<:v_width  THEN n_id-:v_width+1  ELSE 999999 END AS n3  ----- 参照邻居的右上角
       ,CASE WHEN n_c>1                   THEN n_id-1           ELSE 999999 END AS n4  ----- 参照邻居的左侧
       ,CASE WHEN n_r<:v_height AND n_c>1 THEN n_id+:v_width-1  ELSE 999999 END AS n6  ----- 参照邻居的左下角
       ,NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n_id,1))),0)  n_cnt
       ,CASE WHEN r>1 AND c>1 AND SUBSTR(:v_str,cell_id-:v_width-1,1)=' '  THEN cell_id-:v_width-1 ELSE 0 END AS en1  ---- 左上方邻居的id
       ,CASE WHEN r>1 AND SUBSTR(:v_str,cell_id-:v_width,1)=' '            THEN cell_id-:v_width   ELSE 0 END AS en2  ---- 正上方邻居的id
       ,CASE WHEN r>2 AND c<:v_width AND SUBSTR(:v_str,cell_id-:v_width+1,1)=' ' THEN cell_id-:v_width+1 ELSE 0 END AS en3  ---- 右上角邻居的id，由于排序的原因，从第三行开始, 此邻居才先于本单元猜测
       ,CASE WHEN c>1 AND SUBSTR(:v_str,cell_id-1,1)=' '                   THEN cell_id-1          ELSE 0 END AS en4  ---- 左边邻居的id
       ,CASE WHEN r=1 AND c>1 AND SUBSTR(:v_str,cell_id+:v_width-1,1)=' '  THEN cell_id+:v_width-1 ELSE 0 END AS en6  ---- 左下角邻居的id，由于排序的原因，只有在第一行, 此邻居才先于本单元猜测
   FROM (SELECT * FROM cells2
          WHERE cnt=0          ------- 空位
         ORDER BY CASE WHEN cell_id<=2*:v_width THEN c ELSE 9999 END  -------------- 霹雳火思路
                           ,CASE WHEN cell_id<=2*:v_width THEN r ELSE 9999 END
                           ,cell_id
        ) cc
)
,guess AS (SELECT 0 AS mine FROM DUAL UNION ALL SELECT 1 FROM DUAL)
,t(m_cnt     ---- 到目前为止猜测为地雷的总数, 达到:V_CNT时就结束
   ,empty_id  ---- 目前要猜测哪个空位
   ,res       ---- 最后输出的结果。每猜出一个雷就拼一个 * 进去
   ) AS (
SELECT 0   ------- 未猜测之前总雷数为0   
       ,1   ------- 从第一个空位开始遍历
       ,CAST(:v_str AS VARCHAR2(1000))  -------- 输出初始为原分布，在递归过程中嵌入地雷
   FROM DUAL
UNION ALL
SELECT m_cnt + guess.mine ---- 总雷数递增或不变，取决于当前猜测
       ,t.empty_id+1  ------- 空单元格编号推进
       ,SUBSTR(res,1,e.cell_id-1)||CASE WHEN guess.mine=1 THEN '*' ELSE ' ' END||SUBSTR(t.res,e.cell_id+1) ---在输出结果中嵌入地雷
   FROM t
       ,empty_cells e
       ,guess  ---和两种猜测做笛卡尔积：0:没有地雷，1:有地雷
WHERE t.empty_id<=(SELECT MAX(empty_id) FROM empty_cells)   ------- 空位编号推进直至最大
        AND t.empty_id=e.empty_id   ------连接到empty_cells表，取当前猜测空位的坐标、邻居等信息
        AND  t.m_cnt<=:v_cnt  ---- 总雷数不能溢出
        AND (e.cell_id=1 OR
             CASE WHEN e.n_cnt=0 THEN
                       DECODE(SUBSTR(t.res,e.n_id,1),'*',1,0)
                  WHEN DECODE(SUBSTR(t.res,e.n1,1),'*',1,0)
                      +DECODE(SUBSTR(t.res,e.n2,1),'*',1,0)                  
                      +DECODE(SUBSTR(t.res,e.n3,1),'*',1,0)                  
                      +DECODE(SUBSTR(t.res,e.n4,1),'*',1,0)                  
                      +DECODE(SUBSTR(t.res,e.n6,1),'*',1,0)
                      <e.n_cnt THEN 1
                  ELSE 0
             END = guess.mine                  
             AND CASE WHEN e.en1>0 THEN DECODE(SUBSTR(t.res,e.en1,1),'*',1,0) ELSE guess.mine END = guess.mine
             AND CASE WHEN e.en2>0 THEN DECODE(SUBSTR(t.res,e.en2,1),'*',1,0) ELSE guess.mine END = guess.mine
             AND CASE WHEN e.en3>0 THEN DECODE(SUBSTR(t.res,e.en3,1),'*',1,0) ELSE guess.mine END = guess.mine
             AND CASE WHEN e.en4>0 THEN DECODE(SUBSTR(t.res,e.en4,1),'*',1,0) ELSE guess.mine END = guess.mine
             AND CASE WHEN e.en6>0 THEN DECODE(SUBSTR(t.res,e.en6,1),'*',1,0) ELSE guess.mine END = guess.mine
             )
)
SELECT res
  FROM t
WHERE m_cnt=:v_cnt ---------- 总雷数必须符合
       AND t.empty_id=(SELECT MAX(empty_id) FROM empty_cells)+1
;

〇〇

newkid 发表于 2013-12-4 23:00
再增强校验条件:
WITH cells AS (                      ------- 构造所有单元格及其坐标
    SELECT LEV ...

这下对了
ID             1     2     3     4     5     6     7     8     9    10    11    12    13    14   100
---------- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
148          .22   .14   .12    .1   .15   .18   .22   .09   .29   .15    .2   .55   .47   .35 29.97

X-Power

观摩中

〇〇

在oracle 19c中，34楼和42楼都报错了
SQL> @wdl5.txt
SELECT guess.mine AS solution_id
       *
ERROR at line 10:
ORA-01722: invalid number


SQL> @wdl6.txt
             WHEN c>1                      THEN cell_id-1                ---- 左边邻居的id
                                                                                     *
ERROR at line 12:
ORA-01722: invalid number

newkid

当年有多热闹，现在就有多凄凉

〇〇

让deepseek把43楼SQL改成的python,一次成功

1. 
   
2. import itertools
   
3. from typing import List, Dict, Any
   
4. 
   
5. def sql_to_python(width: int, height: int, grid_str: str):
   
6.     # CTE 1: cells
   
7.     cells = [
   
8.         {
   
9.             'cell_id': i,
   
10.             'r': (i - 1) // width + 1,
    
11.             'c': (i - 1) % width + 1,
    
12.             'cnt': grid_str[i-1] if i <= len(grid_str) else ' '
    
13.         }
    
14.         for i in range(1, width * height + 1)
    
15.     ]
    
16.    
    
17.     # CTE 2: cells2
    
18.     cells2 = []
    
19.     for cell in cells:
    
20.         cnt = cell['cnt']
    
21.         r = cell['r']
    
22.         c = cell['c']
    
23.         cell_id = cell['cell_id']
    
24.         
    
25.         # 处理cnt值
    
26.         if cnt == ' ':
    
27.             cnt_val = 0
    
28.         elif cnt == '*':
    
29.             cnt_val = None
    
30.         else:
    
31.             cnt_val = int(cnt) if cnt.strip() else None
    
32.         
    
33.         # 计算n_id
    
34.         if r > 1 and c > 1:
    
35.             n_id = cell_id - width - 1
    
36.         elif r > 1:
    
37.             n_id = cell_id - width
    
38.         elif c > 1:
    
39.             n_id = cell_id - 1
    
40.         else:
    
41.             n_id = None
    
42.         
    
43.         cells2.append({
    
44.             'cell_id': cell_id,
    
45.             'r': r,
    
46.             'c': c,
    
47.             'cnt': cnt_val,
    
48.             'n_id': n_id,
    
49.             'n_r': r - 1 if r > 1 else r,
    
50.             'n_c': c - 1 if c > 1 else c
    
51.         })
    
52.    
    
53.     # CTE 3: empty_cells
    
54.     empty_cells = []
    
55.     # 先筛选出空单元格(cnt=0)
    
56.     empty_candidates = [cell for cell in cells2 if cell['cnt'] == 0]
    
57.    
    
58.     # 按SQL中的ORDER BY排序
    
59.     empty_candidates.sort(key=lambda x: (
    
60.         9999 if x['cell_id'] > 2 * width else x['c'],
    
61.         9999 if x['cell_id'] > 2 * width else x['r'],
    
62.         x['cell_id']
    
63.     ))
    
64.    
    
65.     for idx, cell in enumerate(empty_candidates, 1):
    
66.         r = cell['r']
    
67.         c = cell['c']
    
68.         cell_id = cell['cell_id']
    
69.         n_id = cell['n_id']
    
70.         n_r = cell['n_r']
    
71.         n_c = cell['n_c']
    
72.         
    
73.         # 计算邻居ID
    
74.         n1 = n_id - width - 1 if (n_r > 1 and n_c > 1) else 999999
    
75.         n2 = n_id - width if n_r > 1 else 999999
    
76.         n3 = n_id - width + 1 if (n_r > 1 and n_c < width) else 999999
    
77.         n4 = n_id - 1 if n_c > 1 else 999999
    
78.         n6 = n_id + width - 1 if (n_r < height and n_c > 1) else 999999
    
79.         
    
80.         # 计算n_cnt
    
81.         if n_id is None or n_id < 1 or n_id > width * height:
    
82.             n_cnt = 0
    
83.         else:
    
84.             neighbor_char = grid_str[n_id-1]
    
85.             if neighbor_char == '*' or not neighbor_char.strip():
    
86.                 n_cnt = 0
    
87.             else:
    
88.                 n_cnt = int(neighbor_char)
    
89.         
    
90.         # 计算en1, en2, en4
    
91.         en1 = cell_id - width - 1 if (r > 1 and c > 1 and grid_str[cell_id - width - 2] == ' ') else 0
    
92.         en2 = cell_id - width if (r > 1 and grid_str[cell_id - width - 1] == ' ') else 0
    
93.         en4 = cell_id - 1 if (c > 1 and grid_str[cell_id - 2] == ' ') else 0
    
94.         
    
95.         empty_cells.append({
    
96.             **cell,
    
97.             'empty_id': idx,
    
98.             'n1': n1,
    
99.             'n2': n2,
    
100.             'n3': n3,
     
101.             'n4': n4,
     
102.             'n6': n6,
     
103.             'n_cnt': n_cnt,
     
104.             'en1': en1,
     
105.             'en2': en2,
     
106.             'en4': en4
     
107.         })
     
108.    
     
109.     # CTE 4: guess
     
110.     guess = [{'mine': 0}, {'mine': 1}]
     
111.    
     
112.     return {
     
113.         'cells': cells,
     
114.         'cells2': cells2,
     
115.         'empty_cells': empty_cells,
     
116.         'guess': guess
     
117.     }
     
118. 
     
119. def solve_minesweeper(width: int, height: int, grid_str: str, total_mines: int):
     
120.     # 使用之前定义的函数生成基础数据
     
121.     data = sql_to_python(width, height, grid_str)
     
122.     empty_cells = data['empty_cells']
     
123.     guess = data['guess']
     
124.    
     
125.     # 递归基 case
     
126.     recursive_t = [{
     
127.         'm_cnt': 0,
     
128.         'empty_id': 1,
     
129.         'res': grid_str
     
130.     }]
     
131.    
     
132.     max_empty_id = max([ec['empty_id'] for ec in empty_cells]) if empty_cells else 0
     
133.    
     
134.     # 使用循环模拟递归（避免Python递归深度限制）
     
135.     while True:
     
136.         new_rows = []
     
137.         for t in recursive_t:
     
138.             current_empty_id = t['empty_id']
     
139.             if current_empty_id > max_empty_id:
     
140.                 continue
     
141.             
     
142.             # 找到当前empty_id对应的empty_cell
     
143.             current_ec = next((ec for ec in empty_cells if ec['empty_id'] == current_empty_id), None)
     
144.             if not current_ec:
     
145.                 continue
     
146.             
     
147.             # 与guess做笛卡尔积
     
148.             for g in guess:
     
149.                 mine = g['mine']
     
150.                
     
151.                 # 检查WHERE条件
     
152.                 if not (t['m_cnt'] + mine <= total_mines):
     
153.                     continue
     
154.                
     
155.                 # 第一个条件：e.cell_id = 1
     
156.                 if current_ec['cell_id'] == 1:
     
157.                     pass  # 满足条件
     
158.                 else:
     
159.                     # 复杂条件检查
     
160.                     n_cnt = current_ec['n_cnt']
     
161.                     res = t['res']
     
162.                     
     
163.                     # 计算CASE WHEN e.n_cnt = 0...部分
     
164.                     if n_cnt == 0:
     
165.                         case_val = 1 if (current_ec['n_id'] <= len(res) and res[current_ec['n_id'] - 1] == '*') else 0
     
166.                     else:
     
167.                         # 计算各个邻居的雷数
     
168.                         mine_count = 0
     
169.                         for n in ['n1', 'n2', 'n3', 'n4', 'n6']:
     
170.                             n_pos = current_ec[n]
     
171.                             if n_pos <= len(res) and res[n_pos - 1] == '*':
     
172.                                 mine_count += 1
     
173.                         
     
174.                         case_val = 1 if mine_count < n_cnt else 0
     
175.                     
     
176.                     # 检查主条件
     
177.                     if case_val != mine:
     
178.                         continue
     
179.                     
     
180.                     # 检查en1, en2, en4条件
     
181.                     valid = True
     
182.                     for en in ['en1', 'en2', 'en4']:
     
183.                         en_pos = current_ec[en]
     
184.                         if en_pos > 0:
     
185.                             if en_pos > len(res):
     
186.                                 valid = False
     
187.                                 break
     
188.                             en_val = 1 if res[en_pos - 1] == '*' else 0
     
189.                             if en_val != mine:
     
190.                                 valid = False
     
191.                                 break
     
192.                     if not valid:
     
193.                         continue
     
194.                
     
195.                 # 构建新行
     
196.                 new_res = (
     
197.                     t['res'][:current_ec['cell_id'] - 1] +
     
198.                     ('*' if mine == 1 else ' ') +
     
199.                     t['res'][current_ec['cell_id']:]
     
200.                 )
     
201.                
     
202.                 new_rows.append({
     
203.                     'm_cnt': t['m_cnt'] + mine,
     
204.                     'empty_id': current_empty_id + 1,
     
205.                     'res': new_res
     
206.                 })
     
207.         
     
208.         if not new_rows:
     
209.             break
     
210.         
     
211.         # 添加新行到递归表（替换原有内容以模拟递归）
     
212.         recursive_t = new_rows
     
213.    
     
214.     # 筛选最终结果
     
215.     solutions = [t['res'] for t in recursive_t if t['m_cnt'] == total_mines]
     
216.     return solutions
     
217. 
     
218. # 使用示例
     
219. if __name__ == "__main__":
     
220.     width, height,total_mines,grid_str =9,9,27,' 2**2  2* 3**3  3* 3**3  3* 3**3  3* 3**3  3* 3**3  3* 3**3  3* 3**3  3* 2**2  2*'.replace('*', ' ')
     
221. 
     
222.     solutions = solve_minesweeper(width, height, grid_str, total_mines)
     
223.     print(f"找到 {len(solutions)} 个解:")
     
224.     for i, sol in enumerate(solutions, 1):
     
225.         print(f"解 {i}: {sol}")
     

复制代码