ECE497 Project Sudoku Solver
Embedded Linux Class by Mark A. Yoder
I'm using the following template to grade. Each slot is 10 points. 0 = Missing, 5=OK, 10=Wow!
00 Executive Summary 00 Installation Instructions 00 User Instructions 00 Highlights 00 Theory of Operation 00 Work Breakdown 00 Future Work 00 Conclusions 00 Demo 00 Late Comments: I'm looking forward to seeing this. Score: 10/100
Our project is about implementing a Sudoku solver on the Beaglebone Blue. We will first feed the picture of an unsolved 9x9 sudoku puzzle to the BeagleBone and display it onto the LCD. We are using the Google Vision API to convert the text (numbers) of the picture into a text file. We then press a GPIO button to trigger the Sudoku solver which takes a text file as an input and outputs the solved Sudoku grid. The correct result will be shown on the LCD too.
What works: Right now we are using a PlayStation camera to take a picture of our Sudoku board that we send to the Google Vision API. We are now able to use a board with grid lines, but still need to put in zeros for the blank puzzle spots. We are using ImageMagick features to remove the grid lines on the board before sending it to API. We then take the API results and send it to our Sudoku solver. We can then take the final result and use ImageMagick to compose a blank grid onto the Sudoku answers to display a completed puzzle on the LCD Display. We did have to input 0s into the blank spots of our puzzle to get the best results for the API. Most of the puzzles we tested were also made from a table in Microsoft word in order for it to have thin enough grid lines. We observed that thick grid lines seemed to mess up our API results. Our Sudoku solver came from GitHub: https://github.com/Sanahm/SudoCAM-Ku. Our camera handling files came from a GitHub repository by Derek Molloy: https://github.com/derekmolloy/boneCV.git
What doesn't work: What now everything that was within the scope of our project works. Future work could be added which is discussed Future work section.
Overall we found the our project worked fairly well. Once we grabbed a good enough frame, the API was pretty accurate. Once we got good results from the API, the rest of the program worked great.
In addition to BeagleBone Blue and a breadboard, you will need:
- LCD screen
- JST jumpers for GPIO and SPI
- One set of SPI jumper wires
- A pushbutton and a jumper wire
- A webcam. This is the webcam we used, though it looked like it was out of stock last time we checked. You do not have to use this specific webcam though.
- Connect the SPI and GPIO jumper wires of the LCD screen to S1.1 and GP0 on the BeagleBone Blue.
- Connect GP1 jumper wires to a random spot on the breadboard.
- Connect GP1_3 (white wire, also third wire from right to left) to one side of a pushbutton.
- Connect the other side of the button to ground.
- Connect your webcam to the Beaglebone's USB port.
The installation of this project is as follows:
Begin by cloning the GitHub repository for this project with the command below:
Make sure you clone this into your home directory as some of the java code depends on specific directory paths and this will prevent you from having to change it. Next you will need to set up a Google Cloud Platform in order to use the Google Vision API. After you have that set up, go to your console and select "Getting started" on the left side of the page. Select "Create an empty project" to use the Vision API for. After you have created a project, you should receive a notification shown at the top right of the screen. Select the notification icon and then select your project. This should bring you to the dashboard for your project. Next select "billing" on the right side of the screen and make sure billing is enabled for the project. Go back to the dashboard and select "APIs and services" on the right side of the screen. Search for google cloud vision API and select the option that comes up. Make sure this API is enabled for your project. This should bring you to the dashboard for the vision API. Select "credentials" on the right side of the screen. Select "Create credentials", then select "API key". This will generate an authorization key for your project which is needed when running the program.
To set up authorization for the project, cd into the BeagleboneSudoku/boggle directory:
Open up the boggle.js file with an editor. Copy the generated key for your project and set it equal to the "key" variable at the top of the boggle.js file.
Next you will need to run the install and setup scripts in the boggle directory. First set the permissions for the setup.sh script with the command below:
chmod +x ./setup.sh
Execute the install and setup script:
Cd into the newly cloned adafruit directory (located in the BeagleboneSudoku/boggle directory) and set up python3:
cd adafruit-beaglebone-io-python sudo python3 setup.py install
Next cd into the java directory and set the permissions for the setup.sh script:
cd ~/BeagleboneSudoku/boggle/dddddd/src/ chmod +x ./setup.sh
Then run the setup script:
Next you will have to set up the drivers for the LCD display. The install script will also install dependencies needed to display images on the LCD screen:
cd ~/BeagleboneSudoku/ili9341/ ./install.sh
Finally you will have to change the policy rights for the Imagemagick application. You should have the file "etc/ImageMagick-6/policy.xml" on your Beaglebone. Open up this policy file and remove the line that sets zero rights to the "@" command. You will need user permissions to edit this policy file. The line you are looking for should say some along the lines of:
<policy domain="path" rights="none" pattern="@*"/>
You should now be good to go to use this project.
Once everything is installed and set up, you can execute the capture.sh script by doing:
When this begins to run, the camera will begin capturing frames which will be displayed on the LCD display. You need to capture a clear frame of the Sudoku puzzle you are trying to solve. The challenging part is capturing a frame which shows every row and column clearly. Once you see a frame you like on the LCD display, quickly press
CTRL+C on your keyboard.
This will initiate the image processing functions on the frame. Once image processing is complete, the processed image will be displayed on the display. If you are satisfied with the image, you can press the GPIO push button to send it to the Google API. The detected digits will be shown on the LCD display. Once this occurs, you can press the push button again to send the digits to the solver. After the solver is complete, the final results will be shown on the display.
Our project can solve a Sudoku puzzle from a single image frame. It uses some cool image processing features from ImageMagick to remove the grid lines of the Sudoku puzzle and can create a new puzzle grid to display the results. It is also pretty user friendly and just requires a couple GPIO button presses and one keyboard press.
Here is a YouTube video of our demo.
The Imagemagick can perform a great job at removing grid lines if the image is a good quality. However, it takes almost two minutes to do the processing and it does not work well with the images taken by the camera we are using.
Theory of Operation
The flow of the program can be described as follows:
1. The program starts with a while loop that keeps taking photos until a user presses "Ctrl+C" which will capture the image;
2. The image is then processed using ImageMagick to remove grid lines in order to achieve better results; Both the original image and processed image will be seen on the LCD.
3. The Google API will do digit recognition on the processed image and send the data back to the bone in the form of a json file;
4. The program will then convert the json file into a text file from which the Java solver program will use as an input. The Image from google will also be shown on the LCD;
5. The Java program has two parts: The first part is correction.java which is written in an attempt to fix the spacing from the Google API(such as spaces, brackets and etc) to make it compatible with the actual solver. The second part is Sukoku.java which is basically an algorithm that will be used to solve the Sudoku puzzle.
6. We actually have two versions of the correction.java file(one for fixing spacing and the other one for adding 0s that the API may have missed). The working one is the first one. The correctionV1.java was correct, but we were having trouble finding the reason why it would not write to our output text file so just use the first one and not V1 version.
7. Finally, ImageMagick techniques are used to composite two picture (one from soluton.txt, which holds our puzzle solution, and the other one from the boundbox.png, which is a blank Sudoku grid). The final image will be shown on the LCD;
- Google Vision API setup-Joey
- Hardware interfacing-Joey
- API and solver merging-Joey and Donglai
- Solver setup and editing-Donglai
- Image processing work-Donglai
As mentioned above, we finished everything within the scope of our project.
There are a couple of neat ideas that we came up with that could be added to this project. One idea would be to get a stream from the camera so that it's a bit easier to capture a good frame. Another idea might be using image processing to append zeros to the Sudoku puzzle so that you didn't have replace blank spots with them.
The project idea is from https://www.hackster.io because we thought it will be cool to solve a Sudoku puzzle using the Beaglebone Blue. We primarily thought the project would be just two parts: acquiring and image and solving. However, as we delved further into this project, we found it quite challenging to get a perfect image using a camera. Thus we decided to do some interesting pre-processing and post-processing to improve the results: Imagemagick tricks. We have successfully made the results significantly better with those tricks. For the future, we should probably add a live streaming video of the camera to the project and also use imagemagick to append 0s to empty grids.
Embedded Linux Class by Mark A. Yoder