Sudoku Checker Algorithm

[CelestialX]

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?

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

[Chibiken]

Can you respond to the JLBorges's post? His post seems helpful.
http://www.cplusplus.com/forum/beginner/202240/#msg962973

[mbozzi]

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:

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.

[CelestialX]

Mr. Mbozzi what is "not unique WRT cells"?

[mbozzi]

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.

[CelestialX]

so this is how did it: I seem to have trouble with find_violation

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

[mbozzi]

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.