如何利用 MySQL 解八皇后問題

這篇文章主要介紹“如何利用 MySQL 解八皇后問題”，在日常操作中，相信很多人在如何利用 MySQL 解八皇后問題問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”如何利用 MySQL 解八皇后問題”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

前言

在新的公司經常會遇到上百行的 SQL 代碼，主要用于進行數據獲取與處理，因為公司使用阿里的 ADB，所以希望將數據間簡單處理的邏輯都放在 ADB  上進行。這讓我適應了一段時間，畢竟之前的經驗都是盡量將 SQL 簡單化，然后通過代碼對獲取的數據進行處理，所以我 SQL 功力不強。

SQL 不強，那就學一下，所以在學習的過程中，突然好奇，我是否可以通過 MySQL 來解算法題，這個過程遇到了很多坑，但探究的過程還是很有趣的。

大部分 SQL 語言細節或其他知識，都會在最后的參考小節中給出對應的文章，這些文章是我學習 SQL 語法和解決具體問題的內容。

八皇后

國際象棋中的皇后可以橫向、縱向、斜向移動，所謂八皇后問題就是如何在一個 8x8 的棋盤上放置 8 個皇后，使得任意 2  個皇后都不在同一條橫線、豎線、斜線方向上，具體如下圖所示，圖中在棋盤的 (1,1) 位置放置一個皇后，那么圖中綠色的部分就不能放置其他皇后。

問題是：8 個皇后在 8x8 的棋盤上可以有多少種放法?

這是一道經典的回溯算法題，回溯算法的本質其實就是通過遞歸的方式遍歷完所有的情況，最終獲得所有的情況。

回溯算法的關鍵如其名，就是做回溯操作，比如某個皇后，嘗試了一行中的 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;

如果比較難理解，可以看回文中講解代碼時的注釋。

最終效果如下：

執行日志：

查詢計算過程：

對了，這個程序大概運行了 2.9 分鐘，非常的慢，可能是遞歸過程中涉及了大量 INSERT 操作。

到此，關于“如何利用 MySQL 解八皇后問題”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！