Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Brute force grid/puzzle generator

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
eswrite

Joined: 02 Sep 2005
Posts: 4
:

Items
PostPosted: Fri Sep 02, 2005 5:06 pm    Post subject: Brute force grid/puzzle generator Reply with quote
I am fairly new to sudoku puzzles and thought it would be cool to write my own puzzle generator. So far, I have code that generates a 9x9 grid that follows the row, column and sub-grid requirement to include all numbers between 1-9. I call it a brute force generator, because I basically start assigning numbers at random, on a row by row basis, using only those numbers that conform to sudoku rules. Sometimes I have to "rewind" a row or two (my tests show no more than 3 row rewinds) when things get stuck, but still program performance is pretty good. I will include the code below (sorry, somewhat long). My next step is to generate the puzzle by hiding numbers, but I have no idea how to do this so that:
a) I have a solvable puzzle.
b) I can choose which number to remove for various levels of difficulty.

C++ code (updated), compilable with Borland C++ 5.5
Code:

//=============================================================================
// Brute force Sudoku generator. Generates pseudo-random numbers on a row-by-row
// basis, checking that number placement conforms with Sudoku row, column and
// sub-grid rules.
//
// Copyright(c) Eduardo Suastegui, 2005
//=============================================================================

#include<iostream>
#include<fstream>
#include <stdlib.h>
#include <math.h>
#include <conio.h>

#ifndef _RWSTD_NO_NAMESPACE
  using namespace std;
#endif

//============================
// Generate a random value between 1 and max_value
int getRandValue(int max_value)
{
  int rnd_value;
 
  rnd_value = int((double(std::rand()) / RAND_MAX) * max_value + 1);
 
//  printf("%d ", rnd_value);
  return rnd_value; 
}

//============================
// Get the grid value at the specified location
int getGridValue(int row, int col, int* grid)
{
  return grid[row * 9 + col];
}

//============================
// Check whether a value already exists along a colum
bool isInCol(int row, int col, int value, int* grid)
{
  bool inCol = false;
 
  for (int r=0; r<row & !inCol; r++)
    inCol = (getGridValue(r, col, grid) == value) ? true : false;
   
  for (int r=row+1; r<9 & !inCol; r++)
    inCol = (getGridValue(r, col, grid) == value) ? true : false;
     
  return inCol;
}

//============================
// Check whether a value already exists along a row
bool isInRow(int row, int col, int value, int* grid)
{
  bool inRow = false;
 
  for (int c=0; c<col & !inRow; c++)
    inRow = (getGridValue(row, c, grid) == value) ? true : false;
   
  for (int c=col+1; c<9 & !inRow; c++)
    inRow = (getGridValue(row, c, grid) == value) ? true : false;
   
  return inRow;
}

//============================
// Check whether a value already exists in a sub-grid
bool isInSub(int row, int col, int value, int* grid)
{
#ifndef _RWSTD_NO_NAMESPACE
  using namespace std;
#endif
 
  bool inSub = false;
  int srow, scol;
 
  // Determine grid row,column starting position
  srow = (row / 3) * 3;
  scol = (col / 3) * 3;
 
  //cout << "(" << srow << "," << scol << ")";
 
  for (int r=srow; r<=srow+2 && !inSub; r++)
    for (int c=scol; c<=scol+2 && !inSub; c++)
      inSub = (getGridValue(r, c, grid) == value && r != row && c != col) ? true : false;
     
  return inSub;
}

//============================
// Set a random value at the specified grid location
bool setGridValue(int row, int col, int* grid)
{
  bool done = false;
  int vbag[9] = {1,2,3,4,5,6,7,8,9};  // bag of random values
  int len = 9;
  int pick;
  int value;
 
  while (!done)
  {
    pick = len > 0 ? random(len) : 0;
    value = vbag[pick];
   
    done = (!isInRow(row, col, value, grid) &&
            !isInCol(row, col, value, grid) &&
            !isInSub(row, col, value, grid)) || len == 0;
           
    if (!done)
    {
      if (len == 0)
        break;       
      // Take duplicate out of bag by removing it from the array:
      for (int i = pick; i < len-1; i++)
        vbag[i] = vbag[i+1];  // shift left
      --len;                  // reduce bag size
    }
  }

  grid[row * 9 + col] = value;
  //cout <<  len << "@" << pick << "=" << value << " ";
  return done;
}

//============================
// Print the Grid, using the Simple Sudoku (ss) format:
// Example:
// *-----------*
// |.6.|1.4|.5.|
// |..8|3.5|6..|
// |2..|...|..1|
// |---+---+---|
// |8..|4.7|..6|
// |..6|...|3..|
// |7..|9.1|..4|
// |---+---+---|
// |5..|...|..2|
// |..7|2.6|9..|
// |.4.|5.8|.7.|
// *-----------*

void printGrid(ostream& out, int* grid)
{
  int row, col;
  int value;
 
  out << " *-----------*" << endl;
  for (row = 0; row < 9; row++)
  {
    out << " ";
    for (col = 0; col < 9; col++)
    {
      if ((col % 3) == 0)
        out << "|";
      value = getGridValue(row, col, grid);
      if (value == 0)
        out << ".";
      else
        out << value;
    }
    out << "|" << endl;
    if (row == 2 || row == 5)
      out << " |---+---+---|" << endl;
  } 
  out << " *-----------*" << endl;
}

//============================
// Check a row
bool checkRow(int row, int* grid)
{
  bool rowOk = true;
  int value;
 
  for (int c = 8; c >= 0 && rowOk; c--)
  {
    value = getGridValue(row, c, grid);
    rowOk = !isInRow(row, c, value, grid) && !isInCol(row, c, value, grid) && !isInSub(row, c, value, grid); 
  }
 
  return rowOk;
}

// Clear the rows in the specified row range
void clearRows(int row1, int row2, int* grid)
{
  int s_row = row1 > 0 ? row1 : 0;
  int e_row = row2 < 9 ? row2 : 8;
 
  for (int row = s_row; row <= e_row; row++)
    for (int col = 0; col < 9; col++)
      grid[row * 9 + col] = 0; 
}

//============================
// Check the grid
bool checkGrid(int *grid)
{
  int row, col;
  int value;
  bool gridOk = true;
 
  cout << "Grid check..." << endl;
  cout << "   S = sub-grid violation" << endl;
  cout << "   R = Row violation" << endl;
  cout << "   C = Column violation" << endl;
  cout << "+-+-+-+-+-+-+-+-+-+" << endl;
  for (row = 0; row < 9; row++)
  {
    for (col = 0; col < 9; col++)
    {
      cout << "|";
      value = getGridValue(row, col, grid);
      if (isInSub(row, col, value, grid))
      {
        cout << "S";
        gridOk = false;
      }
      else if (isInRow(row, col, value, grid))
      {
        cout << "R";
        gridOk = false;
      }
      else if (isInCol(row, col, value, grid))
      {
        cout << "C";
        gridOk = false;
      }
      else
        cout << value;
    }
    cout << "|" << endl;
    cout << "+-+-+-+-+-+-+-+-+-+" << endl;
  } 
 
  return gridOk;
}

//============================
// Make a puzzle from the full grid by leaving num_squares revealed
// and hiding everything else. Revealed squares are chosen at random
int* makePuzzle(int* grid, int num_squares)
{
  int row, col, value, pick;
  int* gpuz = (int *) malloc(9*9 * sizeof(int));
  int pbag[81];
  memset(gpuz, 0x00, 9*9 * sizeof(int));
 
  for (int n = 0; n < 81; ++n)
    pbag[n] = n;
 
  for (int n = 0; n < num_squares; ++n)
  {
    pick = getRandValue(81-n) - 1; 
    row = pbag[pick] / 9;
    col = pbag[pick] % 9;
       
    //cout << pbag[pick] << "=" << row << "," << col << endl;
    gpuz[row * 9 + col] = getGridValue(row, col, grid);

    for (int i = pick; i < 81-n-1; ++i)
      pbag[i] = pbag[i+1];  // shift left
  } 
 
  cout << "Puzzle generated" << endl;
  printGrid(cout, gpuz);
 
  return gpuz;
}

void main(int argc, char **argv)
{
  int* grid;
  int  col, row;
  int  drow = 1;
  int  rowgen = 0;
  char cval[16];
  string paramStrIn;
  string oFileStr = "mksudoku.ss";
  int  num_squares = 30;
 
 
  // Read application parameters:
  for (int a = 1; a < argc; ++a)
  {
    paramStrIn = argv[a];   
    if (paramStrIn[0] == '-' && paramStrIn.length() > 2)
    {
      switch (paramStrIn[1])
      {
        case 'f':
          oFileStr = paramStrIn.substr(2, paramStrIn.length()-2);   
          break;
        case 'n':
          num_squares = atoi(paramStrIn.substr(2, paramStrIn.length()-2).c_str());
          break;
        default:
          cout << "Invalid parameter: " << paramStrIn.substr(0,2) << endl;
          cout << "  Valid syntax: mksudoku -f[file_name] -n[num_squares]" << endl;
      }
    }
  }
 
 
  // Allocate grid:
  grid = (int *) malloc(9*9 * sizeof(int));
  memset(grid, 0x00, 9*9 * sizeof(int));
 
  // Initialize randomizer:
  std::srand(static_cast<unsigned>(std::time(0)));
 
  // Fill in grid:
  for (row = 0; row < 9; row++)
  {
    for (col = 0; col < 9; col++)
    {
      setGridValue(row, col, grid);
    }

    if (row > 0 && !checkRow(row, grid))
    {
      if (rowgen > 100)
      {
        // Unwind drow rows to re-generate random grid entries:
        cout << row << "X";
        cout << endl;
        printGrid(cout, grid);
        clearRows(row-drow, row, grid);
        ++drow;
        row = row - drow >= -1 ? row - drow : -1;
        rowgen = 0;
      }
      else
      {
        ++rowgen;
        cout << row << "G";
        --row;
      }
    }
    else
    {
      rowgen = 0;
      cout << row << ".";
    }
    cout << " ";
   
  }
  cout << endl;
     
     
  // Output the grid and check it:
  printGrid(cout, grid);
 
  if (!checkGrid(grid))
    cout << "Grid is faulty. Please re-generate.\n";
  else
  {
    int* gpuz = makePuzzle(grid, num_squares);
   
    // Output puzzle and solution to file:
    fstream out(oFileStr.c_str(), ios_base::out );
    printGrid(out, gpuz);
   
    cout << "Puzzle written to: " << oFileStr << endl;
   
    free(gpuz);
  }
 
  // Free grid array:
  free(grid); 
     
  return;
}

_________________
Test Everything; Hold On to the Good
Back to top
View user's profile Send private message
eswrite

Joined: 02 Sep 2005
Posts: 4
:

Items
PostPosted: Fri Sep 02, 2005 8:00 pm    Post subject: Reply with quote
Okay, I've gotten a little farther now, with the updated code shown above. Now, the code generates a puzzle, with the "revealed" squares chosen purely at random and written to a file in a format that SimpleSudoku (see www.angusj.com/sudoku) can accept. When I load the output file into SimpleSudoku, for 30-40 revealed squares, SimpleSudoku tells me the puzzle is invalid because it has multiple solutions. This probably has to do with the squares my program chose to reveal at random, or perhaps with the original sudoku grid (solution), I can't tell. Here's a sample run with 30 revealed squares, for which SimpleSudoku tells me there are 264(!) solutions. Anyone care to give this newbie a little insight?

Code:
C:\Downloads\sudoku>mksudoku
0. 1G 1G 1G 1. 2. 3. 4. 5G 5G 5G 5G 5G 5G 5G 5G 5G 5G 5G 5G 5G 5G 5G 5G 5G 5G 5G
 5G 5G 5. 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6
G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6G 6. 7G 7G 7G 7G 7G 7G 7G 7G 7G
7. 8.
 *-----------*
 |475|963|218|
 |861|724|539|
 |932|581|674|
 |---+---+---|
 |786|495|123|
 |329|618|457|
 |514|237|896|
 |---+---+---|
 |243|176|985|
 |698|352|741|
 |157|849|362|
 *-----------*
Grid check...
   S = sub-grid violation
   R = Row violation
   C = Column violation
+-+-+-+-+-+-+-+-+-+
|4|7|5|9|6|3|2|1|8|
+-+-+-+-+-+-+-+-+-+
|8|6|1|7|2|4|5|3|9|
+-+-+-+-+-+-+-+-+-+
|9|3|2|5|8|1|6|7|4|
+-+-+-+-+-+-+-+-+-+
|7|8|6|4|9|5|1|2|3|
+-+-+-+-+-+-+-+-+-+
|3|2|9|6|1|8|4|5|7|
+-+-+-+-+-+-+-+-+-+
|5|1|4|2|3|7|8|9|6|
+-+-+-+-+-+-+-+-+-+
|2|4|3|1|7|6|9|8|5|
+-+-+-+-+-+-+-+-+-+
|6|9|8|3|5|2|7|4|1|
+-+-+-+-+-+-+-+-+-+
|1|5|7|8|4|9|3|6|2|
+-+-+-+-+-+-+-+-+-+
Puzzle generated
 *-----------*
 |47.|...|...|
 |.6.|..4|.3.|
 |..2|..1|674|
 |---+---+---|
 |786|495|...|
 |.2.|..8|...|
 |5.4|2..|8..|
 |---+---+---|
 |243|.76|..5|
 |...|...|...|
 |..7|...|.6.|
 *-----------*
Puzzle written to: mksudoku.ss

_________________
Test Everything; Hold On to the Good
Back to top
View user's profile Send private message
eswrite

Joined: 02 Sep 2005
Posts: 4
:

Items
PostPosted: Wed Sep 07, 2005 3:55 pm    Post subject: Reply with quote
From what I have been able to learn here and elsewhere (in spite of zero answers to my post), is that the program can't just hide squares at random. It needs a solver to guarantee a unique solution every time another square is removed. Don't know whether I'll try this. For now, I think I'll just use Simple Sudoku--what a great little program--although I'm not sure it generates puzzles from a randomly selected solution; rather, it seems to pick puzzles from a library of solutions?
_________________
Test Everything; Hold On to the Good
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Wed Sep 07, 2005 11:30 pm    Post subject: Reply with quote
eswrite wrote:
From what I have been able to learn here and elsewhere (in spite of zero answers to my post), is that the program can't just hide squares at random.

Correct. You need to test that the resulting puzzle is valid.

eswrite wrote:
It needs a solver to guarantee a unique solution every time another square is removed.

That's certainly one very good way to do it Very Happy.

eswrite wrote:
For now, I think I'll just use Simple Sudoku--what a great little program--

Thanks Embarassed

eswrite wrote:
although I'm not sure it generates puzzles from a randomly selected solution; rather, it seems to pick puzzles from a library of solutions?

Simple Sudoku definitely does generate a random puzzle every time.
Back to top
View user's profile Send private message Visit poster's website
mystman23

Joined: 28 Aug 2005
Posts: 5
:

Items
PostPosted: Sat Sep 10, 2005 2:37 pm    Post subject: Not working Reply with quote
Does it matter if you use Dev C++ instead of Borland because it is not working. I tryed all the code from you first post and it says there is an error at line 104. It says "'random' undeclared (first use in function)". Do you know what is wrong?
Back to top
View user's profile Send private message
eswrite

Joined: 02 Sep 2005
Posts: 4
:

Items
PostPosted: Wed Sep 21, 2005 7:43 pm    Post subject: Reply with quote
mystman23: you have probably figured it out by now, but just in case, different libraries include the random (or rand) function in different include files. Identify which include file contains it in Dev C++, include it, and you should be good to go. Alternatively, you can substitute the call to random with a call to getRandValue(9)-1.
_________________
Test Everything; Hold On to the Good
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron