利用OCR和Python自动解决数独谜题的实战指南

本文介绍了如何使用OCR技术识别数独图片并用Python回溯算法求解数独问题。

在文章Python图像处理之图片文字识别（OCR），笔者刚入门学习OCR，并在文章中介绍了OCR的概念和Tesseract工具的使用。

在本文中，笔者将会介绍如何借助OCR技术去识别数独图片，并使用Python求解。因此，本文将会分以下部分来介绍：

• 使用OCR识别数独图片：以表格形式展示，获得每个单元格内的数字（或空白字符）
• 使用回溯法进行数独求解

本文将会着重解法算法部分的实现，因此并不会太注重工程方面的技巧。

OCR识别图片

使用OCR去识别数独图片，并以表格形式将图片中的单元格内容进行展示，如今应当是一项成熟的技术。现在的OCR模型早已能够胜任这项任务，为了避免重复造轮子，笔者使用TextIn OCR服务来实现这项任务。

在通用文字识别页面 https://www.textin.com/product/textin_text 即可开通图片表格识别服务，我们在这里开通免费使用，额度为1000次。在控制台获取对应的API key。

我们选取网络中公开的数独题目，并保存为图片。以下图片来源于网站https://sudoku-cn.com/，题目难度为高级+，如下：

数独题目

我们使用腾讯云OCR服务中的表格识别API来识别该图片，并以嵌套数组的格式输出。

首先需要安装对应的Python模块：pip install tencentcloud-sdk-python-ocr==3.0.1206。

实现Python代码如下：

# -*- coding: utf-8 -*-
# @place: Pudong, Shanghai
# @file: ocr_for_table_reg.py
# @time: 2024/8/7 21:34
import json
import requests


class CommonOcr(object):
    def __init__(self, img_path):
        self._app_id = 'xxx'
        self._secret_code = 'xxx'
        self._img_path = img_path

    @staticmethod
    def get_file_content(file_path):
        with open(file_path, 'rb') as fp:
            return fp.read()

    def recognize(self):
        # 通用表格识别
        url = 'https://api.textin.com/ai/service/v2/recognize/table/multipage'
        head = {}
        try:
            image = self.get_file_content(self._img_path)
            head['x-ti-app-id'] = self._app_id
            head['x-ti-secret-code'] = self._secret_code
            result = requests.post(url, data=image, headers=head)
            return result.json()
        except Exception as e:
            return e

    def run(self):
        tables = self.recognize()['result']['pages'][0]['tables'][0]
        cells = tables['table_cells']
        cell_list = []
        for i in range(9):
            cell_list.append([0] * 9)
        for i, cell in enumerate(cells):
            num = int(cell['text']) if cell['text'].isdigit() else 0
            cell_list[i // 9][i % 9] = num

        # print in table format
        for row in cell_list:
            print(row)

        # save to json file
        with open('sudoku.json', 'w') as f:
            f.write(json.dumps({'result': cell_list}, indent=4))


if __name__ == "__main__":
    ocr = CommonOcr('sudoku2.png')
    ocr.run()

输出结果（即数独题目识别结果）如下：

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

可以看到这81个单元格的内容全部正确，我们将其保存为JSON文件格式，便于后续读取。

Python求解数独

使用回溯法来解决刚才的数独题目，输入为OCR识别后的结果，实现Python代码如下:

# -*- coding: utf-8 -*-
# @place: Pudong, Shanghai
# @file: answer.py
# @time: 2024/8/7 22:22
# Search for a solution
import json
with open('sudoku.json', 'r') as f:
    grid = json.load(f)['result']


# Obtain a list of free cells from the puzzle
def get_free_cell_list(grid):
    free_cell_list = []
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                free_cell_list.append([i, j])

    return free_cell_list


# Check whether grid[i][j] is valid in the grid
def is_valid(i, j, grid):
    # Check whether grid[i][j] is valid at the i's row
    for column in range(9):
        if column != j and grid[i][column] == grid[i][j]:
            return False

    # Check whether grid[i][j] is valid at the j's column
    for row in range(9):
        if row != i and grid[row][j] == grid[i][j]:
            return False

    # Check whether grid[i][j] is valid at the 3-by-3 box
    for row in range((i // 3) * 3, (i // 3) * 3 + 3):
        for col in range((j // 3) * 3, (j // 3) * 3 + 3):
            if row != i and col != j and grid[row][col] == grid[i][j]:
                return False

    return True  # The current value at grid[i][j] is valid


def search(grid):
    free_cell_list = get_free_cell_list(grid)
    number_of_free_cells = len(free_cell_list)
    if number_of_free_cells == 0:
        return True

    k = 0  # Start from the first free cell

    while True:
        i = free_cell_list[k][0]
        j = free_cell_list[k][1]
        if grid[i][j] == 0:
            grid[i][j] = 1

        if is_valid(i, j, grid):
            if k + 1 == number_of_free_cells:
                # no more free cells
                return True  # A solution is found
            else:
                # Move to the next free cell
                k += 1
        elif grid[i][j] < 9:
            # Fill the free cell with the next possible value
            grid[i][j] += 1
        else:
            # grid[i][j] is 9,backtrack
            while grid[i][j] == 9:
                if k == 0:
                    return False  # No possible value
                grid[i][j] = 0  # Reset to free cell
                k -= 1  # Backtrack to the preceding free cell
                i = free_cell_list[k][0]
                j = free_cell_list[k][1]

            # Fill the free cell with the next possible value
            # search continues from this free cell at k
            grid[i][j] += 1


if __name__ == "__main__":
    found_answer = search(grid)
    if found_answer:
        for row in grid:
            print(row)

解答结果如下：

[2, 6, 9, 1, 4, 8, 5, 3, 7]
[4, 8, 1, 7, 3, 5, 9, 6, 2]
[7, 3, 5, 6, 9, 2, 1, 8, 4]
[5, 1, 8, 2, 6, 7, 3, 4, 9]
[3, 7, 6, 9, 1, 4, 8, 2, 5]
[9, 4, 2, 5, 8, 3, 6, 7, 1]
[6, 2, 7, 8, 5, 1, 4, 9, 3]
[1, 9, 4, 3, 7, 6, 2, 5, 8]
[8, 5, 3, 4, 2, 9, 7, 1, 6]

将这些数字回填至页面，回答正确！

总结

在这篇文章中，我们详细探讨了如何使用OCR技术识别数独图片，并使用Python求解数独问题的全过程。首先，我们介绍了OCR的基本概念，并使用TextIn OCR服务实现了数独图片的识别，将图片中的每个单元格内容提取出来，并以嵌套数组的格式展示。接着，我们编写了Python代码，使用回溯法求解OCR识别后的数独题目。

具体步骤如下：

1. OCR识别数独图片： • 使用TextIn OCR服务中的表格识别API，成功识别并提取数独图片中的数字，形成嵌套数组表示的数独题目。 • 将识别结果保存为JSON文件，便于后续读取和处理。
2. Python求解数独： • 使用回溯法（Backtracking）编写Python代码，解决OCR识别后的数独题目。 • 回溯法通过递归和回溯的方式，逐步尝试每个单元格的数字，直至找到解决方案或确定无解。 • 将求解结果打印出来，验证其正确性。

通过这两个主要步骤，我们展示了OCR技术与Python编程在解决实际问题中的强大结合。OCR技术能够快速、准确地将图像中的文本转换为可处理的数据，而Python提供了灵活强大的编程能力来实现各种算法，解决实际问题。

本篇文章为读者提供了从OCR识别到数独求解的完整解决方案，希望能为您的实际应用提供参考和帮助。今后，我们可以进一步优化OCR识别和求解算法，提高识别准确性和求解效率，探索更多实际应用场景。