### Checking whether a sudoku is valid (still unsolved round 2)!

Hello everyone, I am working on a programme that check whether the rows, columns and subsquares of the sudoku are valid, where the numbering of the subsquares is as follow:

123
456
789

I have successfully declared and run two functions to check the rows and columns, while I have no idea how to check the subsquares. My thought is to break them to 9 arrays for checking.

For reference, please see my code of checking the rows below.
 ``123456789101112131415`` `````` void row_verify( char x[9][9]) { // x is the 2D array storing the sudoku char temp; int count; for ( int i = 0 ; i < 9 ; i++) { for ( int j = 0 ; j < 9 ; j++) { count = 0; temp = x[i][j]; if ( temp != '.') { for ( int k = 0 ; k < 9 ; k++ ) { if (x[i][k] == temp) count++; } } if (count >= 2) { cout << "Row " << i << " is invalid." << endl; i++; } } } }``````

To trojansdestroy:

Thank you for your answer. However, I found wrong results (all subsquares were invalid) were given either directly copying your code or adjusting it by myself so as not to use boolean. And I don't understand why temp = x[ j + (i / 3) ] [ k + (i % 3) ];, where in my understanding, the first digit of the second box is x[0][3], but not x[0][1], as in the formula.Same case apply to if ( x[ m + i ][ n + i % 3 ] == temp) count++;

Am I correct? Thank you once again for reading and posting comments.

To trojansdestroy:

 ``12345678910111213141516`` ``````void subsq_verify( char x[9][9]) { char temp; int count; for ( int i=0; i < 9 ; i++) { for ( int j = 0; j<3 ; j++) { for ( int k = 0 ; k<3 ; k++) { temp = x[j+i][k+(i%3)*3]; count = 0; if (temp != '.') { //my test for blanks for ( int m = 0; m<3 ; m++) { for ( int n = 0; n<3; n++) { if (x[m+i][n+(i%3)*3] == temp ) count ++; } } } } if ( count >= 2) { cout << "Sub-square " << i+1 << " is invalid." << endl; //using i+1 to fit in my numbering of box break;} }}} ``````

However, wrong result was still given. Also, I noticed that, for example, in box 4 in your numbering style (0-9) ,the first digit checked should be x[3][3], however, in the code, if (x[m+i][n+(i%3)*3] == temp ), at first it is checking x[4][3], do you know how to solve this problem? Thank you very much.

Last edited on
Imagine the subsquares numbered this way:
 ```0 1 2 3 4 5 6 7 8```

This makes solving this easier for us.

Let's start small, by analyzing a single 3x3 square.
 ```Indices Row, col 0 1 2 0,0 0,1 0,2 3 4 5 1,0 1,1 1,2 6 7 8 2,0 2,1 2,2```

A given spot's row is determined by:
row = index / numberOfColumns
And column:
col = index % numberOfColumns (since `int` division rounds down)

So, if you want to find if a given 3x3 subsquare contains all numbers 1-9, just determine that subsquare's boundaries. For instance, the 0th subsquare has boundaries (all spots except the middle) at:
 ```(0,0) (0,1) (0,2) (1,0) (0,2) (2,0) (2,1) (2,2)```

That means you want to check rows 0 through 2, but only where the column is 0 through 2.
In your 9x9 array, it means this:
[ 0 : 2 ] [ 0 : 2 ]
( [ rows ] [ cols ] )

To find the same for, say, the 4th subsquare (counting from 0, the dead center of the game),
As a subsquare, it has row = 4 / 3 = 1; col = 4 % 3 = 1;
So use this to find the indices of its elements by multiplying its row and column by 3, and adding to the "base" calculation we did for subsquare 0.
In your 9x9 array, you'd want to check: [ (0 + (row * 3)) : (2 + (row * 3)) ] [ (0 + (col * 3)) : (0 + (col * 3)) ]
In real numbers, this becomes: [ 3 : 5 ] [ 3 : 5 ]

So, in code this would look like:
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748`` ``````// i - the subsquare's index // j - row inside that subsquare to use as temp // k - column inside that subsquare to use as temp // m - row inside that subsquare to compare to temp // n - column inside that subsquare to compare to temp void subsquare_verify(char x[9][9]) { char temp; int count; bool subSquareInvalid; // If ever true, no need to set "temp" to other // elements of a subsquare (it's already invalid) // Choose a subsquare for (int i = 0; i < 9; i++) { subSquareInvalid = false; // Initially assume subsquare is valid // Choose a row to use as temp for (int j = 0; j < 3; j++) { // Choose a column to use as temp for (int k = 0; k < 3; k++) { // I forgot to multiply i by 3 (which should have cancelled out the divided by three) for the row // as well as multiplying (i % 3) by 3. This shifts temp to the correct location within the subsquare. temp = x[ j + (i / 3) * 3 ] [ k + (i % 3) * 3 ]; cout << "\nTemp = x[" << j + (i / 3) * 3 << "][" << k + (i % 3) * 3 << "] with value: " << temp << endl; count = 0; // Choose a row to compare to temp for (int m = 0; m < 3; m++) { // Choose a column to compare to temp for (int n = 0; n < 3; n++) { cout << "\tComparing x[" << m + (i / 3) * 3 << "][" << n + (i % 3) * 3 << "]\n"; cout << "\t\twith value: " << x[ m + (i / 3) * 3 ][ n + (i % 3) * 3 ] << endl; // Divided by 3, times three cancels for the row in the next line if ( x[ m + (i / 3) * 3 ][ n + (i % 3) * 3 ] == temp) count++; // Notify, then move on to next subsquare, // as we already know if this one is invalid if (count > 1) { cout << "Subsquare " << i << " is invalid." << endl; subSquareInvalid = true; break; // Back to row to compare to temp } } if (subSquareInvalid) break; // Back to column of temp } if (subSquareInvalid) break; // Back to row of temp } if (subSquareInvalid) continue; // Move on to next subsquare } } }``````

It's sort of like breaking it into 9 arrays, as you suggested. It's very similar to the code you've already written to verify the rows and columns, just with different boundaries (as verifying a single subsquare is a 3x3 process, instead of 1x9 or 9x1). You still have to check 9 spots against "temp"; they're just in a different shape.

Edit: I noticed in your code that you don't break immediately upon noticing that count is greater than 1. When dealing with only 9 numbers as you are here, runtime isn't really an issue, but I put the `bool subSquareInvalid` along with `break` statements if it is greater. These are not necessary, and if you'd like, you can remove them altogether.

If you choose to do so, move the [code]if (count > 1) cout << "Subsquare " << i " << " is invalid." << endl;[code] so that it's the very last thing that executes in the outermost for loop (the one that uses "i" as an iterator). It will still notify the user if a subsquare is invalid.

Edit 2.0: Yes sherlock, you are correct. In the line determining temp's indices, I forgot to multiply (for the row) (i / 3) by 3, which results in just i. As well as (for the column) (i % 3) by 3. Sorry for the mistake! I've updated the code, and the logic should all be correct now. That's what I get for not testing.
Also, since you allow for blank spots to still be present when checking the row, column, and subsquare validity (I assume "." means a blank spot), you may want to add that check to the code I've written, because I didn't do so.

Let me know if it still doesn't work, I'm happy to do some more testing.
Last edited on
http://norvig.com/sudoku.html

I strongly recommend this article. It shows very interesting techniques to solve sudokus that can be used in many other situations. It's coded in Python, bute there are translations to many other languages, including, obviously, C++
Sherlock, you're absolutely right. See my updated post.
Sorry for repling by own topic but it is urgent. After my adjustments, my code is as follow, but still incorrect result is given.

 ``12345678910111213141516`` ``````void subsq_verify( char x[9][9]) { char temp; int count; for ( int i=0; i < 9 ; i++) { for ( int j = i/3 ; j < i/3 +2 ; j++) { for ( int k = 0 ; k<3 ; k++) { temp = x[j][k+(i%3)*3]; count = 0; if (temp != '.') { for ( int m = i/3 ; m < i/3 +2 ; m++) { for ( int n = 0; n<3; n++) { if (x[m][n+(i%3)*3] == temp ) count ++; } } } if ( count >= 2) { cout << "Sub-square " << i+1 << " is invalid." << endl; break;} }} } }``````
Perhaps the following will be of some help. It should be trivial to modify it to meet your needs.

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768`` ``````#include typedef char board_type[9][9]; bool verify_block(board_type board, unsigned blockID) { unsigned digits[9] = { 0 } ; const unsigned rowBegin = (blockID / 3) * 3 ; const unsigned colBegin = (blockID % 3) * 3 ; for ( unsigned i=0; i<3; ++i ) for ( unsigned j=0; j<3; ++j ) if ( digits[board[rowBegin+i][colBegin+j]-1]++ ) return false ; return true ; } bool subsq_verify(board_type board) { bool verified = true ; for ( unsigned i=0; i<9; ++i ) if ( !verify_block(board, i) ) { std::cout << "Sub-square " << i+1 << " is not correct.\n" ; verified = false ; } return verified ; } int main() { board_type correctBoard = { {8,3,5,4,1,6,9,2,7}, {2,9,6,8,5,7,4,3,1}, {4,1,7,2,9,3,6,5,8}, {5,6,9,1,3,4,7,8,2}, {1,2,3,6,7,8,5,4,9}, {7,4,8,5,2,9,1,6,3}, {6,5,2,7,8,1,3,9,4}, {9,8,1,3,4,5,2,7,6}, {3,7,4,9,6,2,8,1,5} } ; board_type incorrectBoard = { {8,3,5,4,1,6,9,2,7}, {2,9,6,8,5,7,4,3,1}, {4,1,7,2,9,3,6,5,8}, {5,6,9,1,3,4,7,2,2}, {1,2,3,6,7,8,5,4,9}, {7,4,8,5,2,9,1,6,3}, {6,5,2,7,8,1,3,9,4}, {9,8,1,3,4,5,2,7,6}, {3,7,4,9,6,2,8,1,5} } ; std::cout << "correctBoard:\n" ; if ( subsq_verify(correctBoard) ) std::cout << "\tverified correct.\n" ; std::cout << "incorrectBoard:\n" ; if ( subsq_verify(incorrectBoard) ) std::cout << "\tverified correct.\n" ; }``````
Found the problem with my code! Where I claimed that `(i / 3) * 3` is equal to i, I was wrong. Those spots do not cancel out, because for i=1, you ought to add (i/3)*3, which is zero, but actually adds 1! I'm sorry! Tried to condense too much.

I've tested my new code, and replaced the bad code above. It checks all spaces in order, and you can see for yourself with the couts I left.
Last edited on
Topic archived. No new replies allowed.