So…
I have been working on this for a few days and although I’m not quite done with it, I wanted to go ahead and get some feedback from you guys here. I haven’t done a whole lot of programming before, but this is my first REAL C++ program to accomplish a task.
It’s a Sudoku Solver!
So yeah, my sudoku solving algorithm lies upon a few ideas. Imagine this, Take a sudoku puzzle and write the numbers 1-9 in each blank square. Find the first “filled-in” square (one that is filled in from the beginning). Let’s say it’s a 7. From that square, erase all of the 7’s up and down and across and “all around” (in the same 9x9 sector). This is in the function called ClearRoutine. Move on to the next “filled in” number and do the same. Repeat until you’re done with the entire set of “pre-filled numbers.”
Once you’re done with this you’ll have a few cells which only have one number left. That is the new number for the cell, obviously. Repeat the above step for the new “filled-in” numbers.
After you do that, you look across, up and down, and in the sectors for numbers that appear only once. So if you look at a column, and the number 3 appears as a possibility only once (remember at the beginning we filled the empty squares with all possible numbers and started erasing them). Thus the only square that has 3 as a possibility in that column MUST be 3. This is in the function called FindSolos
This is the logic I tried to include in the program.
Here’s how I went about it…
I started with an array…Yes I realize there’s probably better ways of doing this. That’s why I’m writing this! Please help me improve it if possible!
So I started with an array. It’s a 3d array called grid. it’s initialized as grid[10][10][10] because I wanted to be able to access the cells in a more natural way. I didn’t want to have to call the first one 0,0 but 1,1
Anyway, the first two elements are i, and j. I is the horizontal compenent, and j is the vertical. I realize this is backwards-like but I got used to it. The third component is the important part. That is what I call “k.” Let me explain a bit here with an example.
If cell 1,1 is filled with the number 6, that will be represented by grid[1][1][0]=5. That is to say when a cell is finished, grid*[j][0]=whatever number it is. Otherwise grid*[j][0]=0. So what do grid*[j][1-9] represent? That is where I stored the values for the possible values. If 5 has been ruled out for cell 1,1 then grid[1][1][5]=0. Obviously at the start I fill grid*[j][1-9] with all ones.
So anyway here is the code:
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
void ReadInGrid();
void PrintOutGrid();
void FillPossible();
void ClearRoutine(int, int, int);
void WriteNumb(int, int, int);
void CheckNewFinished();
void IsDone();
void FindSolos();
void DetailComplete();
void CheckNew();
int grid [10][10][10];
int i, j, k;
int o;
int main ()
{
ReadInGrid();
PrintOutGrid();
FillPossible();
CheckNew();
int count=0;
while (grid [0][0][0]!=1 && count < 30)
{
CheckNewFinished();
FindSolos();
cout << "Pass Number: "<< count << endl << endl;
PrintOutGrid();
DetailComplete();
count++;
/* cout << "Number Test"<< endl;
cout << "input i" << endl;
cin >> i;
cout << "input j" << endl;
cin >> j;
cout << "detail grid" << endl;
DetailComplete();
cout << "Some Stats:"<< endl;
for (k=1; k<=9; k++){
cout << k << " "<< grid *[j][k]<< ", "<< endl;
}*/
}
return 0;
}
void ReadInGrid()
{
ifstream sdkin("/Users/Mike/sudoku.sdk");
for (i=1; i<=9; i++)
{
j=1;
for(j=1; j<=9; j++)
{
sdkin >> grid *[j][0]; //*[j][0] is the position for the confirmed numbers
}
}
}
void PrintOutGrid()
{
cout << "suduko grid as of now"<< endl;
cout << " --------------------"<< endl;
for (i=1; i<=9; i++)
{
j=1;
cout << "|";
for(j=1; j<=9; j++)
{
if(grid*[j][0]!=0) cout << grid*[j][0] << " ";
else cout << " ";
if(j%3==0)cout << "|";
}
cout << endl;
if(i%3==0)cout << "---------------------"<< endl;
}
}
void FillPossible()
//fills in all of the k values for all empty cells
//only run to initialize in the beginning
{
for (i=1; i<=9; i++){
for (j=1; j<=9; j++){
//new cycle for the possible values in k
if (grid*[j][0]==0)
for (k=1; k<=9; k++){
grid*[j][k]=1;
}
}
}
}
void CheckNewFinished(){
int total = 0;
int newnumb = 0;
for (i=1; i<=9; i++){
for (j=1; j<=9; j++){
for (k=1; k<=9; k++){
total += grid *[j][k];
if (grid*[j][k] == 1)
newnumb=k;
}
if (total == 1)
{
WriteNumb(i, j, newnumb);
cout << "HI OPAL!!!"<<endl;
cout << "Location: " << i << ", "<< j << endl;
}
if (grid*[j][0]>0)
{
WriteNumb(i,j,grid*[j][0]);
}
total=0;
newnumb=0;
}
}
}
void IsDone(){
int count = 0;
for(i=1; i<=9; i++){
for (j=1; j<=9; j++){
if (grid*[j][0]==0) count++;
}
}
if (count<=1) grid[0][0][0]=1;
count=0;
}
void FindSolos(){
//this function also incorporates another sudoku solving technique
//namely that if there is only one existing k:x in a column, row, or quadrant
//then then X must be located in the square. So this function starts and checks every
//row starting with the number one. If the row contains only one cell with a possibility
//of a 1 then it marks it there. Same for the vertical. The final part of this functin
//does a test of all 9 quadrants in a similar way to the ClearRoutine earlier
int test, testsum, posi, posj;
posi=0;
posj=0;
testsum=0;
//horizontal
for(test=1; test<=9; test++)
{
for(i=1; i<=9; i++)
{
testsum=0;
posi=0;
posj=0;
for (j=1; j<=9; j++)
{
if (grid*[j][test]==1)
{
posi=i;
posj=j;
testsum++;
}
}
if (testsum==1)
{
WriteNumb(posi, posj, test);
}
}
}
posi=0;
posj=0;
testsum=0;
/*
//vertical
for(test=1; test<=9; test++)
{
for(j=1; j<=9; i++)
{
testsum=0;
posi=0;
posj=0;
for (i=1; i<=9; i++)
{
if (grid*[j][test]==1)
{
posi=i;
posj=j;
testsum++;
}
}
if (testsum==1)
{
WriteNumb(posi, posj, test);
}
}
}
*/
}
void DetailComplete(){
int i, j, test;
cout << " ---------------------------------------------------------------- "<< endl;
for (i=1; i<=9; i++){
cout << "|";
for (j=1; j<=9; j++){
for (test=1; test<=3; test++){
if(grid*[j][test]==1)cout << test << " ";
else cout << " ";
if(test%3==0 && j%3==0 && j<9) cout << "||";
else if(test%3==0) cout << "|";
}
}
cout << endl;
cout << "|";
for (j=1; j<=9; j++){
for (test=4; test<=6; test++){
if(grid*[j][test]==1)cout << test << " ";
else cout << " ";
if(test%3==0 && j%3==0 && j<9) cout << "||";
else if(test%3==0) cout << "|";
}
}
cout << endl;
cout << "|";
for (j=1; j<=9; j++){
for (test=7; test<=9; test++){
if(grid*[j][test]==1)cout << test << " ";
else cout << " ";
if(test%3==0 && j%3==0 && j<9) cout << "||";
else if(test%3==0) cout << "|"; }
}
if(i%3==0 && i<9)cout << "
----------------------------------------------------------------
---------------------------------------------------------------- ";
else cout << "
---------------------------------------------------------------- ";
cout << endl;
}
}
void ClearRoutine(int i, int j, int numb)
//clears the relavent parts of the suduko grid
//based on a solved square. This will remove the
//possibility (k values) from all vertical, horizontal
//and quadrant positions. i and j are the position in the
//grid and numb is the number that will be cleared.
{
int q;
//cout <<"please pass"<< endl;
//cin >> q;
//DetailComplete();
//PrintOutGrid();
int oldi, oldj, indexi, indexj;
oldi=i;
oldj=j;
//horizontal
for (i=1; i<=9; i++)
{
grid*[j][numb]=0;
}
i=oldi; //reset to original values
j=oldj;
//vertical
for (j=1; j<=9; j++)
{
grid*[j][numb]=0;
}
i=oldi;
j=oldj;
/* In order to do operations on the square
it is important to make sure that you can
input any number and come up with a consistent
way to clear the cells in the "quadrant" So the
way it's done here is to subtract one then divide by 3.
then multiplying by 3 and adding one always results in
the "index square" which is the top left corner of the
9x9 "quadrant" to be cleared. This is what is done below
*/
indexi=(((i-1)/3)*3)+1;
indexj=(((j-1)/3)*3)+1;
// now loop to clear 9x9 quadrant
for (i=indexi; i<=indexi+2; i++)
{
for (j=indexj; j<=indexj+2; j++)
{
grid*[j][numb]=0;
}
}
}
void WriteNumb(int i, int j, int numb)
//this is the standard function for writing
//a number to the grid. It's good to control
//it this way in order to make sure the appropriate
//clearing routines are done afterwards to update
//the grid with a new status
{
grid*[j][0]=numb;
ClearRoutine(i, j, numb);
for(k=1; k<=9; k++)
{
grid*[j][k]=0; //since it's done, set all other k values to 0
}
}
void CheckNew()
//This is to initialize the array based on the
//beginning values.
{
for (i=1; i<=9; i++)
{
for (j=1; j<=9; j++)
{
if (grid*[j][0]>0){
{
ClearRoutine(i,j,grid*[j][0]);
}
}
}
}
}
//Finde Finished
//ClearRoutine
Also, if you want to compile and run it you’ll need to change the path for the input file which is in the function ReadInGrid. The format for the file is as follows:
0 5 0 7 0 0 0 0 8
0 0 3 0 5 4 0 7 0
2 0 9 3 0 0 5 0 4
0 0 5 1 0 2 4 0 0
3 4 0 0 0 0 0 0 7
0 0 1 4 3 0 9 0 5
0 0 2 0 0 0 0 5 6
0 3 0 6 0 5 8 0 2
5 9 0 0 2 3 0 0 0
Essentially just write out the numbers and keep spaces in between the numbers. Plain text. Also notice that in the FindSolos function I only have the horizontal component. For some reason when I turned on the vertical part it froze. I have no idea why. And also to do functions in the same quadrant or whatever you want to call it, I did a weird division thing to go to an index cell and do a loop from there.
But the way it is now, it seems to solve the puzzle except for the squares that require guessing. I have tested it with a few puzzles and have found that the ones it filled in were correct. I do want to figure out some way to make it guess the correct answers down the line though.
Anyway, I don’t know a whole lot about this (just finished intro to CompSci with C++) and just want any kind of feedback whatsoever. Should I have gone about it another way? What do you think of what I’ve done? Also do you guys know of a place I could possibly post this to get more feedback? Maybe a more targeted board?
Thanks agian
ETA: Just wanted to ask, how can I prompt the user for the path of the input file? I was having trouble doing that with a string, that’s why I included the string library.