Sudoku

[zoner7]

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.

[Duoas]

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.

[zoner7]

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?

[zoner7]

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.

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

int x, y;
int Random_Number();
bool Verify(int,int);

int main()
{
      bool BoardStatus [9][9];
      
      int Board [9][9];  // Creates the Sudoku board
      
      for (int y = 0; y < 8; y++)
      {
         for (int x = 0; x < 8; x++)
         {
            if (BoardStatus [y][x] = false)
            {
               Board [y][x] = Random_Number;  // If the cell fufills the proper requirements, a random number is placed inside that cell.
               Verify (y,x);
            }  
         }      
      }
      
      for (int y = 0; y < 8; y++) //Prints the completed Sudoku board.
      {
         for (int x = 0; x < 8; x++)
         {
             cout << Board [x][y];
         }
      }  
      return 0;
}

int Random_Number() //  Used to create random integers.  This will ensure that each sudoku board is unique.
{
      srand((unsigned)time(0)); 
      int random_integer = (rand()%9)+1;
      return random_integer;
}

bool Verify(y,x)
{
               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.
               {
                   if (Board [y][x] == Board [n][x] || Board [y][n])
                   {
                      status == false;
                   }
               }
               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.
               {
                  if (Board [y][x] == Board [y+1][x+1] || Board [y+2][x+1] || Board [y+1][x+2] || Board [y+2][x+2]);
                  {
                     status = false;
                  }
               }
               if (x%3 == 1 & y%3 == 0)
               {
                  if (Board [y][x] == Board [y+1][x-1] || Board[y+2][x-1] || Board [y+1][x+1] || Board [y+2][x+1])
                  {
                     status = false;
                  }
               }
               if (x%3 == 2 & y%3 == 0)
               {
                  if (Board [y][x] == Board [y+1][x-1] || Board [y+2][x-1] || Board [y+1][x-2] || Board [y+2] [x-2])
                  {
                     status = false;
                  }
               }
               if (x%3 == 0 & y%3 == 1)
               {
                  if (Board [y][x] == Board [y-1][x+1] || Board [y-1][x+2] || Board [y+1][x+1] || Board [y+1][x+2]);
                  {
                     status = false;
                  }
               }
               if (x%3 == 1 & y%3 == 1)
               {
                  if (Board [y][x] == Board [y-1][x-1] || Board[y+1][x-1] || Board [y-1][x+1] || Board [y+1][x+1])
                  {
                     status = false;
                  }
               }
               if (x%3 == 2 & y%3 == 1)
               {
                  if (Board [y][x] == Board [y-1][x-2] || Board [y-1][x-1] || Board [y+1][x-2] || Board [y+2] [x-1])
                  {
                     status = false;
                  }
               }
               if (x%3 == 0 & y%3 == 2)
               {
                  if (Board [y][x] == Board [y-1][x+1] || Board [y-2][x+1] || Board [y-1][x+2] || Board [y-2][x+2]);
                  {
                     status = false;
                  }
               }
               if (x%3 == 1 & y%3 == 2)
               {
                  if (Board [y][x] == Board [y-1][x-1] || Board[y-2][x-1] || Board [y-1][x+1] || Board [y-2][x+1])
                  {
                     status = false;
                  }
               }
               if (x%3 == 2 & y%3 == 2)
               {
                  if (Board [y][x] == Board [y-2][x-2] || Board [y-1][x-2] || Board [y-2][x-1] || Board [y-1] [x-1])
                  {
                     status = false;
                  }
               }
               else
               {
               status = true;
               } 
     return status;
}

[Duoas]

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:

[ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
 0  1  2   3  4  5   6  7  8   (x)
----0---- ----1---- ----2----  (x%3)

check( x, y ):

  int val = board[y][x];

  // check row
  for x0 = 0 to 8
    if (x0 != x)
      if (board[y][x0] >= 0)
        if (board[y][x0] == val)
          return false;

  // same kind of thing for column

  // check square:
  int square_y = (x %3) *3;
  int square_y = (y %3) *3;

  for y0 = 0 to 2
  for x0 = 0 to 2
    if (x0 != x) and (y0 != y)
      if (board[ square_y +y0 ][ square_x +x0 ] == val)
        return false;

  return true

Hope this helps.

[zoner7]

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:

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

/////////////  Define variables (arrays) ////////////////////

int Board [9][9];  // Creates the Sudoku board

/////////////  Define Function Prototypes ///////////////////
int Random_Number(); //  Used to create random integers.  This will ensure that each sudoku board is unique.
bool Verify(int, int); // Determines whether the values within a given cell are valid or not.

///////////// Main ////////////////
int main()
{
    bool BoardStatus [9][9]; // Sets all cell values to false, maening that they do not contain legitmate values.
    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.
    {
        for (int x = 0; x <= 8; x++)
        {
            BoardStatus [y][x] = false;
        }
    }
    for (int y = 0; y <= 8; y++)
    {
        for (int x = 0; x <= 8; x++)
        {
            while (BoardStatus [y][x] == false)
            {
               Board [y][x] = Random_Number();  // If the cell fufills the proper requirements, a random number is placed inside that cell.
               BoardStatus[y][x] = Verify (y,x);
            }
        cout << Board [y][x];   //Prints the completed Sudoku board.
        }
    }
    return 0;
}
int Random_Number()
{
      srand((unsigned)time(0)); 
      int random_integer = (rand()%9)+1;
      return random_integer;
}

bool Verify(int y, int x)
{
     bool Status;
     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.
     {
         if (Board [y][x] == Board [n][x] || Board [y][n])
         {
            Status = false;
         }
     }
          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.
     {
        if (Board [y][x] == Board [y+1][x+1] || Board [y+2][x+1] || Board [y+1][x+2] || Board [y+2][x+2]);
        {
           Status = false;
        }
     }
     if (x%3 == 1 && y%3 == 0)
     {
        if (Board [y][x] == Board [y+1][x-1] || Board[y+2][x-1] || Board [y+1][x+1] || Board [y+2][x+1])
        {
           Status = false;
        }
     }
     if (x%3 == 2 && y%3 == 0)
     {
        if (Board [y][x] == Board [y+1][x-1] || Board [y+2][x-1] || Board [y+1][x-2] || Board [y+2] [x-2])
        {
           Status = false;
        }
     }
     if (x%3 == 0 && y%3 == 1)
     {
        if (Board [y][x] == Board [y-1][x+1] || Board [y-1][x+2] || Board [y+1][x+1] || Board [y+1][x+2]);
        {
           Status = false;
        }
     }
     if (x%3 == 1 && y%3 == 1)
     {
        if (Board [y][x] == Board [y-1][x-1] || Board[y+1][x-1] || Board [y-1][x+1] || Board [y+1][x+1])
        {
           Status = false;
        }
     }
     if (x%3 == 2 && y%3 == 1)
     {
        if (Board [y][x] == Board [y-1][x-2] || Board [y-1][x-1] || Board [y+1][x-2] || Board [y+2] [x-1])
        {
           Status = false;
        }
     }
     if (x%3 == 0 && y%3 == 2)
     {
        if (Board [y][x] == Board [y-1][x+1] || Board [y-2][x+1] || Board [y-1][x+2] || Board [y-2][x+2]);
        {
           Status = false;
        }
     }
     if (x%3 == 1 && y%3 == 2)
     {
        if (Board [y][x] == Board [y-1][x-1] || Board[y-2][x-1] || Board [y-1][x+1] || Board [y-2][x+1])
        {
           Status = false;
        }
     }
     if (x%3 == 2 && y%3 == 2)
     {
        if (Board [y][x] == Board [y-2][x-2] || Board [y-1][x-2] || Board [y-2][x-1] || Board [y-1] [x-1])
        {
           Status = false;
        }
     }
     else
     {
         Status = true;
     } 
     return Status;
}

[zoner7]

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.

[Nick Evan]

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:

int Random_Number()
{
  int random_integer = (rand()%9)+1;
  return random_integer;
}

I suspect that this should solve the problem

[zoner7]

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?

[zoner7]

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.

[Nick Evan]

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?

C++ should have no problem with this.

Without getting to deep in your logic (don't have time) I can tell you that these sort of lines: if (Board [y][x] == Board [y+1][x+1] || Board [y+2][x+1] || Board [y+1][x+2] || Board [y+2][x+2]); are wrong

First remove the semicolon at the end of line : .....[y+2][x+2]); <---that one

Then what you say here is in fact : if (Board [y][x] == Board [y+1][x+1] || Board [y+2][x+1] != 0 || Board [y+1][x+2] != 0 || Board [y+2][x+2] != 0) And I guess you meant something like: if (Board [y][x] == Board [y+1][x+1] || Board [y][x] == Board [y+2][x+1] || Board [y][x] == Board [y+1][x+2] || Board [y][x] == Board [y+2][x+2]) Go through your code again, there's a lot of these

[Duoas]

Wow, sleep a little...

You would have a much easier time of it, and much more robust code, if you were to scrap all those if statements and use the algorithms I suggested to you.

[zoner7]

heh... yeah algorithm... I realize that the code is strikingly inefficient. I'm just impressed with myself that I am even able to make this thing work, considering how little C++ experience I have had. I sort of want to make the program work and then try to make it more effective. Maybe if I can't make it work under the current circumstances I'll try to implement the aforementioned algorithm. I just don't even entirely understand it, let alone how to implement it. So as long as there is an inkling that the current strategy will work, I'll stick with it. Thank you both. I'm going to try to fix what I have now.

[zoner7]

hmm... could things be messing up when I am comparing the indices to each other because of default values. What are the indice values in each array set to by default?

[Duoas]

It isn't so much that the code itself is inefficient (aside from that it doesn't work);
It is the way you are trying to "do it the easy way" that is inefficient. What you think is easy will just send you in circles for days.

Do it right the first time (...............algorithm) and you'll get it right almost immediately.

[zoner7]

So I came back to this problem. Right now I'm trying to get each step of the solution to work. I'm currently working on simply making the Sudoku board check whether or not a given cell equals the cells in its respective column or row.

Here is my code.

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

/////////////  Define Global Variables (arrays) ////////////////////
int Board [9][9];  // Creates the Sudoku board

/////////////  Define Function Prototypes ///////////////////
int Random_Number(); //  Used to create random integers.  This will ensure that each Sudoku board is unique.
bool Verify(int row, int column); // Determines whether the values within a given cell are valid or not.

///////////// Main ////////////////
int main()
{
    srand((unsigned)time(0));
    bool BoardStatus [9][9];
    for (int row = 0; row <= 8; row++)
    {
        for (int column = 0; column <= 8; column++)
        {
            BoardStatus [row][column] = false;
            Board [row][column] = -1;    //  Sets Board values to an impossible value to ensure that false positive comparisons are not made between cells.
        }
    }
    for (int row = 0; row <= 8; row++) 
    {
        cout << endl;
        for (int column = 0; column <= 8; column++)
        {
            while (BoardStatus [row][column] == false)
            {
               if (Board [row][column] == -1)
               {
                  Board [row][column] = Random_Number();  // a random number is placed inside every cell before the validation process begins in order to randomize each puzzle.
               }
               BoardStatus [row][column] = Verify(row, column);
               if (BoardStatus [row][column] == false)
               {
                    ((Board [row][column]) + 1);
                    if (Board [row][column] == 9) // A value inside a cell cannot be greater than 9.
                    {
                         Board[row][column] = 0;
                    }
               }
            }
            cout << Board [row][column];   //Prints the completed Sudoku board.
        }
    }
    return 0;
}
int Random_Number()
{
      int random_integer = (rand()%9)+1;
      return random_integer;
}

bool Verify(int row, int column)
{
     for (int n=0; n <= 8; n++)  // If the given cell equals a cell in its horizontal row or vertical column, the cell's status is set to false.
     {
         if ( (Board [row][column] == Board [n][column]) || (Board [row][column] == Board [row][n]) )
             {
                 return false;
             }
         else
             {
             return true;
             }
     }   
}

I think I just figured out what my problem is.

[zoner7]

So I came back to this problem. Right now I'm trying to get each step of the solution to work. I'm currently working on simply making the Sudoku board check whether or not a given cell equals the cells in its respective column or row.

Here is my code.

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

/////////////  Define Global Variables (arrays) ////////////////////
int Board [9][9];  // Creates the Sudoku board

/////////////  Define Function Prototypes ///////////////////
int Random_Number(); //  Used to create random integers.  This will ensure that each Sudoku board is unique.
bool Verify(int row, int column); // Determines whether the values within a given cell are valid or not.

///////////// Main ////////////////
int main()
{
    srand((unsigned)time(0));
    bool BoardStatus [9][9];
    for (int row = 0; row <= 8; row++)
    {
        for (int column = 0; column <= 8; column++)
        {
            BoardStatus [row][column] = false;
            Board [row][column] = -1;    //  Sets Board values to an impossible value to ensure that false positive comparisons are not made between cells.
        }
    }
    for (int row = 0; row <= 8; row++) 
    {
        cout << endl;
        for (int column = 0; column <= 8; column++)
        {
            while (BoardStatus [row][column] == false)
            {
               if (Board [row][column] == -1)
               {
                  Board [row][column] = Random_Number();  // a random number is placed inside every cell before the validation process begins in order to randomize each puzzle.
               }
               BoardStatus [row][column] = Verify(row, column);
               if (BoardStatus [row][column] == false)
               {
                    ((Board [row][column]) + 1);
                    if (Board [row][column] == 9) // A value inside a cell cannot be greater than 9.
                    {
                         Board[row][column] = 0;
                    }
               }
            }
            cout << Board [row][column];   //Prints the completed Sudoku board.
        }
    }
    return 0;
}
int Random_Number()
{
      int random_integer = (rand()%9)+1;
      return random_integer;
}

bool Verify(int row, int column)
{
     for (int n=0; n <= 8; n++)  // If the given cell equals a cell in its horizontal row or vertical column, the cell's status is set to false.
     {
         if ( (Board [row][column] == Board [n][column]) || (Board [row][column] == Board [row][n]) )
             {
                 return false;
             }
         else
             {
             return true;
             }
     }   
}

I think I just figured out what my problem is. In line 62 I compare each line to itself. Of course the function will return false every time. This would explain why the program displays nothing. How do I create an exception or something along those lines in an if statement?

[Duoas]

You'll have to split the condition.

for (int n = 0; n < 8; n++)
  {
  if ((n != row) and (board[row][column] == board[n][column]))
    return false;
  if ((n != column) and (board[row][column] == board[row][n]))
    return false;
  }
return true;

Be sure to keep that last line out of the loop. You only want to return true once you have verified against all possibilities.

Hope this helps.