The world’s leading publication for data science, AI, and ML professionals.

Sudoku smashing solution

Exhaustive Sudoku solving bot tutorial: Image and optical character recognition plus text to speech

Ask bot to solve your Sudoku for you (Photo by John Morgan on Unsplash)
Ask bot to solve your Sudoku for you (Photo by John Morgan on Unsplash)

In a previous article we created a bot called Isaac (inteligible solution for administrative and analytical communication). In this post we will teach Isaac how to play Sudoku. Isaac will receive eyes to see, hands to write and a mouth to speak. With those skills Isaac will be able to look at our Sudoku and reveal to us the missing digits verbally.

Say hello world, Isaac! (image by author)
Say hello world, Isaac! (image by author)

Sudoku is abbreviated from the Japanese words "suuji wa dokushin ni kagiru", which means " the numbers (or digits) must remain single". Each Sudoku consists of 9 columns and 9 rows, where each column and each row must contain the numbers 1–9 each one time only. In each 3×3 square there must not be any duplicates.

One example of an unsolved Sudoku (image by author).
One example of an unsolved Sudoku (image by author).

The main purpose of this post is to show how to bring machine learning Image Recognition, optical character recognition (OCR), text to speech and "condition check problem coding" in Python all together streamlined into one data product. You will find the complete code in my Github repository. To avoid information overload the details of each milestone will be explained in single posts separately (links will be added as soon as possible).

Milestones:

  • image recognition with CV2 (finding the Sudoku on each image)
  • number recognition with Tensorflow (finding already entered digits in each Sudoku square)
  • Sudoku solving logic (condition check coding)
  • Text To Speech converting with gtts

Solution:

Beside the obligatory Numpy, both Google`s Tensorflow and gtts as well as CV2 are the magical libraries to solve our quest.

import numpy as np
import cv2
from tensorflow.keras.models import load_model
from gtts import gTTS

As mentioned earlier, the detailed explanation of each code module will follow in other articles yet to come. In this post we are rather focusing on understanding the main concept and text to speech conversion.

CV2 is used so we can show the Sudoku image to Isaac.

picture = cv2.imread("SudokuUnfinished.jpg")
Isaac will screen this Sudoku jpg (image by author)
Isaac will screen this Sudoku jpg (image by author)

As a next step, CV2 will spot the Sudoku on that image first.

def GreatestOutline(outline):
    biggest = np.array([])
    biggestArea = 0
    for i in outline:
        area = cv2.contourArea(i)
        if area > 50:
            peri = cv2.arcLength(i, True)
            approx = cv2.approxPolyDP(i, 0.02 * peri, True)
            if area > biggestArea and len(approx) == 4:
                biggest = approx
                biggestArea = area
    return biggest,biggestArea

The biggest contour on the image found is expected to be the Sudoku. That Sudoku will further more be separated into its 9*9 squares.

def SplitBoxes(picture): 
    rows = np.vsplit(picture,9)
    boxes=[]
    for r in rows:
        column= np.hsplit(r,9)
        for box in column:
            boxes.append(box)
    return boxes
boxes = SplitBoxes(warpColored)

Each square will then be checked -using Tensorflow- for already entered numbers. Each found number will be compared against a previously trained model. If the number is at least matching with what the model expects to have a 80% match, that number will be taken. Otherwise the square will be considered as being empty and therefore will be dealt as zero (remember that 0 does not exist in Sudoku).

def RecPrediction(boxes,model):
    result = []
    for image in boxes:
        picture = np.asarray(image)
        picture = picture[4:picture.shape[0] - 4, 4:picture.shape[1] -4]
        picture = cv2.resize(picture, (28, 28))
        picture = picture / 255
        picture = picture.reshape(1, 28, 28, 1)
        predictions = model.predict(picture)
        classIndex = model.predict_classes(picture)
        probabilityValue = np.amax(predictions)
        if probabilityValue > 0.8: 
            result.append(classIndex[0])
        else:
            result.append(0) 
    return result
numbers = RecPrediction(boxes, model)

Isaac now knows the currently filled Sudoku status.

In row 0, column 0 Isaac can see that number 6 has been entered (image by author)
In row 0, column 0 Isaac can see that number 6 has been entered (image by author)

Let’s check if that is correct.

textfile = open("SudokuInput.txt", "w") 
for element in numbers:
    textfile.write(str(element))
textfile.close()
0 means no number available for that field
0 means no number available for that field

Comparing Isaac’s output with the Sudoku image we see that Isaac got it right. But the format is not very convenient to read, so we will add new lines after each 9 digits:

textfiles = open("SudokuInput.txt", "r")
data = textfiles.read()
my_str = str(data)
group = 9
char = "n"
hallo =char.join(my_str[i:i + group] for i in range(0, len(my_str), group))
textfile = open("SudokuRev.txt", "w")
for element in hallo:
    textfile.write(str(element))
textfiles.close()
textfile.close()

That finally looks much more Sudoku like:

SudokuRev.txt (image by author)
SudokuRev.txt (image by author)

Knowing the existing number, we must now teach Isaac how to play Sudoku the right way. That will be the explicit coding part.

class Sudoku:
    def __init__(self, variables, areas, condition):
        self.variables = variables
        self.areas = areas
        self.condition = condition #...explanation details to follow

Now that Isaac knows how to play, let’s give it a try. Let us see what Isaac is entering as the missing digits:

6 1 5 8 3 4 7 9 2 |2 4 7 5 1 9 8 6 3 |9 8 3 7 6 2 4 1 5 |3 2 1 6 7 5 9 4 8 |5 6 4 9 8 3 2 7 1 |8 7 9 2 4 1 3 5 6 |4 5 6 3 2 7 1 8 9 |1 9 2 4 5 8 6 3 7 |7 3 8 1 9 6 5 24

Good job, Isaac! The missing numbers have been filled correctly in the right sequence order.

I created this solution for my Sudoku loving grandma. Unfortunately she would prefer to listen to the results (rather than looking up the results on her small pc screen). So Isaac must learn how to speak. That is fairly easy and straightforward thanks to Google’s gtts. In plain English, we are splitting through the result string adding a space in between after each digit. That is, so Isaac speaks "one", "two", "three" instead of "one hundred twenty three". Otherwise it will be hard to follow the right number sequence of the Sudoku.

voice_texts = ""
for line in range(0, 9):
    voice_texts += '|'
    for column in range(0, 9):
        if (line, column) in assignment:
            voice_texts += str(assignment[(line, column)])
        else:
            voice_texts += ''
        voice_texts += ' '
print(voice_texts)
voice_text = ""
for i in voice_texts.split(): 
    voice_text += i + ' '
voice_text = voice_text[:-1]
voice_text ="Hi, this is Isaac telling you your Sudoku numbers"+voice_text
tts = gTTS(voice_text)
tts.save("IsaacReadsYourSudokuSolution.mp3")
Text to speech saves mp3 audio files (image by author)
Text to speech saves mp3 audio files (image by author)

Congratulations:

You teached Isaac to screen Sudokus and tell you the solution. In a future post we will learn how to deploy Isaac with Flask as a web accessible app. As an even further step, we will build an Android app. So you can upload a photo for Isaac to tell you the answer on your smartphone right away. We will also challenge Isaac in the future to see if he will be able to solve even more difficult real life puzzles than only Sudoku:

Probably not the most serious Danish ad in the world, I reckon (image by author)
Probably not the most serious Danish ad in the world, I reckon (image by author)

Many thanks for reading! I hope this article is helpful for you. Feel free to connect with me on LinkedIn, Twitter or Workrooms.

Join Medium with my referral link – Jesko Rehberg

You can find the complete code in my Github repository. Feel free to connect with me on LinkedIn, Twitter or Workrooms (with or without VR).


Related Articles