PostgreSQL 生成任意基数数独 - 2

本文涉及的产品
云原生数据库 PolarDB PostgreSQL 版,企业版 4核16GB
推荐场景:
HTAP混合负载
云原生数据库 PolarDB 分布式版,标准版 2核8GB
云原生数据库 PolarDB MySQL 版,Serverless 5000PCU 100GB
简介:

标签

PostgreSQL , 数独


背景

《PostgreSQL 生成任意基数数独 - 1》 提供了一种方法,计算一个未完成的数独矩阵每个像素在XYB方向上还有多少个未填充的像素。

通过XYB的值,进行各种排序,选出下一个要填充的像素,进行随机填充。

可以通过调整规则,实现不同的填充位置选择,从而达到生成可解数独的目的。

创建一个生成以N为基数的数独的函数

函数输入条件为N(基数),例如81个像素的数独,基数为3。(3*3)平方。

返回一个数独(如果无解的话,raise出来).

create or replace function gen_sudoku(    
  dim int  -- 基数    
) returns int[] as $$    
declare    
  res int[];           -- 结果  
  dims int := dim^2;   -- X,Y,BOX集合元素个数  
  
  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    
  
  -- 初始化矩阵    
  select array( select (select array_agg(0) from generate_series(1,dims)) from generate_series(1,dims)) into res;    
      
  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、生成基数为2的数独,16个像素。

postgres=# select sudo from (select gen_sudoku(2) as sudo from generate_series(1,50)) t where sudo is not null limit 1;  
NOTICE:  计算有解,计算16次,结束。  
                   sudo                      
-------------------------------------------  
 {{3,4,2,1},{2,1,4,3},{1,2,3,4},{4,3,1,2}}  
(1 row)  
  
Time: 30.798 ms  

2、生成基数为3的数独,81个像素。

但是非常的遗憾,填充个数50个左右,后面就没法符合速度条件进行填充了。

postgres=# select sudo from (select gen_sudoku(3) as sudo from generate_series(1,10)) t where sudo is not null limit 1;  
NOTICE:  本像素已循环18次,计算无解。已填充45个元素。无解数独如下: {{5,3,6,2,0,0,0,8,0},{0,9,0,5,8,4,6,0,0},{7,0,0,6,0,0,5,2,4},{6,4,5,3,0,0,0,9,0},{0,8,0,9,7,5,0,4,0},{1,0,0,0,2,0,3,7,8},{0,7,4,0,5,6,0,0,3},{0,0,3,0,1,2,8,0,5},{9,0,8,0,0,3,4,0,6}}  
NOTICE:  本像素已循环18次,计算无解。已填充46个元素。无解数独如下: {{8,3,9,2,4,0,0,5,0},{0,2,0,6,3,9,8,0,0},{1,0,0,5,0,0,4,7,6},{7,8,2,3,0,0,0,1,0},{0,9,0,4,2,6,0,8,0},{3,0,0,0,8,0,5,4,7},{0,4,7,0,1,5,0,0,8},{0,0,6,0,7,4,2,0,3},{5,0,8,0,0,3,7,0,1}}  
NOTICE:  本像素已循环18次,计算无解。已填充49个元素。无解数独如下: {{8,4,6,1,9,0,0,2,0},{9,2,0,7,5,6,8,0,0},{3,0,0,4,0,0,1,5,6},{5,7,3,2,0,1,0,4,0},{0,9,4,3,8,7,0,1,0},{6,0,0,0,4,0,3,9,8},{0,5,8,0,6,4,0,0,7},{0,0,1,0,3,2,5,0,4},{4,0,2,0,0,5,6,0,1}}  
NOTICE:  本像素已循环18次,计算无解。已填充45个元素。无解数独如下: {{6,8,2,3,0,0,0,4,0},{0,5,0,7,2,1,9,0,0},{7,0,0,9,0,0,1,5,3},{1,3,4,6,0,0,0,9,0},{0,9,0,8,1,3,0,6,0},{8,0,0,0,4,0,3,2,7},{0,2,7,0,5,6,0,0,4},{0,0,9,0,8,2,7,0,5},{4,0,3,0,0,7,8,0,2}}  
NOTICE:  本像素已循环18次,计算无解。已填充45个元素。无解数独如下: {{1,6,7,9,0,0,0,5,0},{0,2,0,4,3,8,7,0,0},{4,0,0,5,0,0,8,6,3},{3,5,8,7,0,0,0,2,0},{0,7,0,1,2,6,0,3,0},{6,0,0,0,9,0,5,4,1},{0,8,1,0,5,2,0,0,4},{0,0,5,0,7,3,6,0,2},{2,0,4,0,0,1,9,0,8}}  
NOTICE:  本像素已循环18次,计算无解。已填充50个元素。无解数独如下: {{2,3,5,6,9,0,0,7,0},{6,7,0,2,8,4,1,0,0},{4,0,0,7,0,0,9,8,5},{1,4,7,3,0,8,0,5,0},{0,9,3,5,7,6,0,4,0},{5,0,0,0,4,0,2,6,3},{0,2,8,4,3,7,0,0,1},{0,0,1,0,6,5,3,0,2},{3,0,6,0,0,2,8,0,7}}  
NOTICE:  本像素已循环18次,计算无解。已填充46个元素。无解数独如下: {{2,6,7,9,5,0,0,8,0},{0,5,0,2,4,1,3,0,0},{1,0,0,6,0,0,4,5,7},{8,7,9,4,0,0,0,3,0},{0,1,0,3,2,6,0,4,0},{3,0,0,0,8,0,6,2,9},{0,3,5,0,1,7,0,0,2},{0,0,8,0,6,3,9,0,5},{4,0,6,0,0,9,8,0,1}}  
NOTICE:  本像素已循环18次,计算无解。已填充29个元素。无解数独如下: {{4,3,2,5,0,0,0,0,0},{0,0,0,6,8,7,0,0,0},{0,0,0,0,0,0,1,9,4},{6,5,0,4,0,0,0,7,0},{0,1,0,8,3,0,0,0,0},{2,0,0,0,0,0,3,5,0},{0,0,3,0,0,8,0,0,5},{0,0,4,0,5,9,0,0,0},{9,0,0,0,0,0,2,0,3}}  
NOTICE:  本像素已循环18次,计算无解。已填充46个元素。无解数独如下: {{4,8,3,5,9,0,0,1,0},{0,5,0,7,4,1,2,0,0},{1,0,0,2,0,0,7,3,8},{9,6,8,3,0,0,0,4,0},{0,2,0,4,1,5,0,7,0},{7,0,0,0,8,0,3,5,6},{0,4,9,0,5,3,0,0,7},{0,0,2,0,7,6,5,0,3},{6,0,7,0,0,4,8,0,2}}  
NOTICE:  本像素已循环18次,计算无解。已填充56个元素。无解数独如下: {{5,6,3,8,4,0,7,2,0},{4,2,0,9,7,1,5,0,0},{8,9,0,2,0,0,1,4,3},{3,7,5,4,0,9,0,6,2},{0,4,9,1,2,8,0,5,0},{2,0,6,0,5,0,9,3,8},{0,3,2,5,1,7,0,0,6},{0,5,8,0,6,4,3,0,9},{6,0,1,0,0,3,4,8,7}}  
 sudo   
------  
(0 rows)  
  
Time: 1037.195 ms (00:01.037)  

调整选取填充像素的方法

1、从各维度冲突最大的开始填充

    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) ,   
      greatest(t.x,t.y,t.b)    
    limit 1;    

使用这种选择像素的方法,从填充像素个数来看,很快就会发现无解,因为冲突最大化了。

NOTICE:  本像素已循环18次,计算无解。已填充35个元素。无解数独如下: {{5,7,2,4,6,3,1,8,9},{8,1,4,5,7,9,2,3,6},{6,9,3,2,8,1,5,4,7},{9,4,6,0,0,0,0,0,0},{3,5,7,0,0,0,0,0,0},{1,8,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}  
NOTICE:  本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{1,2,6,7,9,8,0,0,0},{3,8,4,1,5,2,0,0,0},{5,7,9,4,6,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}  
NOTICE:  本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{1,2,5,9,3,4,0,0,0},{7,9,6,2,1,8,0,0,0},{3,8,4,6,5,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}  
NOTICE:  本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{7,5,6,8,4,9,0,0,0},{4,3,8,5,2,6,0,0,0},{2,1,9,7,3,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}  
NOTICE:  本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{7,2,6,9,5,3,0,0,0},{3,4,1,6,8,2,0,0,0},{5,8,9,7,4,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}  
NOTICE:  本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{8,3,7,6,4,2,0,0,0},{1,6,5,8,9,3,0,0,0},{4,9,2,7,5,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}  
NOTICE:  本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{8,7,4,9,6,5,0,0,0},{3,5,2,7,4,8,0,0,0},{1,6,9,2,3,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}  
NOTICE:  本像素已循环18次,计算无解。已填充8个元素。无解数独如下: {{7,4,5,0,0,0,0,0,0},{9,3,2,0,0,0,0,0,0},{8,6,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}  
NOTICE:  本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{3,6,7,5,1,8,0,0,0},{5,1,2,9,6,3,0,0,0},{4,8,9,7,2,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}  
NOTICE:  本像素已循环18次,计算无解。已填充8个元素。无解数独如下: {{3,2,8,0,0,0,0,0,0},{7,4,9,0,0,0,0,0,0},{6,5,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}  
 sudo   
------  
(0 rows)  
  
Time: 486.963 ms  

2、你还可与根据其他的想法来选择每次需要填充的像素。

从BOX维度冲突最小,x,y维度冲突最小的像素开始填充

    select ax,ay into x,y from   
      unnest(vxyb) t   
    where   
      t.x+t.y+t.b <> 0   
    order by   
      t.b desc ,   
      greatest(t.x,t.y)  desc  
    limit 1;    

小结

暂时使用这几种方法,经过少量的计算,无法生成有解的数独。

1、选择下一个要填充的像素(根据未知值个数排行,从总未知值最多,按单轴最多的位置中随机取一个位置)

2、从BOX维度冲突最小,x,y维度冲突最小的像素开始填充

3、从各维度冲突最大的开始填充

随机的方法生成数独,效率比较低,维度越高,生成成功的概率越低。需要寻找更高效的生成数独的方法。

参考

NP完全问题近似求解。

《PostgreSQL 生成任意基数数独 - 1》

《PostgreSQL 生成任意基数数独 - 2》

《PostgreSQL 生成任意基数数独 - 3》

相关实践学习
使用PolarDB和ECS搭建门户网站
本场景主要介绍基于PolarDB和ECS实现搭建门户网站。
阿里云数据库产品家族及特性
阿里云智能数据库产品团队一直致力于不断健全产品体系,提升产品性能,打磨产品功能,从而帮助客户实现更加极致的弹性能力、具备更强的扩展能力、并利用云设施进一步降低企业成本。以云原生+分布式为核心技术抓手,打造以自研的在线事务型(OLTP)数据库Polar DB和在线分析型(OLAP)数据库Analytic DB为代表的新一代企业级云原生数据库产品体系, 结合NoSQL数据库、数据库生态工具、云原生智能化数据库管控平台,为阿里巴巴经济体以及各个行业的企业客户和开发者提供从公共云到混合云再到私有云的完整解决方案,提供基于云基础设施进行数据从处理、到存储、再到计算与分析的一体化解决方案。本节课带你了解阿里云数据库产品家族及特性。
相关文章
|
人工智能 关系型数据库 PostgreSQL
|
16天前
|
存储 关系型数据库 MySQL
探索MySQL:关系型数据库的基石
MySQL,作为全球最流行的开源关系型数据库管理系统(RDBMS)之一,广泛应用于各种Web应用、企业级应用和数据仓库中
|
14天前
|
关系型数据库 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 数据库主从复制
|
14天前
|
缓存 运维 关系型数据库
数据库容灾 | MySQL MGR与阿里云PolarDB-X Paxos的深度对比
经过深入的技术剖析与性能对比,PolarDB-X DN凭借其自研的X-Paxos协议和一系列优化设计,在性能、正确性、可用性及资源开销等方面展现出对MySQL MGR的多项优势,但MGR在MySQL生态体系内也占据重要地位,但需要考虑备库宕机抖动、跨机房容灾性能波动、稳定性等各种情况,因此如果想用好MGR,必须配备专业的技术和运维团队的支持。 在面对大规模、高并发、高可用性需求时,PolarDB-X存储引擎以其独特的技术优势和优异的性能表现,相比于MGR在开箱即用的场景下,PolarDB-X基于DN的集中式(标准版)在功能和性能都做到了很好的平衡,成为了极具竞争力的数据库解决方案。
|
4天前
|
分布式计算 大数据 关系型数据库
MaxCompute产品使用合集之如何实现类似mysql实例中的数据库功能
MaxCompute作为一款全面的大数据处理平台,广泛应用于各类大数据分析、数据挖掘、BI及机器学习场景。掌握其核心功能、熟练操作流程、遵循最佳实践,可以帮助用户高效、安全地管理和利用海量数据。以下是一个关于MaxCompute产品使用的合集,涵盖了其核心功能、应用场景、操作流程以及最佳实践等内容。
|
7天前
|
SQL Oracle 关系型数据库
MySQL、SQL Server和Oracle数据库安装部署教程
数据库的安装部署教程因不同的数据库管理系统(DBMS)而异,以下将以MySQL、SQL Server和Oracle为例,分别概述其安装部署的基本步骤。请注意,由于软件版本和操作系统的不同,具体步骤可能会有所变化。
28 3
|
20天前
|
XML Java 关系型数据库
Action:Consider the following: If you want an embedde ,springBoot配置数据库,补全springBoot的xml和mysql配置信息就好了
Action:Consider the following: If you want an embedde ,springBoot配置数据库,补全springBoot的xml和mysql配置信息就好了
|
20天前
|
关系型数据库 MySQL 数据库
关系型数据库mysql数据增量恢复
【7月更文挑战第3天】
134 2

相关产品

  • 云原生数据库 PolarDB