PostgreSQL 生成任意基数数独 - 4

本文涉及的产品
云原生数据库 PolarDB PostgreSQL 版,企业版 4核16GB
推荐场景:
HTAP混合负载
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
云原生数据库 PolarDB MySQL 版,Serverless 5000PCU 100GB
简介:

标签

PostgreSQL , 数独 , 求解 , 动态规划


背景

使用《PostgreSQL 生成任意基数数独 - 3》 提供的方法,可以生成有解数独。在不知道数独答案的情况下,如何暴力破解呢?

实际上可以修改一下《PostgreSQL 生成任意基数数独 - 2》 里面的随机生成数独的函数,破解数独。

破解数独函数如下

create or replace function resolve_sudoku(      
  vsudoku int[]  -- 求解数独  
) returns int[] as $$      
declare      
  res int[];           -- 结果    
  dims int := array_length(vsudoku,1);   -- X,Y,BOX集合元素个数    
  dim int := sqrt(dims);  -- 基数  
    
  vxyb xyb[];          -- 存储每个像素在XYB方向上未填充的元素个数    
  x int;               -- 从xyb[]集合中,按指定方法选中一个像素。  X坐标    
  y int;               -- 从xyb[]集合中,按指定方法选中一个像素。  Y坐标    
    
  vloops int := 2*dims;     -- 计算N次(实际上就是随机多少次能覆盖到所有的值,值的取值空间为dims,通常来说执行DIMS次,能覆盖到所有的随机数)    
  vloop int :=0;            -- 计算N次计数器    
    
  cnt int := 0;             -- 统计当前数独总共填充了多少个元素    
    
  rand int;                 -- 随机值    
begin      
  -- 求解  
  res := vsudoku;  
        
  loop    
    -- 生成每个像素X,Y,B方向的未知值个数    
    select comp_xyb(res, dim) into vxyb;    
    
    -- 选择下一个要填充的像素(根据未知值个数排行,从总未知值最多,按单轴最多的位置中随机取一个位置)    
    select ax,ay into x,y from     
      unnest(vxyb) t     
    where     
      t.x+t.y+t.b <> 0     
    order by     
      (t.x+t.y+t.b) desc ,     
      greatest(t.x,t.y,t.b) desc     
    limit 1;      
    
    -- 如果全部为0,0,0,说明已解完,返回res。    
    if not found then    
      raise notice '计算有解,计算%次,结束。', cnt;    
      return res;    
    end if;    
    
    -- 初始化以下计算循环次数    
    vloop := 0;    
    loop      
      -- 生成随机值      
      rand := 1+(random()*(dims-1))::int;      
    
      -- 这轮循环无法生成并返回空     
      if vloop >= vloops then      
        raise notice '本像素已循环%次,计算无解。已填充%个元素。无解数独如下: %', vloop, cnt, res;    
	-- return res;    
	return null;    
      end if;      
    
      -- 循环次数+1    
      vloop := vloop+1;      
    
      -- 横向验证      
      perform 1 where array(select res[x][generate_series(1,dims)]) && array[rand];      
      if found then      
        continue;      
      end if;      
            
      -- 纵向验证      
      perform 1 where array(select res[generate_series(1,dims)][y]) && array[rand];      
      if found then      
        continue;      
      end if;      
            
      -- BOX验证      
      perform 1 where     
        array(    
          select res[xx][yy] from     
            (select generate_series(((((x-1)/dim)::int)*dim)+1, ((((x-1)/dim)::int)*dim)+dim) xx) t1,     
            (select generate_series(((((y-1)/dim)::int)*dim)+1, ((((y-1)/dim)::int)*dim)+dim) yy) t2    
        ) && array[rand];      
      if found then      
        continue;      
      end if;      
            
      -- 这个像素值,通过验证      
      res[x][y] := rand;      
      -- raise notice 'res[%][%] %', x, y, rand;      
          
      -- 通过验证并跳出循环,找下一个需要填充的像素    
      cnt := cnt+1;    
      exit;      
    end loop;      
    
  end loop;      
end;    
$$ language plpgsql strict volatile;     

例子

1、首先按难易程度生成几个数独

postgres=# select gen_sudoku_question(20);   
                                                                                  gen_sudoku_question                                                                                    
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
 {{1,6,7,9,5,8,4,3,2},{9,5,8,4,3,2,1,6,7},{4,3,2,1,6,7,9,5,8},{6,7,1,5,8,9,3,2,4},{5,8,9,3,2,4,6,7,1},{3,2,4,6,7,1,5,8,9},{7,1,6,8,9,5,2,4,3},{8,9,5,2,4,3,7,1,6},{2,4,3,7,1,6,8,9,5}}  
 {{1,0,7,9,0,8,4,3,2},{9,0,8,0,3,2,0,6,7},{4,3,2,1,6,7,0,5,8},{6,0,1,0,8,9,0,2,4},{5,0,9,3,2,4,0,7,1},{3,2,0,6,7,1,5,8,9},{7,1,0,0,0,5,0,4,3},{0,9,5,2,4,0,7,1,6},{0,4,3,7,0,6,8,9,5}}  
(2 rows)  
  
postgres=# select gen_sudoku_question(41);   
NOTICE:  relation "tmp_sudoku" already exists, skipping  
                                                                                  gen_sudoku_question                                                                                    
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
 {{5,3,9,2,6,7,1,4,8},{1,4,8,5,3,9,2,6,7},{2,6,7,1,4,8,5,3,9},{9,5,3,7,2,6,8,1,4},{8,1,4,9,5,3,7,2,6},{7,2,6,8,1,4,9,5,3},{3,9,5,6,7,2,4,8,1},{4,8,1,3,9,5,6,7,2},{6,7,2,4,8,1,3,9,5}}  
 {{5,0,0,2,0,7,1,0,8},{0,4,0,0,0,9,0,6,7},{2,0,7,0,0,0,0,0,0},{9,0,3,0,2,6,8,1,4},{0,1,0,0,0,0,7,0,6},{0,0,6,0,0,0,0,5,3},{0,9,0,6,0,2,4,0,1},{4,8,0,0,9,0,6,7,2},{6,0,2,4,0,1,0,0,5}}  
(2 rows)  
  
postgres=# select gen_sudoku_question(51);   
NOTICE:  relation "tmp_sudoku" already exists, skipping  
                                                                                  gen_sudoku_question                                                                                    
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
 {{3,4,5,8,1,6,2,9,7},{8,1,6,2,9,7,3,4,5},{2,9,7,3,4,5,8,1,6},{4,5,3,1,6,8,9,7,2},{1,6,8,9,7,2,4,5,3},{9,7,2,4,5,3,1,6,8},{5,3,4,6,8,1,7,2,9},{6,8,1,7,2,9,5,3,4},{7,2,9,5,3,4,6,8,1}}  
 {{0,4,5,0,0,6,2,9,0},{8,1,0,0,0,0,0,4,0},{2,0,0,3,4,0,8,0,6},{0,0,3,1,6,8,0,0,0},{0,0,8,0,0,0,4,5,0},{0,0,0,4,0,0,1,6,0},{0,0,0,0,0,1,0,0,9},{6,0,0,7,0,0,0,3,4},{0,0,0,0,0,0,0,0,1}}  
(2 rows)  

2、使用上面创建的函数破解数独
填充20个值的数独基本上秒解。

postgres=# select res from (select resolve_sudoku('{{1,0,7,9,0,8,4,3,2},{9,0,8,0,3,2,0,6,7},{4,3,2,1,6,7,0,5,8},{6,0,1,0,8,9,0,2,4},{5,0,9,3,2,4,0,7,1},{3,2,0,6,7,1,5,8,9},{7,1,0,0,0,5,0,4,3},{0,9,5,2,4,0,7,1,6},{0,4,3,7,0,6,8,9,5}}'::int[]) res from generate_series(1,100) ) t where t.res is not null ;  
                                                                                          res                                                                                            
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
 {{1,6,7,9,5,8,4,3,2},{9,5,8,4,3,2,1,6,7},{4,3,2,1,6,7,9,5,8},{6,7,1,5,8,9,3,2,4},{5,8,9,3,2,4,6,7,1},{3,2,4,6,7,1,5,8,9},{7,1,6,8,9,5,2,4,3},{8,9,5,2,4,3,7,1,6},{2,4,3,7,1,6,8,9,5}}  
(1 row)  

但是对于需要填充41个,51个的,这种暴力尝试的方式,跑1000次也解不出来。

还是需要一个非常行之有效的。

目前的暴力破解存在的问题,一个值一旦确定下来(XYB方向满足约束)之后,后面就不会去修正它,从而导致了一个错误后面的计算全是浪费的。增加了破解成本。

扩展

在数据库中执行计划也与之类似,目前大多数执行计划是静态的,一旦执行计划确定下来了,后面就只能按照执行计划执行,无法中途调整。

所以,动态执行计划也成为目前很多数据库优化器突破的方向,在执行过程中,根据执行过程中的统计信息,不断修正执行计划,达到最佳的目的。

实际上,导航也与之类似,如果你根据当前的路况规划好了导航,在行驶过程中,可能某些路段发生了变化(拥堵情况),静态导航就无法修正这样的问题,还是按一开始既定的线路行驶。而动态导航,可以根据实时路况进行修正,选择下一跳。

在生产中有很多类似的例子,比如数据路由,负载均衡等等。

相关实践学习
使用PolarDB和ECS搭建门户网站
本场景主要介绍基于PolarDB和ECS实现搭建门户网站。
阿里云数据库产品家族及特性
阿里云智能数据库产品团队一直致力于不断健全产品体系,提升产品性能,打磨产品功能,从而帮助客户实现更加极致的弹性能力、具备更强的扩展能力、并利用云设施进一步降低企业成本。以云原生+分布式为核心技术抓手,打造以自研的在线事务型(OLTP)数据库Polar DB和在线分析型(OLAP)数据库Analytic DB为代表的新一代企业级云原生数据库产品体系, 结合NoSQL数据库、数据库生态工具、云原生智能化数据库管控平台,为阿里巴巴经济体以及各个行业的企业客户和开发者提供从公共云到混合云再到私有云的完整解决方案,提供基于云基础设施进行数据从处理、到存储、再到计算与分析的一体化解决方案。本节课带你了解阿里云数据库产品家族及特性。
相关文章
|
人工智能 关系型数据库 PostgreSQL
|
17天前
|
存储 关系型数据库 MySQL
探索MySQL:关系型数据库的基石
MySQL,作为全球最流行的开源关系型数据库管理系统(RDBMS)之一,广泛应用于各种Web应用、企业级应用和数据仓库中
|
15天前
|
关系型数据库 MySQL 网络安全
Mysql 数据库主从复制
在MySQL主从复制环境中,配置了两台虚拟机:主VM拥有IP1,从VM有IP2。主VM的`my.cnf`设置server-id为1,启用二进制日志;从VM设置server-id为2,开启GTID模式。通过`find`命令查找配置文件,编辑`my.cnf`,在主服务器上创建复制用户,记录二进制日志信息,然后锁定表并备份数据。备份文件通过SCP传输到从服务器,恢复数据并配置复制源,启动复制。检查复制状态确认运行正常。最后解锁表,完成主从同步,新用户在从库中自动更新。
990 7
Mysql 数据库主从复制
|
15天前
|
缓存 运维 关系型数据库
数据库容灾 | MySQL MGR与阿里云PolarDB-X Paxos的深度对比
经过深入的技术剖析与性能对比,PolarDB-X DN凭借其自研的X-Paxos协议和一系列优化设计,在性能、正确性、可用性及资源开销等方面展现出对MySQL MGR的多项优势,但MGR在MySQL生态体系内也占据重要地位,但需要考虑备库宕机抖动、跨机房容灾性能波动、稳定性等各种情况,因此如果想用好MGR,必须配备专业的技术和运维团队的支持。 在面对大规模、高并发、高可用性需求时,PolarDB-X存储引擎以其独特的技术优势和优异的性能表现,相比于MGR在开箱即用的场景下,PolarDB-X基于DN的集中式(标准版)在功能和性能都做到了很好的平衡,成为了极具竞争力的数据库解决方案。
|
5天前
|
分布式计算 大数据 关系型数据库
MaxCompute产品使用合集之如何实现类似mysql实例中的数据库功能
MaxCompute作为一款全面的大数据处理平台,广泛应用于各类大数据分析、数据挖掘、BI及机器学习场景。掌握其核心功能、熟练操作流程、遵循最佳实践,可以帮助用户高效、安全地管理和利用海量数据。以下是一个关于MaxCompute产品使用的合集,涵盖了其核心功能、应用场景、操作流程以及最佳实践等内容。
|
6天前
|
消息中间件 DataWorks 关系型数据库
DataWorks产品使用合集之遇到无法连接到本地 MySQL 数据库的问题,该如何解决
DataWorks作为一站式的数据开发与治理平台,提供了从数据采集、清洗、开发、调度、服务化、质量监控到安全管理的全套解决方案,帮助企业构建高效、规范、安全的大数据处理体系。以下是对DataWorks产品使用合集的概述,涵盖数据处理的各个环节。
|
8天前
|
SQL Oracle 关系型数据库
MySQL、SQL Server和Oracle数据库安装部署教程
数据库的安装部署教程因不同的数据库管理系统(DBMS)而异,以下将以MySQL、SQL Server和Oracle为例,分别概述其安装部署的基本步骤。请注意,由于软件版本和操作系统的不同,具体步骤可能会有所变化。
35 3
|
21天前
|
关系型数据库 MySQL 数据库
关系型数据库mysql数据增量恢复
【7月更文挑战第3天】
135 2

相关产品

  • 云原生数据库 PolarDB