473,585 Members | 2,720 Online

# Sudoku correctness checking

5 New Member
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:\Document s and Settings\HP\Des ktop\assignment \sud1.txt");
vector<int> S;
int buffer;
while(in>>buffe r)
S.push_back(buf fer);
if(S.size()==81 )
cout << "input worked" << endl;
else
cout << "input error" << endl;
int counter=0;
for(int i=1;i<4;i++)&&f or(int i=4;i<7;i++)&&f or(int i=7;i<10;i++))
{
for(int j=1;j<4;j++)&&f or(int j=4;j<7;i++)&&f or(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.
Sep 23 '08 #1
21 11356
Rajesh V
15 New Member
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
Sep 23 '08 #2
JosAH
11,448 Recognized Expert MVP
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.
Sep 23 '08 #3
whodgson
542 Contributor
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.
Sep 24 '08 #4
Laharl
849 Recognized Expert Contributor
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.
Sep 24 '08 #5
ningxin
5 New Member
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.

Expand|Select|Wrap|Line Numbers
1. #include <cstdlib>
2. #include <iostream>
3. #include <fstream>
4. #include <vector>
5.
6. using namespace std;
7.
8. char file[] = "sud1.txt";
9.
10. int main(int argc, char *argv[])
11. {
12. cout << file << ":" << endl << endl;
13. ifstream in("C:\\Documents and Settings\\HP\\Desktop\\sud1.txt");
14. vector<int> S;
15. int buffer;
16. while(in>>buffer)
17. S.push_back(buffer);
18. if(S.size()==81)
19. cout << "input worked" << endl;
20. else
21. cout << "input error" << endl;
22.
23. int i;
24.
25. for(i=0;i<8;i++)
26. {
27. if(S.at(i)==S.at(i+1))
28. {
29. cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
30. }
31.
32. for(i=9;i<17;i++)
33. {
34. if(S.at(i)==S.at(i+1))
35. {
36. cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
37. }
38.
39. for(i=18;i<26;i++)
40. {
41. if(S.at(i)==S.at(i+1))
42. {
43. cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
44. }
45.
46. for(i=27;i<35;i++)
47. {
48. if(S.at(i)==S.at(i+1))
49. {
50. cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
51. }
52.
53. for(i=36;i<44;i++)
54. {
55. if(S.at(i)==S.at(i+1))
56. {
57. cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
58. }
59.
60. for(i=45;i<53;i++)
61. {
62. if(S.at(i)==S.at(i+1))
63. {
64. cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
65. }
66.
67. for(i=54;i<62;i++)
68. {
69. if(S.at(i)==S.at(i+1))
70. {
71. cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
72. }
73.
74. for(i=63;i<71;i++)
75. {
76. if(S.at(i)==S.at(i+1))
77. {
78. cout<<S.at(i)<< " appears twice at row"<< (i/9)+1 <<endl;
79. }
80.
81. for(i=72;i<80;i++)
82. {
83. if(S.at(i)==S.at(i+1))
84. {
85. cout<<S.at(i)<< " appears twice at row "<< (i/9)+1 <<endl;
86. }
87.
88. int j;
89.
90. for(int j=0;j<8;j++)
91. {
92. for(int i=0;i<8;i++)
93. {
94. S.at(j)=(9*i)+1;
95. if(S.at(j)==S.at(j+1))
96. {
97. cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
98. }
99. }
100. }
101.
102. for(int j=9;j<17;j++)
103. {
104. for(int i=9;i<17;i++)
105. {
106. S.at(j)=(9*i)+2;
107. if(S.at(j)==S.at(j+1))
108. {
109. cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
110. }
111. }
112. }
113.
114. for(int j=18;j<26;j++)
115. {
116. for(int i=18;i<26;i++)
117. {
118. S.at(j)=(9*i)+3;
119. if(S.at(j)==S.at(j+1))
120. {
121. cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
122. }
123. }
124. }
125.
126. for(int j=27;j<35;j++)
127. {
128. for(int i=27;i<35;i++)
129. {
130. S.at(j)=(9*i)+4;
131. if(S.at(j)==S.at(j+1))
132. {
133. cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
134. }
135. }
136. }
137.
138. for(int j=36;j<44;j++)
139. {
140. for(int i=36;i<44;i++)
141. {
142. S.at(j)=(9*i)+1;
143. if(S.at(j)==S.at(j+1))
144. {
145. cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
146. }
147. }
148. }
149.
150. for(int j=45;j<53;j++)
151. {
152. for(int i=45;i<53;i++)
153. {
154. S.at(j)=(9*i)+1;
155. if(S.at(j)==S.at(j+1))
156. {
157. cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
158. }
159. }
160. }
161.
162. for(int j=54;j<62;j++)
163. {
164. for(int i=54;i<62;i++)
165. {
166. S.at(j)=(9*i)+1;
167. if(S.at(j)==S.at(j+1))
168. {
169. cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
170. }
171. }
172. }
173.
174. for(int j=63;j<71;j++)
175. {
176. for(int i=63;i<71;i++)
177. {
178. S.at(j)=(9*i)+1;
179. if(S.at(j)==S.at(j+1))
180. {
181. cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
182. }
183. }
184. }
185.
186. for(int j=72;j<80;j++)
187. {
188. for(int i=72;i<80;i++)
189. {
190. S.at(j)=(9*i)+1;
191. if(S.at(j)==S.at(j+1))
192. {
193. cout<<S.at(j)<< " appears twice at column "<< (j/9)+1 << endl;
194. }
195. }
196. }
197.
198. bool A[9];
199. int x;
200. for(x=1;x<10;x++)
201. {
202. if(x=true)
203.
204.
205.
206.
207.
208. system("PAUSE");
209. return EXIT_SUCCESS;
210. }
211.
Sep 24 '08 #6
JosAH
11,448 Recognized Expert MVP
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:

Expand|Select|Wrap|Line Numbers
1. int collect(int x, int dx, int n, int mask) {
2.
3.    for (; n--; x+= dx)
6. }
7.
If we want to check the nine rows we have to do this:

Expand|Select|Wrap|Line Numbers
1. for (int row= 0; row < 81; row+= 9)
2.    if (collect(row, 1, 9, 0) != 0x1ff)
3.       printf("row %d is incorrect\n", row);
4.
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
Sep 24 '08 #7
ningxin
5 New Member
i looked at it for quite some time and could get most of it. but i could not understand this statement:
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&&8 1)
{
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?
Sep 24 '08 #8
stragatto
7 New Member
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 !
Sep 24 '08 #9
ningxin
5 New Member
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:\\Documen ts and Settings\\HP\\D esktop\\sud3.tx t");
vector<int> S;
int buffer;
while(in>>buffe r)
S.push_back(buf fer);
if(S.size()==81 )
cout << "input worked" << endl;
else
cout << "input error" << endl;

for(; n--;i+=di)
{
}
}
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||0 x004||0x008||0x 010||0x020||0x0 40||0x080||0x10 0

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;g rid++)
{
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:expect ed primary expression before ')' token;

sorry for asking so many questions...
Sep 25 '08 #10