Python调用C语言实现数独计算逻辑提速100倍

之前我们实现python自动玩数独游戏，详见：《让程序自动玩数独游戏让你秒变骨灰级数独玩家》

链接：https://blog.csdn.net/as/article/details/

最终达到了这样的效果：

中间我们将一个超难的数独，程序计算耗时由17秒优化到3秒，有读者希望将计算数独的逻辑用C++改写一遍重发。

完全不会C/C++的我，想到能否将计算逻辑用C语言或go语言重写后，交给Python调用实现程序性能的进一步优化。经过几十次瞎尝试，顺利用Python调用了c语言编写的计算逻辑，成功将程序优化到耗时1毫秒以内。后面也尝试了python调用go语言，但是不知道如何通过python生成[]byte的splice对象，只好宣步失败，也说明python借助ctypes调用go语言并不是那么随心所欲，还是直接调用c语言来的方便。

下面看看python调用c语言的操作流程：

Python调用c语言

下载gcc编译工具

作为非专业人士用MinGW就够了，官方下载地址是：https://sourceforge.net/projects/mingw-w64/

本人使用的是win10系统，经测试x86_64-8.1.0-release-win32-seh-rt_v6-rev0好使。

下载并解压后，将MinGW的bin目录加入环境变量中：

命令行执行gcc -v出现如下提示后说明安装成功：

C语言解数独代码

编写c语言的解数独的代码：

#include  
     #include  
     #include  
     #include  
     typedef enum __bool { 
    false = 0, true = 1, } bool; int line[9]; int column[9]; int block[3][3]; bool valid; int* spaces[81]; int spacesSize; void flip(int i, int j, int digit) { 
    line[i] ^= (1 << digit); column[j] ^= (1 << digit); block[i / 3][j / 3] ^= (1 << digit); } void dfs(char** board, int pos) { 
    if (pos == spacesSize) { 
    valid = 1; return; } int i = spaces[pos][0], j = spaces[pos][1]; int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff; for (; mask && !valid; mask &= (mask - 1)) { 
    int digitMask = mask & (-mask); int digit = __builtin_ctz(digitMask); flip(i, j, digit); board[i][j] = digit + '0' + 1; dfs(board, pos + 1); flip(i, j, digit); } } void solveSudoku(char** board) { 
    memset(line, 0, sizeof(line)); memset(column, 0, sizeof(column)); memset(block, 0, sizeof(block)); valid = 0; spacesSize = 0; for (int i = 0; i < 9; ++i) { 
    for (int j = 0; j < 9; ++j) { 
    if (board[i][j] != '.') { 
    int digit = board[i][j] - '0' - 1; flip(i, j, digit); } } } while (true) { 
    bool modified = false; for (int i = 0; i < 9; ++i) { 
    for (int j = 0; j < 9; ++j) { 
    if (board[i][j] == '.') { 
    int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff; if (!(mask & (mask - 1))) { 
    int digit = __builtin_ctz(mask); flip(i, j, digit); board[i][j] = digit + '0' + 1; modified = true; } } } } if (!modified) { 
    break; } } for (int i = 0; i < 9; ++i) { 
    for (int j = 0; j < 9; ++j) { 
    if (board[i][j] == '.') { 
    spaces[spacesSize] = malloc(sizeof(int) * 2); spaces[spacesSize][0] = i; spaces[spacesSize++][1] = j; } } } dfs(board, 0); } 

上述函数，未编写main函数直接在c语言中测试，而是在后续python调用中测试通过。若有对c语言感兴趣的童鞋，可以自行编写main函数，直接运行c程序进行测试。

个人使用以下main函数进行测试：

int main() { 
    char *board[] ={ 
    "...6...3.", "5.....6..", ".9...5...", "..4.1...6", "...4.3...", "8...9.5..", "...7...4.", "..5.....8", ".3...8..." }; for(int i=0;i<9;i++) printf ("%s\n",board[i]); solveSudoku((char)board); for(int i=0;i<9;i++) printf ("%s\n",board[i]); return 0; } 

结果程序在solveSudoku的递归调用中直接停止运行，无法得到结果。如果有对c语言编译器比较熟悉的读者，看看能不能给个简单的解决方案。

但神奇的是，后续测试发现Python却能正常调用这个函数，真是神奇，这似乎说明有些c代码无法在纯c的环境中跑，需要在Python等其他高级环境中才能跑？间接性说明Python和c语言可以结合起来一起用，既能享受Python的便捷，又能享受c语言操作内部字节的高效。

下面我们继续操作：

将C代码编译为动态链接库

假设上述代码的文件名是solveSudoku.c，使用如下命令编译：

gcc -shared solveSudoku.c -o solveSudoku.dll 

注意：以上编译命令仅针对Windows平台编译测试通过，Mac平台可能需要-Wl和-fPIC参数

Python调用C语言

准备就绪，现在开始使用python来调用c语言。为了向c函数传入二维char指针，着实让我犯了难。在经过几十次测试后，居然实验成功了一种方法，可能这个方法并不是最优的，但确实已经是一种简单可行的方案。

最终编写的python代码如下：

import time from ctypes import * from pprint import pprint def solveSudoku(board: list): c_char_datas = (c_char_p * 9)() for i in range(9): row_chars = "".join(board[i]).encode('utf-8') c_char_datas[i] = c_char_p(row_chars) solve_sudoku_c = cdll.LoadLibrary('solveSudoku.dll').solveSudoku solve_sudoku_c(c_char_datas) return [list(row.decode()) for row in c_char_datas] board = [ ['.', '.', '.', '6', '.', '.', '.', '3', '.'], ['5', '.', '.', '.', '.', '.', '6', '.', '.'], ['.', '9', '.', '.', '.', '5', '.', '.', '.'], ['.', '.', '4', '.', '1', '.', '.', '.', '6'], ['.', '.', '.', '4', '.', '3', '.', '.', '.'], ['8', '.', '.', '.', '9', '.', '5', '.', '.'], ['.', '.', '.', '7', '.', '.', '.', '4', '.'], ['.', '.', '5', '.', '.', '.', '.', '.', '8'], ['.', '3', '.', '.', '.', '8', '.', '.', '.'] ] start = time.time() pprint(board) board = solveSudoku(board) pprint(board) print(f"耗时：{time.time() - start:.2f}s") 

结果：

[['.', '.', '.', '6', '.', '.', '.', '3', '.'], ['5', '.', '.', '.', '.', '.', '6', '.', '.'], ['.', '9', '.', '.', '.', '5', '.', '.', '.'], ['.', '.', '4', '.', '1', '.', '.', '.', '6'], ['.', '.', '.', '4', '.', '3', '.', '.', '.'], ['8', '.', '.', '.', '9', '.', '5', '.', '.'], ['.', '.', '.', '7', '.', '.', '.', '4', '.'], ['.', '.', '5', '.', '.', '.', '.', '.', '8'], ['.', '3', '.', '.', '.', '8', '.', '.', '.']] [['7', '4', '1', '6', '2', '9', '8', '3', '5'], ['5', '8', '2', '3', '4', '1', '6', '9', '7'], ['3', '9', '6', '8', '7', '5', '4', '2', '1'], ['9', '2', '4', '5', '1', '7', '3', '8', '6'], ['6', '5', '7', '4', '8', '3', '2', '1', '9'], ['8', '1', '3', '2', '9', '6', '5', '7', '4'], ['1', '6', '8', '7', '5', '2', '9', '4', '3'], ['2', '7', '5', '9', '3', '4', '1', '6', '8'], ['4', '3', '9', '1', '6', '8', '7', '5', '2']] 耗时：0.04s 

非常棒，1毫秒内已经完成数独题的解题，比之前用python编写的相同逻辑的代码快了近100倍。

Python调用C进行数独解题的完整代码

那么之前的完整代码可以修改为：

""" 小小明的代码 CSDN主页：https://blog.csdn.net/as """ __author__ = '小小明' __time__ = '2021/7/23 17:09' from ctypes import * from selenium import webdriver from selenium.webdriver.common.by import By from selenium.webdriver.support import expected_conditions as EC from selenium.webdriver.support.ui import WebDriverWait browser = webdriver.Chrome() url = "https://www.sudoku.name/index.php?ln=cn&puzzle_num=&play=1&difficult=4&timer=&time_limit=0" browser.get(url) wait = WebDriverWait(browser, 10) table = wait.until(EC.element_to_be_clickable( (By.CSS_SELECTOR, 'table#sudoku_main_board'))) board = [] for tr in table.find_elements_by_xpath(".//tr"): row = [] for input_e in tr.find_elements_by_xpath(".//input[@class='i3']"): cell = input_e.get_attribute("value") row.append(cell if cell else ".") board.append(row) def solveSudoku(board: list): c_char_datas = (c_char_p * 9)() for i in range(9): row_chars = "".join(board[i]).encode('utf-8') c_char_datas[i] = c_char_p(row_chars) solve_sudoku_c = cdll.LoadLibrary('solveSudoku.dll').solveSudoku solve_sudoku_c(c_char_datas) return [list(row.decode()) for row in c_char_datas] board = solveSudoku(board) for i, tr in enumerate(table.find_elements_by_xpath(".//tr")): for j, input_e in enumerate(tr.find_elements_by_xpath(".//input[@class='i3']")): if input_e.get_attribute("readonly") == "true": continue input_e.click() input_e.clear() input_e.send_keys(board[i][j])