C++

Forum

 
Question about a class, and brute for algorithm

xxhashxx (9)
So on wikipedia, theres and example algorithm to solve a sudoku grid by brute force, written in c. I wanted to implement it in a class, it works but i have the following two problems:

code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
class sudoku

{
public:
	sudoku()
	{
	int i, j;
 
  for(i=0;i<9;i++)
    for(j=0;j<9;j++)
    {
          grid[i][j]=0;
    }
	}

	sudoku(sudoku& S)
	{
	int i, j;
 

  for(i=0;i<9;i++)
    for(j=0;j<9;j++)
    {
          grid[i][j]=S.grid[i][j];
    }
	}
	sudoku& operator = (const sudoku &S)
	{
	int i, j;
 

  for(i=0;i<9;i++)
    for(j=0;j<9;j++)
    {
          grid[i][j]= S.grid[i][j];
    }

	return *this;
	}
	
	
	
	



void input()
{

int i, j;
 
cout << "enter the grid" << endl;
  for(i=0;i<9;i++)
    for(j=0;j<9;j++)
    {
          cin >> grid[i][j];
    }
}
void output()
{
for(int i = 0; i< 9 ; i++)
{
for(int j = 0; j<9 ; j++)
{
cout << grid[i][j]<< "  " ;
}
cout << endl;
}
}

int valid(int row, int col, int val)
{
if(grid[row][col] == val)return true;
if(grid[row][col] != 0) return false;

for(int i =0; i<9;i++)
if(grid[row][i]== val)return false;
for(int j=0;j<9;j++)
if(grid[j][col] == val)return false;


int r = row/3;
int c = col/3;

  for (int i = r * 3; i < (r + 1) * 3; i++)
    for (int j = c * 3; j < (c + 1) * 3; j++)
      if (grid[i][j] == val) return false;
 
  return true;
}



void solve(int row, int col)
{
int t;
	if(row == 9){output();}
	else
		{
			for(int i = 1; i <=9; i++)
			{
				if(valid(row,col,i))
				{
					t = grid[row][col];
					grid[row][col] = i;
					if(col == 8)
					{
					solve(row+1,0);
					}
					else
					{
					solve(row,col+1);
					}
					grid[row][col]=t;
					
				}
			
			}
		
	}

}
private:
	int grid[9][9];

};



on line 97, i need to place an output statement to view the completed grid:

i.e.

1
2
3
4
5
6
7
 
int main()
{
sudoku S;
S.input();
S.solve(0,0)
S.output()
}


when the output in intmain is called it returns the unsolved grid, why does this happen? doesnt the stement in line 115 change the value of the grid, or is it because i am not passing it as a refernence but as a value, although solve() is a member function?

the second problem is, that the solver works for a lot of different type of grids, but when i place a completly blank grid into the solver it goes on solving the grid and doesnt stop at the first soln. Since a blank grid will have 6x10^21 possible soln.

As perwhat i have seen, if the output() is placed on line 97, aand a blank grid is entered the output is constantly changed and doesnt stop, but since it enters the if stement (row == 9) doesnt that make row 9 so why does it still kep on outputing the grid.

any idea?
jsmith (5804)
It sure looks to me like all solve() does is solve a single cell, not the entire grid.
Topic archived. No new replies allowed.