### 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.

### 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.

###### 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.
``````
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);
``````

### 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