9x9 Sudoku solver

Question

I wrote this in C++ in February and am planning on adding a generator to it. Before I do that, I'd like to get input on how to improve what I've done thus far.

The goal was to be able to solve every Sudoku I throw at it. This includes the ones that reach a point where you can no longer assign numbers based on what they might be. Then you have to start guessing from the list of potential values until you find the right one(s).

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class subSquare{
private:
    //fNum is the final assigned number, pNums are numbers that a subsquare could potentially be.
    int fNum;
    vector<int> pNums;
public:
    void assignFNum(int const& num){
        pNums.clear();
        fNum=num;
    }
    void assignPNum(int const& num){
        pNums.push_back(num);
    }
    int getFNum(){
        return fNum;
    }
    vector<int> getPNums(){
        return pNums;
    }
    void removePNum(int const& num){
        int pos = (distance(pNums.begin(), find(pNums.begin(), pNums.end(), num)));
        pNums.erase(pNums.begin() + pos);
    }
    bool PNumsContain(int const& num){
        return(find(pNums.begin(), pNums.end(), num) < pNums.end());
    }
};

//Used to make sure the user is only entering rows of numbers.
bool isNumeric(string const& input){
    for(int itr=0; itr<input.length(); itr++){
        if(!isdigit(input.at(itr))){
            return false;
        }
    }
    return true;
}

//Because I'll be damned if I'm gonna write a program that crashes when the user types "soLvE" or "BacK".
void strToUpper(string& input){
    for(int itr=0; itr<input.length(); itr++){
        input[itr]=toupper(input[itr]);
    }
}

//Reads the Sudoku grid. Name says it all.
void readGrid(subSquare input[9][9]){
    for(int row=0; row<9; row++){
        for(int col=0; col<9; col++){
            printf("%d ", input[row][col].getFNum());
        }
        printf("\n");
    }
}

//User enters the Sudoku row by row. Allows for mess-up correction.
void createGrid(subSquare input[9][9]){
    string currentRow;
    printf("Enter the grid below, row by row. put zeroes where nothing is assigned. No delimiting characters. Enter 'back' to go back one row if you messed up.\n");
    int row=0;
    while(row<9){
        currentRow="";
        printf("Enter row %d:\n", row+1);
        getline(cin, currentRow);
        strToUpper(currentRow);
        if(isNumeric(currentRow)){
            if(currentRow.length()==9){
                for(int col=0; col<9; col++){
                    input[row][col].assignFNum(currentRow.at(col) - '0');
                }
                row++;
            }else if(currentRow.length() < 9){
                printf("ERROR: entry too short\n");
            }else{
                printf("ERROR: entry too long\n");
            }
        }else{
            if(currentRow=="BACK"){
                switch(row){
                    case 0: printf("Cannot go back further\n"); break;
                    default: row--; break;
                }
            }else{
                printf("ERROR: entry not valid\n");
            }
        }
    }
}

//Copies one grid of sudoku subsquares to another. For use in the event the state of one 2D grid needs saved.
void cpyGrid(subSquare dst[9][9], subSquare src[9][9]){
    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            dst[row][col] = src[row][col];
        }
    }
}

//Needed to make this one to use sets of sudoku grids. Mode denotes whether or not we're adding to a set of grids (TD) or copying one from a set of grids to another individual 2D grid (arr, couldn't think of a decent name).
void cpyGrid2(subSquare TD[9][9][9], subSquare arr[9][9], int const& TDIndx, string const& mode){
    if(mode == "TO_3D"){
        for(int row = 0; row < 9; row++){
            for(int col = 0; col < 9; col++){
                TD[TDIndx][row][col] = arr[row][col];
            }
        }
    }else if(mode == "TO_2D"){
        for(int row = 0; row < 9; row++){
            for(int col = 0; col < 9; col++){
                arr[row][col] = TD[TDIndx][row][col];
            }
        }
    }
}

//Checks if there are any 0s (i.e. unassigned subsquares) in the grid passed in.
bool gridUnsolved(subSquare input[9][9]){
    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            if(input[row][col].getFNum() == 0){
                return true;
            }
        }
    }
    return false;
}

//For checking the relevant 3x3 square. Indx vars are the subsquare in question, PH means PlaceHolder (i.e. the row/column where the upper-left-most subsquare in the 3x3 square is.
void mkSqrVars(int const& rowIndx, int const& colIndx, int& rowPH, int& colPH){
    switch(rowIndx){
        case 0: case 1: case 2:
            rowPH=0;
            break;
        case 3: case 4: case 5:
            rowPH=3;
            break;
        case 6: case 7: case 8:
            rowPH=6;
            break;
        default: break;
    }
    switch(colIndx){
        case 0: case 1: case 2:
            colPH=0;
            break;
        case 3: case 4: case 5:
            colPH=3;
            break;
        case 6: case 7: case 8:
            colPH=6;
            break;
        default: break;
    }
}

/*Quick note about the (x)ContainsNum functions when they're looking for pNums: they return true when instances exceeds 1 because if a number could potentially be assigned to a
part of the grid, it will have one (but ONLY one) instance in that part of the grid.*/

//Checks if a 3x3 square contains an fNum or pNums. Does this by checking the subsquare that mkSqrVars tells it to for the fNum.
bool squareContainsNum(subSquare input[9][9], int const& rowIndx, int const& colIndx, int const& num, string const& checkingFor){
    int instances = 0;

    int row;
    int rowPH;
    int col;
    int colPH;
    mkSqrVars(rowIndx, colIndx, rowPH, colPH);
    //stopRow/Col: the row or col to stop at (i.e. the place where the relevant 3x3 square ends.
    int stopRow=rowPH+3;
    int stopCol=colPH+3;
    if(checkingFor == "fNums"){
        for(row=rowPH; row<stopRow; row++){
            for(col=colPH; col<stopCol; col++){
                if(input[row][col].getFNum() == num){
                    return true;
                }
            }
        }
        return false;
    }else if(checkingFor == "pNums"){
        for(row = rowPH; row < stopRow; row++){
            for(col = colPH; col < stopCol; col++){
                if(input[row][col].PNumsContain(num)){
                    instances++;
                    if(instances > 1){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

//Checks if the row contains an fNum or pNums.
bool rowContainsNum(subSquare input[9][9], int const& rowIndx, int const& num, string const& checkingFor){
    int instances = 0;
    if(checkingFor == "fNums"){
        for(int col = 0; col < 9; col++){
            if(input[rowIndx][col].getFNum() == num){
                return true;
            }
        }
        return false;
    }else if(checkingFor == "pNums"){
        for(int col = 0; col < 9; col++){
            if(input[rowIndx][col].PNumsContain(num)){
                instances++;
                if(instances>1){
                    return true;
                }
            }
        }
        return false;
    }
}

//Checks if the column contains an fNum or pNums.
bool colContainsNum(subSquare input[9][9], int const& colIndx, int const& num, string const& checkingFor){
    int instances = 0;
    if(checkingFor == "fNums"){
        for(int row = 0; row < 9; row++){
            if(input[row][colIndx].getFNum() == num){
                return true;
            }
        }
        return false;
    }else if(checkingFor == "pNums"){
        for(int row = 0; row < 9; row++){
            if(input[row][colIndx].PNumsContain(num)){
                switch(instances){
                    case 0: instances++; break;
                    default: return true; break;
                }
            }
        }
        return false;
    }
}

//Assigns an fNum to a subSqaure. This means removing the pNums matching the fNum being assigned from the adjescent row, column, and 3x3 square.
void fullAssign(subSquare input[9][9], int const& rowIndx, int const& colIndx, int const& num){
    input[rowIndx][colIndx].assignFNum(num);

    //Erase number from pNums of subsquares where it's no longer applicable: row
    for(int c = 0; c < 9; c++){
        if(input[rowIndx][c].PNumsContain(num)){
            input[rowIndx][c].removePNum(num);
        }
    }
    //Erase number from pNums of subsquares where it's no longer applicable: col
    for(int r = 0; r < 9; r++){
        if(input[r][colIndx].PNumsContain(num)){
            input[r][colIndx].removePNum(num);
        }
    }
    //Erase number from pNums of subsquare where it's no longer applicable: square
    int row;
    int rowPH;
    int col;
    int colPH;
    mkSqrVars(rowIndx, colIndx, rowPH, colPH);
    int stopRow = rowPH+3;
    int stopCol = colPH+3;
    for(row = rowPH; row < stopRow; row++){
        for(col = colPH; col < stopCol; col++){
            if(input[row][col].PNumsContain(num)){
                input[row][col].removePNum(num);
            }
        }
    }
}

//Assigns pNums based on what fNums are already assigned.
void phase1(subSquare input[9][9]){
    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            for(int num = 1; num < 10; num++){
                //Pushes num to pNums if it's not already an fNum in the subSquare's row/col/3x3 square.
                if(input[row][col].getFNum() == 0){
                    if(!squareContainsNum(input, row, col, num, "fNums") &&
                     !rowContainsNum(input, row, num, "fNums") &&
                     !colContainsNum(input, col, num, "fNums")){
                       input[row][col].assignPNum(num);
                    }
                }
            }
        }
    }
}

//Assigns fNums based on what the pNums will allow. Does this over and over as long as numbers keep getting assigned. Not all Sudokus will require phase3, this solves most easy ones.
void phase2(subSquare input[9][9]){
    int numbersAssigned = 0;
    do{
        numbersAssigned = 0;
        for(int row = 0; row < 9; row++){
            for(int col = 0; col < 9; col++){
                for(int num = 1; num < 10; num++){
                    //Does a full assign if the subSquare is unassigned, could be num, and is the only one that could be num in at least its row/col/3x3 square.
                    if(input[row][col].getFNum() == 0 && input[row][col].PNumsContain(num)){
                        if( (input[row][col].getPNums().size() == 1) ||
                            (!squareContainsNum(input, row, col, num, "pNums") || 
                             !rowContainsNum(input, row, num, "pNums") || 
                             !colContainsNum(input, col, num, "pNums"))){
                                fullAssign(input, row, col, num);
                                numbersAssigned++;
                        }
                    }
                }
            }
        }
    }while(numbersAssigned);
}

/*For when phase2 stops but there are still 0s. This occurs when the pNums can no longer be used alone to decide what should be assigned where, which means we've got to start guessing.
This is where it's either solved or deemed impossible to solve (by the standards of the program, at least...).*/
void phase3(subSquare input[9][9]){
    //Save the state of the subSquare to revert in the event of an incorrect guess.
    subSquare savedState[9][9];
    cpyGrid(savedState, input);

    //Row and column for where we're going to start guessing.
    int guessRow;
    int guessCol;

    //Finds the first zero to start guessing on.
    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            if(input[row][col].getFNum() == 0){
                guessRow = row;
                guessCol = col;
                row = 10;
                col = 10;
            }
        }   
    }

    //The number of guesses to be made (i.e. pNums in the chosen subSquare).
    int guesses = savedState[guessRow][guessCol].getPNums().size();

    //The number with which the guess is being made.
    int guessNum;
    //The number of guesses that have been made.
    int guessNumIndx = 0;
    //An array of 9x9 grids, for when we need to make more than one guess. This rarely happens, but it still happens.
    subSquare TD[9][9][9];
    //Number of grids produced as a result of guessing.
    int numGuessGrids = 0;

    if(input[guessRow][guessCol].getPNums().size() > 0){
        while(guessNumIndx < guesses && gridUnsolved(input)){
            cpyGrid(input, savedState);
            guessNum = input[guessRow][guessCol].getPNums()[guessNumIndx];
            fullAssign(input, guessRow, guessCol, guessNum);
            phase2(input);
            if(gridUnsolved(input)){
                //If that guess didn't work, then we just try the next one.
                cpyGrid2(TD, input, guessNumIndx, "TO_3D");
                numGuessGrids++;
                guessNumIndx++;
            }else{
                guessNumIndx = guesses+1;
            }
            if(guessNumIndx == guesses){
                /*If we've gone through every guess and none of them solved it, but it's still solveable, one of them MUST be right. So we have to revert to the first guess, and then make guesses on the zero after THAT one, repeating the process
                until it's made all the correct guesses. Basically goes through every possible guessing path until it finds the right one.*/
                int i = 0;
                subSquare ss[9][9];
                cpyGrid(ss, savedState);
                while(gridUnsolved(ss) && i < numGuessGrids){
                    cpyGrid2(TD, ss, i, "TO_2D");
                    phase3(ss);
                    i++;
                }
                cpyGrid(input, ss);
            }
        }
    }
}

void solve(subSquare grid[9][9]){
    printf("Before solving: \n");
    readGrid(grid);
    phase1(grid);
    phase2(grid);
    if(gridUnsolved(grid)){
        phase3(grid);
    }
    if(!gridUnsolved(grid)){
        printf("After solving:\n");
        readGrid(grid);
    }else{
        printf("ERROR: Impossible to solve. Closest it got:\n");
        readGrid(grid);
    }
}

int main(){
    printf("Enter 'gen' or 'solve'\n");
    string str;
    cin >> str;
    cin.ignore();
    strToUpper(str);
    if(str=="SOLVE"){
        subSquare grid[9][9];
        createGrid(grid);
        solve(grid);
    }else if(str=="GEN"){
        //This comes next
    }else{
        printf("ERROR: invalid option entered\n");
        return 1;
    }
    return 0;
}

Answer 1

using namespace std;

using namespace std;

Why is “using namespace std;” considered bad practice?

The particular reason why I don't like it is that it makes it hard to tell what is and is not coming from std. Another issue is that it can be hard to refactor code into separate files.

Naming

    int fNum;
    vector<int> pNums;

Consider

    int value;
    std::vector<int> possibilities;

Then you don't have to remember what you meant by fNum and pNums.

    bool PNumsContain(int const& num){

Could be

    bool isPossible(int const& num) {

Same argument.

    void assignFNum(int const& num){

Consider

    void setValue(int const& num) {

would be more idiomatic.

    void assignPNum(int const& num){

could be

    void addPossibility(int const& num) {

Which is clearer about what it is doing.

Indexes vs. iterators

    for(int itr=0; itr<input.length(); itr++){
        if(!isdigit(input.at(itr))){

When I see this, the first thing that I think is "That's no iterator!"

    for (auto itr = input.begin(); itr != input.end(); itr++) {
        if (!isdigit(*itr)) {

This is a C++ iterator. It's more common to call index variables (what you originally had) i.

Numbers don't have an uppercase

        strToUpper(currentRow);
        if(isNumeric(currentRow)){

You don't need to convert numeric rows to uppercase. You only need to convert to upper case if it is not upper case.

        if (isNumeric(currentRow)) {
// ...
        } else {
            strToUpper(currentRow);

printf vs. cout

You shouldn't mix C (printf, scanf) and C++ (cout, cin). Weird things can happen. You can use std::cout with objects. So you probably should usually stick with cout when writing C++ so as to only have one.

You can see more discussion at printf vs cout in C++.

Use enums where appropriate

    if(mode == "TO_3D"){

This is screaming for an enum. Why do a string comparison where a simple integer comparison would do? An enum gives the same readability as a string with the performance of an integer, relying on the compiler to reconcile them.

Answer 2

class subSquare{
    vector<int> pNums;

Instead of a vector, I would have chosen a simple bitset, which takes constant time for the add and remove operations. Plus, it consumes less memory.

void assignFNum(int const& num){

This is not idiomatic C++. Why don't you use a simple int num here?

if(!isdigit(input.at(itr))){

This invokes undefined behavior as soon as you get non-ASCII input on a platform that has char == signed char, e.g. x86. Use isdigit((unsigned char)(input.at(itr))) instead.

input[itr]=toupper(input[itr]);

Same here, and you need to include <ctype.h> for these functions to be available.

//Reads the Sudoku grid. Name says it all.
void readGrid(subSquare input[9][9]){
    for(int row=0; row<9; row++){
        for(int col=0; col<9; col++){
            printf("%d ", input[row][col].getFNum());
        }
        printf("\n");
    }
}

Remove the comment above the function. When the name says it all, the comment is redundant and should be removed. And, by the way, correct the name from readGrid to printGrid, so that the function does what it says.

void createGrid(subSquare input[9][9]){

Instead of passing subSquare input[9][9] to each function, you should rather make a new class called SudokuGrid for this type.

getline(cin, currentRow);

Always check if reading the line succeeded. The code must read if (getline(std::cin, currentRow)) {.

bool gridUnsolved(subSquare input[9][9]){

Try to avoid negations in API names. Prefer isSolved over isUnsolved.

    switch(rowIndx){
        case 0: case 1: case 2:
            rowPH=0;
            break;
        case 3: case 4: case 5:
            rowPH=3;
            break;
        case 6: case 7: case 8:
            rowPH=6;
            break;
        default: break;
    }

What about a simple rowPH = rowIndx - rowIndx % 3?

bool squareContainsNum(subSquare input[9][9], int const& rowIndx, int const& colIndx, int const& num, string const& checkingFor){

Split this into two separate functions. Currently, the two cases for "fNums" and "pNums" have few enough lines in common.

printf("Before solving: \n");

A space at the end of the line is not necessary.

int main(){
    printf("Enter 'gen' or 'solve'\n");
    string str;
    cin >> str;
    cin.ignore();
    strToUpper(str);
    if(str=="SOLVE"){

When the instructions say Enter 'gen' or 'solve', would anyone really press the Shift key? This thought might make the whole strToUpper function useless.

Answer 3

Cleaner Utility functions:

You can make isNumeric much shorter and clearer:

bool isNumeric(const std::string& s) {
    return std::all_of(s.begin(), s.end(), isdigit);
}

Similarly strToUpper can be:

void strToUpper(string& s) {
    for (auto& c : s) { c = toupper(c); }
}

Naming: It's typical to make objects (nouns) start with a capital letter: class subSquare would be class SubSquare.

File structure & correctness: If this is in a header, all of these functions outside of the class definition need to be marked inline (you'll get multiple definition errors if you ever include it into multiple cpps without marking them inline). However I would suggest not having this be completely in the header. Split it with a header and cpp, and I would also suggest to move generic utility functions like isNumeric and strToUpper into some other utility file that you might reuse elsewhere.

Answer 4

This is a nice first Code Review Question. It's not a simple hello world program and it took some real effort.

Use the Tools You Have
When developing new code in C++ always compile with -Wall switch. This switch provides additional compiler error checking and allows removal of possible bugs as early as possible. The compile can also treat all warnings as errors.

When I compiled the code I got the following warnings:
../src/SudokuSolver.cpp: In function ‘bool isNumeric(const string&)’:
../src/SudokuSolver.cpp:46:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int itr = 0; itr < input.length(); itr++){
../src/SudokuSolver.cpp: In function ‘void strToUpper(std::string&)’:
../src/SudokuSolver.cpp:56:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int itr=0; itr ^
../src/SudokuSolver.cpp: In function ‘bool squareContainsNum(subSquare ()[9], const int&, const int&, const int&, const string&)’:
../src/SudokuSolver.cpp:208:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
../src/SudokuSolver.cpp: In function ‘bool rowContainsNum(subSquare ()[9], const int&, const int&, const string&)’:
../src/SudokuSolver.cpp:231:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
../src/SudokuSolver.cpp: In function ‘bool colContainsNum(subSquare (*)[9], const int&, const int&, const string&)’:
../src/SudokuSolver.cpp:254:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^

Type MisMatch
When using any C++ container type that has the function length(). the function returns type size_t. The type size_t is currently defined as unsigned int. Comparing or assigning type size_t to type int can lead to surprising results because a positive unsigned value may become negative when it is converted.

The loop should be recoded as

    for(size_t itr = 0; itr < input.length(); itr++){

Missing Header File
The function printf() is defined in stdio.h. My compiler reports printf() as an error because stdio.h is not included.

Using printf() instead of std::cout
The code already uses std::cin for input (this is a good thing since the standard C++ input and output std::cin and std::cout). This is another mismatch. If using printf() for ouput than use scanf() for input.

While printf() and scanf() are still accepted in C++ as long as the proper header files are included, they are not the standard methods for C++ input and output. Prefer std::cin and std::cout over scanf() and printf().

Magic Numbers
The term Magic Numbers is sometimes used when code contains numeric constants where a named constant is more readable and maintainable. A named constant in this case might be:

const int SUDOKU_PUZZLE_SIZE = 9;

It's much easier to maintain code when it only requires a one line edit. If I needed to change the puzzle size in this code, I would have to edit 44 lines rather than just 1 line.

Namespaces
Name spaces were invented to solve a very real problem in enterprise level programming. In the bad old days, libraries acquired from other sources might contain functions that that had the same name and variable types as the code one might be writing. Then we would have to change our function names so that they didn't collide with the library names. When a programmer includes:

using namespace std;

in their code they are allow possible collisions of functions from their code and different libraries they might be using. The code here is complicated enough that one might want to include libraries to do some of the work.

Most professional programmers will use std::cin, std::cout and std::vector rather than the using namespace std; statement.