Ad:

C++ Discussion Thread
Unsolved
Views: 1618

Feb 14th, 2009

recursive sudoku solver (asap)

Expand Post »

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

(Toggle Plain Text)

#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

(Toggle Plain Text)

#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++)
    {
        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!=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;
}

#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++)
    {
        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!=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

(Toggle Plain Text)

#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!

azwraith69

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

21 posts
since Jul 2008

Permalink

Feb 14th, 2009

Re: recursive sudoku solver (asap)

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..

azwraith69

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

21 posts
since Jul 2008

Permalink

Feb 14th, 2009

Re: recursive sudoku solver (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?

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

Feb 14th, 2009

Re: recursive sudoku solver (asap)

Additionally, to the errors above: Errors on initialization.

c++ Syntax (Toggle Plain Text)
 
 bool solved;
  int i,j;
  if (solved)  // ERROR: Un-initialized variable
    {
      return;
    }
 bool solved;
  int i,j;
  if (solved)  // ERROR: Un-initialized variable
    {
      return;
    }

You have a faliure to limit range on
line

c++ Syntax (Toggle Plain Text)
 // 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;
        }
    }
 // 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.

StuXYZ

Reputation Points: 732

Solved Threads: 134

Practically a Master Poster

Offline

659 posts
since Nov 2008

Permalink

Feb 14th, 2009

Re: recursive sudoku solver (asap)

thx for the great helps...

these are the new codes

main.cpp

(Toggle Plain Text)

#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

(Toggle Plain Text)

#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;
}

#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

(Toggle Plain Text)

#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..

azwraith69

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

21 posts
since Jul 2008

Permalink

Feb 14th, 2009

Re: recursive sudoku solver (asap)

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.

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

Feb 14th, 2009

Re: recursive sudoku solver (asap)

too late

Last edited by Sky Diploma; Feb 14th, 2009 at 12:12 pm.

Sky Diploma

Reputation Points: 673

Solved Threads: 125

Practically a Posting Shark

Offline

818 posts
since Mar 2008

Permalink

Feb 14th, 2009

Re: recursive sudoku solver (asap)

Click to Expand / Collapse Quote originally posted by Salem ...

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..

(Toggle Plain Text)

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..

azwraith69

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

21 posts
since Jul 2008

Permalink

Feb 14th, 2009

Re: recursive sudoku solver (asap)

i think the problem is here:

in solve function:

(Toggle Plain Text)

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,,

(Toggle Plain Text)

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

(Toggle Plain Text)

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!

azwraith69

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

21 posts
since Jul 2008

Permalink

Feb 15th, 2009

Re: recursive sudoku solver (asap)

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

this is my latest sudoku.cpp

(Toggle Plain Text)

#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)
        	{
        		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;
                                          }
              }
    }
    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;
}

#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)
        	{
        		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;
                                          }
              }
    }
    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!

Last edited by azwraith69; Feb 15th, 2009 at 1:24 am.

azwraith69

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

21 posts
since Jul 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: C++ classes!

Next Thread in C++ Forum Timeline: ipod simulator program

DaniWeb Message

Cancel Changes

User Name
Password