473,585 Members | 2,720 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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)
  4.       mask|= 1<<board[x]-1;
  5.    return mask;
  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:
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&&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)
{
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||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

Sign in to post your reply or Sign up for a free account.

Similar topics

12
6330
by: kalinga1234 | last post by:
hy guys i am having a problem with my sudoku program which i coded using c++.; currently in my program if a duplicate number exist in either row/column/block i would make the particualr square 0. but thats not i want to do. I want to recurse back until until it find a correct number. i will post the function which i need the help; ...
125
6517
by: jacob navia | last post by:
We hear very often in this discussion group that bounds checking, or safety tests are too expensive to be used in C. Several researchers of UCSD have published an interesting paper about this problem. http://www.jilp.org/vol9/v9paper10.pdf Specifically, they measured the overhead of a bounds
1
3320
by: AndyB | last post by:
I have found a lot of material on removing duplicates from a list, but I am trying to find the most efficient way to just check for the existence of duplicates in a list. Here is the best I have come up with so far: CheckList = for x in self.__XRList] FilteredList = filter((lambda x:x != 0),CheckList) if len(FilteredList)...
6
11871
by: blux | last post by:
I am working on a function to check the validity of a sudoku puzzle. It must check the 9x9 matrix to make sure it follows the rules and is a valid sudoku puzzle. this is what I have come up with so far: However I have found that it does not check it correctly. I just need to check the 9x9 array, which I am passing to this function...
1
1858
by: deanchhsw | last post by:
Part A (http://bytes.com/topic/java/insights/645821-sudoku) B (http://bytes.com/topic/java/insights/739704-sudoku-b) C (http://bytes.com/topic/java/insights/739703-sudoku-c) this question refers to the Sudoku howto posted on this website. The links are shown above. My question centers around the boolean variables declared in Part A, such as...
1
3257
by: runningsnake24 | last post by:
We are writing a program to check that a filled in Sudoku puzzle is solved correctly. We are required to use the Iterator and Iterable interfaces. The program uses a Cell class to represent each individual cell of a puzzle, and uses a 2D array to represent the entire puzzle. The next method in our class that implements Iterator must return a...
3
5962
by: DannyB13 | last post by:
Hi, and thanks for possible help in advance. Here's my dilemma. I've been making a sudoku generator, and I'm now stuck on one part. I must be able to take a 'solution' and verify that it is correct, by checking a few things. 1. There are enough numbers, no 'periods' which signify '0' or 'no input'. 2. That there are no duplicate numbers in any...
1
2810
by: 361162 | last post by:
Sudoku puzzles are made up of the numbers 1-9 arranged in a 9by9 grid, where every number must appear exactly once in every column, row and 3by3 block in order for the solution to be valid. Sudoku puzzles are often given as competition in newspapers. Your job is to write a sudoku checker that will check if sudoku solution is valid or not. Input...
3
3934
by: diggity | last post by:
okay, so i started on code for Sudoku on ready to program java ... very close to java. I was able to create a 2d array and display and change the variables. What i want to do now is to generate random numbers in the array. Numbers in between 1 and 9. and then i need to check for rows, columns and the boxes... i am new to arrays and i really need...
0
7900
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
8332
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7943
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
8204
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6592
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5705
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
3828
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
2338
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1442
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.