944,123 Members | Top Members by Rank

Software Development > C++ > C++ function to check validity of sudoku
Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 6823
  • C++ RSS
Permalink
Nov 20th, 2007
0

C++ function to check validity of sudoku

Expand Post »
Hello all!

New here at daniweb.

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:

C++ Syntax (Toggle Plain Text)
  1. /** Check whether grid[i][j] is valid in the grid */
  2. bool isValid(int grid[] [9])
  3. {
  4. 	int i, j;
  5. 	bool status;
  6. 	status = true;
  7.  
  8. 	for (int column = 0; column < 9; column++)
  9. 		if (column != j && grid[i] [column] == grid[i] [j])
  10. 			status = false;
  11.  
  12. 	for (int row = 0; row < 9; row++)
  13. 		if (row != i && grid[row] [j] == grid[i] [j])
  14. 			status = false;
  15.  
  16. 	for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)
  17. 		for (int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++)
  18. 			if (row != i && col != j && grid[row] [col] == grid[i] [j])
  19. 				status = false;
  20.  
  21. 	for (int i = 0; i < 9; i++)
  22. 		for (int j = 0; j < 9; j++)
  23. 			if (grid[i][j] != 0)
  24. 				status = false;
  25.  
  26. 	for (int i = 0; i < 9; i++)
  27. 		for (int j = 0; j < 9; j++)
  28. 			if ((grid[i][j] < 0) || (grid[i][j] > 9))
  29. 				status = false;
  30.  
  31.  
  32. 	return status;
  33.  
  34. }


Any ideas?
Reputation Points: 10
Solved Threads: 0
Newbie Poster
brlukosk is offline Offline
9 posts
since Nov 2007
Permalink
Nov 20th, 2007
0

Re: C++ function to check validity of sudoku

Click to Expand / Collapse  Quote originally posted by brlukosk ...
Hello all!

New here at daniweb.

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:

...

Any ideas?
Maybe finish the program, I suppose...
Moderator
Reputation Points: 3281
Solved Threads: 895
Posting Sage
WaltP is offline Offline
7,747 posts
since May 2006
Permalink
Nov 20th, 2007
0

Re: C++ function to check validity of sudoku

Well of course...

This is just a function of the program.

My main question is how to check the 9x9 array to determine if it is a valid puzzle.

Here is the program:

C++ Syntax (Toggle Plain Text)
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <iomanip>
  5.  
  6. using namespace std;
  7. void readAPuzzle(int grid[] [9]);
  8. bool search(int grid[] [9]);
  9. void printGrid(int grid[] [9]);
  10. bool isValid(int grid[] [9]);
  11.  
  12. int main()
  13. {
  14. 	// Read a Sudoku puzzle
  15. 	int grid[9] [9];
  16.  
  17. 	readAPuzzle(grid);
  18.  
  19. 	printGrid(grid);
  20.  
  21. 	if (isValid(grid))
  22.     cout << "Is a sudoku puzzle. " << endl;
  23.  
  24. 	else 
  25. 	cout << "Is not a sudoku puzzle. " << endl;
  26.  
  27. 	return 0;
  28. }
  29.  
  30. //Reads Puzzle into 9x9 array ( modify to read from file )
  31. void readAPuzzle(int grid[] [9])
  32. {
  33. 	ifstream in_f;
  34.  
  35. 	in_f.open("ma1.dat");
  36.  
  37. 	for (int i = 0; i < 9; i++)
  38. 	for (int j = 0; j < 9; j++)
  39. 	in_f >> grid[i] [j];
  40. }
  41.  
  42. //Prints out the puzzle read from file (keep)
  43. void printGrid(int grid[] [9])
  44. {
  45. 	for (int i = 0; i < 9; i++)
  46. 	{
  47. 		for (int j = 0; j < 9; j++)
  48. 			cout << grid[i] [j] << " ";
  49. 		cout << endl;
  50. 	}
  51. }
  52. /** Check whether grid[i][j] is valid in the grid */
  53. bool isValid(int grid[] [9])
  54. {
  55. 	int i, j;
  56. 	bool status;
  57. 	status = true;
  58.  
  59. 	for (int column = 0; column < 9; column++)
  60. 		if (column != j && grid[i] [column] == grid[i] [j])
  61. 			status = false;
  62.  
  63. 	for (int row = 0; row < 9; row++)
  64. 		if (row != i && grid[row] [j] == grid[i] [j])
  65. 			status = false;
  66.  
  67. 	for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)
  68. 		for (int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++)
  69. 			if (row != i && col != j && grid[row] [col] == grid[i] [j])
  70. 				status = false;
  71.  
  72. 	for (int i = 0; i < 9; i++)
  73. 		for (int j = 0; j < 9; j++)
  74. 			if (grid[i][j] != 0)
  75. 				status = false;
  76.  
  77. 	for (int i = 0; i < 9; i++)
  78. 		for (int j = 0; j < 9; j++)
  79. 			if ((grid[i][j] < 0) || (grid[i][j] > 9))
  80. 				status = false;
  81.  
  82.  
  83. 	return status;
  84.  
  85. }
Reputation Points: 10
Solved Threads: 0
Newbie Poster
brlukosk is offline Offline
9 posts
since Nov 2007
Permalink
Nov 20th, 2007
0

Re: C++ function to check validity of sudoku

Click to Expand / Collapse  Quote originally posted by brlukosk ...
Well of course...

This is just a function of the program.

My main question is how to check the 9x9 array to determine if it is a valid puzzle.
Oh, I get it. That was not a question in your previous post.

It looks to me like you are already checking the 9x9 array in isValid() so I don't understand exactly what you need help with. Please read the post Read Me: Read This Before Posting so you can ask exactly what you need to know in a way we can help you.
Moderator
Reputation Points: 3281
Solved Threads: 895
Posting Sage
WaltP is offline Offline
7,747 posts
since May 2006
Permalink
Nov 20th, 2007
0

Re: C++ function to check validity of sudoku

I said: "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."

I figured that the code I posted could be fixed some how. My apologies for not submitting a proper question.

The problem I have run into is that the program does not know the difference from a valid and invalid puzzle.

I have several solved puzzles that I am in inputting, and several that are just random numbers. The isValid() function is supposed to check for this very occurrence. However it is not.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
brlukosk is offline Offline
9 posts
since Nov 2007
Permalink
Nov 21st, 2007
0

Re: C++ function to check validity of sudoku

Click to Expand / Collapse  Quote originally posted by brlukosk ...
I said: "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."
That's not a question. That is a statement. No one can tell if there is a problem or not.

Click to Expand / Collapse  Quote originally posted by brlukosk ...
I figured that the code I posted could be fixed some how. My apologies for not submitting a proper question.
It probably can. But you never mentioned what the problem is.

Click to Expand / Collapse  Quote originally posted by brlukosk ...
The problem I have run into is that the program does not know the difference from a valid and invalid puzzle.
That's obvious if you posted here. The problem is you aren't explaining what nor where the problem is. Is it ALL your tests? Just one? We didn't write it. We can't run it. You have to tell us what's wrong.

Click to Expand / Collapse  Quote originally posted by brlukosk ...
I have several solved puzzles that I am in inputting, and several that are just random numbers. The isValid() function is supposed to check for this very occurrence. However it is not.
Why not? What's going wrong? What area is it in? Did you output values at key places to figure out where the problem might be?

In other words, read the link, ask a proper question.
Moderator
Reputation Points: 3281
Solved Threads: 895
Posting Sage
WaltP is offline Offline
7,747 posts
since May 2006
Permalink
Nov 21st, 2007
0

Re: C++ function to check validity of sudoku

If I knew what was going wrong I wouldn't have asked the question or made the post.


My function is supposed to check whether or not a given input of a 9x9 matrix is a valid and solvable puzzle; that is, whether or not each row, column, and region in the matrix contains each value from 1 to 9 exactly once.

I have attempted to write the code that will do this, however for some reason my code is not working as it should. It is not checking whether or not a given input of a 9x9 matrix is a valid and solvable puzzle; that is, whether or not each row, column, and region in the matrix contains each value from 1 to 9 exactly once.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
brlukosk is offline Offline
9 posts
since Nov 2007
Permalink
Nov 21st, 2007
0

Re: C++ function to check validity of sudoku

Fine. If you can't tell us anything, run this version of your program. Maybe then it can give you a clue how to figure out what is happening.

C++ Syntax (Toggle Plain Text)
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <iomanip>
  5.  
  6. using namespace std;
  7. void readAPuzzle(int grid[] [9]);
  8. bool search(int grid[] [9]);
  9. void printGrid(int grid[] [9]);
  10. bool isValid(int grid[] [9]);
  11.  
  12. int main()
  13. {
  14. 	// Read a Sudoku puzzle
  15. 	int grid[9] [9];
  16.  
  17. 	readAPuzzle(grid);
  18.  
  19. 	printGrid(grid);
  20.  
  21. 	if (isValid(grid))
  22.     cout << "Is a sudoku puzzle. " << endl;
  23.  
  24. 	else 
  25. 	cout << "Is not a sudoku puzzle. " << endl;
  26.  
  27. 	return 0;
  28. }
  29.  
  30. //Reads Puzzle into 9x9 array ( modify to read from file )
  31. void readAPuzzle(int grid[] [9])
  32. {
  33. 	ifstream in_f;
  34.  
  35. 	in_f.open("ma1.dat");
  36.  
  37. 	for (int i = 0; i < 9; i++)
  38. 	for (int j = 0; j < 9; j++)
  39. 	in_f >> grid[i] [j];
  40. }
  41.  
  42. //Prints out the puzzle read from file (keep)
  43. void printGrid(int grid[] [9])
  44. {
  45. 	for (int i = 0; i < 9; i++)
  46. 	{
  47. 		for (int j = 0; j < 9; j++)
  48. 			cout << grid[i] [j] << " ";
  49. 		cout << endl;
  50. 	}
  51. }
  52. /** Check whether grid[i][j] is valid in the grid */
  53. bool isValid(int grid[] [9])
  54. {
  55. 	int i, j;
  56. 	bool status;
  57. 	status = true;
  58.  
  59. 	for (int column = 0; column < 9; column++)
  60. 		if (column != j && grid[i] [column] == grid[i] [j])
  61. 			status = false;
  62. cout << "1st test: " << status << endl;
  63.  
  64. 	for (int row = 0; row < 9; row++)
  65. 		if (row != i && grid[row] [j] == grid[i] [j])
  66. 			status = false;
  67. cout << "2nd test: " << status << endl;
  68.  
  69. 	for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)
  70. 		for (int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++)
  71. 			if (row != i && col != j && grid[row] [col] == grid[i] [j])
  72. 				status = false;
  73. cout << "3rd test: " << status << endl;
  74.  
  75. 	for (int i = 0; i < 9; i++)
  76. 		for (int j = 0; j < 9; j++)
  77. 			if (grid[i][j] != 0)
  78. 				status = false;
  79. cout << "4th test: " << status << endl;
  80.  
  81. 	for (int i = 0; i < 9; i++)
  82. 		for (int j = 0; j < 9; j++)
  83. 			if ((grid[i][j] < 0) || (grid[i][j] > 9))
  84. 				status = false;
  85. cout << "5th test: " << status << endl;
  86.  
  87.  
  88. 	return status;
  89.  
  90. }
Look at the output and you should be able to tell which loop is working improperly.
Moderator
Reputation Points: 3281
Solved Threads: 895
Posting Sage
WaltP is offline Offline
7,747 posts
since May 2006
Permalink
Nov 21st, 2007
0

Re: C++ function to check validity of sudoku

It appears that the line:

C++ Syntax (Toggle Plain Text)
  1. if (column != j && grid[i] [column] == grid[i] [j])

is incorrect.

How can I fix it?
Reputation Points: 10
Solved Threads: 0
Newbie Poster
brlukosk is offline Offline
9 posts
since Nov 2007

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: Check for valid date, fine if no date entered
Next Thread in C++ Forum Timeline: Help With Recursive function coding in C++





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC