用PLSQL解数独(SUDOKU)

heixue789

我笨，看了几遍也没搞明白

fengzj

看不懂 收藏了

永远的蓝黑

慢慢研究

vivianpippo

非常感谢，太牛b了。。

newkid

刚刚发现顶楼提到的用MODEL解SUDOKU的牛人Anton Scheffer又推出了11GR2的版本：
http://technology.amis.nl/blog/6 ... -subquery-factoring

with x( s, ind ) as
( select sud, instr( sud, ' ' )
  from ( select '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79' sud from dual )
  union all
  select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
       , instr( s, ' ', ind + 1 )
  from x
     , ( select to_char( rownum ) z
         from dual
         connect by rownum <= 9
       ) z
  where ind > 0
  and not exists ( select null
                   from ( select rownum lp
                          from dual
                          connect by rownum <= 9
                        )
                   where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
                   or    z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
                   or    z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
                                      + trunc( ( ind - 1 ) / 27 ) * 27 + lp
                                      + trunc( ( lp - 1 ) / 3 ) * 6
                                   , 1 )
                 )
)
select s
from x
where ind = 0
/


我没有11GR2, 用如下办法来模拟一下：

CREATE GLOBAL TEMPORARY TABLE SUD (lvl NUMBER,S VARCHAR2(100), IND NUMBER) ON COMMIT PRESERVE ROWS;

CREATE OR REPLACE PROCEDURE P_SUD (p_str IN VARCHAR2)
AS
   v_level NUMBER :=1;
   v_answer VARCHAR2(100);
BEGIN
   DELETE SUD;
   INSERT INTO SUD VALUES(1,p_str,INSTR(p_str,' '));
   LOOP
       INSERT INTO SUD
       select v_level+1
            , substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
            , instr( s, ' ', ind + 1 )
       from SUD
          , ( select to_char( rownum ) z
              from dual
              connect by rownum <= 9
            ) z
       where lvl =v_level AND ind > 0
       and not exists ( select null
                        from ( select rownum lp
                               from dual
                               connect by rownum <= 9
                             )
                        where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
                        or    z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
                        or    z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
                                           + trunc( ( ind - 1 ) / 27 ) * 27 + lp
                                           + trunc( ( lp - 1 ) / 3 ) * 6
                                        , 1 )
                      );
       EXIT WHEN SQL%ROWCOUNT=0;
       v_level := v_level+1;
   END LOOP;
   SELECT s
     INTO v_answer
     FROM sud
    WHERE ind = 0;
   DBMS_OUTPUT.PUT_LINE(v_answer);
END;
/

测试：
EXEC P_SUD('53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79');

输出：
534678912672195348198342567859761423426853791713924856961537284287419635345286179

写法极其简练，他用的是未经优化的穷尽法，因此效率略低，但我不知道在11GR2中表现如何，有环境的可以试一下。

wanglina

[oracle@testdb ~]$ sqlplus /nolog

SQL*Plus: Release 11.2.0.1.0 Production on Thu Jan 7 07:40:46 2010

Copyright (c) 1982, 2009, Oracle.  All rights reserved.

SQL> conn / as sysdba
Connected.
SQL> set lines 120
SQL> with x( s, ind ) as
  2  ( select sud, instr( sud, ' ' )
  3    from ( select '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79' sud from dual )
  4    union all
  5    select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
  6         , instr( s, ' ', ind + 1 )
  7    from x
  8       , ( select to_char( rownum ) z
  9           from dual
10           connect by rownum <= 9
11         ) z
12    where ind > 0
13    and not exists ( select null
                   from ( select rownum lp
14                            from dual
15   16                            connect by rownum <= 9
17                          )
18                     where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
19                     or    z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
20                     or    z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
21                                        + trunc( ( ind - 1 ) / 27 ) * 27 + lp
22                                        + trunc( ( lp - 1 ) / 3 ) * 6
23                                     , 1 )
24                   )
25  )
26  select s
27  from x
28  where ind = 0
29  /

S
------------------------------------------------------------------------------------------------------------------------
534678912672195348198342567859761423426853791713924856961537284287419635345286179

SQL>

wanglina

SQL> set timing on
SQL> /

S
------------------------------------------------------------------------------------------------------------------------
534678912672195348198342567859761423426853791713924856961537284287419635345286179

Elapsed: 00:00:00.90

newkid

谢谢丽娜MM, 我模拟的代码也是差不多1秒。用我前面写的存储过程则只需要0.09秒。

lastwinner

原帖由 newkid 于 08-11-7 03:12 发表
刚刚找到了你的算法描述：



有一点不懂的是第4:
这样的格子必定存在吗？如果找不出来怎么办？
还有，4做完了转2我觉得也不能理解，因为你4所确定的数字A是其它格子中不包含的，它不能帮你再除去任何候选数字。是不是应该一直重复步骤4直到结束?

这个……你当时是在回复我给的blog链接么？
尽管我没找到下面这段话在哪儿出现过

算法见帖子开头：排除法
1、已确定数字的位置直接填该数字，未确定数字的位置可能取值为1～9
2、根据规则将未知格子中的不可能存在的数字除去
3、如果某格子只剩下一个可能数字，则该数字就是此格子的值，并转2；若还剩下多个数字，则转4
4、找出同一行／列／方阵中还有哪些数字未确定，并查找这样的格子，它包含一个其他未确定格子中没有的数字A。如果数字A存在，则A为该格子的值
5、转2，直至每个格子中的数字都已确定

但看样子像是我写的，那我就来回答你当时的疑问吧！

首先要明确一点，人做和机器做，采用的是不同的思路（起码我是这样的，人做就是先确定能确定的格子然后再采用排除法，而机器做则是先将未知格子里都填上可能的数字然后再按规则消去不可能出现的数字）
但殊途同归，最终的结果总是一样的


Q：这样的格子必定存在吗？如果找不出来怎么办？
A：
程序在运行时，是按预先指定的套路去走的，比如对某个格子中的可能数字，记作pList，先按行查找已确定的数字，记作hList，然后从pList中消除在hList中存在的数字
然后再按列查找并消去……，最后按方阵查找并消去……
这样，针对该格子的一轮循环就完成了

假设我们当前按该格子所在行来执行4，在该行其他未确定值的格子都执行了按行、列和方阵的消去后
这时，就可能出现下面的情况，按最简单的，还有三个格子未确定情况，他们的pList分别是
{1,2,4}, {1,2}, {1,2}
后两个格子pList中的4，是在按列查找并消去的环节中消除的
于是就可以判断出，第一个格子中肯定是4而不会是1或者2
如果不按步骤4去做，就仅仅是按行、列和方阵的消去，在每次仅对单一格子进行处理的情况下，是不可能判定第一个格子的值的（人在看到这种情况的时候，很自然会想到第二和第三个格子肯定是其中一个是1另外一个是2，于是第一个格子不会是1和2，于是就只剩下4了。但这是在关联两个格子进行判定的前提下得出的，程序要做到这个程度比较麻烦）



Q：4做完了转2我觉得也不能理解，因为你4所确定的数字A是其它格子中不包含的，它不能帮你再除去任何候选数字。是不是应该一直重复步骤4直到结束?
A：从刚才的描述你其实可以看出，如果4中没找到这样的数字，其实就直接转到第5步了，相当于在第3步中某格子的pList长度大于1，有多个可能数字，然后又直接跳到2了等于这一轮啥事儿都没干。
   其实这是个错觉，在一个格子上没进展，并不代表在其他格子上没进展，就如刚才举的例子，第一个格子已经确定是4，显然，他不能帮助从行中消除任何格子中的候选数字，即其他格子pList中的元素。但是，别忘了，我们还有列和方阵呢，他可以帮助消去这两条路上的多余数字。这样，我们的下一轮循环就有意义了
   当然，我在blog中也提到了，该算法无法解决所有的九宫阵，只能解决有唯一解的。在碰到这种局的时候，很容易可以发现，某一轮循环过后，没有任何的进展，那这时候可以宣布，该九宫阵有多个解。很典型的一个例子就是第一行2、3格和第四行2、3格，pList都是{1,2}
    从单一格子去判定，根本无法确定该格子到底是什么，但实际上，人要碰到了，很容易可以给出两组答案    所以我说，程序里加上尝试算法，就可以解决所有的九宫阵了

lastwinner

原帖由 newkid 于 10-1-7 08:54 发表
谢谢丽娜MM, 我模拟的代码也是差不多1秒。用我前面写的存储过程则只需要0.09秒。

这种事情，单条SQL无疑在理解还是效率上，都不是一个好的选择
太多的无用的中间结果没有去掉而是保留到了最后，这导致了sql效率大大降低