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

[sherlock111]

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.

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

Thank you for your help.

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:

Thank you very much for your kind help again. Below please find my code adjusted with your code.

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.

[DEUX92yv]

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:

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

[Marcos Modenesi]

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

[DEUX92yv]

Sherlock, you're absolutely right. See my updated post.

[sherlock111]

Sorry for repling by own topic but it is urgent. After my adjustments, my code is as follow, but still incorrect result is given.

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

[cire]

Perhaps the following will be of some help. It should be trivial to modify it to meet your needs.

#include <iostream>

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

[DEUX92yv]

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.