Chào mọi người mình là Dũng đến từ team AI VTI-VN!

Vậy là đã đến tuần cách ly thứ 4 rồi. Hôm nay chính phủ Hà Nội đã làm căng hơn so với những tuần trước. Hy vọng mọi chuyện sẽ ổn.

Có lẽ trong thời gian giãn cách như thế này là khoảng thời gian mà mình chơi game nhiều nhất (do quá rảnh rỗi mà).

Về game mình chơi thì có nhiều trò cổ điển như caro, dò mìn,... tuy nhiên có những trò làm mình cay cú rất nhiều - sudoku. và mình tự hỏi là liệu máy tính có thể tự giải giúp mình trò chơi này hay không.

Nói qua về sudoku theo wiki nhé: Sudoku (数独 (số độc) sūdoku?), ban đầu có tên gọi là Number Place là một trò chơi câu đố sắp xếp chữ số dựa trên logic theo tổ hợp.Mục tiêu của trò chơi là điền các chữ số vào một lưới 9×9 sao cho mỗi cột, mỗi hàng, và mỗi phần trong số chín lưới con 3×3 cấu tạo nên lưới chính (cũng gọi là "hộp", "khối", hoặc "vùng") đều chứa tất cả các chữ số từ 1 tới 9. Câu đố đã được hoàn thành một phần, người chơi phải giải tiếp bằng việc điền số. Mỗi câu đố được thiết lập tốt có một cách làm duy nhất.

Luật chơi rất đơn giản đúng không. Giải thuật của mình có lẽ là tìm hàng, cột nhiều chữ nhất và tìm những số còn thiếu trong hàng hay cột đó và làm tương tự với các cột còn lại. Tuy nhiên mình phải có khá nhiều giả thiết để giải. Và đôi khi giải một nửa mình đã quên mất mình đã giả định cái gì mất rồi =)).Chắc có lẽ mình là người lười động não nên mình đã nhờ máy tính giải quyết giúp mình trò chơi này luôn 😀

Cách mình tạo chương trình của mình như sau:
Input: ảnh trò chơi sudoku (9x9)
output: ảnh input có điền các số còn thiếu

Cách thực hiện:

• Tạo các template có sẵn của các chữ số trong sudoku.
• Tiền xử lý ảnh đầu vào.
• Dùng thuật toán Template Matching tìm số có trong ảnh.
• Giải quyết bài toán sudoku.
• Hậu xử lý.

Mô tả ảnh đầu vào và đầu ra:

Khá đơn giản đúng không nào. Hãy cùng mình đi đến hết bài blog nhé!!!!

1. Tạo các template có sẵn của các chữ số trong sudoku.

Các template ở đây là các hình ảnh chứa chữ số bao gồm từ 0-9 của hình ảnh. Mỗi số chỉ cần 1 bức ảnh.
Ở đây mình đã cắt sẵn nên chỉ cần lấy về và dùng thôi.
Các template:

2. Tiền xử lý ảnh đầu vào.

Do đây chỉ là bài toán hết sức đơn giản(vì không có yếu tố môi trường bên ngoài) mình chỉ cần các bước như sau:

• Chuyển về ảnh đen trắng.
• Tìm các ô trong ảnh input.

code:

img = cv2.imread(in_file)
gray= cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
ret,thresh1 = cv2.threshold(gray,225,255,cv2.THRESH_BINARY_INV)

contours, hierarchy = cv2.findContours(thresh1,cv2.RETR_LIST , cv2.CHAIN_APPROX_NONE)
contours = sorted(contours, key=cv2.contourArea,reverse=True )[1:82]
contours = sorted(contours, key=lambda ctr: cv2.boundingRect(ctr)[0] + cv2.boundingRect(ctr)[1] * img.shape[1])

img0 = img.copy()
cv2.drawContours(img0,contours, -1, (0,255,0), 3)
cv2.imshow('img0', img0)

arr = []
for j, contour in enumerate(contours):
    x, y, w, h = cv2.boundingRect(contour)
    arr.append([x,y])

giải thích:
Đọc và chuyển ảnh về ảnh Gray.

img = cv2.imread(in_file)
gray= cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
ret,thresh1 = cv2.threshold(gray,225,255,cv2.THRESH_BINARY_INV)

Tìm các ô có ở trong ảnh sau đó sắp xếp các ô từ trên xuống dưới, từ trái qua phải.

contours, hierarchy = cv2.findContours(thresh1,cv2.RETR_LIST , cv2.CHAIN_APPROX_NONE)
contours = sorted(contours, key=cv2.contourArea,reverse=True )[1:82]
contours = sorted(contours, key=lambda ctr: cv2.boundingRect(ctr)[0] + cv2.boundingRect(ctr)[1] * img.shape[1])

arr = []
for j, contour in enumerate(contours):
    x, y, w, h = cv2.boundingRect(contour)
    arr.append([x,y])

Kết quả:
Mình đã tô màu xanh lá cây cho dễ nhìn.

3. Dùng thuật toán Template Matching tìm số có trong ảnh.

Dùng thuật toán Template Matching để tìm các ảnh template trên ảnh đầu ra ở bước 2.
Điền các số có sẵn vào ma trận (9x9).

code:

img1 = img.copy()
arr_matrix = np.zeros((9,9))
img1 = img.copy()
for j in range(1, 10):
    template = cv2.imread(os.path.join("data", f"match{j}.png"),0)
    w, h = template.shape[::-1]

    res = cv2.matchTemplate(thresh1,template,cv2.TM_CCOEFF_NORMED)
    threshold = 0.8
    loc = np.where( res >= threshold)
    for pt in zip(*loc[::-1]):
        # print(pt)
        # cv2.rectangle(img1, pt, (pt[0] + w, pt[1] + h), (0,0,255), 2)
        cv2.putText(img1, "{}".format(j), (pt[0], pt[1]+30), cv2.FONT_HERSHEY_SIMPLEX, 1, 
            (0, 0, 255), 2);
        distance = distance_matrix([[pt[0], pt[1]]],arr)
        x,y = np.unravel_index(np.argmin(distance),arr_matrix.shape)
        arr_matrix[x][y] = j
cv2.imshow('img1', img1)

giải thích:
template = cv2.imread(os.path.join("data", f"match{j}.png"),0) Đọc các bức ảnh template và chuyển sang màu xám.
res = cv2.matchTemplate(thresh1,template,cv2.TM_CCOEFF_NORMED) Dùng để tìm các bức ảnh template có trong bức ảnh ban đầu. Kết quả trả ra là các hộp(x,y,w,h) có chứa ảnh template.
distance = distance_matrix([[pt[0], pt[1]]],arr) Hàm tìm khoảng cách từ (pt[0],pt[1]) đến tất cả các ô trong arr mục đích là tìm xem ảnh template đó nằm ở đâu trong ma trận (9x9).

Kết quả :

Mình đã điền các số từ template matching vào các ô ảnh gốc - ma trận 9x9 tượng trưng bằng chữ màu đỏ

4. Giải quyết bài toán sudoku

Vậy là mình đã xong phần xử lý ảnh, chúng ta đã có ma trận chứa các số có sẵn. Giờ chỉ cần tìm các số còn thiếu nghe có vẻ đơn giản nhỉ =)). Nhưng thật ra cũng đơn giản thật. Cho đến hiện tại thì cách đơn giản nhất vẫn là tạo các tổ hợp có thể xảy ra và kiểm tra kết quả có hợp lệ hay không. Tìm được kết quả hợp lệ là xong.

Thuật toán mình sử dụng là backtracking nhé

code:

def find_empty_location(arr, l): 
    for row in range(9): 
        for col in range(9): 
            if(arr[row][col]== 0): 
                l[0]= row 
                l[1]= col 
                return True
    return False

def used_in_row(arr, row, num): 
    for i in range(9): 
        if(arr[row][i] == num): 
            return True
    return False

def used_in_col(arr, col, num): 
    for i in range(9): 
        if(arr[i][col] == num): 
            return True
    return False

def used_in_box(arr, row, col, num): 
    for i in range(3): 
        for j in range(3): 
            if(arr[i + row][j + col] == num): 
                return True
    return False

def check_location_is_safe(arr, row, col, num): 
    return not used_in_row(arr, row, num) and not used_in_col(arr, col, num) and not used_in_box(arr, row - row % 3, col - col % 3, num) 

def solve(arr):   
    l =[0, 0] 

    if(not find_empty_location(arr, l)): 
        return True

    row = l[0] 
    col = l[1] 

    for num in range(1, 10): 
        if(check_location_is_safe(arr, row, col, num)): 
            arr[row][col]= num 
            if(solve(arr)): 
                return True
            arr[row][col] = 0    
    return False 

def solve_sudoku(grid):
    if(solve(grid)): 
        return grid
    else: 
        return None

5. Hậu xử lý.

Đến đây chỉ cần hiện kết quả của thuật toán lên bức ảnh là xong.
code:

for i in range(0, 9):
    for j in range(0, 9):
        idx = i * 9 + j
        pt = arr[idx]
        cv2.putText(img, "{}".format(int(arr_matrix[i][j])), (pt[0], pt[1]+30), cv2.FONT_HERSHEY_SIMPLEX, 1, 
            (0, 0, 255), 2);
cv2.imshow('img', img)
cv2.waitKey()

Kết quả:

6. Full code

ảnh đầu vào:
Truy cập:

https://sudoku.game/
bấm lưu ảnh để có ảnh đầu vào

resolve.py

def find_empty_location(arr, l): 
    for row in range(9): 
        for col in range(9): 
            if(arr[row][col]== 0): 
                l[0]= row 
                l[1]= col 
                return True
    return False

def used_in_row(arr, row, num): 
    for i in range(9): 
        if(arr[row][i] == num): 
            return True
    return False

def used_in_col(arr, col, num): 
    for i in range(9): 
        if(arr[i][col] == num): 
            return True
    return False

def used_in_box(arr, row, col, num): 
    for i in range(3): 
        for j in range(3): 
            if(arr[i + row][j + col] == num): 
                return True
    return False

def check_location_is_safe(arr, row, col, num): 
    return not used_in_row(arr, row, num) and not used_in_col(arr, col, num) and not used_in_box(arr, row - row % 3, col - col % 3, num) 

def solve(arr):   
    l =[0, 0] 

    if(not find_empty_location(arr, l)): 
        return True

    row = l[0] 
    col = l[1] 

    for num in range(1, 10): 
        if(check_location_is_safe(arr, row, col, num)): 
            arr[row][col]= num 
            if(solve(arr)): 
                return True
            arr[row][col] = 0    
    return False 

def solve_sudoku(grid):
    if(solve(grid)): 
        return grid
    else: 
        return None

main.py

import cv2
import os
import numpy as np
from resolve import solve_sudoku
from scipy.spatial import distance_matrix
in_file = os.path.join("data", "page.png")

img = cv2.imread(in_file)
gray= cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
ret,thresh1 = cv2.threshold(gray,225,255,cv2.THRESH_BINARY_INV)
cv2.imwrite("thresh1.jpg",thresh1)
contours, hierarchy = cv2.findContours(thresh1,cv2.RETR_LIST , cv2.CHAIN_APPROX_NONE)
contours = sorted(contours, key=cv2.contourArea,reverse=True )[1:82]
contours = sorted(contours, key=lambda ctr: cv2.boundingRect(ctr)[0] + cv2.boundingRect(ctr)[1] * img.shape[1])
img0 = img.copy()
cv2.drawContours(img0,contours, -1, (0,255,0), 3)
cv2.imwrite("img0.jpg",img0)
cv2.imshow('img0', img0)
arr = []
for j, contour in enumerate(contours):
    x, y, w, h = cv2.boundingRect(contour)
    arr.append([x,y])

arr_matrix = np.zeros((9,9))
img1 = img.copy()
for j in range(1, 10):
    template = cv2.imread(os.path.join("data", f"match{j}.png"),0)
    w, h = template.shape[::-1]

    res = cv2.matchTemplate(thresh1,template,cv2.TM_CCOEFF_NORMED)
    threshold = 0.8
    loc = np.where( res >= threshold)
    for pt in zip(*loc[::-1]):
        # print(pt)
        # cv2.rectangle(img1, pt, (pt[0] + w, pt[1] + h), (0,0,255), 2)
        cv2.putText(img1, "{}".format(j), (pt[0], pt[1]+30), cv2.FONT_HERSHEY_SIMPLEX, 1, 
            (0, 0, 255), 2);
        distance = distance_matrix([[pt[0], pt[1]]],arr)
        print(np.argmin(distance),len(arr))
        x,y = np.unravel_index(np.argmin(distance),arr_matrix.shape)
        arr_matrix[x][y] = j
cv2.imshow('img1', img1)
cv2.imwrite("img1.jpg",img1)
arr_matrix = solve_sudoku(arr_matrix)
for i in range(0, 9):
    for j in range(0, 9):
        idx = i * 9 + j
        pt = arr[idx]
        cv2.putText(img, "{}".format(int(arr_matrix[i][j])), (pt[0], pt[1]+30), cv2.FONT_HERSHEY_SIMPLEX, 1, 
            (0, 0, 255), 2);
cv2.imshow('img', img)
cv2.imwrite("img.jpg",img)
cv2.waitKey()

7. Kết luận

Vậy là đã hết chủ đề blog xây dựng chương trình giải sudoku đơn giản với Opencv. Qua đây mình thấy là chỉ cần với opencv mà không cần dùng đến AI hay Computer Vision chúng ta đã có thể làm rất nhiều ứng dụng thú vị rồi. Cám ơn các bạn đã theo dõi !!!