Sudoku

Please support our C++ advertiser: Programming Forums - DaniWeb Sister Site
Reply
1 2

•
•
Join Date: Dec 2007
Posts: 113
Reputation: zoner7 is an unknown quantity at this point 
Solved Threads: 4
zoner7 zoner7 is offline Offline
Junior Poster

Sudoku

 
0
  #1
May 18th, 2008
So I decided that I wanted to make a Sudoku creator and solver for fun. My plan is to fill a sudoku board with random, however, compatible answers using brutefruce. I simply check random numbers against the two prerequisite rules for a legitimate Sudoku: a given cell cannot contain the same number as any cell in the same vertical or horizontal axises as itself and a given cell cannot contain the same number as those contained by cells in its respective 3x3.

Later I hope to enumerate the strategies that humans use to solve Sudoku puzzles and apply these hueristics to a solver. Next, I want to remove numbers one by one from the random, bruteforce-created solved sudoku puzzle. I could then verify that the resulting sequence of numbers is solvable using my sudoku puzzle solver. If it is not, a different random number can be removed.

Currently I am curious how to implement the second rule of sudoku above. I currently have a 9x9 multidimensional array, and I want to verify that a given cell in this array is not equal to any of the other cells in its 3x3 square. I was thinking of creating a set of rules for each coordinate using the modulus operator. If I divided by 3, I could use the remainder of each cell in some sort of algorithm. Using modulus would ensure that each number is located in the same place within its respective 3x3 square and thus has the same value. Depending on the value, a certain set of rules would determine which indices to compare a given square to.

I am not too sure how to proceed from here. Any suggestions. My main issue is that I cannot say
if (Board [x%3] != so and so) because each of these indices have values. I would be comparing the values inside the indices with one another, which is not what I want to do. I hope this makes some sense. I'll post my code if this is as confusing as it sounds to me.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2007
Posts: 1,953
Reputation: Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of 
Solved Threads: 214
Featured Poster
Duoas's Avatar
Duoas Duoas is offline Offline
Posting Virtuoso

Re: Sudoku

 
0
  #2
May 18th, 2008
You could always initialize the board to be filled with invalid values (like -1) which is excluded from all comparisons.

Your modulus idea is good.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 113
Reputation: zoner7 is an unknown quantity at this point 
Solved Threads: 4
zoner7 zoner7 is offline Offline
Junior Poster

Re: Sudoku

 
0
  #3
May 18th, 2008
I was actually considering doing that. How can I do some mass initialization, where every indice in the array takes on the same value?
Is it possible to avoid int bob [] = {-1,-1,-1,-1,-1,-1...}; 81 times? Additionally, how do I do this for a multidimensional array?
Last edited by zoner7; May 18th, 2008 at 9:10 pm.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 113
Reputation: zoner7 is an unknown quantity at this point 
Solved Threads: 4
zoner7 zoner7 is offline Offline
Junior Poster

Re: Sudoku

 
0
  #4
May 18th, 2008
Aside from its striking inefficiency, this code simply doesn't work, mainly because I've forgotten some important syntax (besides, I think the logic is currently flawed as well). I'm basically requesting some help with some of the basic syntax.

line 22: Invalid conversion from int(*)() to int().
I really have no idea what this means. I always thought * was used to indicate a pointer, but I never used any.

Line 45: Bool Verify redeclared as a different kind of symbol.
I imagine this relates to the return value being boolean but the argument being integer. I am not exactly sure how to remedy this.

Also, my use of the variable x and y is very screwed up. I need a way for the function to access them without causing errors. if anyone can help me out with some of these issues - and any others that you find - it would be greatly appreciated. Thank you for the help in advance. The code is below.



C++ Syntax (Toggle Plain Text) 
  1. #include <iostream>
  2. #include <ctime>
  3. #include <cstdlib>
  4. using namespace std;
  5.  
  6. int x, y;
  7. int Random_Number();
  8. bool Verify(int,int);
  9.  
  10. int main()
  11. {
  12.       bool BoardStatus [9][9];
  13.  
  14.       int Board [9][9];  // Creates the Sudoku board
  15.  
  16.       for (int y = 0; y < 8; y++)
  17.       {
  18.          for (int x = 0; x < 8; x++)
  19.          {
  20.             if (BoardStatus [y][x] = false)
  21.             {
  22.                Board [y][x] = Random_Number;  // If the cell fufills the proper requirements, a random number is placed inside that cell.
  23.                Verify (y,x);
  24.             }  
  25.          }      
  26.       }
  27.  
  28.       for (int y = 0; y < 8; y++) //Prints the completed Sudoku board.
  29.       {
  30.          for (int x = 0; x < 8; x++)
  31.          {
  32.              cout << Board [x][y];
  33.          }
  34.       }  
  35.       return 0;
  36. }
  37.  
  38. int Random_Number() //  Used to create random integers.  This will ensure that each sudoku board is unique.
  39. {
  40.       srand((unsigned)time(0)); 
  41.       int random_integer = (rand()%9)+1;
  42.       return random_integer;
  43. }
  44.  
  45. bool Verify(y,x)
  46. {
  47.                for (n=0; n <= 8; n++)  // If the given cell equals a cell in its horizontal row or vertical column, a random integer will not be inserted.
  48.                {
  49.                    if (Board [y][x] == Board [n][x] || Board [y][n])
  50.                    {
  51.                       status == false;
  52.                    }
  53.                }
  54.                if (x%3 == 0 & y%3 == 0) // the following lines test whether or not the value in the cell equals a value within that cell's respective 3x3 square.
  55.                {
  56.                   if (Board [y][x] == Board [y+1][x+1] || Board [y+2][x+1] || Board [y+1][x+2] || Board [y+2][x+2]);
  57.                   {
  58.                      status = false;
  59.                   }
  60.                }
  61.                if (x%3 == 1 & y%3 == 0)
  62.                {
  63.                   if (Board [y][x] == Board [y+1][x-1] || Board[y+2][x-1] || Board [y+1][x+1] || Board [y+2][x+1])
  64.                   {
  65.                      status = false;
  66.                   }
  67.                }
  68.                if (x%3 == 2 & y%3 == 0)
  69.                {
  70.                   if (Board [y][x] == Board [y+1][x-1] || Board [y+2][x-1] || Board [y+1][x-2] || Board [y+2] [x-2])
  71.                   {
  72.                      status = false;
  73.                   }
  74.                }
  75.                if (x%3 == 0 & y%3 == 1)
  76.                {
  77.                   if (Board [y][x] == Board [y-1][x+1] || Board [y-1][x+2] || Board [y+1][x+1] || Board [y+1][x+2]);
  78.                   {
  79.                      status = false;
  80.                   }
  81.                }
  82.                if (x%3 == 1 & y%3 == 1)
  83.                {
  84.                   if (Board [y][x] == Board [y-1][x-1] || Board[y+1][x-1] || Board [y-1][x+1] || Board [y+1][x+1])
  85.                   {
  86.                      status = false;
  87.                   }
  88.                }
  89.                if (x%3 == 2 & y%3 == 1)
  90.                {
  91.                   if (Board [y][x] == Board [y-1][x-2] || Board [y-1][x-1] || Board [y+1][x-2] || Board [y+2] [x-1])
  92.                   {
  93.                      status = false;
  94.                   }
  95.                }
  96.                if (x%3 == 0 & y%3 == 2)
  97.                {
  98.                   if (Board [y][x] == Board [y-1][x+1] || Board [y-2][x+1] || Board [y-1][x+2] || Board [y-2][x+2]);
  99.                   {
  100.                      status = false;
  101.                   }
  102.                }
  103.                if (x%3 == 1 & y%3 == 2)
  104.                {
  105.                   if (Board [y][x] == Board [y-1][x-1] || Board[y-2][x-1] || Board [y-1][x+1] || Board [y-2][x+1])
  106.                   {
  107.                      status = false;
  108.                   }
  109.                }
  110.                if (x%3 == 2 & y%3 == 2)
  111.                {
  112.                   if (Board [y][x] == Board [y-2][x-2] || Board [y-1][x-2] || Board [y-2][x-1] || Board [y-1] [x-1])
  113.                   {
  114.                      status = false;
  115.                   }
  116.                }
  117.                else
  118.                {
  119.                status = true;
  120.                } 
  121.      return status;
  122. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2007
Posts: 1,953
Reputation: Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of Duoas has much to be proud of 
Solved Threads: 214
Featured Poster
Duoas's Avatar
Duoas Duoas is offline Offline
Posting Virtuoso

Re: Sudoku

 
0
  #5
May 19th, 2008
Line 22: Random_Number() is a function. It needs to be followed by ().

On line 45: you didn't declare x and y's types. Your function header must match its prototype above exactly.

Use some math:

C++ Syntax (Toggle Plain Text) 
  1. [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
  2.  0  1  2   3  4  5   6  7  8   (x)
  3. ----0---- ----1---- ----2----  (x%3)
  4.  
  5. check( x, y ):
  6.  
  7.   int val = board[y][x];
  8.  
  9.   // check row
  10.   for x0 = 0 to 8
  11.     if (x0 != x)
  12.       if (board[y][x0] >= 0)
  13.         if (board[y][x0] == val)
  14.           return false;
  15.  
  16.   // same kind of thing for column
  17.  
  18.   // check square:
  19.   int square_y = (x %3) *3;
  20.   int square_y = (y %3) *3;
  21.  
  22.   for y0 = 0 to 2
  23.   for x0 = 0 to 2
  24.     if (x0 != x) and (y0 != y)
  25.       if (board[ square_y +y0 ][ square_x +x0 ] == val)
  26.         return false;
  27.  
  28.   return true

Hope this helps.
Last edited by Duoas; May 19th, 2008 at 1:06 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 113
Reputation: zoner7 is an unknown quantity at this point 
Solved Threads: 4
zoner7 zoner7 is offline Offline
Junior Poster

Re: Sudoku

 
0
  #6
May 22nd, 2008
So on the bright side my code compiles! Unfortunately, it doesn't do anything! It simply outputs a 0. Can anyone take a look at this and see if there is some glaring error, or better yet, is there a good way for me to debug the program?

Here is an updated version of the code:

C++ Syntax (Toggle Plain Text) 
  1. #include <iostream>
  2. #include <ctime>
  3. #include <cstdlib>
  4. using namespace std;
  5.  
  6. /////////////  Define variables (arrays) ////////////////////
  7.  
  8. int Board [9][9];  // Creates the Sudoku board
  9.  
  10. /////////////  Define Function Prototypes ///////////////////
  11. int Random_Number(); //  Used to create random integers.  This will ensure that each sudoku board is unique.
  12. bool Verify(int, int); // Determines whether the values within a given cell are valid or not.
  13.  
  14. ///////////// Main ////////////////
  15. int main()
  16. {
  17.     bool BoardStatus [9][9]; // Sets all cell values to false, maening that they do not contain legitmate values.
  18.     for (int y = 0; y <= 8; y++)  // Tells program that all initial cells begin with illegitmate values, forcing them to begin the process or finding a correct value.
  19.     {
  20.         for (int x = 0; x <= 8; x++)
  21.         {
  22.             BoardStatus [y][x] = false;
  23.         }
  24.     }
  25.     for (int y = 0; y <= 8; y++)
  26.     {
  27.         for (int x = 0; x <= 8; x++)
  28.         {
  29.             while (BoardStatus [y][x] == false)
  30.             {
  31.                Board [y][x] = Random_Number();  // If the cell fufills the proper requirements, a random number is placed inside that cell.
  32.                BoardStatus[y][x] = Verify (y,x);
  33.             }
  34.         cout << Board [y][x];   //Prints the completed Sudoku board.
  35.         }
  36.     }
  37.     return 0;
  38. }
  39. int Random_Number()
  40. {
  41.       srand((unsigned)time(0)); 
  42.       int random_integer = (rand()%9)+1;
  43.       return random_integer;
  44. }
  45.  
  46. bool Verify(int y, int x)
  47. {
  48.      bool Status;
  49.      for (int n=0; n <= 8; n++)  // If the given cell equals a cell in its horizontal row or vertical column, a random integer will not be inserted.
  50.      {
  51.          if (Board [y][x] == Board [n][x] || Board [y][n])
  52.          {
  53.             Status = false;
  54.          }
  55.      }
  56.           if (x%3 == 0 && y%3 == 0) // the following lines test whether or not the value in the cell equals a value within that cell's respective 3x3 square.
  57.      {
  58.         if (Board [y][x] == Board [y+1][x+1] || Board [y+2][x+1] || Board [y+1][x+2] || Board [y+2][x+2]);
  59.         {
  60.            Status = false;
  61.         }
  62.      }
  63.      if (x%3 == 1 && y%3 == 0)
  64.      {
  65.         if (Board [y][x] == Board [y+1][x-1] || Board[y+2][x-1] || Board [y+1][x+1] || Board [y+2][x+1])
  66.         {
  67.            Status = false;
  68.         }
  69.      }
  70.      if (x%3 == 2 && y%3 == 0)
  71.      {
  72.         if (Board [y][x] == Board [y+1][x-1] || Board [y+2][x-1] || Board [y+1][x-2] || Board [y+2] [x-2])
  73.         {
  74.            Status = false;
  75.         }
  76.      }
  77.      if (x%3 == 0 && y%3 == 1)
  78.      {
  79.         if (Board [y][x] == Board [y-1][x+1] || Board [y-1][x+2] || Board [y+1][x+1] || Board [y+1][x+2]);
  80.         {
  81.            Status = false;
  82.         }
  83.      }
  84.      if (x%3 == 1 && y%3 == 1)
  85.      {
  86.         if (Board [y][x] == Board [y-1][x-1] || Board[y+1][x-1] || Board [y-1][x+1] || Board [y+1][x+1])
  87.         {
  88.            Status = false;
  89.         }
  90.      }
  91.      if (x%3 == 2 && y%3 == 1)
  92.      {
  93.         if (Board [y][x] == Board [y-1][x-2] || Board [y-1][x-1] || Board [y+1][x-2] || Board [y+2] [x-1])
  94.         {
  95.            Status = false;
  96.         }
  97.      }
  98.      if (x%3 == 0 && y%3 == 2)
  99.      {
  100.         if (Board [y][x] == Board [y-1][x+1] || Board [y-2][x+1] || Board [y-1][x+2] || Board [y-2][x+2]);
  101.         {
  102.            Status = false;
  103.         }
  104.      }
  105.      if (x%3 == 1 && y%3 == 2)
  106.      {
  107.         if (Board [y][x] == Board [y-1][x-1] || Board[y-2][x-1] || Board [y-1][x+1] || Board [y-2][x+1])
  108.         {
  109.            Status = false;
  110.         }
  111.      }
  112.      if (x%3 == 2 && y%3 == 2)
  113.      {
  114.         if (Board [y][x] == Board [y-2][x-2] || Board [y-1][x-2] || Board [y-2][x-1] || Board [y-1] [x-1])
  115.         {
  116.            Status = false;
  117.         }
  118.      }
  119.      else
  120.      {
  121.          Status = true;
  122.      } 
  123.      return Status;
  124. }
Last edited by zoner7; May 22nd, 2008 at 4:35 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 113
Reputation: zoner7 is an unknown quantity at this point 
Solved Threads: 4
zoner7 zoner7 is offline Offline
Junior Poster

Re: Sudoku

 
0
  #7
May 22nd, 2008
I found one glaring error! Now at least the program outputs a single random number instead of just 0. I changed the = sign in the while loop on line 30 to ==. The code had been updated to reflect this change.

Edit: Found another glaring error. After moving the return 0 outside the for loop, I receive a list of identical numbers before the program stops functioning. It's starting to work Just need that list to become random.

EDIT 2: I realized that all of my if statements were using single & for comparisons instead of doubled. Changes have been made.

EDIT 3: Made the code a little my eliminating more comprehensive by eliminating a global variable.
Last edited by zoner7; May 22nd, 2008 at 4:36 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2006
Posts: 2,989
Reputation: niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute niek_e has a reputation beyond repute 
Solved Threads: 308
Moderator
Featured Poster
niek_e's Avatar
niek_e niek_e is offline Offline
Cenosillicaphobiac

Re: Sudoku

 
0
  #8
May 22nd, 2008
Every time you call the Random_Number() function, you're re-seeding rand(): srand((unsigned)time(0)); .

You should only seed once per program. So move that line to the first line in main() and remove it from the function:
cpp Syntax (Toggle Plain Text) 
  1. int Random_Number()
  2. {
  3.   int random_integer = (rand()%9)+1;
  4.   return random_integer;
  5. }

I suspect that this should solve the problem
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 113
Reputation: zoner7 is an unknown quantity at this point 
Solved Threads: 4
zoner7 zoner7 is offline Offline
Junior Poster

Re: Sudoku

 
0
  #9
May 22nd, 2008
Thank you for the help. I honestly didn't exactly know what that function did. I sort of snagged the code from somewhere else on the site. I simply knew that the function needed to be included when using a random number generator.

yes! The code works... I think. I am getting a list of random numbers; however, there sure aren't 81 of them. I think the command prompt will only display so many. Do I need to split them up onto different lines or what?
Last edited by zoner7; May 22nd, 2008 at 4:39 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 113
Reputation: zoner7 is an unknown quantity at this point 
Solved Threads: 4
zoner7 zoner7 is offline Offline
Junior Poster

Re: Sudoku

 
0
  #10
May 22nd, 2008
Looks like its getting hung up on the 21st number every time... Is it likely that there is a problem in the logic, or is this about one of those little intricacies of C++ that I'm not expected to understand but that haunts my programs anyways? I'll go over the logic in detail tomorrow, but if this is just some weird C++ thing, I would love any help. Thank you all so much so far.
Reply With Quote Quick reply to this message  
Reply
1 2

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum


Views: 1380 | Replies: 17
Thread Tools Search this Thread



Tag cloud for C++
6 add api array arrays beginner binary c++ c/c++ calculator char class classes code compile compiler console conversion convert count data delete desktop directshow dll dynamic encryption error file forms fstream function functions game givemetehcodez google graph homeworkhelper iamthwee ifstream input int integer java lazy lib linkedlist linker linux loop looping loops map math matrix memory microsoft newbie news number output parameter pointer problem program programming project proxy python random read recursion recursive reference return sort stream string strings struct studio system template templates test text tree unix url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC