Sudoku Checker Algorithm

I have created a Sudoku Checker Algorithm based on a vector<vector<cell> > of type cell. This specific code is supposed to go through all 9 sub-squares of 3 by 3 and output the boxes with discrepancies. How can I fix the code so that it can do exactly this?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
			for(int n = 1; n <= 3; n++){
				int s = 0; int t = 0;
				for (int row = s*n; row < 3*n; row++, s++){
					for (int col = t*n; col < 3*n; col++, t++){
						compareNUM = m_map[row][col].getNum();
						if (compareNUM == m_map[row][col].getNum()){
							count++;
							if (count <= 2)
							cout << "Found Inconsistency in Component Starting at Row " << char('P' + t*n)
							<<" Column" << char('A' + t*n) << endl; break; continue;
							}
						else if (m_map[row][col].getNum() == 0){
						cout << "Found Inconsistency in Row " << char('P' + row)
						<< "Column" << char('A' + col) << endl;
						cout << "Found Inconsistency in Component Starting at Row " << char('P' + s*n)
						<<" Column" << char('A' + t*n) << endl; break; continue;}
							}
						}
			}
Last edited on
Can you respond to the JLBorges's post? His post seems helpful.
http://www.cplusplus.com/forum/beginner/202240/#msg962973
My suggestion is to write a function (like the one I suggested to you in your first related thread) that accepts a collection of elements to check, and returns the indices of any invalid elements.

For instance, define a function named find_violations() which accepts a vector of possibly-invalid values and returns a vector of indices pointing to violations of the constraints.

Here's psuedocode:
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
vector<int> find_violations(vector<cell> cells) { 
  vector <int> result
  for each i in cells:  
    if cells[i] is not marked OR cells[i] is not unique WRT cells
      add i to result;
  return result;
}

procedure verify_whole_board() {
  // sub-procedure check-rows
  for each row r in board 
    build a collection elems containing all the elements in r
    for each c in find_violations (elems):
      print "violation at r, c"

  // sub-procedure check-columns
  for each column c in board
    build a collection elems containing all the elements in c
    for each r in find_violations (elems):
      print "violation at r, c"

  // Now for each 3x3 block -- same idea as the above for rows and columns:
  // This is the tricky part -- do something like this:
  int voffset, hoffset; 
  vector <cell> block;
  for (voffset = 0; voffset <= 6; voffset += 3) {
    for (hoffset = 0; hoffset <= 6; voffset += 3) { 
      block = getblock(voffset, hoffset)
      for each index in find_violations(block);
      // convert index back to a literal row, column.  I think this is correct. 
      print "violation at (voffset + (index / 3), hoffset + (index % 3))"
    }
  }
}

vector <cell> getblock(int voffset, int hoffset) {
  vector <cell> result;
  for (int i = voffset; i < voffset + 3; i ++) 
    for (int j = hoffset; j < hoffset + 3; j ++) 
      add board[voffset][hoffset] to result;
  return result;   
}


For such a long procedure, functional decomposition is your friend. Break things down. Probably even more so then my psuedocode does.
Last edited on
Mr. Mbozzi what is "not unique WRT cells"?
WRT stands for "with respect to". In other words, if the currently-considered element is a duplicate of another in cells, then you should add it to the list of violations. Same thing if it's un-marked.
Last edited on
so this is how did it: I seem to have trouble with find_violation

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
void verify_whole_board() {
	  // sub-procedure check-rows
	  for (int r = 0; r < 9; r++){
	    for(int c = 0; c < 9; c++)
	    if (find_violations (r) != 0)
	        cout << "Found Inconsistency at Row " << char('P' + r) << "and" << "Column" << char('A' + c) << endl;
	  }

	  // sub-procedure check-columns
	  	  for (int c = 0; c < 9; c++){
	  	    for(int r = 0; r < 9; r++)
	  	    if (find_violations (c) != 0)
	  	        cout << "Found Inconsistency at Row " << char('P' + r) << "and" << "Column" << char('A' + c) << endl;
	  	  }

	  // Now for each 3x3 block -- same idea as the above for rows and columns:
	  // This is the tricky part -- do something like this:
	  int result = 0;
	  int voffset = 0, hoffset = 0;
	  vector <cell> block;
	  for (voffset = 0; voffset <= 6; voffset += 3) {
	    for (hoffset = 0; hoffset <= 6; voffset += 3) {
	      result = getblock(voffset, hoffset);
	      for (int i = 0; i < 9; i++){ find_violations(result);
	      // convert index back to a literal row, column.  I think this is correct.
	      cout << "Found inconsistency at" << char('P' + (voffset + (i / 3)) << "and" << char('A' + hoffset + (i % 3)));
	    }
	    }
	  }
	}

	vector <cell> getblock(int voffset, int hoffset) {
	  vector <cell> result;
	  for (int i = voffset; i < voffset + 3; i ++)
	    for (int j = hoffset; j < hoffset + 3; j ++)
	      result += board[voffset][hoffset];
	  return result;
	}
I think you're misunderstanding what find_violations() is intended to do. As I wrote it, it's supposed to take in a bunch of cells, and tell you which of them are duplicates or unset -- which ones violate the alldifferent constraint (duplicate cells) or the node-consistency constraint (unset cells).

You can take the output of that function and convert each location it returned back into a row and column number.

I guess I should point out that violations = find_violations(elems), each time it appears...
I've edited my psuedocode slightly to fix some typos, and to make that clearer.
Last edited on
Topic archived. No new replies allowed.