Handwriting Sudoku Solver

This project is a combination of handwriting handwriting digital recognition and Sudoku solver. The program read a handwriting sudoku problem as an image and then give the solution.
Obviously, it contains two parts: recognising the sudoku and solving it.

    • Demo
placeholder

Sudoku Recognition

As we know, the MNIST dataset for handwriting digit recognition is the “hello world” of object recognition for machine learning and deep learning. And a Sudoku is a combination of some digits and blanks. In my program, to recognise the sudoku, there are two steps: extracting the digits from the squares and recognising the digit.

    • Extracting digits
         I use a OpenCV function called findContours to get all the contours of the sudoku. Here is the sample code. Then we get the image below.

    src = imread("Data/Image/sudoku.jpg");
	cvtColor(src, src_gray, CV_BGR2GRAY);
	blur(src_gray, src_gray, Size(3, 3));
	Mat canny;
	Canny(src_gray, canny, thresh, thresh * 2, 3);
	Mat threshmat;
	threshold(src_gray, threshmat, 200, 255, 1);
    Mat kernel;
	kernel  = getStructuringElement(MORPH_CROSS, Point(5,5));
	Mat dilated;
	dilate(threshmat, dilated, kernel);
	Mat roi_img = Mat::zeros(28,28, CV_8UC3);
	std::vector<std::vector<Point> > contours;
	std::vector<Vec4i> hierarchy;

	findContours(dilated, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE, Point(0, 0));
	/// Draw contours
	Mat drawing = Mat::zeros(dilated.size(), CV_8UC3);
	for (int i = 0; i < contours.size(); i++)
	{
		Scalar color = Scalar(rng.uniform(0, 255), rng.uniform(0, 255), rng.uniform(0, 255));
		drawContours(drawing1, contours, i, color, 2, 8, hierarchy, 0, Point());
	}

	/// Show in a window
	namedWindow("Contours", CV_WINDOW_AUTOSIZE);
	imshow("Contours", drawing);
                    
placeholder
    • Recognising digits
         To recognize individual digits I used a three-layer neural network and train the network by gradient descent method. Because this is my first machine learning project, I used most simple neural network algorithm and structure and the result was not good. After this project I used convolutional neural network to improve the program, the result was much better.
placeholder

Sudoku Solver

Sample Code


bool Sudoku::Check(IntVector2 pos,int index)
{
	int cur_row = pos.x;
	int cur_col = pos.y;
	// check row
	for (int i = 0; i < MAX_SIZE; i++) {
		if (index == sudoku[i][cur_col] || index == sudoku[cur_row][i]) {
			return false;
		}
	}

	//  check 3*3
	int grid_row = (cur_row / 3) * 3;
	int grid_col = (cur_col / 3) * 3;
	for (int i = 0; i < 3; i++) {
		if (index == sudoku[grid_row][i + grid_col] ||
			index == sudoku[grid_row + i][grid_col]) {
			return false;
		}
	}

	return true;
}

bool Sudoku::Solve(std::deque <IntVector2> &posArray)

{
	if (posArray.empty()) {
		Print();
		return true;
	}
	IntVector2 current(posArray.front().x, posArray.front().y);  // current digital to put
	posArray.pop_front();
	for (int i = 1; i <= 9; i++) {       // trial from 1 ~9
		if (Check(current, i)) {
			sudoku[current.x][current.y] = i;   // digital to current
			if (!Solve(posArray)) {      // next position
								  // if next failed, back
				sudoku[current.x][current.y] = 0;   // reset current
			}
			else {    // if next success
				return true;
			}
		}
	}
	posArray.push_front(current);  //if cannot do anyway,
						//reset current digital info, and back
	return false;
}

                    

Post-Mortem

I'm a big fan of machine learning and soduku. I really like to watch agent or robot to do things for human. That's why I did this project.
During the project I always felt like something was wrong somewhere. After several weeks finishing this project, I finally realised the problem.
As a practice, this project is fine. But it is really useless. Because no one would have a handwriting sudoku. The sudokus are always printed. So, maybe I'll change it to a AI project later.
XD.

publish
publish