Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Feb 14th, 2008, 10:01 PM   #1
stayscrisp
Newbie
 
Join Date: Feb 2008
Posts: 2
Rep Power: 0 stayscrisp is on a distinguished road
Sudoku Problem
hi i am currently working on a sudoku solver which is a basic brute force method, i will post my code but i think where im having trouble is the 3x3 box checking function which is called BadBox() i have got this code working on a 4x4 grid and just cant seem to get it right with a 9x9 any help on this function would be greatly appreciated

c++ Syntax (Toggle Plain Text) 
  1. #include <iostream>
  2.  
  3. // Print out a 4x4 grid using one loop, from 0 to 15
  4. void PrintGrid(int squares[])
  5. {
  6.     int num = 0;
  7.     for (int i = 0; i < 81; i++)
  8.     {
  9.         std::cout << squares[i] << " ";
  10.         num++;
  11.         if (num == 9)
  12.         {
  13.             std::cout << "\n";
  14.             num = 0;
  15.         }
  16.     }
  17. }
  18.  
  19. // Print out the 4x4 grid but using 2 nested loops.
  20. // This does the same as the function above - it's just a slightly different
  21. //  way of doing it.
  22. void PrintNested(int squares[])
  23. {
  24.     // Nested loop
  25.     int num = 0;
  26.     for (int i = 0; i < 9; i++)
  27.     {
  28.         for (int j = 0; j < 9; j++)
  29.         {
  30.             std::cout << squares[num] << " ";
  31.             num++;
  32.         }
  33.         std::cout << "\n";
  34.     }
  35. }
  36.  
  37. // Check if we have a Bad Column: if any square in the same column as squareNum
  38. //  contains the same value as squareNum, this column is bad, because it has the
  39. //  same number in it more than once.
  40. bool BadColumn(int squareNum, int solution[])
  41. {
  42.     int top = squareNum % 9;
  43.     for (int i = 0; i < 9; i++)
  44.     {
  45.         // Don't check squareNum with itself! If the 'top' square number is the same
  46.         //  as squareNum, just go on to the next square.
  47.         if (top == squareNum)
  48.         {
  49.             top += 9;
  50.             continue;
  51.         }
  52.  
  53.         if (solution[top] == solution[squareNum])
  54.         {
  55.             return true;
  56.         }
  57.         top += 9;
  58.     }
  59.     return false;
  60. }
  61.  
  62. // Check if we have a bad row: if any square in the same row as squareNum contains
  63. //  the same value as in squareNum, this is a bad row.
  64. bool BadRow(int squareNum, int solution[])
  65. {
  66.     int left = (squareNum / 9) * 9;
  67.     for (int i = 0; i < 9; i++)
  68.     {
  69.         // Same as for BadColumn(), we don't want to check squareNum against itself.
  70.         if (left == squareNum)
  71.         {
  72.             left++;
  73.             continue;
  74.         }
  75.  
  76.         if (solution[left] == solution[squareNum])
  77.         {
  78.             return true;
  79.         }
  80.         left++;
  81.     }
  82.     return false;
  83. }
  84.  
  85. // Check if a 2x2 box is bad
  86. bool BadBox(int squareNum, int solution[])
  87. {
  88.     // Get the top-left position: either 0 or 8
  89.     int topLeft = (squareNum / 27) * 27;
  90.     // Now add 2 if the box is to the right - so we now have a top-left position
  91.     //  of 0, 2, 8 or 10.
  92.     if ((squareNum % 9) > 1)
  93.     {
  94.         topLeft += 3;
  95.     }
  96.     else
  97.     {
  98.     if ((squareNum % 9) > 4)
  99.     {
  100.        topLeft += 3;
  101.     }
  102. }
  103.  
  104.     // Count through the 4 squares in the box
  105.     for (int i = 0; i < 9; i++)
  106.     {
  107.         // Again, we don't want to test squareNum against itself.
  108.         // This time we are not using continue, for some exciting variety.
  109.         if (topLeft != squareNum)
  110.         {
  111.             if (solution[topLeft] == solution[squareNum])
  112.             {
  113.                 return true;
  114.             }
  115.         }
  116.  
  117.         // Slightly more complicated than for row and column, we add 3 to the topLef square
  118.         //  if i is 1, to go the leftmost square of the next row in the box.
  119.         if (i == 1)
  120.         {
  121.             topLeft += 4;
  122.         }
  123.         else
  124.         {
  125.             topLeft++;
  126.         }
  127.     }
  128.     return false;
  129. }
  130.  
  131. // Check if a square is bad: it is bad if we have a duplicate in the row, column or box
  132. //  that squareNum occupies.
  133. bool BadSquare(int squareNum, int solution[])
  134. {
  135.     if (BadColumn(squareNum, solution))
  136.     {
  137.         return true;
  138.     }
  139.     if (BadRow(squareNum, solution))
  140.     {
  141.         return true;
  142.     }
  143.     if (BadBox(squareNum, solution))
  144.     {
  145.         return true;
  146.     }
  147.     // Column, Row and Box are all good - so this is NOT a bad square.
  148.     return false;
  149. }
  150.  
  151. // Check if we have found a solution for a sudoku.
  152. // The way this works is: we check each square. If all the squares are 'good' we have
  153. //  solved the puzzle.
  154. // A good square means it does not have a duplicated value in the same row, column or
  155. //  box.
  156. bool IsSolved(int solution[])
  157. {
  158.     // Check every square. For a 4x4 sudoku, that means 16 squares, right?!
  159.     for (int i = 0; i < 81; i++)
  160.     {
  161.         // If we find a bad square, the puzzle is not solved.
  162.         if (BadSquare(i, solution))
  163.         {
  164.             return false;
  165.         }
  166.     }
  167.     // No bad squares - the puzzle is solved!
  168.     return true;
  169. }
  170.  
  171. // Test function: work out if a grid has a valid puzzle solution in it.
  172. // We can use this to make sure IsSolved() works as we want it to.
  173. void Test(int grid[])
  174. {
  175.     if (IsSolved(grid))
  176.     {
  177.         std::cout << "This is a good solution:\n";
  178.     }
  179.     else
  180.     {
  181.         std::cout << "This is a bad solution:\n";
  182.     }
  183.     PrintGrid(grid);
  184. }
  185.  
  186. int main()
  187. {
  188.     // Test our IsSolved() function by testing a good puzzle solution, and a
  189.     //  bad solution.
  190.     // This gives us some confidence but the best way to check it is to step
  191.     //  through the code - we did this in class and found bugs!
  192.     int good[] =
  193.     {
  194.       9, 6, 1, 5, 4, 8, 2, 7, 3,
  195.       8, 7, 2, 9, 3, 1, 6, 4, 5,
  196.       4, 5, 3, 6, 2, 7, 8, 9, 1,
  197.       5, 4, 9, 3, 8, 2, 1, 6, 7,
  198.       2, 8, 6, 7, 1, 5, 4, 3, 9,
  199.       1, 3, 7, 4, 9, 6, 5, 8, 2,
  200.       6, 9, 4, 1, 5, 3, 7, 2, 8,
  201.       3, 2, 5, 8, 7, 4, 9, 1, 6,
  202.       7, 1, 8, 2, 6, 9, 3, 5, 4
  203.  
  204.     };
  205.     // Test the good puzzle - we expect Test() to say that this is a good solution.
  206.     Test(good);
  207.  
  208.     int bad[] =
  209.     {
  210.         1, 2, 3, 4, 5, 6, 7, 8, 9,
  211.         3, 1, 2, 3, 3, 4, 5, 6, 9,
  212.         4, 4, 4, 2, 4, 5, 6, 7, 9,
  213.         2, 3, 1, 1, 6, 7, 7, 8, 9,
  214.         3, 4, 1, 2, 3, 4, 5, 6, 9,
  215.         1, 2, 3, 4, 5, 6, 7, 8, 9,
  216.         1, 2, 3, 4, 5, 6, 7, 8, 9,
  217.         1, 2, 3, 4, 5, 6, 7, 8, 9,
  218.         1, 2, 3, 4, 5, 6, 7, 8, 9,
  219.     };
  220.     // Test the bad puzzle - we expect Test() to say that this is a bad solution.
  221.     Test(bad);
  222.  
  223.  
  224.  
  225. }

it should return the good solution as being good and the bad as bad, but it always returns the good as bad please help :s
sorry most of the comments are from my 4x4 version but they should still be of some help.
so at the moment it doesnt actually solve the sudoku for you, it is simply trying out wether or not it recognises when the puzzle is solved or not and as you see the good grid i have is definetley a valid sudoku. once this is working i can get onto the rest of my code
stayscrisp is offline   Reply With Quote
Old Feb 15th, 2008, 5:13 PM   #2
OpenLoop
Expert Programmer
 
OpenLoop's Avatar
 
Join Date: May 2005
Location: East Lansing, MI
Posts: 663
Rep Power: 4 OpenLoop is on a distinguished road
Re: Sudoku Problem
First let me say that this is not the best way to implement a full 81 square sudoku, it's not even a good one. However, if you're a beginner programmer then you're excused. Let's get to business, you were right about BadBox(). It was not calculating the topleft correctly and wasn't bumping up the counter correctly either. A row/column approach would've made this program a lot simpler, but since you decided otherwise, I recoded your BadBox() function consistently with your current code.
C++ Syntax (Toggle Plain Text) 
  1. #include <iostream>
  2.  
  3. // Print out a 4x4 grid using one loop, from 0 to 15
  4. void PrintGrid(int squares[])
  5. {
  6.     int num = 0;
  7.     for (int i = 0; i < 81; i++)
  8.     {
  9.         std::cout << squares[i] << " ";
  10.         num++;
  11.         if (num == 9)
  12.         {
  13.             std::cout << "\n";
  14.             num = 0;
  15.         }
  16.     }
  17. }
  18.  
  19. // Print out the 4x4 grid but using 2 nested loops.
  20. // This does the same as the function above - it's just a slightly different
  21. //  way of doing it.
  22. void PrintNested(int squares[])
  23. {
  24.     // Nested loop
  25.     int num = 0;
  26.     for (int i = 0; i < 9; i++)
  27.     {
  28.         for (int j = 0; j < 9; j++)
  29.         {
  30.             std::cout << squares[num] << " ";
  31.             num++;
  32.         }
  33.         std::cout << "\n";
  34.     }
  35. }
  36.  
  37. // Check if we have a Bad Column: if any square in the same column as squareNum
  38. //  contains the same value as squareNum, this column is bad, because it has the
  39. //  same number in it more than once.
  40. bool BadColumn(int squareNum, int solution[])
  41. {
  42.     int top = squareNum % 9;
  43.     for (int i = 0; i < 9; i++)
  44.     {
  45.         // Don't check squareNum with itself! If the 'top' square number is the same
  46.         //  as squareNum, just go on to the next square.
  47.         if (top == squareNum)
  48.         {
  49.             top += 9;
  50.             continue;
  51.         }
  52.  
  53.         if (solution[top] == solution[squareNum])
  54.         {
  55.             return true;
  56.         }
  57.         top += 9;
  58.     }
  59.     return false;
  60. }
  61.  
  62. // Check if we have a bad row: if any square in the same row as squareNum contains
  63. //  the same value as in squareNum, this is a bad row.
  64. bool BadRow(int squareNum, int solution[])
  65. {
  66.     int left = (squareNum / 9) * 9;
  67.     for (int i = 0; i < 9; i++)
  68.     {
  69.         // Same as for BadColumn(), we don't want to check squareNum against itself.
  70.         if (left == squareNum)
  71.         {
  72.             left++;
  73.             continue;
  74.         }
  75.  
  76.         if (solution[left] == solution[squareNum])
  77.         {
  78.             return true;
  79.         }
  80.         left++;
  81.     }
  82.     return false;
  83. }
  84.  
  85. // Check if a 2x2 box is bad
  86. bool BadBox(int squareNum, int solution[])
  87. {
  88.     //get row and col or requested square 
  89.     int row = (int)(squareNum / 9);
  90.     int col = squareNum % 9;        
  91.     //get the topleft square in the box
  92.     int topLeft = (row - row%3)*9 + (col - col%3);
  93.  
  94.     // Count through the 9 squares in the box
  95.     int curSquare = topLeft;
  96.     for (int i = 0; i < 9; i++)
  97.     {
  98.         // Again, we don't want to test squareNum against itself.
  99.         // This time we are not using continue, for some exciting variety.    
  100.         if (curSquare != squareNum)
  101.         {
  102.             if (solution[curSquare] == solution[squareNum])
  103.             {
  104.                 return true;
  105.             }
  106.         }
  107.  
  108.         //go to the next square in the box. If i is at the border of the 3x3
  109.         //box, bump up the curSquare to the next line (add 9 and subtract the 
  110.         //2 we already added)
  111.         if (i % 3 == 2)
  112.            curSquare += 7;
  113.         else
  114.            curSquare++;
  115.  
  116.     }
  117.     return false;
  118. }
  119.  
  120. // Check if a square is bad: it is bad if we have a duplicate in the row, column or box
  121. //  that squareNum occupies.
  122. bool BadSquare(int squareNum, int solution[])
  123. {
  124.     if (BadColumn(squareNum, solution))
  125.     {
  126.         return true;
  127.     }
  128.     if (BadRow(squareNum, solution))
  129.     {
  130.         return true;
  131.     }
  132.     if (BadBox(squareNum, solution))
  133.     {
  134.         return true;
  135.     }
  136.     // Column, Row and Box are all good - so this is NOT a bad square.
  137.     return false;
  138. }
  139.  
  140. // Check if we have found a solution for a sudoku.
  141. // The way this works is: we check each square. If all the squares are 'good' we have
  142. //  solved the puzzle.
  143. // A good square means it does not have a duplicated value in the same row, column or
  144. //  box.
  145. bool IsSolved(int solution[])
  146. {
  147.     // Check every square. For a 4x4 sudoku, that means 16 squares, right?!
  148.     for (int i = 0; i < 81; i++)
  149.     {
  150.         // If we find a bad square, the puzzle is not solved.
  151.         if (BadSquare(i, solution))
  152.         {
  153.             return false;
  154.         }
  155.     }
  156.     // No bad squares - the puzzle is solved!
  157.     return true;
  158. }
  159.  
  160. // Test function: work out if a grid has a valid puzzle solution in it.
  161. // We can use this to make sure IsSolved() works as we want it to.
  162. void Test(int grid[])
  163. {
  164.     if (IsSolved(grid))
  165.     {
  166.         std::cout << "This is a good solution:\n";
  167.     }
  168.     else
  169.     {
  170.         std::cout << "This is a bad solution:\n";
  171.     }
  172.     PrintGrid(grid);
  173. }
  174.  
  175. int main()
  176. {
  177.     // Test our IsSolved() function by testing a good puzzle solution, and a
  178.     //  bad solution.
  179.     // This gives us some confidence but the best way to check it is to step
  180.     //  through the code - we did this in class and found bugs!
  181.     int good[] =
  182.     {
  183.       9, 6, 1, 5, 4, 8, 2, 7, 3,
  184.       8, 7, 2, 9, 3, 1, 6, 4, 5,
  185.       4, 5, 3, 6, 2, 7, 8, 9, 1,
  186.       5, 4, 9, 3, 8, 2, 1, 6, 7,
  187.       2, 8, 6, 7, 1, 5, 4, 3, 9,
  188.       1, 3, 7, 4, 9, 6, 5, 8, 2,
  189.       6, 9, 4, 1, 5, 3, 7, 2, 8,
  190.       3, 2, 5, 8, 7, 4, 9, 1, 6,
  191.       7, 1, 8, 2, 6, 9, 3, 5, 4
  192.  
  193.     };
  194.     // Test the good puzzle - we expect Test() to say that this is a good solution.
  195.     Test(good);
  196.  
  197.     int bad[] =
  198.     {
  199.         1, 2, 3, 4, 5, 6, 7, 8, 9,
  200.         3, 1, 2, 3, 3, 4, 5, 6, 9,
  201.         4, 4, 4, 2, 4, 5, 6, 7, 9,
  202.         2, 3, 1, 1, 6, 7, 7, 8, 9,
  203.         3, 4, 1, 2, 3, 4, 5, 6, 9,
  204.         1, 2, 3, 4, 5, 6, 7, 8, 9,
  205.         1, 2, 3, 4, 5, 6, 7, 8, 9,
  206.         1, 2, 3, 4, 5, 6, 7, 8, 9,
  207.         1, 2, 3, 4, 5, 6, 7, 8, 9,
  208.     };
  209.     // Test the bad puzzle - we expect Test() to say that this is a bad solution.
  210.     Test(bad);
  211.  
  212.     system("pause");
  213.  
  214. }
OpenLoop is offline   Reply With Quote
Old Feb 16th, 2008, 7:36 AM   #3
stayscrisp
Newbie
 
Join Date: Feb 2008
Posts: 2
Rep Power: 0 stayscrisp is on a distinguished road
Re: Sudoku Problem
thanks thats really helpful, and well commented thanks, i had a method like this but had trouble implementing it so thanks a lot
stayscrisp is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes
Linear Mode Linear Mode

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Challenging Programming Problem - "Pinball Ranking" Sane Coder's Corner Lounge 38 Jan 15th, 2008 5:16 PM
Problem solving ReggaetonKing Software Design and Algorithms 7 Jan 4th, 2008 1:49 PM
Sudoku Solver code is making my head explode FoSheezy C 1 Nov 1st, 2007 6:20 PM
Sudoku program info & description Adak Software Design and Algorithms 4 Jul 2nd, 2006 12:49 PM
cgi/perl script + IE problem joyceshee Perl 2 Jan 24th, 2006 11:10 AM


Contact Us - DaniWeb IT Discussion Community - Privacy Statement - Top


DaniWeb IT Discussion Community
All times are GMT -5. The time now is 2:34 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC