c++ program that checks if sudoku is valid

[user42]

I am writing a program that check the validity of a Sudoku entered. I got stuck on the two function row_ok and col_ok. they return false when they are supposed to return true. the two functions are supposed to get a row or col along with the matrix and check that all the values within it are not equal to each other. The value zero is allowed to be there twice.
as of now this is what i wrote i believe there is a problem with my square_ok function.i realized that once when i want to check a sub square i am checking a square that is 3*3 but the problem that the row_ok and col_ok functions check 9*9 how do i work around this problem i would appreciate some feedback.

//---------------------------------include's---------------------------------//

#include <iostream>
#include <cstdlib>

//-----------------------------------using's---------------------------------//

using std::cin;
using std::cout;
using std::endl;

//------------------------------------const----------------------------------//

const int N = 3;

//----------------------------------prototype--------------------------------//

void get_matrix(int matrix[][N*N]); //function which receives values of ->
                                    //matrix along with conditions

bool row_ok(int matrix[][N*N],int row); //to check if a single row is valid
bool col_ok(int matrix[][N*N],int col); //to check if a single col is valid
bool square_ok(int matrix[][N*N], int box_row,int box_col);
//-----------------------------------main------------------------------------//

int main()
{
	int matrix[N*N][N*N],count=0;
	bool check_col=true,check_row=true,check2=true,check4=true,check_sub_square=true;
	get_matrix(matrix);



	check2=square_ok(matrix,7,4);
	if (check2)

		cout<<"true\n";
	else
		cout<<"false\n";




	for (int i=0;i<N*N && check_row;i++)
    {
        check_row = row_ok(matrix,i);
    }

    for (int j=0;j<N*N && check_col && check_row ;j++)
    {
        check_col = col_ok(matrix,j);
    }



	for (int i = 0 ;i<N+N && check4;i+=N)

	{
		for(int j=0;j<N+N && check4;j+=N)
		{
			check4 = square_ok(matrix,i,j);

			if (check4)
			{
				count++;
			}
			else
			{
				check4=false;
				break;
			}

		}
	}

	if (count == N*N)
	{
		check_sub_square = true;
	}
	else
	{
		check_sub_square=false;
	}

	 if (!check_row || !check_col ||!check_sub_square)
        cout<<"0\n";
     else
        cout<<"1\n";


}


//------------------------------------functions------------------------------//

void get_matrix(int matrix[N*N][N*N])  //initializing the function
{
	int i,j,temp=0;   //initialing assistance variables

	for (i=0;i<N*N;i++)  //running through rows
	{

		for (j=0;j<N*N ;j++)  //running through columns
		{
			cin >> temp;   //receiving value into variable temp
			if(temp>=0 && temp<=N*N)   //checking if temp is between 0 and 9
			{
				matrix[i][j]=temp;   //if it is then the cell gets value of temp
			}
			else       //if not ->.....
				j--;   //then we go one backwards to receive the value once more
		}
	}
}   //end of function.......



bool row_ok(int matrix[][N*N],int row)  //initializing row_ok func
{
	for(int i=0;i<N*N;i++)   //running through rows
	{
		for(int j=(N*N)-1;j>0;j--)  //running through columns starting with last

		{
			if (matrix[i][row]!=0) //if the cell isnt equal to zero
			{
				if (matrix[i][row] == matrix[j][row] && i != j)  //checking if->
				{                   //the values of cells are equal its not the same cell
					return false;   //if the conditions are met the functions returns false
				}
			}
		}
	}
	return true;  //else the function returns true
}
  //the following function does the same as row_of but with columns
bool col_ok(int matrix[][N*N],int col)
{
	for(int i=0; i < N*N;i++)
	{
		for(int j=(N*N)-1; j > 0; j--)
		{
			if (matrix[col][i]!=0)
			{
				if (matrix[col][i] == matrix[col][j]  && i != j )
				{
					return false;
				}
			}
		}
	}
	return true;
}

//the function which splits the matrix into N*N sub-matrices
bool square_ok(int matrix[][N*N],int box_row,int box_col) //initializing

{
	int remainder1,remainder2,corner_row,corner_col;  //initializing variables




	remainder1 = box_row %N;  //getting remainder
	remainder2 = box_col %N;  //getting remainder
	int corner_row_holder=box_row - remainder1  //setting to the edge
			,corner_col_holder =box_col - remainder2 ;  //setting to the edge


	for(corner_row=box_row - remainder1;corner_row<corner_row_holder+N;corner_row++)
    {
		for(corner_col=box_col - remainder2;corner_col<corner_col_holder+N;corner_col++)
		{

			for (int i=corner_row_holder+N-1;i>=corner_row_holder;i--)
			{
				for (int j=corner_col_holder+N-1;j>=corner_col_holder;j--)
				{
					if (matrix[i][j]!=0 && i!=j!=corner_col!=corner_row)
					{
						if (matrix[i][j] == matrix[corner_row][corner_col])
						{
							return false;

						}
					}

				}
			}
		}
	}
	return true;

}
/*input for example
9 8 5 2 4 3 1 6 7
3 2 8 7 8 1 9 5 4
7 4 1 9 1 5 3 8 2
4 5 2 8 7 9 6 3 1
1 9 3 6 5 4 1 7 8
6 7 8 1 3 2 5 4 9
5 3 9 4 1 7 8 2 6
8 1 7 5 2 6 4 5 3
2 6 4 3 9 8 7 1 5
*/

[dhayden]

I think you need to throw away row_ok() and col_ok() and rewrite them from scratch. It looks to me like you got confused between checking a single row and checking a sub-square.

Looking at row_ok():
line 110: why do you have to pass corner_row and corner_row_holder? If you're checking a row, then shouldn't you just have to pass the row number?

Line 114; This will check two columns: corner_row_holder+2 and corner_row_holder+1. Why would you check 2 rows to see if one row is okay??

Line 118. This always compares the same square (matrix[corner_col][corner_col_holder]) to some other square. How can that help determine if a row is valid?

You can tell if a row or column is valid in one pass with the help of a bitset<10>. The idea is to record the numbers that you've seen so far. If you run across a number that you've already seen then the row isn't valid. In pseudocode:

bitset<10> numbersSeen;
for each square in the row {
   if square's value != 0 {
        if (numbersSeen.test(square's value)) {
             row is invalid;
        else {
             numbersSeen.set(square's value);
         }
    }
}
row is valid; 

[user42]

some of the things you are using in youre example i still havet learned. i edited the code. please have a look.
what i am trying to do is write a program that has three functions.
one that checks that all rows are valid.
another that check that all columns are valid .
and a third to check if each subsquare is valid.
if something is not clear and you did not understand what i did please tell me and i will try and explain. thanx for your'e help.
p.s i am still a beginner have only been coding for about three weeks, sorry if there is a mess in the code.

[TheIdeasMan]

i edited the code. please have a look.

Please don't do that, it makes it hard to follow.

if something is not clear and you did not understand what i did please tell me and i will try and explain. thanx for your'e help.

dhayden has decades of professional experience - I am sure he and many others understand what you are trying to do. Look at his reply carefully - what he is proposing is quite simple.

It might help to name things clearly. I would call an individual number a cell, while the 9 3 by 3 cells, I would call squares.

I think you are over thinking the problem.

Try to write psuedo code before writing any actual code - it helps one organise one's thoughts, and sort out what code should be in a function or a loop. Start out very general then go back and put in more detail until happy to convert to actual code:

// Check rows
// Check columns
// Check 9 Squares 

With the first 2 follow dhaydens psuedo-code.

With the last one, make a function that takes row, column parameters which represent the start of the square.

Some other hints:

Wait until you have a valid value, then declare and initialise the variable one variable per line. This is not initialisation:

int i,j,temp=0; //initialing assistance variables

This is, we have provided a value for each variable:

//initialising assistance variables
int i = 0;
int j = 0;
int  temp = 0;   

But one can do this instead, the scope of row and col extend to the closing brace of the for loop. Also, I don't like having i and j for variable names - they look too similar, which can cause problems. Name the variables after what they actually are:

// use const wherever possible
// use unsigned because the numbers are never negative
const unsigned int MAX = 9; // this variable saves the compiler calculating N*N all the time
       
unsigned int CellInput = 0; // better name than temp, initialised to an invalid value - which is better than a garbage value

for (unsigned int row = 0; row < MAX; row++) { // always use braces - even for 1 statement
     for (unsigned int col = 0;col < MAX; col++) {
           // get Cell Input
     }
}

Good variable and function names aid understanding and make the code self documenting - less need for useless comments. Comments should say why the code is doing something - if it isn't obvious.

Here is a comical example of good naming:
http://www.cplusplus.com/forum/lounge/176684/#msg872881

For testing purposes, one can hard code the value of the input. That way you can test if the algorithm works with out having to repeatedly and tiresomely entering in all those numbers 1 at a time. Then change it to accept input.

This is called function implementation:

bool square_ok(int matrix[][N*N],int box_row,int box_col) // initializing function implementation

{

Good Luck !!

[user42]

understood thanx!
i still have a problem with my program and i cant seem to find it.i believe the problem mght be with the square_ok function or possibley in the main.
would really appreciate if you could look over it.

p.s when i change my code you said i should not edit my question it as to not confuse should i instead add another comment with the new code?

[TheIdeasMan]

i still have a problem with my program and i cant seem to find it.i believe the problem mght be with the square_ok function or possibley in the main.
would really appreciate if you could look over it.

I would rather you rewrite the function entirely, and possibly most of the program as per advice so far.

p.s when i change my code you said i should not edit my question it as to not confuse should i instead add another comment with the new code?

Post the pieces of code you changed with code tags and line numbers, or if you make major changes post all of it again.

Read this to see how to put line numbers on code fragments - like I did with lines 157 -159
http://www.cplusplus.com/articles/z13hAqkS/

[dhayden]

I think the code at line 180 should be

// Don't check it if it's zero. Don't compare a square to itself
if (matrix[i][j]!=0 && !(i==corner_col && j==corner_row))

[dhayden]

i still have a problem with my program and i cant seem to find it.

That's too vague for us to help. If possible, post your current code, the input you're using (or say that it's the same as what you've already given), the output you're expecting and the output that you're actually receiving. You goal is to make it as easy as possible for us to reproduce the problem. The easier it is for someone to reproduce it, the more likely they are to help.

[user42]

i changed the line that you stated above

//---------------------------------include's---------------------------------//

#include <iostream>
#include <cstdlib>

//-----------------------------------using's---------------------------------//

using std::cin;
using std::cout;
using std::endl;

//------------------------------------const----------------------------------//

const int N = 3;

//----------------------------------prototype--------------------------------//

void get_matrix(int matrix[][N*N]);


bool row_ok(int matrix[][N*N],int row); //to check if a single row is valid
bool col_ok(int matrix[][N*N],int col); //to check if a single col is valid
bool square_ok(int matrix[][N*N], int box_row,int box_col);
//-----------------------------------main------------------------------------//

int main()
{
	int matrix[N*N][N*N],count=0;
	bool check2=true,check4=true;
	get_matrix(matrix);



	check2=square_ok(matrix,1,2);
	if (check2)

		cout<<"true\n";
	else
		cout<<"false\n";

	for (int i = 0 ;i<N+N && check4;i+=N)

	{
		for(int j=0;j<N+N && check4;j+=N)
		{
			check4 = square_ok(matrix,i,j);

			if (check4)
			{
				count++;
			}
			else
			{
				check4=false;
				break;
			}

		}
	}

	if (count == N*N)
	{
		cout<<"1\n"<<endl;
	}
	else
	{
		cout <<"0\n"<<endl;
	}

}


//------------------------------------functions------------------------------//

void get_matrix(int matrix[N*N][N*N])
{
	int i,j,temp=0;

	for (i=0;i<N*N;i++)
	{

		for (j=0;j<N*N ;j++)
		{
			cin >> temp;
			if(temp>=0 && temp<=N*N)
			{
				matrix[i][j]=temp;
			}
			else
				j--;
		}
	}
}



bool row_ok(int matrix[][N*N],int row)
{
	for(int i=0;i<N*N;i++)
	{
		for(int j=(N*N)-1;j>0;j--)

		{
			if (matrix[i][row]!=0)
			{
				if (matrix[i][row] == matrix[j][row] && i != j)
				{
					return false;
				}
			}
		}
	}
	return true;
}

bool col_ok(int matrix[][N*N],int col)
{
	for(int i=0; i < N*N;i++)
	{
		for(int j=(N*N)-1; j > 0; j--)
		{
			if (matrix[col][i]!=0)
			{
				if (matrix[col][i] == matrix[col][j]  && i != j )
				{
					return false;
				}
			}
		}
	}
	return true;
}


bool square_ok(int matrix[][N*N],int box_row,int box_col)

{
	int remainder1,remainder2,corner_row,corner_col;




	remainder1 = box_row %N;
	remainder2 = box_col %N;
	int corner_row_holder=box_row - remainder1
			,corner_col_holder =box_col - remainder2 ;


	for(corner_row=box_row - remainder1;corner_row<corner_row+N;corner_row++)
	{
		for(corner_col=box_col - remainder2;corner_col<corner_col+N;corner_col++)
		{

			for (int i=corner_row_holder+N-1;i>=corner_row_holder;i--)
			{
				for (int j=corner_col_holder+N-1;j>=corner_col_holder;j--)
				{
					if (matrix[i][j]!=0 && !(i==corner_col && j==corner_row))
					{
						if (matrix[i][j] == matrix[corner_row][corner_col])
						{
							return false;

						}
					}

				}
			}
		}
	}
	return true;

}

but i am still getting zero when i am supposed to get 1




input: 6 9 2 3 7 4 5 1 8
5 3 1 8 2 6 9 4 7
4 7 8 1 9 5 3 6 2
2 5 6 4 8 7 1 9 3
9 1 7 5 3 2 4 8 6
3 8 4 9 6 1 7 2 5


output: 0


expected output: 1

[dhayden]

My mistake. In your new code, line 160 should be
if (matrix[i][j]!=0 && !(i==corner_row && j==corner_col))

The input you posted is only 6 lines long. Is there more?

Regardless, I suggest you add some temporary debugging code to square_ok() to see what's going on:

bool
square_ok(int matrix[][N * N], int box_row, int box_col)
{
    int remainder1, remainder2, corner_row, corner_col;

    cout << "square_ok(" << box_row << ',' << box_col << ") ";
    remainder1 = box_row % N;
    remainder2 = box_col % N;
    int corner_row_holder = box_row - remainder1, corner_col_holder =
        box_col - remainder2;

    for (corner_row = box_row - remainder1; corner_row < corner_row + N; corner_row++) {
        for (corner_col = box_col - remainder2; corner_col < corner_col + N; corner_col++) {
            for (int i = corner_row_holder + N - 1; i >= corner_row_holder; i--) {
                for (int j = corner_col_holder + N - 1; j >= corner_col_holder; j--) {
                    if (matrix[i][j] != 0 && !(i == corner_row && j == corner_col)) {
                        if (matrix[i][j] == matrix[corner_row][corner_col]) {
                            cout << "false: m[" << i << ',' << j
                                 << "] = m[" << corner_row << ','
                                 << corner_col << "]\n";
                            return false;

                        }
                    }

                }
            }
        }
    }
    cout << "true\n";
    return true;
}

[48T7M4Gy]

Still room for me to simplify with the digit array function, but I found all the bools were cumbersome so I tried a slight modification.

#include <iostream>

const int N = 3;
const int SIDE = N * N;

void get_matrix(int matrix[][SIDE] );

bool row_ok(int matrix[][SIDE], int);
bool col_ok(int matrix[][SIDE], int);
bool sub_matrix_ok( int aMatrix[][SIDE], int, int);

int main()
{
    //HARD CODE FOR TESTING
    int matrix[][SIDE] =
    {
        {9,8,5,2,4,3,1,6,7},
        {3,2,8,7,8,1,9,5,4},
        {7,4,1,9,1,5,3,8,2},
        {4,5,2,8,7,9,6,3,1},
        {1,9,3,6,5,4,1,7,8},
        {6,7,8,1,3,2,5,4,9},
        {5,3,9,4,1,7,8,2,6},
        {8,1,7,5,2,6,4,5,3},
        {2,6,4,3,9,8,7,1,5}
    };
    
    //CHECK EACH ROW
    std::cout << "CHECK ROWS:\n";
    for (int row = 0; row < SIDE; row++)
        std::cout << "Row " << row << ": " << row_ok(matrix, row ) << '\n';
    
    //CHECK EACH COLUMN
    std::cout << "CHECK COLUMNS:\n";
    for (int col = 0; col < SIDE; col++)
        std::cout << "Col " << col << ": " << col_ok(matrix, col ) << '\n';
    
    // CHECK EACH SUB-MATRIX
    std::cout << "CHECK SUB-MATRICES:\n";
    for (int R = 0 ; R < N; R++)
    {
        for(int C = 0; C < N; C++)
            std::cout << "Sub-matrix [" << R << "][" << C << "]: " << sub_matrix_ok( matrix, R, C) << '\n';
    }
    return 0;
}

// CHECK A SUB_MATRIX
bool sub_matrix_ok( int aMatrix[][SIDE], int R, int C)
{
    int digit[9] = {0};
    
    for(int row = N * R; row < N * (R + 1); row++)
    {
        for(int col = N * C; col < N * (C + 1); col++)
            digit[ aMatrix[row][col] - 1 ] = 1;
    }
    
    for (int i = 0; i < 9; i++)
    {
        if(digit[i] == 0)
            return false;
    }
    return true;
}

// GET MATRIX VALUES - STILL NEEDS TO BE FULLY TESTED
void get_matrix(int matrix[SIDE][SIDE])
{
    int temp = 0;
    for (int i = 0; i < SIDE; i++)
    {
        for (int j = 0; j < SIDE; j++ )
        {
            while ( std::cout << "Please enter a value: " and std::cin >> temp and temp > 0 and temp <= SIDE)
            {
                matrix[i][j] = temp;
                std::cout << "matrix[" << i << "[[" <<  j << "] = " << temp << '\n';
            }
        }
    }
}

// EACH ROW MEMBER MUST BE DIFFERENT (ALREADY BETWEEN 1 & 9)
bool row_ok(int matrix[][SIDE], int row)
{
    int digit[9] = {0};
    
    for(int col = 0; col < SIDE; col++)
        digit[ matrix[row][col] - 1 ] = 1;
    
    for (int i = 0; i < 9; i++)
    {
        if(digit[i] == 0)
            return false;
    }
    
    return true;
}

// EACH COL MEMBER MUST BE DIFFERENT (ALREADY BETWEEN 1 & 9)
bool col_ok(int matrix[][SIDE], int col)
{
    int digit[9] = {0};
    
    for(int row = 0; row < SIDE; row++)
        digit[ matrix[row][col] - 1 ] = 1;
    
    for (int i = 0; i < 9; i++)
    {
        if(digit[i] == 0)
            return false;
    }
    
    return true;
}

CHECK ROWS:
Row 0: 1
Row 1: 0
Row 2: 0
Row 3: 1
Row 4: 0
Row 5: 1
Row 6: 1
Row 7: 0
Row 8: 1
CHECK COLUMNS:
Col 0: 1
Col 1: 1
Col 2: 0
Col 3: 1
Col 4: 0
Col 5: 1
Col 6: 0
Col 7: 0
Col 8: 1
CHECK SUB-MATRICES:
Sub-matrix [0][0]: 0
Sub-matrix [0][1]: 0
Sub-matrix [0][2]: 1
Sub-matrix [1][0]: 1
Sub-matrix [1][1]: 1
Sub-matrix [1][2]: 0
Sub-matrix [2][0]: 1
Sub-matrix [2][1]: 1
Sub-matrix [2][2]: 0
Program ended with exit code: 0

[dhayden]

There you go!

Your solution is now similar to the one I proposed in my first post. I was using a bitvec<> instead of simply a vector of int.

[48T7M4Gy]

great minds think alike. I haven't read it.

The next big challenge is to rationalise the digit functionality. throw 9 numbers at the function and spit back true or false. That should trim down a few lines.

Yeah I've read it now. pity it wasn't developed. OP was not familiar with bitset so can only hope with self-documenting success of digit[]..

[user42]

thank you all for youre help.i will go over your'e tips andtry and understand them