Sudoku Solver (easy/medium)

Question

I have written my first real C++ project, a Sudoku solver! It's not elegant, but it works well. It solves easy and medium but not hard!

#include <locale>
#include <iostream>
#include <fstream>
#include <string>
#include <ctype.h>
#include <cstring>


const char test[11] = {'e', '1', '2', '3', '4', '5', '6', '7', '8', '9', '*'};


class Grid { // A Class With The Goal Of Solving A Sudoku

    public:

    char board[9][9] = { {0} }; // Declare (and apparently initialize) the sudoku grid array

    void mapChars(std::string fileName) { // function to get a users input sudoku file and parse to the array

        std::ifstream myfile (fileName.c_str());

        if (myfile.is_open()) {
            std::string line;
            unsigned int x = 0;
            unsigned int y = 0;
            while (getline(myfile,line)) {
                for(unsigned int i = 0; i < 20; i++) {
                    if(strchr(test, line[i]) != NULL){
                        if (line[i] == 'e') {
                            y++; x=0;
                        } else {
                            board[y][x] = line[i];
                            x++;
                        }
                    }
                }
            } myfile.close();
        }
    }

    void dumpMap() {
        for(unsigned int j = 0;j < 9;j++){
            for(unsigned int i = 0;i < 9;i++){
                std::cout << board[j][i] << ' ';
            }
            std::cout << std::endl;
        }
    }

    bool testGrid(char sType, char ident, unsigned int num) { // sType takes type { c: col , r: row, s: square, a: all
        unsigned int count = 0;
        if ( sType == 'r' ) {
            for(int it = 0; it < 9; it++) {
                if(board[num][it] == ident) { count = 1; }
            }
            if(count == 1){
                return true;
            } else {
                return false;
            }
                return false;
        }
        if ( sType == 'c' ) {
            for(int it = 0; it < 9; it++) {
                if(board[it][num] == ident) { count = 1; }
            }
            if(count == 1){
                return true;
            } else {
                return false;
            }
        }
        if ( sType == 's' ) {
            unsigned int startY = 0;
            unsigned int startX = 0;
            unsigned int count = 0;

            startY = (num / 3) * 3;
            startX = (num % 3) * 3;

            unsigned int rw = startY;
            unsigned int cl = startX;

            while(rw < (startY + 3)) {
                while(cl < (startX + 3)) {
                    if(board[rw][cl] == ident){ count = 1; }
                cl++;
                }
                rw++;
                cl = startX;
            }
            if(count == 1){
                return true;
            } else {
                return false;
            }
        }
                return false;
    }

    unsigned int wildCardCount() {
        unsigned int wildCards = 0;
       for(unsigned int j = 0;j < 9;j++){
            for(unsigned int i = 0;i < 9;i++){
                    if(board[j][i] == '*') { wildCards++; }
            }
        }
        return wildCards;
    }

    // find coords of first blank cell in square 1

void doStuff(int iter) {

    unsigned int startY = 0;
    unsigned int startX = 0;

    startY = (iter / 3) * 3;
    startX = (iter % 3) * 3;

    unsigned int rw = startY;
    unsigned int cl = startX;

    while(rw < (startY + 3)) {
        while(cl < (startX + 3)) {
            if(board[rw][cl] == '*'){

                char poss[9] = {'1','2','3','4','5','6','7','8','9'};
                unsigned int totalcount = 0;
                unsigned int possibilities = 0;

                for(unsigned int alpha = 0; alpha < 9; alpha++){

                    if (testGrid('r', poss[alpha], rw) == true) { totalcount++; }
                    if (testGrid('c', poss[alpha], cl) == true) { totalcount++; }
                    if (testGrid('s', poss[alpha], iter) == true) { totalcount++; }

                    if(totalcount == 0) { possibilities++; }

                    totalcount = 0;
                }

                //std::cout << possibilities << " possibilities" << std::endl;

                if(possibilities == 1) {
                    unsigned int possibleRow = rw;
                    unsigned int possibleCol = cl;
                    unsigned int lastCheck = 0;

                    for(unsigned int alpha = 0; alpha < 9; alpha++){
                        if (testGrid('r', poss[alpha], possibleRow) == true) { lastCheck++; }
                        if (testGrid('c', poss[alpha], possibleCol) == true) { lastCheck++; }
                        if (testGrid('s', poss[alpha], iter) == true) { lastCheck++; }
                        if(lastCheck == 0) { board[rw][cl] = poss[alpha]; }
                        lastCheck = 0;
                    }
                }
                possibilities = 0;
            }
            cl++;
        }
        rw++;
        cl = startX;
    }
}

} sudoku;

int main() {

    unsigned int initialBlanks = 0;

    sudoku.mapChars("med1.map");
    sudoku.dumpMap();
    initialBlanks = sudoku.wildCardCount();
    std::cout << std::endl << initialBlanks << " blanks remain." << std::endl << std::endl;;

    while(sudoku.wildCardCount() != 0){

        for(unsigned int beta = 0; beta < 10; beta++) {
            sudoku.doStuff(beta);
            sudoku.dumpMap();
            std::cout << std::endl << sudoku.wildCardCount() << " blanks remain." << std::endl << std::endl;;
        }
    }

    std::cout << std::endl << "Completed. " << initialBlanks << " blanks filled.";
    return 0;

    }

It takes a .MAP file, which is just the following:

s-*-*-*-*-*-1-4-5-9-e
s-*-*-1-*-5-6-*-*-8-e
s-*-*-*-3-*-*-*-*-6-e
s-1-8-*-*-*-7-*-*-*-e
s-*-*-*-*-3-*-*-*-*-e
s-3-*-*-*-*-2-*-*-*-e
s-8-*-*-4-7-*-3-*-*-e
s-7-9-2-6-*-*-*-*-*-e

Am I please with myself? Yes. Am I finished? No.

I just now need to work out what I need to do to start solving those hard grids, tidy up the code and put in some validation.

Answer 1

First off, please forgive me for taking the easy route and just commenting on the structure of your code and variable naming.

In testGrid, you have this:

if ( sType == 'r' ) {
  //...
}
if ( sType == 'c' ) {
  //...
}
if ( sType == 's' ) {

Generally, consider using else if. This won't have any effect for now but it increases readability (as the intention is clear that one of x possibilities will be executed) and might prevent some hard to find bugs later on if you modify the code and two branches are executed instead of one.

In this case, those three disjoint if() branches make up the whole function, though, so I suggest creating three separate functions. This way, you don't need to pass any sType and the function name will inform you and any readers exactly what is happening (compare testGrid('r', 3, 0) vs. testRow(3, 0).

This would also offer you the opportunity of giving the parameter num a more meaningful name, say row, col and square or square_nr. It will also help you: if you want to optimize the code for rows, you're not stuck in this huge function and you don't have to worry that you'll break something somewhere else by accident.

(In all fairness, the idea of "flags" sounds nice, though. It's better than some magic if(nr == 2) { /* process a row */ } kind of code.

---

unsigned int startY = 0;
// ...
startY = (num / 3) * 3;

I would immediately do unsigned int startY = (num / 3) * 3; It threw me a little off that the declaration with = 0 and the actual initialization were a few lines apart and that nothing happened with that 0. Or just drop the = 0 at the declaration; that would probably be the nicest way.

---

Variable naming. I would add that one additional letter to rw and cl to make them row and col and then a reader doesn't have to deduct from rw = startY that it is indeed a row number.

I have no clue what void doStuff(int iter) does, nor do the counter variables alpha and beta in the for loops provide any information on their meaning, on what is being iterated through.

You're not only doing code readers a favor, but also yourself: if you iterate through rows and appropriately call the variable row, it will be less troublesome to identify a bug. If you reference board[col] instead of board[row] at one point, I'd say you have better chances of noticing the error compared to board[alpha] and board[beta], where you have to keep in mind from which loop the variables stems from.

---

if(count == 1){
   return true;
} else {
   return false;
}
   return false;

One return false too many; you can choose which one you want to remove (but please fix the indentation of the second one if you keep it).

---

After renaming doStuff, it would probably be wise to make two functions out of this one as well: one where you iterate through all of those loops (your entry point function) and one where you check if you can attribute a number to a cell.

Right now, doStuff goes through two whiles, one if, one for and then a few if checks. If you just have two whiles, your if the cell is * check and then something like examineCell(row, col), I know "Ahh! He's going through every cell and then examining it if it's empty."

Answer 2

Hard grids often require a guess, followed by normal solving. If it fails, then you need to back track and try another guess.

An approach I like is to create objects that are "views" of the grid. That is, each view is an array of 9 cells. Separate arrays of these views are created for rows, columns and squares. You can then apply consistent rules that operate on any view.

There is a lot of related information on the net. I've just scratched the surface.