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

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

最终达到了这样的效果：

中间我们将一个超难的数独算法耗时由17秒优化到3秒到，有读者提出能否计算数独的逻辑用C++改写进一步提升性能。

完全不会C/C++的我，在找到c语言大佬写的数独算法后，经过几十次尝试，顺利用Python调用了该算法，成功将程序优化到耗时1毫秒以内，下面看看操作流程：

下载gcc编译工具

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

百度云下载地址：
https://pan.baidu.com/s/1ZmjQUf5QcBbeHCi7mIrYxg 提取码: edc5

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

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

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

C语言解数独代码

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

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

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);
}

上述函数，个人不懂c语言，实在不知道如何直接在c的main函数中使用，测试了几十次依然失败，如果有懂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完整代码

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

"""
小小明的代码
CSDN主页：https://blog.csdn.net/as604049322
"""
__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])

原文链接:https://blog.csdn.net/as604049322/article/details/119040450