如何利用MySQL解八皇后问题

这篇文章主要介绍“如何利用 MySQL 解八皇后问题”,在日常操作中,相信很多人在如何利用 MySQL 解八皇后问题问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”如何利用 MySQL 解八皇后问题”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

创新互联建站服务项目包括道外网站建设、道外网站制作、道外网页制作以及道外网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,道外网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到道外省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!

前言

在新的公司经常会遇到上百行的 SQL 代码,主要用于进行数据获取与处理,因为公司使用阿里的 ADB,所以希望将数据间简单处理的逻辑都放在 ADB  上进行。这让我适应了一段时间,毕竟之前的经验都是尽量将 SQL 简单化,然后通过代码对获取的数据进行处理,所以我 SQL 功力不强。

SQL 不强,那就学一下,所以在学习的过程中,突然好奇,我是否可以通过 MySQL 来解算法题,这个过程遇到了很多坑,但探究的过程还是很有趣的。

大部分 SQL 语言细节或其他知识,都会在最后的参考小节中给出对应的文章,这些文章是我学习 SQL 语法和解决具体问题的内容。

八皇后

国际象棋中的皇后可以横向、纵向、斜向移动,所谓八皇后问题就是如何在一个 8x8 的棋盘上放置 8 个皇后,使得任意 2  个皇后都不在同一条横线、竖线、斜线方向上,具体如下图所示,图中在棋盘的 (1,1) 位置放置一个皇后,那么图中绿色的部分就不能放置其他皇后。

问题是:8 个皇后在 8x8 的棋盘上可以有多少种放法?

如何利用 MySQL 解八皇后问题

这是一道经典的回溯算法题,回溯算法的本质其实就是通过递归的方式遍历完所有的情况,最终获得所有的情况。

回溯算法的关键如其名,就是做回溯操作,比如某个皇后,尝试了一行中的 8  个格子,都无法满足条件,这就说明此前皇后的放置位置有问题,我们需要回到此前的某次操作并修改那次操作,比如将那次操作的皇后放置到新的位置。

回溯算法很适合用递归的方式去实现,递归的本质是函数帧的出栈与入栈,即栈的出入操作满足回溯的特点。

SQL 的差异

聪明的你在遇到如果通过 MySQL 实现八皇后问题时,肯定会 Google 搜索一下前人的解决方法,遗憾的是,我没有搜索到参考答案,唯一搜索的与 SQL  相关的答案是用 PL/SQL 实现的。

SQL 其实就是一种邻域内语言 (DDL),它有自己的标准,但不同的数据库对这套标准有不同的实现,这与流量器有自己对 Web  标准的实现类似,这让不同数据库之前的 SQL 不能通用。

PL/SQL 是 Oracle 数据库对 SQL 标准的实现,它对标准 SQL 进行了扩展,让其具有过程化编程语言的能力,在 PL/SQL  中,你可以轻松实现数组、循环、判断等操作。

MySQL 也对 SQL 标准有自己的实现,事实是,MySQL 实现的 SQL 相比于 PL/SQL  弱了很多,它更擅长与数据的操作,而不是过程化的程序编程。

我之所以选择 MySQL,有几点原因:

1. 目前没发现有人通过 MySQL 来解八皇后问题,没有参考答案。2.MySQL 的 SQL 语言对过程化支持比较弱,有点挑战。3.MySQL  是大部分程序员都使用的数据库,大家比较熟悉(方便理解我装的 B)。

因为没人弄过,我也不熟悉 MySQL 流程控制相关的语法,所以一开始我是没有把握的,但解决问题的过程才有意思。

为了描述方便,后文以 SQL 表示 MySQL 中的 SQL,以 MySQL 表示数据库。

此外,MySQL 不同版本间的 SQL 实现可能也有所差异,本文使用的 MySQL 版本为 8.0.19,大家可以自行通过 select  version(); 查看自己 MySQL 的版本。

Python 解题

我的解题思路很简单,用一个长度为 8  的列表来存皇后位置,具体而言,列表的下标表示当前皇后所在的行,该下标对应的值则表示该行上皇后所在的列,这样不同的皇后所在的行就不会重复了,所以只需要判断列和斜边是否会冲突。

具体的 Python 代码如下:

num = 0  def is_ok(queen, row):     for r in range(1, row):         # 第 r 行与第 row 行皇后在同一列,冲突         if queen[r] == queen[row]:             return False         t = abs(queen[r] - queen[row])         # 第 r 行与第 row 行皇后在同一斜线,冲突         # 如果 2 个皇后所在位置的行差与列差相同,则在同一斜线         if t == abs(r - row):             return False     return True  def find(queen, row):     global num     # 每一行都从第一列到第八列进行尝试     for col in range(1, (8+1)):         queen[row] = col         # 判断是否满足条件         if is_ok(queen, row):             if row == 8:                 num += 1                 return             # 如果没有到第八行,则继续递归             find(queen, row + 1)  # Python列表下标从0开始,为了从1开始,所以这样 queen = [0,1,2,3,4,5,6,7,8] find(queen, 1) print('result is ', num)

去除注释,代码其实很短。

当然还有更优的解法,大家可以上力扣看看,我看了其 Python 版的代码,我感觉代码太多了...

Python 版的解法有了,后面要做的就是将他翻译成 SQL 的形式,这个过程有蛮多问题的。

没有数组怎么办?

在 MySQL 实现的 SQL 中,是不存在容器类型的变量的,即数组、字典这些在语言层面上不支持,怎么办呢?

通过 Google  搜索,发现大多数人的做法是利用字符串来模拟数组,字符串以逗号作为分割,然后通过字符相关的方法来实现字符串的中元素的查找与更新,具体可以看参考部分给出的文章。

经过试验,我发现这个方式并不好用,在我的 MySQL 上,运行会报语法错误。

简单思考后,我决定使用临时表的方式来解决数组的。

临时表主要用于临时保存一些数据,它的特点是只对创建该表的用户可见,当会话结束上,MySQL  会自动删除临时表,它的优势在于:建表和删表消耗资料都极小,其创建的语法为:

CREATE TEMPORARY TABLE tbl_name(...);

即正常建表语句中加上 TEMPORARY 关键字则可,具体的语句如下。

-- 如果临时表存在,则删除临时表 DROP TABLE IF EXISTS queen; -- id 模仿列表的下标,location 存列表中的值 CREATE TEMPORARY TABLE queen ( id INT, location INT );

看回 Python 的代码,可以发现,默认设置了对应的值。

queen = [0,1,2,3,4,5,6,7,8]

为了模仿这种效果,临时表中也要有对应的默认值,因为 MySQL 中的表其下标是从 1 开始的,所以只需要创建 8  行则可,这里我定义了一个存储过程来实现初始化临时表中值的效果,代码如下:

-- 如果存储过程存在,则删除该PROCEDURE(过程) DROP PROCEDURE IF EXISTS init_queen; -- 定义过程 CREATE PROCEDURE init_queen() BEGIN   -- 声明变量  DECLARE i int DEFAULT 1;  -- 循环  WHILE i <= 8 DO     -- 将值插入表   INSERT INTO queen (id, location) VALUES (i, -1);   SET i = i + 1;  END WHILE; END;

从注释应该可以理解上述 SQL 的逻辑。

需要注意的是,MySQL 的存储过程并不是函数,所谓存储过程只是用户定义一系列 SQL 语句的集合,在遇到需要重复使用的 SQL  语句时,可以将其定义为存储过程,在执行过程中,MySQL 会对其进行相应的优化。

存储过程通过 PROCEDURE 关键字定义,可以接受多个参数,也可以返回多个参数,但没有 return  语句,其返回的值,通过复制给同名参数的形式实现,通过下面的代码应该可以理解我所表达的意思。

因为后续解八皇后算法时会涉及到列表元素的增删改查,所以我封装了多个存储过程来实现对临时表的增删改查。

DROP PROCEDURE IF EXISTS get_queen; -- in_id 为传入参数,out_lcation 为传出参数 CREATE PROCEDURE get_queen(IN in_id INT, OUT out_location INT) BEGIN   -- 通过 id 获得对应的 location,并通过 INTO 关键字将获得的值赋值给 out_location,实现查询结果的返回  SELECT location INTO out_location FROM queen WHERE id=in_id; END;  -- 通过id更新对应的位置 DROP PROCEDURE IF EXISTS update_queen; -- 多个传入参数 CREATE PROCEDURE update_queen(IN in_id INT, IN new_location INT) BEGIN   -- 更新值  UPDATE queen SET location = new_location WHERE id=in_id; END;

看到 get_queen 方法,其返回值的方式是将需返回的值赋值给 out_location 参数,使用示例如下:

-- 通过 CALL 关键字调用存储过程,通过 @ 表示变量,@q1 则是用于接受结果的变量 CALL get_queen(r, @q1);

遗憾的是,临时表在 MySQL 中的支持也是有限的,当你在具体使用时,会出现「Can't reopen table 错误」。

这是 MySQL 特有的问题,即临时表不能重复使用,这个问题存在已久,但已经没有被解决,MariaDB(MySQL  另外一个分支)已经解决这个问题。

一个简单的解决方案是复制临时表。如果表相对较小,则可以很好地工作,临时表通常就是这种情况。

为了避免这个情况,我直接创建普通表,即会落盘到磁盘中,从而避免这个问题。

即将下面代码

DROP TABLE IF EXISTS queen; CREATE TEMPORARY TABLE queen ( id INT, location INT );

修改为:

DROP TABLE IF EXISTS queen; CREATE TABLE queen ( id INT, location INT );

相关的讨论可以看:参考 4

如何打印日志?

使用 Python 时,我们可以通过 print 方法打印一些内容来方便我们判断当前程序执行流程是否正常,那 SQL 中怎么搞?

目前,我在 Navicat 上编写并执行 SQL,经过查询,Navicat 似乎是无法进行 Debug 的,而 MySQL  也不知道打印,这就很蛋疼,毕竟写比较多的 SQL 时,没有日志比较难看出代码中的 Bug。

为了实现查看执行流程,我觉得单独创建一个表来记录日志,然后定义一个存储过程将相关的信息写入表中,从而实现查看执行日志的目的。

-- 创建日志表 DROP TABLE IF EXISTS queen_log; CREATE TABLE queen_log ( id INT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT, log VARCHAR(500) NOT NULL );  -- 定义存储过程 DROP PROCEDURE IF EXISTS add_log; CREATE PROCEDURE add_log(IN in_log VARCHAR(500)) BEGIN   -- 将日志插入到表中  INSERT INTO queen_log (log) VALUES (in_log); END;  CALL add_log('一条日志');

定义判断函数

在 Python 实现中,我们定义了 is_ok 方法来判断当前皇后的落子是否满足条件,这里通过 SQL 将这个方法再实现一遍。

在实现前,需要再次讨论一下存储过程与函数的差异。

在 SQL 中,存储过程必然会将其中的逻辑执行完,不会中途跳出,即没有 return 方法,而函数可以使用 return  方法在执行的过程中退出函数,但函数的局限在于函数只能返回单个结果,而存储过程可以获得多个返回结果。

回顾一下 is_ok 方法,该方法只需返回 True 或 False 单个结果用于表示当前皇后是否可以落子则可,在满足条件时,is_ok 方法直接通过  return 返回。

简单思考一下,可以发现 is_ok 方法更适合于使用 MySQL 的函数去实现。

-- 如果函数之前存在,则删除 DROP FUNCTION IF EXISTS is_ok; -- 定义函数,函数名为 is_ok,函数的输入为 in_row CREATE FUNCTION is_ok(in_row INT) -- 函数是返回值,INT表示返回值的类型,DETERMINISTIC是语法上要求的写法 RETURNS INT DETERMINISTIC -- 函数的注释 COMMENT '判断当前落子位置是否满足条件' BEGIN   -- 声明变量  DECLARE t int DEFAULT -1;  DECLARE r int DEFAULT 1;  WHILE (r <= (in_row - 1))  DO      -- queen 表中存的是col   CALL get_queen(r, @q1);   CALL get_queen(in_row, @q2);   -- 第 r 行与第 in_row 行在同一列上,冲突   IF (@q1 = @q2) THEN      -- 函数返回 -1    RETURN -1;   END IF;      -- 列数相减   SET t = ABS(@q1 - @q2);   -- 第 r 行与第 row 行皇后在同一斜线,冲突   IF (t = ABS(r - in_row)) THEN    RETURN -2;   END IF;  -- 加一  SET r = r + 1;  END WHILE;  RETURN 1; END;

SQL 版 is_ok 函数的实现比较直观,因为我们通过表来实现队列,所以我们不需要将 queen 列表传入,表结构是全局可见的。

递归限制

掌握了 MySQL 流程控制(IF、WHILE 等)、存储过程、函数等用法后,我感觉自己很快就可以用 MySQL 解出八皇后问题了。

很快,我用函数写了 SQL 版的 find 函数,find 函数中使用了 is_ok 函数,然后再回调自身,代码如下:

DROP FUNCTION IF EXISTS find; CREATE FUNCTION find(in_row INT) RETURNS INT DETERMINISTIC COMMENT '判断当前落子位置是否满足条件' BEGIN  DECLARE col int DEFAULT 1;  WHILE col <= 8 DO    CALL get_queen(in_row, @old_location);   CALL update_queen(in_row, col);   -- 满足条件   IF (is_ok(in_row) = 1) THEN    IF (in_row = 8) THEN     SET @num = @num + 1;     -- 满足条件 跳出递归     RETURN 0;    END IF;    -- 尚未查找到第 8 行,第归查找一下行    SET @a = find(in_row+1);   END IF;   -- 还原递归的值   CALL update_queen(in_row, @old_location);   -- 下一次循环   SET col = col + 1;  END WHILE;  RETURN 0; END;

但 MySQL 中,函数是不能回调的... 会出现「Recursive stored functions and triggers are not  allowed 报错」。

此时就陷入了一个困境:

find 之所以用函数是想着满足条件后就直接 return 返回,结果发现函数不支持递归,只能存储过程才支持递归调用。

如果使用存储过程,它没有 return 关键字,在满足条件后,无法通过 return  返回,只能将所有逻辑执行完后,自动结束,这就需要改蛮多代码的。

最后我发现了 LEAVE 关键字,该关键字主要用于跳出 WHILE 循环,类似于 Python 中的 break  关键字,利用这个方法,在满足条件时,我直接跳出 find 方法的主循环,从而达到 return 返回的效果。

find 最终的代码如下:

SET @num := 0; -- 设置递归查询的层深上限 SET max_sp_recursion_depth = 500;  -- 计算八皇后可能的结果 DROP PROCEDURE IF EXISTS find; CREATE PROCEDURE find(IN in_row INT) BEGIN  DECLARE col INT DEFAULT 1;  -- 添加日志  CALL add_log('find procedure is running.');  -- 循环处,有 loop1 标识  loop1:WHILE col <= 8 DO    CALL get_queen(in_row, @old_location);   CALL update_queen(in_row, col);   -- 满足条件   SET @res = is_ok(in_row);   -- 添加日志   CALL add_log(CONCAT('is_ok running, in_row: ', in_row, ' col: ', col, ' res: ', @res));   IF (@res = 1) THEN    IF (in_row = 8) THEN     SET @num = @num + 1;     CALL add_log(CONCAT('num is: ', @num));     -- 满足条件 跳出递归     LEAVE loop1;    END IF;    -- 未到第 8 行,继续递归    CALL find(in_row+1);    -- 还原递归的值    CALL update_queen(in_row, @old_location);   END IF;   -- 下一次循环   SET col = col + 1;  -- 循环处,有 loop1 标识  END WHILE loop1; END;

还需要注意的一点是,MySQL 对递归深度是有较严格限制的,所以我们需要设置一下 max_sp_recursion_depth。

-- 设置递归查询的层深上限 SET max_sp_recursion_depth = 500;

实现过程中遇到的问题与解决方案。

Not allowed to return a result set from a function 错误

该错误表明:不允许从函数返回结果集。

即你定义的函数中,不能使用 SELECT 打印数据,MySQL 会认为在方法中打印数据是要返回相关的结果集。

Recursive stored functions and triggers are not allowed 报错

MySQL 的方法不支持递归调用,但存储过程可以。

Recursive limit 0 报错

需要修改 max_sp_recursion_depth。

这个修改涉及到全局和 session 级修改, 全局修改的话 需要 有 super 权限:set global  max_sp_recursion_depth=2, session 级修改的话只对当前连接有效,不需要加 global。

Thread stack overrun 错误

错误原因:

thread_stack 太小,默认 128K。

通过下面命令可以查看

mysql> show variables like '%thread%'; +-----------------------------------------+---------------------------+ | Variable_name                           | Value                     | +-----------------------------------------+---------------------------+ | create_admin_listener_thread            | OFF                       | | innodb_parallel_read_threads            | 4                         | | thread_handling                         | one-thread-per-connection | | thread_stack                            | 286720                    | +-----------------------------------------+---------------------------+ 18 rows in set (0.02 sec)  删除的部分无关内容,减少展示

看到其中的 thread_stack 为 286720 Bytes 即 280KB。

最终结果

将上面的代码整理在一起,就获得了最终的 SQL 代码,完整代码如下:

DROP TABLE IF EXISTS queen; CREATE TABLE queen ( id INT, location INT );  DROP TABLE IF EXISTS queen_log; CREATE TABLE queen_log ( id INT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT, log VARCHAR(500) NOT NULL );  DROP PROCEDURE IF EXISTS add_log; CREATE PROCEDURE add_log(IN in_log VARCHAR(500)) BEGIN  INSERT INTO queen_log (log) VALUES (in_log); END;  DROP PROCEDURE IF EXISTS init_queen; CREATE PROCEDURE init_queen() BEGIN  DECLARE i int DEFAULT 1;  WHILE i <= 8 DO   INSERT INTO queen (id, location) VALUES (i, i);   SET i = i + 1;  END WHILE; END;  DROP PROCEDURE IF EXISTS get_queen; CREATE PROCEDURE get_queen(IN in_id INT, OUT out_location INT) BEGIN  SELECT location INTO out_location FROM queen WHERE id=in_id; END;  DROP PROCEDURE IF EXISTS update_queen; CREATE PROCEDURE update_queen(IN in_id INT, IN new_location INT) BEGIN  UPDATE queen SET location = new_location WHERE id=in_id; END;  DROP FUNCTION IF EXISTS is_ok; CREATE FUNCTION is_ok(in_row INT) RETURNS INT DETERMINISTIC COMMENT '判断当前落子位置是否满足条件' BEGIN  DECLARE t int DEFAULT -1;  DECLARE r int DEFAULT 1;  WHILE (r <= (in_row - 1))  DO   CALL get_queen(r, @q1);   CALL get_queen(in_row, @q2);   IF (@q1 = @q2) THEN    RETURN -1;   END IF;   SET t = ABS(@q1 - @q2);   IF (t = ABS(r - in_row)) THEN    RETURN -2;   END IF;  SET r = r + 1;  END WHILE;  RETURN 1; END;   SET @num := 0; SET max_sp_recursion_depth = 500;  -- 计算八皇后可能的结果 DROP PROCEDURE IF EXISTS find; CREATE PROCEDURE find(IN in_row INT) BEGIN  DECLARE col INT DEFAULT 1;  CALL add_log('find procedure is running.');  loop1:WHILE col <= 8 DO    CALL get_queen(in_row, @old_location);   CALL update_queen(in_row, col);   SET @res = is_ok(in_row);   CALL add_log(CONCAT('is_ok running, in_row: ', in_row, ' col: ', col, ' res: ', @res));   IF (@res = 1) THEN    IF (in_row = 8) THEN     SET @num = @num + 1;     CALL add_log(CONCAT('num is: ', @num));     LEAVE loop1;    END IF;    CALL find(in_row+1);    CALL update_queen(in_row, @old_location);   END IF;   SET col = col + 1;  END WHILE loop1; END;  CALL init_queen(); CALL find(1); SELECT @num;

如果比较难理解,可以看回文中讲解代码时的注释。

最终效果如下:

如何利用 MySQL 解八皇后问题

执行日志:

如何利用 MySQL 解八皇后问题

查询计算过程:

如何利用 MySQL 解八皇后问题

对了,这个程序大概运行了 2.9 分钟,非常的慢,可能是递归过程中涉及了大量 INSERT 操作。

到此,关于“如何利用 MySQL 解八皇后问题”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!


分享题目:如何利用MySQL解八皇后问题
网页链接:http://scyanting.com/article/jhdhje.html