hello everyone.. thx for droppin'

i need to write a program, a recursive sudoku solver
and this is what i have so far...

main.cpp

#include <iostream>
#include <vector>
#include "sudoku.h"

using namespace std;

int main()
{
    vector< vector<char> > rows;

    // Load grid
    rows=load();
    // Check if grid is consistent.
    if (checkall(rows))
    {
        cout << "Valid grid." << endl;
    }
    else
    {
        cout << "Invalid grid; exiting";
        return 0;
    }

    // Print initial grid
    print(rows);

    // Solve grid.
    solve(rows);

    // Check solution.
    cout << "Checking solution... "<<endl;
    if (checkall(rows))
    {
        cout << "valid!" << endl;
    }
    else
    {
        cout << "not valid!" << endl;
    }
    return 0;
}

sudoku.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "sudoku.h"
using namespace std;

// Read grid from file sudoku.dat
vector< vector<char> > load()
{
    char line;
    int o;
    ifstream data("sudoku.dat");
    cout << "Loading grid..." << endl;
    vector <char> nums;
    vector < vector<char> > rows;
    for (int i=0; i!=9; i++)
    {
        for (int j=0; j!=9; j++)
        {
            data>>line;
            nums.push_back(line);
        }
        rows.push_back(nums);
        nums.resize(0);
    }
    return rows;
}

// Print grid with nice format
void print(vector< vector<char> > rows)
{
    for (int i=0; i!=9; i++)
    {
        for (int j=0; j!=9; j++)
        {
            cout << rows[i][j];
            if (j==2 || j==5)
            {
                cout << "  ";
            }
            else if (j==8)
            {
                cout << endl;
                if (i==2 || i==5)
                {
                    cout << endl;
                }
            }
            else
            {
                cout << " ";
            }
        }
    }
}

// Returns a string containing the center of the block
// to which position i,j belongs.
string block(int i, int j)
{
    char x,y;
    string result = "00";
    switch (i)
    {
    case 1:
    case 2:
    case 3:
        x='2';
        break;
    case 4:
    case 5:
    case 6:
        x='5';
        break;
    case 7:
    case 8:
    case 9:
        x='8';
        break;
    }
    switch (j)
    {
    case 1:
    case 2:
    case 3:
        y='2';
        break;
    case 4:
    case 5:
    case 6:
        y='5';
        break;
    case 7:
    case 8:
    case 9:
        y='8';
        break;
    }
    result[0] = x;
    result[1] = y;
    return result;
}

// Checks whether value num can be placed at position i,j.
bool check(int num, int i, int j, vector< vector<char> > rows)
{
    char value = (char)(num+48);
    string center;
    int x,y;
    if (value == '-')
    {
        return true;
    }
    // check row
    for (int k=0; k!=9; k++)
    {
        if (rows[i][k]==value && k!=j)
        {
            return false;
        }
    }
    // check column
    for (int k=0; k!=9; k++)
    {
        if (rows[k][j]==value && k!=i)
        {
            return false;
        }
    }
    // check region
    center = block(i,j);
    x = center[0]-48;
    y = center[1]-48;
    for (int m=-1; m<=1; m++)
    {
        for (int n=-1; n<=1; n++)
        {
            if (rows[x+m][y+n]==value && !((x+m)==i && (y+n)==j))
            {
                return false;
            }
        }
    }
    return true;
}

// Recursive Sudoku solver
void solve(vector< vector<char> > rows)
{
	bool solved;
    int i,j;
    if (solved)
    {
        return;
    }

    // Find next empty value
    for (i=0; i!=9; i++)
    {
        for (j=0; j!=9; j++)
        {
            if (rows[i][j] == '-')
            {
                break;
            }
        }
        if (rows[i][j] == '-')
        {
            break;
        }
    }
    // If no empty value is found, grid is solved
    if (i==8 && j==8)
    {
        cout << "Grid solved!" << endl;
        solved = true;
        print(rows);
        return;
    }

    // Try next possible number and solve the rest recursively
    for (int a=1; a<=9; a++)
    {
        [B]if (check(a,i,j,rows))
        {
            rows[i][j] = (char)(a+48);
            solve(rows);
        }[/B]
    }
    rows[i][j] = '-';

    return;
}

//Check all values on grid for consistency (ignores empty values)
bool checkall(vector< vector<char> > rows)
{
    int i,j;
    char value;
    for (i=0; i!=9; i++)
    {
        for (j=0; j!=9; j++)
        {
            if (rows[i][j] != '-')
            {
                value = rows[i][j];
                if (!(check((int)value,i,j,rows)))
                {
                    return false;
                }
            }
        }
        return true;
    }
    return true;
}

sudoku.h

#include <vector>

using namespace std;

vector< vector<char> > load();
void print(vector< vector<char> > rows);
string block(int i, int j);
bool check(int num, int i, int j, vector< vector<char> > rows);
void solve(vector< vector<char> > rows);
bool checkall(vector< vector<char> > rows);

when i run it,, there's an error on the recursive function solve
and i don't understand why... i'm really stuck..

really need help asap(to be submitted after several hours).. thx!

sorry for double post
this is what inside the sudoku.dat:

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

thx for helping,, need this really asap..

> for (int i=0; i!=9; i++)
1. Define a constant for the size, say const int squareSize = 9; 2. Using < is more usual for a for loop. As in for ( int i = 0; i < squareSize ; i++ ) > bool check(int num, int i, int j, vector< vector<char> > rows)
You're passing by value. Which means anything you do to update this will NOT be reflected in the caller. Meaning main() gets no results. Use a reference.
Ditto for calling yourself recursively.

> if (i==8 && j==8)
Are you sure? The values reach 9 at the end?

Additionally, to the errors above: Errors on initialization.

bool solved;
  int i,j;
  if (solved)  // ERROR: Un-initialized variable
    {
      return;
    }

You have a faliure to limit range on
line

// Find next empty value
  for (i=0; i!=9; i++)
    {
      for (j=0; j!=9; j++)
        {
	  if (rows[i][j] == '-')
	    break;
        }
      if (rows[i][j] == '-')   // ERROR j == 9 here and is out of range
        {
            break;
        }
    }

You call block() with i=0, j=0 but your switch [Very UGLY] takes 1-9 and has no default to tell you you have an error.

That results in a memory violation later.

There are others, but please please (a) use -warning-all or (-Wall for gcc). ie. put the warnings in and assume all warnings are errors.
(b) run through a debugger.

thx for the great helps...

these are the new codes

main.cpp

#include <iostream>
#include <vector>
#include "sudoku.h"

using namespace std;

int main()
{
	vector< vector<char> > rows;

    // Load grid
    rows=load();
    // Check if grid is consistent.
    if (checkall(&rows))
    {
        cout << "Valid grid." << endl;
    }
    else
    {
        cout << "Invalid grid; exiting";
        return 0;
    }

    // Print initial grid
    print(&rows);

    // Solve grid.
    solve(&rows);

    // Check solution.
    cout << "Checking solution... "<<endl;
    if (checkall(&rows))
    {
        cout << "valid!" << endl;
    }
    else
    {
        cout << "not valid!" << endl;
    }
	return 0;
}

sudoku.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "sudoku.h"
using namespace std;

// Read grid from file sudoku.dat
vector< vector<char> > load()
{
    char line;
    ifstream data("sudoku.dat");
    cout << "Loading grid..." << endl;
    vector <char> nums;
    vector < vector<char> > rows;
    for (int i=0; i<squaresize; i++)
    {
        for (int j=0; j<squaresize; j++)
        {
            data>>line;
            nums.push_back(line);
        }
        rows.push_back(nums);
        nums.resize(0);
    }
    return rows;
}

// Print grid with nice format
void print(vector< vector<char> > *rows)
{

    for (int i=0; i<squaresize; i++)
    {
        for (int j=0; j<squaresize; j++)
        {
            cout << (*rows)[i][j];
            if (j==2 || j==5)
            {
                cout << "  ";
            }
            else if (j==8)
            {
                cout << endl;
                if (i==2 || i==5)
                {
                    cout << endl;
                }
            }
            else
            {
                cout << " ";
            }
        }
    }
}

// Returns a string containing the center of the block
// to which position i,j belongs.
string block(int i, int j)
{
    char x,y;
    string result = "00";
    switch (i)
    {
		case 0:
		case 1:
		case 2:
			x='2';
			break;
		case 3:
		case 4:
		case 5:
			x='5';
			break;
		case 6:
		case 7:
		case 8:
			x='8';
			break;
    }
    switch (j)
    {
		case 0:
		case 1:
		case 2:
			y='2';
			break;
		case 3:
		case 4:
		case 5:
			y='5';
			break;
		case 6:
		case 7:
		case 8:
			y='8';
			break;
    }
    result[0] = x;
    result[1] = y;
    return result;
}

// Checks whether value num can be placed at position i,j.
bool check(int num, int i, int j, vector< vector<char> > *rows)
{

    char value = (char)(num+48);
    string center;
    int x,y;
    if (value == '-')
    {
        return true;
    }
    // check row
    for (int k=0; k<squaresize; k++)
    {
        if ((*rows)[i][k]==value && k!=j)
        {
            return false;
        }
    }
    // check column
    for (int k=0; k<squaresize; k++)
    {
        if ((*rows)[k][j]==value && k!=i)
        {
            return false;
        }
    }
    // check region
    center = block(i,j);
    x = center[0]-48;
    y = center[1]-48;
    for (int m=-1; m<=1; m++)
    {
        for (int n=-1; n<=1; n++)
        {
            if ((*rows)[x+m][y+n]==value && !((x+m)==i && (y+n)==j))
            {
                return false;
            }
        }
    }
    return true;
}

// Recursive Sudoku solver
void solve(vector< vector<char> > *rows)
{
	bool solved;
    int i,j;
    if (solved)
    {

        return;
    }

    // Find next empty value
    for (i=0; i<squaresize; i++)
    {
        for (j=0; j<squaresize; j++)
        {
            if ((*rows)[i][j] == '-')
            {
                break;
            }
        }
        if ((*rows)[i][j] == '-')
        {
            break;
        }
    }
    // If no empty value is found, grid is solved
    if (i==9 && j==9)
    {
        cout << "Grid solved!" << endl;
        solved = true;
        print((rows));
        return;
    }

    // Try next possible number and solve the rest recursively
    for (int a=1; a<=9; a++)
    {
        if (check(a,i,j,rows))
        {
            (*rows)[i][j] = (char)(a+48);
            solve(rows);
        }
    }
    (*rows)[i][j] = '-';

    return;
}

//Check all values on grid for consistency (ignores empty values)
bool checkall(vector< vector<char> > *rows)
{
    int i,j;
    char value;
    for (i=0; i<squaresize; i++)
    {
        for (j=0; j<squaresize; j++)
        {
            if ((*rows)[i][j] != '-')
            {
                value = (*rows)[i][j];
                if (!(check((int)value,i,j,rows)))
                {
                    return false;
                }
            }
        }
        return true;
    }
    return true;
}

sudoku.h

#include <vector>

using namespace std;
const int squaresize=9;
vector< vector<char> > load();
void print(vector< vector<char> > *);
string block(int i, int j);
bool check(int num, int i, int j, vector< vector<char> > *);
void solve(vector< vector<char> > *);
bool checkall(vector< vector<char> > *);

my problem now is: the program doesn't print the solved grid..
and i can't find why.... really sorry

thx again.. sorry for this program,, i just don't have much time now
thx for helping.. if possible, i would appreciate a fixed revised code of mine..

Why are you using a pointer, and not a reference?

You're still not initialising solved.

You're still running off the end of an array.

too late

Why are you using a pointer, and not a reference?

You're still not initialising solved.

You're still running off the end of an array.

thx salem.. really sorry
here's the current solve function..

void solve(vector< vector<char> > &rows)
{
	bool solved=false;
    int i,j;
    if (solved)
    {

        return;
    }

    // Find next empty value
    for (i=0; i<squaresize; i++)
    {
        for (j=0; j<squaresize; j++)
        {
            if (rows[i][j] == '-')
            {
                break;
            }
        }
        if (rows[i][j-1] == '-')
        {
            break;
        }
    }
    // If no empty value is found, grid is solved
    if (i==9 && j==9)
    {
        cout << "Grid solved!" << endl;
        solved = true;
        print(rows);
        return;
    }

    // Try next possible number and solve the rest recursively
    for (int a=1; a<=9; a++)
    {
        if (check(a,i,j,rows))
        {
            rows[i][j] = (char)(a+48);
            solve(rows);
        }
    }
    rows[i][j] = '-';

    return;
}

but there's still problems in memory while running the program.. is the rows still incorrect? please fix my code.... i really don't understand why there's memory problem,, and why it doesn't print the solved grid..

i think the problem is here:

in solve function:

for (int a=0; a<9; a++)
    {
		if (i==9)
		{
			if (check(a,i-1,j,rows))
			{
				rows[i-1][j] = (char)(a+48);

				solve(rows);
			}
		}
		if (check(a,i,j,rows))
			{

				rows[i][j] = (char)(a+48);

				solve(rows);
			}
    }
    rows[i][j] = '-';

    return;

in check function,,

center = block(i,j);
    x = center[0]-48;
    y = center[1]-48;
    for (int m=0; m<=2; m++)
    {
        for (int n=0; n<=2; n++)
        {
            if (rows[x+m][y+n]==value && !((x+m)==i && (y+n)==j))
            {
                return false;
            }
        }
    }
    return true;

and in block function

string block(int i, int j)
{
    char x,y;
    string result = "00";
    switch (i)
    {
		case 0:
		case 1:
		case 2:
			x='1';
			break;
		case 3:
		case 4:
		case 5:
			x='4';
			break;
		case 6:
		case 7:
		case 8:
			x='7';
			break;
    }
    switch (j)
    {
		case 0:
		case 1:
		case 2:
			y='1';
			break;
		case 3:
		case 4:
		case 5:
			y='4';
			break;
		case 6:
		case 7:
		case 8:
			y='7';
			break;
    }
    result[0] = x;
    result[1] = y;
    return result;
}

i don't know how to fix the problem in the debugger.. pls help
thx!

sorry,, now i'm triple posting... time trouble

this is my latest sudoku.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "sudoku.h"
using namespace std;

// Read grid from file sudoku.dat
vector< vector<char> > load()
{
    char line;
    ifstream data("sudoku.dat");
    cout << "Loading grid..." << endl;
    vector <char> nums;
    vector < vector<char> > rows;
    for (int i=0; i<squaresize; i++)
    {
        for (int j=0; j<squaresize; j++)
        {
            data>>line;
            nums.push_back(line);
        }
        rows.push_back(nums);
        nums.resize(0);
    }
    return rows;
}

// Print grid with nice format
void print(vector< vector<char> > &rows)
{

    for (int i=0; i<squaresize; i++)
    {
        for (int j=0; j<squaresize; j++)
        {
            cout << rows[i][j];
            if (j==2 || j==5)
            {
                cout << "  ";
            }
            else if (j==8)
            {
                cout << endl;
                if (i==2 || i==5)
                {
                    cout << endl;
                }
            }
            else
            {
                cout << " ";
            }
        }
    }
}

// Returns a string containing the center of the block
// to which position i,j belongs.
string block(int i, int j)
{
    char x,y;
    string result = "00";
    switch (i)
    {
		case 0:
		case 1:
		case 2:
			x='1';
			break;
		case 3:
		case 4:
		case 5:
			x='4';
			break;
		case 6:
		case 7:
		case 8:
			x='7';
			break;
    }
    switch (j)
    {
		case 0:
		case 1:
		case 2:
			y='1';
			break;
		case 3:
		case 4:
		case 5:
			y='4';
			break;
		case 6:
		case 7:
		case 8:
			y='7';
			break;
    }
    result[0] = x;
    result[1] = y;
    return result;
}

// Checks whether value num can be placed at position i,j.
bool check(int num, int i, int j, vector< vector<char> > &rows)
{

    char value = (char)(num+48);
    string center;
    int x,y;
    if (value == '-')
    {
        return true;
    }
    // check row
    for (int k=0; k<squaresize; k++)
    {
        if (rows[i][k]==value && k!=j)
        {
            return false;
        }
    }
    // check column
    for (int k=0; k<squaresize; k++)
    {
        if (rows[k][j]==value && k!=i)
        {
            return false;
        }
    }
    // check region
    center = block(i,j);
    x = center[0]-48;
    y = center[1]-48;
    for (int m=0; m<=2; m++)
    {
        for (int n=0; n<=2; n++)
        {
        	if(x==7 && y==7)
        	{
        		[B]for (int m=-1; m<=1; m++)
                            {
                                   for (int n=-1; n<=1; n++)
                                   {
        	                          if(x==-1 && y==-1)
        	                         {
        		                          if (rows[x+m+1][y+n+1]==value && !((x+m+1)==i && (y+n+1)==j))
				                  {
					               return false;
				                   }
        	                         }
        	                         else if(x==-1)
        	                         {
        		                          if (rows[x+m+1][y+n]==value && !((x+m+1)==i && (y+n)==j))
				                  {
					               return false;
				                  }
        	                         }
        	                         else if(y==-1)
        	                         {
        		                         if (rows[x+m][y+n+1]==value && !((x+m)==i && (y+n+1)==j))
				                  {
					             return false;
				                  }
        	                          }
                                          else if(rows[x+m][y+n]==value && !((x+m)==i && (y+n)==j))
                                         {
                                               return false;
                                          }
              }
    }[/B]
    return true;
}

// Recursive Sudoku solver
void solve(vector< vector<char> > &rows)
{
	bool solved=false;
    int i,j;
    if (solved)
    {
        return;
    }
    // Find next empty value
    for (i=0; i<squaresize; i++)
    {
        for (j=0; j<squaresize; j++)
        {
            if (rows[i][j] == '-')
            {
                break;
            }
        }
        if (rows[i][j-1] == '-')
        {
            break;
        }
    }

    // If no empty value is found, grid is solved
    if (i==9 && j==9)
    {
        cout << "Grid solved!" << endl;
        solved = true;
        print(rows);
		return;
    }
    // Try next possible number and solve the rest recursively
    for (int a=1; a<=9; a++)
    {
		if (i==9)
		{
			if (check(a,i-1,j,rows))
			{
				rows[i-1][j] = (char)(a+48);
				solve(rows);
			}
		}
		else
		{
			if (check(a,i,j,rows))
			{
				rows[i][j] = (char)(a+48);
				solve(rows);
			}
		}
    }
}

//Check all values on grid for consistency (ignores empty values)
bool checkall(vector< vector<char> > rows)
{
    int i,j;
    char value;
    for (i=0; i<squaresize; i++)
    {
        for (j=0; j<squaresize; j++)
        {
            if (rows[i][j] != '-')
            {
                value = rows[i][j];
                if (!(check((int)value,i,j,rows)))
                {
                    return false;
                }
            }
        }
        return true;
    }
    return true;
}

it's working except in printing the solved grid.. the last row is what only printed correctly... pls help me modify the bolded part.. i think it's there... thx.. really need asap!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.