AR Sudoku Solver Uses Machine Learning To Solve Puzzles Instantly

Today we are going to show how you can make your own AR sudoku solver and look at what this complex tool has us excited about the future of augmented reality. Though, we are not too sure Stanley Hudson from The Office would approve. So, tread carefully. 

AR Technology: A quick refresher.  

Even if you have never experienced augmented reality, you have surely seen it modeled on the big screen. Films like Minority Report and Iron Man might pop into your mind, although of course, the AR in movies is created through special effects, rather than by creating a working AR.

In short, augmented reality is the result of using technology to superimpose information like sounds, images, and text onto the real world. Unlike virtual reality (VR), which takes you to a virtual world, augmented reality adds to your current reality. You can trace the history of augmented reality all the way back to the 1960s, with Morton Heilig's simulated motorcycle experience and Ivan Sutherland's "Ultimate Display." 

As mentioned above, there is a wide range of applications for AR technology. Researchers are even looking at ways augmented reality could be used to enhance education, improve therapy, and change our behavior.  A little closer to home, it is making its way into our mobile devices and applications. Mobile games, like the legendary Pokemon Go, use AR to allow players to go out and interact with the real world. 

Believe it or not, AR sudoku solvers are some of the most innovative uses of this technology. Let us explain. 

Sudoku solvers show us what AR could be...fast.

Sudoku solvers are impressively fast, let's explain how it all works to truly understand how so. First, let's start with the puzzle. Classic Sudoku games center around a grid of 81 squares, divided into nine blocks of nine squares each. Each of the nine blocks has to contain all the numbers 1-9 within its squares. Importantly, numbers can only appear once in a row, column, or box. Solving the game is no easy feat and can take countless hours. Try the Sudoku above. Can you solve it? Struggling? (answers below)

This is where AR sudoku solver steps in. The mobile app Magic Sudoku, created by the start-up, Hatchlings, can solve this puzzle instantly. By simply aiming your camera at any sudoku puzzle, the answers are displayed directly on your screen. You don't have to take a picture and save it for later. All of this happens in real-time. 

One of the biggest challenges in advancing augmented reality over the years has been improving the speed and consistency. Like any other type of modern technology, users want technology that works quickly and efficiently. Thankfully, this is now starting to happen. Developments in everyone's favorite AI science, machine learning, have made it possible for AI and AR to recognize faces and objects better than ever. 

For example, Google has been very vocal about its investment research into practical uses of AR in the real world. With Google Lens, you can take your phone camera and point it at a restaurant on the street to pull up the latest reviews and the star ratings. 

Sudoku solvers are a reminder that AR technology is not only a cool gimmick, but also a fast tool with limitless potential. Perhaps, you would like to build one for fun?  

But how does it work? 

Within an instant, there is a lot happening in an AR sudoku solver. Although, most Sudoku AR solvers use similar techniques. The puzzle solvers use a combination of computer vision, machine learning, and augmented reality to create an experience that almost seems like magic. The founder of Hatchling, Brad Dwyer, breaks down how and why they created a Magic Sudoku solver in detail on his Medium page.

Magic Sudoku's process of solving a puzzle is as follows:

(1) First, the ARKit software gets a new frame from the camera.

(2) It uses iOS11's Vision Library to detect rectangles in the image.

(3) If rectangles are found, the app determines whether they are a Sudoku grid.

(4) Then, if they find a puzzle, the software splits it up into 81 square images.

(5) Each square is run through a neural network that is trained to determine what number (if any) it represents.

(6) Once enough numbers are gathered, a traditional recursive algorithm is used to solve the puzzle.

(7) Finally, they pass a 3D model representing the solved puzzle back to ARKit to display on top of the original image from the camera. All of this happens several times each second. 

If you want to learn more, be sure to stop by his page here. 

You can make your own sudoku solver. 

There are a handful of ways to create an AR sudoku solver app. And it is not as hard as you might think. Provided that you have some background in coding or machine learning. Colin Eberhardt of Scott Logic created his own WebAssembly powered Augmented Reality Sudoku Solver over just a few days.

He used the WebAssembly build of OpenCV (a machine learning library), Tensorflow, and the multi-paradigm programming language Rust. His Sudoku Solver app worked just as well as Magic Sudoku, following the steps outlined below to create instant solutions. 

Following Colin's diagram:

(1) Adaptive thresholding is used to locate edges, creating a black and white image.

(2) Then the edges are then approximated.

(3) Next, a reversed perspective transform is applied in order to render the grid as a square image.

(4) The gridlines are then erased.

(5) A convolution neural network is used to identify the digits in the 9x9 grid.

(6) The grid is then solved via a Rust-based module.

(7) Finally, the perspective transform from step three is applied to project the solution back onto the image.

(8) The solution is merged back into the original image. All of this is completed in about 70ms. 

As mentioned by Colin in the blog post, "Regarding the speed of processing, it takes approximately 70ms on my computer to perform the full pipeline (threshold, contour, solver, merge, all the magic) which is sufficient. On my iPhone, it is noticeably slower, and the frame rate isn't really good enough to achieve the illusion AR tries to present. I'm sure there is room for improvement..." 

You can find the source code and the AR sudoku solver project on GitHub. There are other projects available if you want to avoid using WebAssembly. The project is discussed in detail here. 

Augmented reality is coming. 

Over the past couple of years, leaks from Apple insiders and the tech company's latest business decisions have pointed to the inevitable release of new AR hardware. Microsoft already has their Hololens, and BMW is said to have something in the pipeline. Once AR technology becomes more accessible, augmenting our reality may become more commonplace, whether you are trying to decide where to eat out for the day or repair a vehicle. For now, we will stick to solving sudoku puzzles. 

Will you try to create your own Sudoku solver? What tool would you use?

For more articles on augmented reality, virtual reality, and everything in between, be sure to stop by here.