Sudoku correctness checking

[ningxin]

Hi, i am currently taking a module in c++ in the university, and was given an assignment. because i have no prior background on the subject, everything is kind of new to me. i have tried for quite some time and still not able to get the solution out. so i hope you guys can help me out. of course i am not expecting a full solution, but i would greatly appreciate it if anyone can suggest to me what should i do. i am very new to this subject so please help me out as much as you can if you have the time. i have put the questions as well as my half-worked answers here. please have a look. thanks!

the assignment:

Assignment 1, Instructions

Problem: Write a C++ program that checks if a 9x9 Sudoku square is filled in correctly. The
81 numbers in the Sudoku square have to be read from a textfile which contains the numbers
row-wise, separated by spaces.

Instructions:
The Sudoku rules are explained in the attached document on the Sudoku rules. As in this
document, we call the 3x3 subsquares of a Sudoku square regions.

The square is saved in a vector<int> S with 81 entries such that the entry in row i and
column j is S[9*(i-1)+j-1].

• Compile and run Assignment1.cpp. It will read the Sudoku square from the file sud1.txt
(which you should have saved) and print a
message to the screen indicating if the input has worked.

• Crucial part: put C++ commands to check
if the Sudoku square is filled in according to the rules. Details:

• Whenever any number 1,2,...,9 appears more than once in any row, column, or region of
the square, this fact should be printed to the screen (by a cout command).

• If the square is completely correct, nothing should be printed to the screen.

• You program will be tested on further examples. Therefore, it is recommended that you
do more tests to make sure your program is correct.

• The following program contains a basic idea needed for checking if a number occurs at
least twice among several numbers. You can use this idea (but not the program itself - it
has to be adjusted to fit the purpose).
# include <cstdlib >
# include <iostream >
using namespace std;
// generate 30 random numbers in
// the range 1 ,... ,100 and check which
// numbers appears more that once
int main ()
{
bool HasOccurred [101];
// HasOccurred [i]== true will mean that
// i has occurred already
for(int i=0;i <101; i++)
HasOccurred [i]= false ;
int number ;
for(int j=0;j <30; j++)
{
number = 1+ rand ()%100;
if( HasOccurred [ number ])
cout << number << " occurred twice " << endl ;
HasOccurred [ number ]= true ;
}
system (" PAUSE ");
return EXIT_SUCCESS ;
}


my half-worked on solution:

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

char file[] = "sud1.txt";

int main(int argc, char *argv[])
{
cout << file << ":" << endl << endl;
ifstream in("C:\Documents and Settings\HP\Desktop\assignment\sud1.txt");
vector<int> S;
int buffer;
while(in>>buffer)
S.push_back(buffer);
if(S.size()==81)
cout << "input worked" << endl;
else
cout << "input error" << endl;
int counter=0;
for(int i=1;i<4;i++)&&for(int i=4;i<7;i++)&&for(int i=7;i<10;i++))
{
for(int j=1;j<4;j++)&&for(int j=4;j<7;i++)&&for(int j=7;j<10;i++))
{
bool S[9];
for (int i=1;i<10;i++)
{
for (int j=1;j<10;i++)
if(S[i])
counter++;
}
}
cout<< "A[i] has occurred "<< counter << "times" << endl;
}

for((int i=1;i<10;i++)
{
for(int j=1;j<10;j++)
{
bool S[9];
for (int i=1;i<10;i++)
{
for (int j=1;j<10;i++)
if(S[i])
counter++;
}
}
cout<< "A[i] has occurred "<< counter << "times" << endl;
}


system("PAUSE");
return EXIT_SUCCESS;
}

my answer might seem stupid to you, but this what i can come up with after many hours.

[Rajesh V]

You can directly check according to the property of a sudoku. Have an array that counts the number of occurrences of each number( 1..9 ). You traverse all the rows. All the columns. And all the 3X3 squares too. For each row, column and a 3X3 sqaure seperately, see that the count value for all the numbers is exactly 1.

I think the following logic might also work. Check whether the sum of all the elements in all rows is 45 and also the sum of all the elements in all columns is 45. Do this for 3X3 square also. I am not sure about the proof of this algorithm.

The idea is only to check whether it is a sudoku or not. The rest part is easy

[JosAH]

I think the following logic might also work. Check whether the sum of all the elements in all rows is 45 and also the sum of all the elements in all columns is 45. Do this for 3X3 square also. I am not sure about the proof of this algorithm.

That doesn't work; counter example: a row with all 5s in it.

kind regards,

Jos

ps. there's an article about Sudoku solving in the Java Howtos section; the logic
in the program also applies to this problem.

[whodgson]

You can't have a row of all 5's
Every row, every column and the 9 minor squares must contain digits 1 to 9.
Therefor every row and column must sum to 45 as must each minor 3x3 square.

[Laharl]

That assumes that the Sudoku is correctly filled. If it is not, then there are sequences of possible input, such as the row of 5s Jos mentioned, that still add up to 45 yet are not correct Sudokus.

[ningxin]

hi, thanks everyone for your help. jos, i looked at the post you made in the java section on sudoku, but i really don't understand it. so sorry. i spent another few hours re-doing up the program and i came up with the program which i posted below. i tested it and there were errors with the way i checked the rows and columns for repeat entries. as for using arrays to count, that is not in my syallabus, so i have no idea how to use it. i have wrote the program to test rows and columns, but is now stuck at how to test for each individual section of 9 squares (at the very last part of the program, i have no idea how to continue). can someone please tell me what to do and what is the problem with my program, the way i test for rows and columns? thanks again very much for your help. (the cout << "appears twice in row" <<endl;) is there because the files given for me to test only has a maximum of 2 repeat entries.

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
char file[] = "sud1.txt";
 
int main(int argc, char *argv[])
{
cout << file << ":" << endl << endl;
ifstream in("C:\\Documents and Settings\\HP\\Desktop\\sud1.txt");
vector<int> S;
int buffer;
while(in>>buffer)
S.push_back(buffer);
if(S.size()==81)
cout << "input worked" << endl;
else
cout << "input error" << endl;
 
int i;
 
for(i=0;i<8;i++)
{
if(S.at(i)==S.at(i+1))
{
cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
}
} 
 
for(i=9;i<17;i++)
{
if(S.at(i)==S.at(i+1))
{
cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
}
} 
 
for(i=18;i<26;i++)
{
if(S.at(i)==S.at(i+1))
{
cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
}
} 
 
for(i=27;i<35;i++)
{
if(S.at(i)==S.at(i+1))
{
cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
}
} 
 
for(i=36;i<44;i++)
{
if(S.at(i)==S.at(i+1))
{
cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
}
} 
 
for(i=45;i<53;i++)
{
if(S.at(i)==S.at(i+1))
{
cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
}
} 
 
for(i=54;i<62;i++)
{
if(S.at(i)==S.at(i+1))
{
cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
}
} 
 
for(i=63;i<71;i++)
{
if(S.at(i)==S.at(i+1))
{
cout<<S.at(i)<< " appears twice at row"<< (i/9)+1 <<endl;
}
} 
 
for(i=72;i<80;i++)
{
if(S.at(i)==S.at(i+1))
{
cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
}
} 
 
int j;
 
for(int j=0;j<8;j++)
{
for(int i=0;i<8;i++)
{
S.at(j)=(9*i)+1;
if(S.at(j)==S.at(j+1))
{
cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
}
}
}
 
for(int j=9;j<17;j++)
{
for(int i=9;i<17;i++)
{
S.at(j)=(9*i)+2;
if(S.at(j)==S.at(j+1))
{
cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
}
}
}
 
for(int j=18;j<26;j++)
{
for(int i=18;i<26;i++)
{
S.at(j)=(9*i)+3;
if(S.at(j)==S.at(j+1))
{
cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
}
}
}
 
for(int j=27;j<35;j++)
{
for(int i=27;i<35;i++)
{
S.at(j)=(9*i)+4;
if(S.at(j)==S.at(j+1))
{
cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
}
}
}
 
for(int j=36;j<44;j++)
{
for(int i=36;i<44;i++)
{
S.at(j)=(9*i)+1;
if(S.at(j)==S.at(j+1))
{
cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
}
}
}
 
for(int j=45;j<53;j++)
{
for(int i=45;i<53;i++)
{
S.at(j)=(9*i)+1;
if(S.at(j)==S.at(j+1))
{
cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
}
}
}
 
for(int j=54;j<62;j++)
{
for(int i=54;i<62;i++)
{
S.at(j)=(9*i)+1;
if(S.at(j)==S.at(j+1))
{
cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
}
}
}
 
for(int j=63;j<71;j++)
{
for(int i=63;i<71;i++)
{
S.at(j)=(9*i)+1;
if(S.at(j)==S.at(j+1))
{
cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
}
}
}
 
for(int j=72;j<80;j++)
{
for(int i=72;i<80;i++)
{
S.at(j)=(9*i)+1;
if(S.at(j)==S.at(j+1))
{
cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
}
}
}
 
bool A[9];
int x;
for(x=1;x<10;x++)
{
if(x=true)
 
 
 
 
 
system("PAUSE");
return EXIT_SUCCESS;
}
 

[JosAH]

Your (repetative) code only checks for two adjacent numbers to be equal. That
is not the way to go. Lets design something more flexible. A row/column/sub
square is only correct if each number from 1 to 9 occurs once and only once.

Assume we keep track of bit flags, one bit for each number 1 ... 9. All nine bits
set make up a number 0x1ff (check this). Any other value for the flags indicate
an incorrect row/column/etc. Given a point (x) in the square and a direction (dx)
and the number of cells n to check we can craft the following function:

int collect(int x, int dx, int n, int mask) {
 
   for (; n--; x+= dx)
      mask|= 1<<board[x]-1;
   return mask;
}
 

If we want to check the nine rows we have to do this:

for (int row= 0; row < 81; row+= 9)
   if (collect(row, 1, 9, 0) != 0x1ff)
      printf("row %d is incorrect\n", row);
 

I leave the column checks as an exercise; those sub squares are a bit more
complicated but can be handled with the same function described above
(hint: n == 3 here)

kind regards,

Jos

[ningxin]

i looked at it for quite some time and could get most of it. but i could not understand this statement:
mask|= 1<<board[x]-1;
sorry, but what does it do? is the |= symbol a mistake? what does this mask function do?
actually another thing i forgot to mention (sorry it was my fault) was that we are not required to use functions to complete this because we are not really taught on that yet. so i thought of another way to do it:
[HTML]for(int i=0;i<9;i++)
{
if (S.at(i)* S.at(i) != 1&&4&&9&&16&&25&&36&&49&&64&&81)
{
continue;
}
else
{
cout<< S.at(i) << " has occured twice in row " << (i/9)+1 << endl;
}
}[/HTML]
but the thing is it has the error which says that the number 1 occured twice in every row. what should i do?

[stragatto]

You should have a "control " array of 9 elements all initialized with 0.
Whenever you check any sudoku array (row, column or 3x3 square) you should first check that digit[i] is not equal (!=) to any of the elements of the control array (and the first will be for sure because they are still all zeroes), and subsequently fill the i-th element of the control array with the value of digit[i].
This way if the sudoku is valid, the control array will become a copy of the digit array, but if some i-th digit is equal to some (i-n)-th digit (as recorded in the control array) the sudoku is invalid.
In order to not repeat 9x9x9 times the same piece of code, it is highly advisable to try to code it into a function or - better - into a class !
Hope not having been too confusing ! :) - Good luck !

[ningxin]

hi everyone thanks again for your help. stragatto, i tried your method but was stuck halfway, so i read up on functions (like you suggested also that i should use functions) and tried jos method again. this is what i came up with:
[HTML]#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

char file[] = "sud1.txt";

int collect(int i, int di, int n, int mask)
{
cout << file << ":" << endl << endl;
ifstream in("C:\\Documents and Settings\\HP\\Desktop\\sud3.txt");
vector<int> S;
int buffer;
while(in>>buffer)
S.push_back(buffer);
if(S.size()==81)
cout << "input worked" << endl;
else
cout << "input error" << endl;

for(; n--;i+=di)
{
mask|=1<<S.at(i)-1;
return mask;
}
}
int main(int argc, char *argv[])
{
enum bitflag
{
bitflag1 = 0x001,
bitflag2 = 0x002,
bitflag3 = 0x004,
bitflag4 = 0x008,
bitflag5 = 0x010,
bitflag6 = 0x020,
bitflag7 = 0x040,
bitflag8 = 0x080,
bitflag9 = 0x100,
}
bitflag == 0x001||0x002||0x004||0x008||0x010||0x020||0x040||0 x080||0x100


int i;
for(int i=0;i<81;i+=9)
{
if (collect(i, 1, 9, 0) != bitflag)
cout<<i<<" appears twice in row "<<(i/9)+1<<endl;
}

int j;
for(int j=0;j<81;j+=9)
{
if (collect(j, 1, 9, 0) != bitflag)
cout<<j<<" appears twice in row "<<(j/9)+1<<endl;
}

int grid[9];
for(int grid=0;grid<9;grid++)
{
if (collect(grid, 1, 3, 0) != bitflag)
cout<<grid<<" appears twice in grid "<<(j/3)+1<<endl;
}



system("PAUSE");
return EXIT_SUCCESS;
}[/HTML]

the sudoku file text which i inputted and was supposed to test is as follows:
[HTML]
8 3 2 5 9 1 6 7 4
4 9 6 3 8 7 2 5 1
5 7 1 2 6 4 9 8 3
1 8 5 7 4 6 3 9 2
2 6 7 9 5 3 4 1 8
9 4 3 8 1 2 7 6 5
7 1 4 6 3 8 5 2 9
3 2 9 1 7 5 8 4 6
6 5 8 4 2 9 1 3 7

[/HTML]
everything is supposed to be a string of numbers, where the 10th value of i(row) is the 2nd value of j(column).

but there are some errors. they are supposedly basic errors in the program, but i could not figure out what was wrong, and had no way to compile and further test the program as the compiler does not let me run it. the errors are as follows:

line 40:expected init-declarator before '==' token;
line 40:expected ',' or ';' token before '==' token;
line 46,53,60:expected primary expression before ')' token;

sorry for asking so many questions...

[newb16]

||0 x080||0x100

mind the space and semicolon after expression, and semicolon after } in enum declaration. Also you can't assign anything to bitflag or compare it with something - it is enum type, not variable.

[Rajesh V]

That doesn't work; counter example: a row with all 5s in it.

kind regards,

Jos

ps. there's an article about Sudoku solving in the Java Howtos section; the logic
in the program also applies to this problem.

Thank you for the counter example. But I think except the input with all the numbers 5, the sum checking should work. The sum checking should be done for all rows, columns, and 3x3 squares.

Thanks again,
Rajesh V

[JosAH]

Thank you for the counter example. But I think except the input with all the numbers 5, the sum checking should work. The sum checking should be done for all rows, columns, and 3x3 squares.

Thanks again,
Rajesh V

Here's another counter example:

5 6 4 5 6 4 5 6 4
4 5 6 4 5 6 4 5 6
6 4 5 6 4 5 6 4 5
5 6 4 5 6 4 5 6 4
4 5 6 4 5 6 4 5 6
6 4 5 6 4 5 6 4 5
5 6 4 5 6 4 5 6 4
4 5 6 4 5 6 4 5 6
6 4 5 6 4 5 6 4 5
 

kind regards,

Jos

[JosAH]

ps. I renamed this thread to something more meaningful.

kind regards,

Jos

[Jondlar]

1. check each row for repeatition of digits 1 to 9
2. check each col for same
3. check each 3x3 block for same

This would require nested loops. Also how you find which element belongs to which 3x3 block is very important.

[Jondlar]

Thank you for the counter example. But I think except the input with all the numbers 5, the sum checking should work. The sum checking should be done for all rows, columns, and 3x3 squares.

Thanks again,
Rajesh V

Imagine a row 1 2 3 4 5 6 6 9 9

All you have to do is increase one number from a row, and decrease another from same row and bingo you have sum 45.

[ningxin]

||0x080||0x100

mind the space and semicolon after expression, and semicolon after } in enum declaration. Also you can't assign anything to bitflag or compare it with something - it is enum type, not variable.

i have edited the mistakes but it seemed the program still contains errors. according to jos, i should use flags to check for errors. so what should be done so that the code can work? from what i checked on the internet, people assign characters (ie apple) to flag instead of integers. how do i go about giving a flag an integer value? for the last flag, is 0x100 actually a correct flag?

in the meantime i have been asking around quite a few people too and there were many suggestions on what i should do. i tried them all out too, together with the ideas all of you kindly suggested to me (thanks very much). below is part of another code to test a particular row, which is to find duplicating numbers. but when i run it, it kept on giving me the same error no matter which input file i put it in. does anyone have any idea?

[HTML] std::map<int, int> freq;

for ( int i = 0; i < 9; i++ )
++freq[std::rand() % 9];

std::cout<<"Duplicates:\n";
std::map<int, int>::iterator it = freq.begin();

while ( it != freq.end() ) {
if ( it->second > 1 )
std::cout<< it->first <<" appears "<< it->second <<" times in row 1\n ";
++it;
}[/HTML]

thanks again for all of your help. i really appreciate it, because my assignment is really going to be due saturday night, and my program is not really going anywhere after trying for 5 days.

[stragatto]

The idea of checksum=45 is ok, but you should check that there is no row (or column, or square) filled with all "5". This could be done by converting the array (if the checksum is 45) into a string and checking that the string does not contain the substring "55".
(if I remember well, the library function for substring matching should be strstr() )
Sorry for being so short, but I must go to our monthly LUG meeting and it's late :)

[Jondlar]

The idea of checksum=45 is ok, but you should check that there is no row (or column, or square) filled with all "5". This could be done by converting the array (if the checksum is 45) into a string and checking that the string does not contain the substring "55".
(if I remember well, the library function for substring matching should be strstr() )
Sorry for being so short, but I must go to our monthly LUG meeting and it's late :)

This is a row with no "55"
1 3 3 4 5 6 7 7 9

The sum = 45

Its not about repeated 5's. If you have any repeated number then the sudoku is incorrect. So you might want to check for all repeated numbers not just "55".

[stragatto]

This is a row with no "55"
1 3 3 4 5 6 7 7 9

The sum = 45

Its not about repeated 5's. If you have any repeated number then the sudoku is incorrect. So you might want to check for all repeated numbers not just "55".

Ah, right! I was in a hurry and I didn't take enough time to think :)
Another algorythm could be as follows:
1) Sort the items of the array
(The result for a sudoku valid array should be ; 1 2 3 4 5 6 7 8 9)
2) check that in the sorted array item[4]=5
3) check that in the sorted array item[0]+item[8]=10
4) check that in the sorted array item[1]+item[7]=10
5) check that in the sorted array item[2]+item[6]=10
6) check that in the sorted array item[3]+item[5]=10
Finally, check that in the sorted array no item[j]=item[j+1]
(this last, to check that there are not repeated couples whose sum is 10)
Of course, the order of the checks should be optimized for efficiency: maybe the check I have put as last one should be done as first or second !
Or maybe the checks could be done while sorting, with some addition to the bubblesort or quicksort algorythm !

[JosAH]

Or maybe the checks could be done while sorting, with some addition to the bubblesort or quicksort algorythm !

There is no need to sort anything; just check if all the nine numbers are present
in that sequence of nine numbers; also see my reply #7.

kind regards,

Jos

[stragatto]

There is no need to sort anything; just check if all the nine numbers are present
in that sequence of nine numbers; also see my reply #7.

kind regards,

Jos

Yes, at the end, when going to real coding, I realized that the simplest way is to do two nested loops with a flag, and to check on the flag.
Since I am lazy, I did it in perl, but I hope that the comments could ease an eventual translation into other languages.

### sudotest.pl ###
 
#reading the lines in the file#
open(SUDOKU,"sudoku.txt") or die "No such file !";
for($i=0;$i<9;$i++){
$myline[$i]=<SUDOKU>;
chomp $myline[$i]; #this cuts away the newline char
}
close(SUDOKU);
 
# print $myline[0]; #this was for debugging
 
# and now let's check a line
check($myline[3]);
 
sub check {
    $line=$_[0]; 
    # this is cryptic for non-perl-users:
    # perl passes the parameters to the functions
    # as an array called @_; $_[0] is the first
    # and in this case the one and only item of @_
 
 
    #let us split the line into the array @digit 
    @digit = split(//,$line); 
 
    #and now start with digit-by-digit check
    foreach $digit(@digit){
        $flag=0;
        foreach $item(@digit){
        if($digit==$item){$flag++;}
        #print $flag; #this for debugging only
        if($flag>1){die "Invalid Sudoku!"};
        }
 
    }
}

Thanks.