I haven't fully verified the output of this yet, nor have I removed all my debug couts (i have them turned off, though), but this appears to be delivering good puzzles...

Unfortunately the formatting is a bit mashed, but it should still be readable


Code:
/*******************
/A Rewritten Sudoku generator
/Based off of sudoku by Harq
/
/Author: Kllrnohj
/Version 1.0
/Released under the GNU GPL
/*******************/

//Includes - Prefer C++ versions
#include <iostream>
#include <cstdlib>
#include <ctime>

//Defines
#define surand() ((rand() % 9) + 1)
#define T_MAX_TRIES 50
#define DEBUG false
#define DEBUG_2 false

//Functions
bool check(int x, int y, int grid[9][9]);
void fill(int grid[9][9]);
bool verify(int grid[9][9]);
void fill_x(int x, int grid[9][9]);
void disp(int grid[9][9]);

int main(int argc, char *argv[]) {
   using namespace std;
   
   int reps, y_reps, total_retries = 0;
   
   cout << "Generating puzzle...";
   
   //Initialize the grid array
   //Could also use a char array to reduce memory usage
   int grid[9][9];
   
   //Initialize the random number generator
   srand(time(0));
   
   do {
      //Fill grid with 0s
      fill(grid);
      for (int x = 0; x < 9; x++) {
         y_reps = 0;
         for (int y = 0; y < 9; y++) {
            reps = 0;
            do {
               grid[x][y] = surand();
               reps++;
            } while ((!check(x, y, grid)) and (reps < 50));      
            if (reps == 50) {
               //Failed 25 times in a row
               //Restart the previous column
               if (DEBUG_2) {
                  disp(grid);
               }
               y = -1;
               fill_x(x, grid);
               y_reps++;
               if (y_reps == 100) {
                  x--;
                  y_reps = 0;
                  fill_x(x, grid);
                  total_retries++;
               }
               if (total_retries == T_MAX_TRIES) {
                  cout << "ERROR!\n"
                     << "Failed to create "
                     << "puzzle. Reached T_MAX_"
                     << "TRIES limit.\n";
                  disp(grid);
                  exit(1);
               }
            }
         }
         if (DEBUG_2) {
            disp(grid);
         }
      }
   } while (!verify(grid)); //This is redundant and could be removed
             //Left in for demonstrative purposes
   
   cout << "Success!\n";
   
   //Display the completed grid
   //Has fancier output than disp()
   for (int x = 0; x < 9; x++) {
      cout << "\n\t";
      for (int y = 0; y < 9; y++) {
         cout << grid[x][y] << " ";
         if ((y == 2) or (y == 5)) {
            cout << "| ";
         }
      }
      if ((x == 2) or (x == 5)) {
         cout << "\n\t---------------------";
      }
   }
   cout << "\n\n";
   
   return 0;
}

//Function definitions
void disp(int grid[9][9]) {
   using namespace std;
   for (int d_x = 0; d_x < 9; d_x++) {
      cout << "\n\t";
      for (int d_y = 0; d_y < 9; d_y++) {
         cout << grid[d_x][d_y] << " ";
      }
   }
   cout << endl;
}

void fill_x(int x, int grid[9][9]) {
   for (int i = 0; i < 9; i++) {
      grid[x][i] = 0;
   }
}

bool verify(int grid[9][9]) {
   for (int x = 0; x < 9; x++) {
      for (int y = 0; y < 9; y++) {
         if (!check(x, y, grid)) {
            //return false;
         }
      }
   }
   return true;
}

void fill(int grid[9][9]) {
   for (int x = 0; x < 9; x++) {
      for (int y = 0; y < 9; y++) {
         grid[x][y] = 0;
      }
   }
}

bool check(int x, int y, int grid[9][9]) {
   int s_x, s_y;
   
   if (DEBUG) {
      std::cout << "Check( " << x << ", " << y << ", "
            << grid[x][y] << ")\n";
   }
   
   //Horiz check
   for (int i = 0; i < 9; i++) {
      if (DEBUG) {
         std::cout << "   " << grid[i][y]
               << " == " << grid[x][y] << std::endl;
      }
      
      if ((grid[i][y] == grid[x][y]) and (i != x)) {
         return false;
      }
   }
   
   if (DEBUG) {
      std::cout << std::endl;
   }
   
   //Vert check
   for (int i = 0; i < 9; i++) {
      if (DEBUG) {
         std::cout << "   " << grid[x][i]
               << " == " << grid[x][y] << std::endl;
      }
      
      if ((grid[x][i] == grid[x][y]) and (i != y)) {
         return false;
      }
   }
   
   if (DEBUG) {
      std::cout << std::endl;
   }
   
   //Square check
   //Set square X offset
   if ((x >= 0) and (x < 3)) {
      s_x = 0;
   } else if ((x >= 3) and (x < 6)) {
      s_x = 3;
   } else {
      s_x = 6;
   }
   
   //Set square Y offset
   if ((y >= 0) and (y < 3)) {
      s_y = 0;
   } else if ((y >= 3) and (y < 6)) {
      s_y = 3;
   } else {
      s_y = 6;
   }
   
   //Check the square
   for (int i_x = 0; i_x < 3; i_x++) {
      for (int i_y = 0; i_y < 3; i_y++) {
         if (DEBUG) {
            std::cout << "   " << grid[i_x + s_x][i_y + s_y]
                  << " == " << grid[x][y] << std::endl;
         }
         
         if ((grid[i_x + s_x][i_y + s_y] == grid[x][y]) and
                    (i_x + s_x != x) and (i_y + s_y != y)) {
            return false;
                    }
      }
   }
   
   return true;
}


I also need to go over it and clean it up a bit, removing unneeded variables and such, but I'll do that after the output is verified

EDIT:
Quote:

couldn't this:

Code:
  //Square check
   //Set square X offset
   if ((x >= 0) and (x < 3)) {
      s_x = 0;
   } else if ((x >= 3) and (x < 6)) {
      s_x = 3;
   } else {
      s_x = 6;
   }
   
   //Set square Y offset
   if ((y >= 0) and (y < 3)) {
      s_y = 0;
   } else if ((y >= 3) and (y < 6)) {
      s_y = 3;
   } else {
      s_y = 6;
   }


Be replaced by 2 switch - case statement (or can you not do multiple conditions/checks other than ==?) ?

I have gone through and taken out all global variables.

Oh yeah, do you mean 4 arguments? because you need the random number too


A switch statement COULD be used, but it would be a bit longer, as you would have to list every case such as


Code:
case 0:
case 1:
case 2:
    s_x = 0;
    break;


I think the if-else statements are cleaner

The random number is set to grid[x][y] before check() is called, and therefore doesn't need to be passed to check(). This allows check() to be more generic function that can be used later on down the line.

EDIT2: Fixed a slight bug in the program that would have been an issue should the main do-while loop ever repeat, which shouldn't be able to happen anyway
Wow, thats really good code, I tested it and it is very fast and has a pretty nice output!

Why do you use argc and argv (unless you plan on adding an option later to write to a txt file)? The output is also accurate.
Harq wrote:
Why do you use argc and argv (unless you plan on adding an option later to write to a txt file)? The output is also accurate.


two reasons:

1) habit Wink

2) i was initally going to have a --debug switch, but then i decided to just use a #DEFINE instead

However, I will now use it to make the file output option

As for the speed, you will quickly learn that even dull, unispired C/C++ code is blazingly fast compared to say, Python, Java, or TI-Basic Very Happy

EDIT: Updated the program with optional file output. Just pass a file as an argument and it will log it. I also cleaned it up a bit, removing the remaining debugging code.

Rather than repasting it here, and watching while phpBB destroys the formatting, I'll just post a link to the source file, which preserves the formatting

http://www.kllrnohj.com/cemetech/misc/sudoku2.cpp
*bump*

Harq, did you ever solve your infinite loop problem with yours?
No, i don't have any idea either, i tried going through step by step with watches on the variables, but id did not work...
Did you ever remove the global variables? Keeping everything scope-limited helps prevent hard-to-debug problems such as the one you are having.

It only took me ~30 minutes to fully debug mine once I had it all coded, and because to everything is self-contained, it was easy to find and plug the holes
Yes, i took out the global variables and it still does not work...
Post your updated code so I can take a look (unless, of course, you don't care)
I just went over the code again and this time when i tried to compile it, it gave me a bunch of "too many arguments to function" and its making me mad. But oh well, atleast I ironed all of the commands i used in the program into my mind Smile , that was one of my purposes, to reinforce all that i had learned.
Thats an easy one to fix. It sounds like you changed a function and you are now passing it too many args. Just follow the line numbers and fix em up (or post the non-compiling code here, whatever)
I will fix that once the darn wasp leaves my upstairs room, the code is on that computer.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 2 of 2
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement