Made a sudoku solver with basic GUI in C++

Question

I've made a sudoku solver which solves a sudoku, given user input, and can also extract digits from a picture of a sudoku to solve it. I've used OpenCV and GTK+ 2.0 to achieve the above. I am very open to any kind of suggestion on how write proper and understandable C++ code. I have the following question:

1. How would you rate my code? What to improve?
2. How to improve its readability? (I tried an object oriented implementation in order to improve readability, I don't know whether that's right)
3. Is there a best practice I'm not following or missing ?
4. I've used some global varibles, is that bad?
5. I've just heard the term unit test cases. Does this program require that?

The code:

    #include <gtk/gtk.h>
    #include <iostream>
    #include <string.h>
    #include "opencv2/imgproc.hpp"
    #include "opencv2/highgui.hpp"
    #include "opencv2/core/core.hpp"
    #include <bits/stdc++.h>
    #include <math.h>

    using namespace std;
    using namespace cv; 

    // Sudoku grid
    static int grid[9][9];
    // Sudoku grid displayed, main window                          
    static GtkWidget *wid [9][9] , *window;
    // Whether to show pre-processing steps
    bool to_show;

    // To initiate solver
    void solver();

    // To show pre-processing steps
    static void show_steps_event( GtkWidget *widget , gpointer data );

    // To get user inputted elements
    static void get_element( GtkWidget *widget , gpointer data );

    // To clear the grid
    static void new_event( GtkWidget *widget , gpointer data );

    // To upload a picture and put digits into grid
    static void upload_element( GtkWidget *widget , gpointer data );

    // For a single datapoint of KNN algorithm dataset
    struct datapoint 
    {
        int val;               // Group of datapoint
        Mat digit;             // Feature values
        double distance;       // 'Distance' from test point
    };

    // To enable sorting to find the k nearest neighbour
    bool comparison ( datapoint a , datapoint b )
    {
        return (a.distance < b.distance);
    }

    // KNN algorithm
    class KNearestNeighbors
    {
        private:
            int k;
            vector <datapoint> imgs;        

        public:

            // Constructor
            KNearestNeighbors ( int n_neighbors = 5 ) { k = n_neighbors; }

            // To find the 'distance' between two datapoints ; Note: cosine similarity can also be used
            double dist ( Mat a , Mat b );

            // To load an image from the dataset
            void load(string s,int group);

            // To load the dataset
            void fit_transform();

            // To predict a number between 1-9 given its image
            int predict ( Mat img );

            // Destructor
            ~KNearestNeighbors(){}

    };

    // Sudoku solver 
    class sudoku
    {
        private:
            int arr[9][9];

        public:

            // Constructor
            sudoku(){}

            // To start the solving of sudoku
            void initiate ();

            // To return the solved array to global variable
            void finish ( int x[][9] , int m , int n );

            // To the find the center of small 3x3 squares in 9x9
            void findc ( int &c );

            // To check whether num is valid at index (x,y)
            bool isValid ( int arr[][9] , int x , int y , int num );

            // To solve and dislay final array
            void solve ( int arr[][9] );

            // Displays the array once solved
            void whenDone ();

            // Destructor
            ~sudoku(){}        
    };

    // For image preprocessing
    class scanner
    {
        private:
            Mat img;
            KNearestNeighbors k;

        public:

            // Constructor
            scanner ( string s , KNearestNeighbors temp );

            // Returns a number using the KNN algorithm
            int getNum ( Mat img );

            // Finds the Euclidean distance between two points
            float distance ( Point p , int i , int j );

            // To find corresponding points for homography transformation
            int findQuad ( Point p , Mat img );

            // Returns a 900x900 resized version of a binary image of the sudoku grid
            Mat preprocessing ( Mat img );

            // To scan each square of the grid and return the digit it contains
            void getDigits ();

            // Destructor
            ~scanner(){}        
    };

    double KNearestNeighbors :: dist ( Mat a , Mat b )
    {
        double val = 0;

        for ( int i = 0 ; i < 20 ; i++ )
        {
            for ( int j = 0 ; j < 20 ; j++ )
            {
                val = val + (a.at<uchar>(i,j)-b.at<uchar>(i,j))*(a.at<uchar>(i,j)-b.at<uchar>(i,j));
            }
        }

        return sqrt(val);
    }

    void KNearestNeighbors :: load(string s,int group)
    {
        vector<cv::String> fn;
        glob(s, fn, false);

        vector<Mat> images;
        size_t count = fn.size(); //number of png files in images folder

        for (size_t i=0; i<count; i++)
        {
            Mat temp = imread(fn[i],0);
            datapoint t;
            t.val = group;
            t.digit = temp;
            imgs.push_back(t);
        }
    }

    void KNearestNeighbors :: fit_transform()
    {
        string direct = "Data/";
        string temp = "/*.png";

        for ( int i = 0 ; i <= 9 ; i++ )
        {
            string new_direct = direct + to_string(i) + temp;
            load(new_direct,i);
        }
    }

    int KNearestNeighbors :: predict ( Mat img )
    {
        for ( int i = 0 ; i < imgs.size() ; i++ )
        {
            imgs[i].distance = dist ( imgs[i].digit , img );
        }

        sort(imgs.begin(),imgs.end(),comparison);

        int freq[10] = {0};

        for ( int i = 0 ; i < k ; i++ )
        {
            for ( int j = 0 ; j < 10 ; j++ )
            {
                if ( imgs[i].val == j )
                {
                    freq[j]++;
                }
            }
        }

        return max_element(freq, freq + sizeof(freq)/sizeof(int)) - freq ;
    }

    void sudoku :: finish ( int x[][9] , int m , int n )
    {
        for ( int i = 0 ; i < 9 ; i++ )
        {
            for ( int j = 0 ; j < 9 ; j++ )
            {
                grid[i][j] = x[i][j];
            }
        }
    }

    void sudoku :: findc ( int &c )
    {
        switch(c)
        {
            case 0:
            case 1:
            case 2: c = 1;
                    return;

            case 3:
            case 4:
            case 5: c = 4;
                    return;

            case 6:
            case 7:
            case 8: c = 7;
                    return;
        }
    }

    bool sudoku :: isValid ( int arr[9][9] , int x , int y , int num )
    {
        bool check = true;
        int i,j;

        for ( i = 0 ; i < 9 ; i++ )
        {
            if ( i == x )
                continue;

            if ( arr[i][y] == num && check == true )
            {
                check = false;
                return check;
            }
        }

        for ( j = 0 ; j < 9 ; j++ )
        {
            if ( j == y )
                continue; 

            if ( arr[x][j] == num && check == true )
            {
                check = false;
                return check;
            }
        }

        i = x;
        j = y;
        findc(i);
        findc(j);

        for ( int k = i-1 ; k < i+2 ; k++ )
        {
            for ( int l = j-1 ; l < j+2 ; l++ )
            {
                if ( k == x && l == y )
                    continue;

                if ( arr[k][l] == num && check == true )
                {
                    check = false;
                    return check;
                }
            }
        }

        return check;
    }

    void sudoku :: solve ( int arr[9][9] )
    {
        for ( int i = 0 ; i < 9 ; i++ )
        {
            for ( int j = 0 ; j < 9 ; j++ )
            {
                if ( arr[i][j] == 0 )
                {
                    for ( int k = 1 ; k <= 9 ; k++ )
                    {
                        if ( isValid (arr,i,j,k) == true )
                        {
                            arr[i][j] = k;
                            whenDone();
                            solve(arr);
                            arr[i][j] = 0;
                        }

                        if ( k == 9 )
                        {
                            arr[i][j] = 0;
                            return;
                        }
                    }

                    if ( !( isValid(arr,i,j,1) || isValid(arr,i,j,2) || isValid(arr,i,j,3) || isValid(arr,i,j,4) || isValid(arr,i,j,5) || isValid(arr,i,j,6) || isValid(arr,i,j,7) || isValid(arr,i,j,8) || isValid(arr,i,j,9) ) )
                    {
                        arr[i][j] = 0;
                        return;
                    }
                }
            }
        }
        finish(arr,9,9);
    }

    void sudoku :: initiate ()
    {
        for ( int i = 0 ; i < 9 ; i++ )
        {
            for ( int j = 0 ; j < 9 ; j++ )
            {
                arr[i][j] = grid[i][j];
            }
        }

        solve(arr);
    }

    void sudoku :: whenDone()
    {
        for ( int i = 0 ; i < 9 ; i++ )
        {
            int sum = 0;

            for ( int j = 0 ; j < 9 ; j++ )
            {
                sum = sum + arr[i][j];
            }

            if ( sum != 55 )
            {
                return;
            }
        }

        finish(arr,9,9);
    }

    scanner :: scanner ( string s , KNearestNeighbors temp )
    {
        img = imread(s,0);
        k = temp;
        k.fit_transform();
    }

    int scanner :: getNum ( Mat img )
    {
        return k.predict(img);
    }

    float scanner :: distance ( Point p , int i , int j )
    {
        return (i-p.x)*(i-p.x) + (j-p.y)*(j-p.y);
    }

    int scanner :: findQuad ( Point p , Mat img )
    {
        vector<Point> s;
        Point p1(0,0) , p2(img.cols,0) , p3(img.cols,img.rows) , p4(0,img.rows);
        s.push_back(p1);
        s.push_back(p2);
        s.push_back(p3);
        s.push_back(p4);

        double d = 0;
        int min = 0;

        for ( int i = 0 ; i < 4 ; i++ )
        {
            if ( distance(p,s[i].x,s[i].y) > d )
            {
                d = distance(p,s[i].x,s[i].y);
                min = i;
            }
        }

        return min;
    }

    Mat scanner :: preprocessing ( Mat img )
    {
        Mat img_blur , canny_output , warp_output , binary_output , square ;

        if ( to_show == true )
        {
            namedWindow("Input Image",0);
            imshow("Input Image",img);
            waitKey(1);
        }

        GaussianBlur( img , img_blur , Size(3,3) , 0 );                     //blurring to remove noise ; Note: we can use an edge preserving filter

        if ( to_show == true )
        {
            namedWindow("Gaussian blur",0);
            imshow("Gaussian blur",img_blur);
            waitKey(1);
        }

        double otsu_thresh_val = threshold(img_blur, img_blur , 0, 255, CV_THRESH_BINARY | CV_THRESH_OTSU);           // Using Otsu thresholding to find the thresholds for Canny Edge detection
        double high_thresh_val  = otsu_thresh_val, lower_thresh_val = otsu_thresh_val * 0.5;

        Canny ( img_blur , canny_output , lower_thresh_val , high_thresh_val );                   //Canny edge detection                  

        if ( to_show == true )
        {
            namedWindow("Canny",0);
            imshow("Canny",canny_output);
            waitKey(1);
        }

        vector<vector<Point>> contours;                                     //contour detection ; Note: needs improvement as in some cases it detects some random contour and not the grid
        findContours( canny_output , contours , CV_RETR_EXTERNAL , CV_CHAIN_APPROX_SIMPLE );       
        double max_area = 0;
        int temp = 0;

        for ( int  i = 0 ; i < contours.size() ; i++ )
        {
            if ( contourArea(contours[i]) >= max_area )
            {
                max_area = contourArea(contours[i]);                       //finding contour of maximum area ; Note: can also use sort function and use contour at index 0
                temp = i;
            }
        }

        double peri = arcLength ( contours[temp] , true );                 //perimeter of outer rectangle
        vector<Point> rect;
        approxPolyDP ( contours[temp] , rect , 0.02*peri , true );         //approxiating the contour to a rectangle

        Point2f inputQuad[4];                                              //Input Quadilateral or Image plane coordinates
        Point2f outputQuad[4];                                             //Output Quadilateral or World plane coordinates
        Mat perspectiveMatrix( 2, 4, CV_32FC1 );                           //perspectiveMatrix

        perspectiveMatrix = Mat::zeros( img.rows, img.cols, img.type() );  //setting it as same type as input image

        for ( int i = 0 ; i < 4 ; i++ )
        {
            inputQuad[findQuad(rect[i],img)] = rect[i];
        }

        outputQuad[0] = Point2f( img.cols , img.rows );
        outputQuad[1] = Point2f( 0 , img.rows );
        outputQuad[2] = Point2f( 0 , 0 );
        outputQuad[3] = Point2f( img.cols , 0 );

        perspectiveMatrix = getPerspectiveTransform( inputQuad, outputQuad );     //Get the Perspective Transform Matrix i.e. perspectiveMatrix
        warpPerspective(img,warp_output,perspectiveMatrix,warp_output.size() );   //Apply the Perspective Transform to the input image

        if ( to_show == true )
        {
            namedWindow("Homography",0);
            imshow("Homography",warp_output);
            waitKey(1);
        }

        int size = warp_output.rows*warp_output.cols/2188;                        //Get the kernel size for adaptive threshold
        if ( size%2 == 0 )  size++;                                               //Making it odd

        adaptiveThreshold( warp_output , binary_output , 255 , ADAPTIVE_THRESH_MEAN_C , THRESH_BINARY , size , 0 );       //Using adaptive thresholding to obtain binary image

        if ( to_show == true )
        {
            namedWindow("Thresholding",0);
            imshow("Thresholding",binary_output);
            waitKey(1);
        }

        Size s(900,900);
        resize(binary_output,square,s);

        if ( to_show == true )
        {
            namedWindow("Final Image",0);
            imshow("Final Image",square);
            waitKey(1);
        }

        return square;
    }

    void scanner :: getDigits ()
    {
        Mat square = preprocessing(img);

        for ( int x = 0 ; x < 9 ; x++ )
        {
            for ( int y = 0 ; y < 9 ; y++ )
            {
                grid[x][y] = 0;

                Mat elm( square.rows*0.13 , square.cols*0.13, CV_8UC1 , Scalar(0) );                      //Making an image containing a square of the grif

                for ( int i = 0 ; i < elm.rows ; i++ )        
                {
                    for ( int j = 0 ; j < elm.cols ; j++ )
                    {
                        if ( i+int(square.rows*x/9) < square.rows && j+int(square.cols*y/9) < square.cols )               //Checking the pixel is valid
                            elm.at<uchar>(i,j) = square.at<uchar>(i+int(square.rows*x/9),j+int(square.cols*y/9));                //Extracting a square
                        else
                            elm.at<uchar>(i,j) = 0;                
                    }
                }

                vector<vector<Point>> num;
                findContours( elm , num , CV_RETR_EXTERNAL , CV_CHAIN_APPROX_SIMPLE );

                double area = 0;
                int idx = 0;

                for ( int  i = 0 ; i < num.size() ; i++ )
                {
                    if ( contourArea(num[i]) >= area )
                    {
                        area = contourArea(num[i]);                       //Finding contour of maximum area
                        idx = i;
                    }
                }

                Rect n = boundingRect(num[idx]);

                Mat number = elm(n);                                              //Cropping out the number from the cell
                Mat fin (number.rows-10,number.cols-10, CV_8UC1 , Scalar(0) );

                for ( int i = 5 ; i < number.rows-5 ; i++ )
                {
                    for ( int j = 5 ; j < number.cols-5 ; j++ )
                    {
                        fin.at<uchar>(i-5,j-5) = number.at<uchar>(i,j);
                    }
                }

                resize(fin,fin,Size(20,20));
                grid[x][y] = getNum ( fin );                                     //Assigning the corresponding numbber to the array
            }
        }
    }

    void solver ()
    {
        sudoku x;
        x.initiate();

        for ( int i = 0 ; i < 9 ; i++ )
        {
            for ( int j = 0 ; j < 9 ; j++ )
            {
                char c[2];
                sprintf(c,"%d",grid[i][j]);

                gtk_entry_set_text(GTK_ENTRY(wid[i][j]),c);
            }
        }
    }

    static void show_steps_event( GtkWidget *widget , gpointer data )
    {
        if ( gtk_toggle_button_get_active(GTK_TOGGLE_BUTTON(widget) ))
        {
            to_show = true;
        }
        else
        {
            to_show = false;
        }
    }

    static void get_element( GtkWidget *widget , gpointer data )
    {
        for ( int i = 0 ; i < 9 ; i++ )
        {
            for ( int j = 0 ; j < 9 ; j++ )
            {
                if ( gtk_entry_get_text(GTK_ENTRY(wid[i][j])) == " " )
                    grid[i][j] = 0;
                else
                    grid[i][j] = atoi(gtk_entry_get_text(GTK_ENTRY(wid[i][j])));
            }
        }
        solver();
    }

    static void new_event( GtkWidget *widget , gpointer data )
    {
        for ( int i = 0 ; i < 9 ; i++ )
        {
            for ( int j = 0 ; j < 9 ; j++ )
            {
                grid[i][j] = 0;
                gtk_entry_set_text(GTK_ENTRY(wid[i][j])," ");
            }
        }
    }

    static void upload_element( GtkWidget *widget , gpointer data )
    {
        GtkWidget *dialog;

        dialog = gtk_file_chooser_dialog_new("Choose a file",GTK_WINDOW(window),GTK_FILE_CHOOSER_ACTION_OPEN,GTK_STOCK_OK,GTK_RESPONSE_OK,GTK_STOCK_CANCEL,GTK_RESPONSE_CANCEL,NULL);

        gtk_widget_show_all(dialog);

        gtk_file_chooser_set_current_folder(GTK_FILE_CHOOSER(dialog),g_get_home_dir());

        gint resp = gtk_dialog_run(GTK_DIALOG(dialog));

        if ( resp == GTK_RESPONSE_OK )
        {
            string s = gtk_file_chooser_get_filename(GTK_FILE_CHOOSER(dialog));
            KNearestNeighbors knn (1);
            scanner scan (s,knn);
            scan.getDigits();

            for ( int i = 0 ; i < 9 ; i++ )
            {
                for ( int j = 0 ; j < 9 ; j++ )
                {
                    char c[2];
                    if( grid[i][j] != 0 )
                        sprintf(c,"%d",grid[i][j]);
                    else
                        sprintf(c," ");

                    gtk_entry_set_text(GTK_ENTRY(wid[i][j]),c);
                }
            }
        }
        gtk_widget_destroy(dialog);
    }

    int main(int argc, char* argv[])
    {
        gtk_init(&argc,&argv);           // Initialising GTK+

        GtkWidget *vbox , *hbox , *separator , *button , *toggle , *file_menu , *menu_bar , *menu_item;
        window = gtk_window_new(GTK_WINDOW_TOPLEVEL);
        g_signal_connect(window, "delete-event", G_CALLBACK(gtk_main_quit), NULL);               // if X is pressed then program is exited

        vbox = gtk_vbox_new(0,0);

        for ( int i = 0 ; i < 9 ; i++ )                   // Making grid full of entry boxes
        {
            hbox = gtk_hbox_new(0,0);

            for ( int j = 0 ; j < 9 ; j++ )
            {
                wid[i][j] = gtk_entry_new();
                gtk_entry_set_max_length(GTK_ENTRY(wid[i][j]),1);
                gtk_widget_set_size_request(wid[i][j],50,50);
                gtk_box_pack_start(GTK_BOX(hbox),wid[i][j],1,1,0);                               

                if ( (j+1)%3 == 0 )                      // Adding separator at columns multiple of 3
                {
                    separator = gtk_vseparator_new();
                    gtk_box_pack_start(GTK_BOX(hbox),separator,1,1,0);
                    separator = gtk_vseparator_new();
                    gtk_box_pack_start(GTK_BOX(hbox),separator,1,1,0);
                }

            }

            gtk_box_pack_start(GTK_BOX(vbox),hbox,1,1,0);

            if ( (i+1)%3 == 0 )                         // Adding separator at rows multiple of 3
            {
                separator = gtk_hseparator_new();
                gtk_box_pack_start(GTK_BOX(vbox),separator,1,1,0);
                separator = gtk_hseparator_new();
                gtk_box_pack_start(GTK_BOX(vbox),separator,1,1,0);
            }
        }

        hbox = gtk_hbox_new(0,0);

        button = gtk_button_new_with_label("Solve");             // Solve button
        g_signal_connect(button,"clicked",G_CALLBACK(get_element),NULL);
        gtk_box_pack_start(GTK_BOX(hbox),button,1,1,0);

        button = gtk_button_new_with_label("Upload");            // Upload image button
        g_signal_connect(button,"clicked",G_CALLBACK(upload_element),NULL);
        gtk_box_pack_start(GTK_BOX(hbox),button,1,1,0);

        button = gtk_button_new_with_label("New");               // Clearing grid for new input
        g_signal_connect(button,"clicked",G_CALLBACK(new_event),NULL);
        gtk_box_pack_start(GTK_BOX(hbox),button,1,1,0);

        toggle = gtk_check_button_new_with_mnemonic("Show steps");       // To show image processing steps
        gtk_box_pack_start(GTK_BOX(hbox),toggle,0,0,0);
        g_signal_connect(toggle,"toggled",G_CALLBACK(show_steps_event),NULL);

        gtk_box_pack_start(GTK_BOX(vbox),hbox,0,0,0);

        gtk_container_add(GTK_CONTAINER(window),vbox);

        gtk_window_set_title(GTK_WINDOW(window),"Sudoku Solver");

        gtk_widget_show_all(window);

        gtk_main();

        waitKey(0);

        return 0;
    }

Note: I've not included the data files which contains templates of images of digits 0-9 for the KNN algorithm.

Answer 1

Answers to your questions

How would you rate my code? What to improve?

It is certainly not the worst code, but there are areas of improvement, which I'll discuss below.

How to improve its readability? (I tried an object oriented implementation in order to improve readability, I don't know whether that's right)

I would start to use a code formatter to ensure the code is formatted in a consistent way. Your use of spaces is very inconsistent, some lines have spaces between literally everything where spaces are possible, and in others there is no space to be seen except for the indentation.

Apart from that, avoid abbreviating variable and function names unnecessarily. For example, instead of wid write widget, instead of imgs write images. Unnecessary abbreviations might make it harder to search the code, and make things confusing. (For example, if you didn't see its declaration before, can you tell if wid a widget, a width or a window ID?)

Is there a best practice I'm not following or missing?

Yes, we'll discuss them.

I've used some global varibles, is that bad?

It's best to avoid using global variables as much as possible. If they are really necessary then by all means use them, but the issue is that they pollute the global namespace, make it harder to modularize your code, and might result in issues if you have multithreaded code.

I've just heard the term unit test cases. Does this program require that?

No, programs don't require unit test cases. They are however a method for ensuring your code has a high quality.

When writing C++ code, prefer to use C++ libraries

Instead of using the C version of GTK, I strongly advise you to use gtkmm instead. It should result in shorter, cleaner code, and will probably help get rid of the global GtkWidget variables.

Avoid forward declarations

Unless you have functions with circular dependencies, you should not need to write forward declarations of functions. Just ensure that a function that is called by other functions comes before those other functions in your source code.

Doing this avoids repeating yourself.

Avoid using namespace std

See this StackOverflow question for a rationale.

Class member value initialization

Instead of initializing values in the body of the constructor, prefer using a member initializer list, like so:

class KNearestNeighbors {
    int k;
    ...
    KNearestNeighbors (int n_neighbors = 5): k(n_neighbors) {}

While it is trivial here, once you have member variables with non-trivial types it has certain advantages.

Avoid writing empty constructors and destructors

C++ provides default constructors and destructors for you if you don't specify them yourself. So for example in class sudoku, you can avoid writing the constructor and destructor. In general, don't write what you don't need to write.

Have sudoku::solve() return a sudoku

What is the difference between an unsolved Sudoku and a finished one? It's just that some more of its squares have been filled with numbers. So the solution to a Sudoku is just another Sudoku (albeit a trivial one). You can use this to return the result of the solve() function, and this also gets rid of another global variable. Also, instead of passing in a whole new array to solve(), I would expect the member function solve() to solve the current sudoku.

Another issue is that a given configuration might not have a solution, so apart from the resulting 9x9 squares, it might be nice to return a value indicating whether it was solved correctly or not. There are several ways to do this, you could use a std::pair<sudoku, bool> to return the 9x9 squares and a boolean, or maybe add a bool solved member variable to class sudoku itself, or use the C++17 std::optional<sudoku>.

With this in place, it should be possible to rewrite your solve() to not have an int arr[9][9] parameter.

Use hypotf() to calculate the distance between two points

For example, in scanner::distance(), you could write:

return std::hypotf(i - p.x, j - p.y);

Try to separate computation from presentation

To avoid the different components of your program depending too much on each other, you should try to separate computation from presentation. For example, in scanner::preprocessing(), you are showing the intermediate results in windows. However, now you've tightly coupled this function with the way you output those results. It would be better to just optionally return the intermediate results, and leave it up to the GUI code to present those results if desired.