C/C++ Efficiently Solving Sudoku in C++

[Fronzbot]

Hey everyone, I'm trying to teach myself C++ and I recalled that a few years ago my Comp Sci major buddy of mine did a sudoku solving program as a project for a class so I decided to tackle it on my own. I'm getting some headway, but I'm having trouble figuring out a way to "brute force" through the puzzle without overwriting any of the given constants. I've included the whole code here and the puzzle I'm inputting is at the bottom.

I have about an intermediate knowledge of C so many of the basic concepts behind C++ I understand. Structures, classes and object oriented programming in general are pretty new to me so please bear with me. If anyone can give me some guidance or even suggest new ways to approach the puzzle (brute force just seemed like the easiest to implement!) feel free to let me know. Thanks in advance!

#include <iostream>
#include <string>
#include <fstream>
#include <cstdlib>

using namespace std;

ifstream puzzleFile;
string puzzleLoc;
int rows[9][9];
int setNum[]={1,2,3,4,5,6,7,8,9};

int main(){
        //original plan involved searching for file to use as puzzle but was having trouble.  I'll figure that out later
	//cout << "Puzzle to solve: ";
	//getline(cin, puzzleLoc);
	puzzleFile.open("puzzle.txt");

	if(!puzzleFile){
		cerr << "\nFAILURE!  Unable to open " << puzzleLoc << endl;
		return(1);
	}
	
	int i = 0;
	int j = 0;
	//Stores puzzle into array rows
	while(!puzzleFile.eof()){
		puzzleFile >> rows[i][j];
		++i;
		if(i == 9){
			++j;
			i = 0;
		}
	}
	
	puzzleFile.close();
	
	i = 0;
	j = 0;
	int k = 0;
	

	/*
	THIS IS WHAT SOLVES THE PUZZLE.  I can't figure out how to go through the puzzle without
	accidentally overwriting the constants in the given puzzle.
	*/  
	while(j <= 9){
		for(i = 0; i <= 9; ++i){
			if(rows[i][j] == 0){
				rows[i][j] == setNum[k];
				if(i != 0){
					while((rows[i-1][j] == rows[i][j])  &&  (k <= 10)){
						++k;
						if(k == 10){
							--i;
						}else{
							rows[i][j] = setNum[k];
						}
					}
				}
				k = 0;
				if(j != 0){
					while((rows[i][j-1] == rows[i][j]) && (k <= 10)){
						++k;
						if(k == 10){
							--j;
						}else{
							rows[i][j] = setNum[k];
						}
					}
				}
			}
		}	
	}
	
        //prints the puzzle solution on screen
	cout << endl;
	cout << "Solution: " << endl;
	cout << "+-----------------+" << endl;
	cout << "|" << rows[0][0] << " " << rows[1][0] << " " << rows[2][0];
	cout << "|" << rows[3][0] << " " << rows[4][0] << " " << rows[5][0];
	cout << "|" << rows[6][0] << " " << rows[7][0] << " " << rows[8][0];
	cout << endl;
	cout << "|" << rows[0][1] << " " << rows[1][1] << " " << rows[2][1];
	cout << "|" << rows[3][1] << " " << rows[4][1] << " " << rows[5][1];
	cout << "|" << rows[6][1] << " " << rows[7][1] << " " << rows[8][1];
	cout << endl;
	cout << "|" << rows[0][2] << " " << rows[1][2] << " " << rows[2][2];
	cout << "|" << rows[3][2] << " " << rows[4][2] << " " << rows[5][2];
	cout << "|" << rows[6][2] << " " << rows[7][2] << " " << rows[8][2];
	cout << endl;
	cout << "|-----+-----+-----|" << endl;
	cout << "|" << rows[0][3] << " " << rows[1][3] << " " << rows[2][3];
	cout << "|" << rows[3][3] << " " << rows[4][3] << " " << rows[5][3];
	cout << "|" << rows[6][3] << " " << rows[7][3] << " " << rows[8][3];
	cout << endl;
	cout << "|" << rows[0][4] << " " << rows[1][4] << " " << rows[2][4];
	cout << "|" << rows[3][4] << " " << rows[4][4] << " " << rows[5][4];
	cout << "|" << rows[6][4] << " " << rows[7][4] << " " << rows[8][4];
	cout << endl;
	cout << "|" << rows[0][5] << " " << rows[1][5] << " " << rows[2][5];
	cout << "|" << rows[3][5] << " " << rows[4][5] << " " << rows[5][5];
	cout << "|" << rows[6][5] << " " << rows[7][5] << " " << rows[8][5];
	cout << endl;
	cout << "|-----+-----+-----|" << endl;
	cout << "|" << rows[0][6] << " " << rows[1][6] << " " << rows[2][6];
	cout << "|" << rows[3][6] << " " << rows[4][6] << " " << rows[5][6];
	cout << "|" << rows[6][6] << " " << rows[7][6] << " " << rows[8][6];
	cout << endl;
	cout << "|" << rows[0][7] << " " << rows[1][7] << " " << rows[2][7];
	cout << "|" << rows[3][7] << " " << rows[4][7] << " " << rows[5][7];
	cout << "|" << rows[6][7] << " " << rows[7][7] << " " << rows[8][7];
	cout << endl;
	cout << "|" << rows[0][8] << " " << rows[1][8] << " " << rows[2][8];
	cout << "|" << rows[3][8] << " " << rows[4][8] << " " << rows[5][8];
	cout << "|" << rows[6][8] << " " << rows[7][8] << " " << rows[8][8];
	cout << endl;
	cout << "+-----------------+" << endl;	
	
	return(0);

}

Puzzle:

0 0 8 6 0 1 0 0 7
7 6 0 5 0 0 0 0 2
0 5 0 0 8 0 9 0 4
0 9 0 3 7 0 0 2 5
0 0 1 0 0 0 7 0 0
8 2 0 0 9 5 0 3 0
3 0 4 0 5 0 0 7 0
6 0 0 0 0 2 0 8 1
2 0 0 9 0 7 6 0 0

 

[Jocko Homo]

Without being specific, you could copy your puzzle state to a new one and manipulate that.

Incidentally, do you understand recursion?

 

[Fronzbot]

Yeah, I had actually thought about using recursion and may still do so. It's been a few years since I had any formal programming class (an Intro to C class my freshman year of college) so I'd just need to read some stuff to refresh my memory. Seems like the safest route to go.

I actually solved my problem by doing something similar to what you said. I just copied the puzzle into my array rows[9][9] and then tested to see if the value was 0 (which means a blank spot). If "rows" was 0 then I placed a 0 in a new array called constLoc (which shows me the location of all the given values). If "rows" was NOT 0, then a 1 was placed in constLoc. I then use that to test to see if I'm allowed to replace a value. That part works fine currently, but now I need to tweak my program some more because it's pretty much just printing the puzzle out with only one or two value changes on the first row and everything else is the same. Probably give it another good think-through later tonight as well as refresh my memory on recursion.

Thanks!