14 Replies - 18635 Views - Last Post: 29 December 2011 - 07:39 AM Rate Topic: -----

#1 ssharma286   User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 93
  • Joined: 04-December 10

Sudoku infinite Loop...

Posted 24 December 2011 - 01:10 AM

Okay I am making a sudoku game and the program gets caught in an infinite loop for me. I debugged it and it gets caught in the while(true) loop in the create box function. The weird thing is sometimes the createbox will make 1 boxes or sometimes even 8 boxes. Its unpredictable where it will get caught up in an infinite loop. I suspect it has something to do with the random number generator. Any ideas?

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


void clearBoard(char sudo[][9]){
  for(int i = 0; i < 9; i++)
    for(int j = 0; j < 9; j++)
      sudo[j][i] = ' ';  
}

char itoc(int a){
  return char(a + 48);
}              

void removePossib(char possib[], int size, char toRemove){
  for(int i = 0; i < size; i++){
    if(possib[i] == toRemove){
      for(int j = i; j < (size - 1); j++)
        possib[j] = possib[j+1];
      break;
    }
  }
}

void printBoard(char sudo[][9]){
  cout <<           "   1  2  3  4  5  6  7  8  9" << endl;
  string board =     " ╔═══╤═══╤═══╦═══╤═══╤═══╦";
  string under =      " ┼──┼──┼──┼──┼──┼──┼──┼──┼──┼";
  cout << board << endl;
  for(int i = 0; i < 9; i++){
    cout << i+1 << "x";
    for(int j = 0; j < 9; j++){
      cout << ' ' << sudo[i][j];
      
      if(j != 0 && ((j+1) % 3 == 0))
        cout << 'l';
      else cout << "│";
    }
    cout << endl;
    if(i != 0 && ((i+1) % 3 == 0))
      cout << board << endl;
    else cout << under << endl;
  }
}

bool rowCheck(char charx, char sudo[]){
  bool result = false;
  for(int i = 0; i < 9; i++)
    if(sudo[i] == charx)
      result = true;
  return result;
}

bool colCheck(char charx, char sudo[][9],int colNum){
  bool  result = false;
  for(int i = 0; i < 9; i++){
    if(sudo[i][colNum] == charx)
      result = true;
  }
  return result;
}

void createBox(char sudo[][9], int rowBoxN, int colBoxN){
  srand(time(NULL));
  char possib[9];
  int possibSize = 9;
  for(int i = 0; i < 9; i++)
    possib[i] = itoc(i+1);

  
  rowBoxN *= 3;
  colBoxN *= 3;
  for(int i = rowBoxN; i < (rowBoxN + 3); i++){
    for(int j = colBoxN; j < (colBoxN + 3); j++){
      while(true){
        char insert = possib[(rand() % possibSize)];
        if(!rowCheck(insert, sudo[i])){
          if(!colCheck(insert, sudo,j)){
            sudo[i][j] = insert;
              removePossib(possib, possibSize,insert);
              possibSize--;
            break;
          
          }
        }
      }
    }
  }
}

void createBoard(char sudo[][9]){
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      createBox(sudo, i, j);
      printBoard(sudo);
    }
      
  }

}

void clearSCR(){
  cout << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl << endl << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl  << endl << endl;
}

int main () {

  char sudo[9][9];
  clearBoard(sudo);
  createBoard(sudo);
  printBoard(sudo);
  return 0;
}




Is This A Good Question/Topic? 0
  • +

Replies To: Sudoku infinite Loop...

#2 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7507
  • View blog
  • Posts: 15,558
  • Joined: 16-October 07

Re: Sudoku infinite Loop...

Posted 24 December 2011 - 04:46 AM

You are... exceptionally optimistic. It's nice, but not very useful to you right now.

Just throwing random numbers down, there's a pretty good chance you'll get to a point where a position has no valid options left but still needs to be filled. That's your infinite loop.

You need to randomly choose from the valid values for a give position. You also need to be prepared to start over if you block yourself. It's just not as straight forward as you think.

Also, put that srand in main, you only want to call it once.
Was This Post Helpful? 1
  • +
  • -

#3 ssharma286   User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 93
  • Joined: 04-December 10

Re: Sudoku infinite Loop...

Posted 24 December 2011 - 11:23 AM

View Postbaavgai, on 24 December 2011 - 04:46 AM, said:

You are... exceptionally optimistic. It's nice, but not very useful to you right now.

Just throwing random numbers down, there's a pretty good chance you'll get to a point where a position has no valid options left but still needs to be filled. That's your infinite loop.

You need to randomly choose from the valid values for a give position. You also need to be prepared to start over if you block yourself. It's just not as straight forward as you think.

Also, put that srand in main, you only want to call it once.


Haha okay I was myself unsure whether randomly picking numbers would work. Guess I'll keep trying maybe change my algorithm a bit more drastically.
Was This Post Helpful? 0
  • +
  • -

#4 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7507
  • View blog
  • Posts: 15,558
  • Joined: 16-October 07

Re: Sudoku infinite Loop...

Posted 24 December 2011 - 01:59 PM

Actually, starting with one 3x3 square is an interesting approach. You could fill two diagonally opposed blocks without risk of collision. I believe you could also do the middle. You could use that as a starting spot.

Then add a random valid to every empty location until the board is filled or you find an empty that can't be filled. There might be a way to build that so you have minimal chance of locking yourself out.
Was This Post Helpful? 1
  • +
  • -

#5 ssharma286   User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 93
  • Joined: 04-December 10

Re: Sudoku infinite Loop...

Posted 25 December 2011 - 01:07 AM

Okay I changed my algorithm and now I made it so if it takes more than 15 times to find a valid number, the whole box gets recreated. With this I am able to create exactly 8 boxes each time but now it keeps trying to recreate the last box to which apparently no possible solution exists...weird. Any more ideas on how I could possibly improve my algorithm to make it actually work! I am going to try the adding boxes from middle right now see how that works out
Here is what it looks like:
PS: Sorry about the weird formatting I copied it and tried to fix it but failed ;[
   1  2  3  4  5  6  7  8  9
 ╔═══╤═══╤═══╦═══╦═══╤═
1x 2│ 6│ 7  l 9│ 4│ 1   l 5│ 8│ 3  l
 ┼──┼──┼──┼──┼──┼──┼
2x 5│ 4│ 1  l 2│ 8│ 3  l 6│ 9│ 7  l
 ┼──┼──┼──┼──┼──┼──┼
3x 3│ 8│ 9  l 5│ 6│ 7  l 4│ 1│ 2  l
 ╔═══╤═══╤═══╦═══╤═══
4x 9│ 7│ 5  l 8│ 1│ 2  l 3│ 4│ 6  l
 ┼──┼──┼──┼──┼──┼──┼
5x 4│ 3│ 8  l 6│ 7│ 9  l 2│ 5│ 1  l
 ┼──┼──┼──┼──┼──┼──┼
6x 6│ 1│ 2  l 3│ 5│ 4  l 8│ 7│ 9  l
 ╔═══╤═══╤═══╦═══╤═══
7x 7│ 9│ 6  l 4│ 3│ 8   l  │  │     l
 ┼──┼──┼──┼──┼──┼──
8x 1│ 2│ 3  l 7│ 9│ 5  l   │  │     l
 ┼──┼──┼──┼──┼──┼──
9x 8│ 5│ 4  l 1│ 2│ 6  l  │   │     l
 ╔═══╤═══╤═══╦═══╤═══


This post has been edited by ssharma286: 25 December 2011 - 01:10 AM

Was This Post Helpful? 0
  • +
  • -

#6 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7507
  • View blog
  • Posts: 15,558
  • Joined: 16-October 07

Re: Sudoku infinite Loop...

Posted 25 December 2011 - 04:09 AM

You do follow how the rules of sudoku work? Just mentally find the list of valid values for each of those squares.

Here's your board:
2 6 7 | 9 4 1 | 5 8 3
5 4 1 | 2 8 3 | 6 9 7
3 8 9 | 5 6 7 | 4 1 2
------+-------+------
9 7 5 | 8 1 2 | 3 4 6
4 3 8 | 6 7 9 | 2 5 1
6 1 2 | 3 5 4 | 8 7 9
------+-------+------
7 9 6 | 4 3 8 | ? ? ?
1 2 3 | 7 9 5 | X ? ?
8 5 4 | 1 2 6 | ? ? X



See the two X positions? There are no available values for those positions. You've used them all up. You will never find a valid combination.

You may continue to follow your box methodology if you like, but you have to know when to start over. You will hit walls. A lot.

Hmm... you have a row check and a col check. What if you also had a box check? Then you could validate any value on the board without looking at the 3x3 box. Then, if you returned available values for a position. You'd immediately know if you'd gotten to the point where you could go no farther.
Was This Post Helpful? 1
  • +
  • -

#7 ssharma286   User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 93
  • Joined: 04-December 10

Re: Sudoku infinite Loop...

Posted 25 December 2011 - 09:34 AM

View Postbaavgai, on 25 December 2011 - 04:09 AM, said:

You do follow how the rules of sudoku work? Just mentally find the list of valid values for each of those squares.

Here's your board:
2 6 7 | 9 4 1 | 5 8 3
5 4 1 | 2 8 3 | 6 9 7
3 8 9 | 5 6 7 | 4 1 2
------+-------+------
9 7 5 | 8 1 2 | 3 4 6
4 3 8 | 6 7 9 | 2 5 1
6 1 2 | 3 5 4 | 8 7 9
------+-------+------
7 9 6 | 4 3 8 | ? ? ?
1 2 3 | 7 9 5 | X ? ?
8 5 4 | 1 2 6 | ? ? X



See the two X positions? There are no available values for those positions. You've used them all up. You will never find a valid combination.

You may continue to follow your box methodology if you like, but you have to know when to start over. You will hit walls. A lot.

Hmm... you have a row check and a col check. What if you also had a box check? Then you could validate any value on the board without looking at the 3x3 box. Then, if you returned available values for a position. You'd immediately know if you'd gotten to the point where you could go no farther.

Yes I am going to try that approach and randomly generate random values..hopefully that may work out
Was This Post Helpful? 0
  • +
  • -

#8 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2034
  • View blog
  • Posts: 5,436
  • Joined: 27-December 05

Re: Sudoku infinite Loop...

Posted 25 December 2011 - 10:06 AM

There are 9! ways to arrange the 9 digits in a 3x3 grid. There are (9!)! ways to lay out the entire board of nine 3x3 grids. That's a pretty big number, bigger than 4 x 10^1800000.

Do you really want to attack this problem by generating and then testing random values?
Was This Post Helpful? 0
  • +
  • -

#9 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7507
  • View blog
  • Posts: 15,558
  • Joined: 16-October 07

Re: Sudoku infinite Loop...

Posted 25 December 2011 - 04:06 PM

View Postr.stiltskin, on 25 December 2011 - 01:06 PM, said:

Do you really want to attack this problem by generating and then testing random values?


Yes! I have a computer do to the work for me. It does it very fast. So... why not.

I was curious, so I tried three random methods. Just random. The random boxes of the OP. And the method I though of starting with boxes and testing. Tests show my three box idea is the suck. Let's have a look.

const int BOARD_ROWS = 9, BOARD_COLS = 9, AVAIL_VALUES_MAX = 9;
typedef CellValue Board[BOARD_ROWS][BOARD_COLS];

typedef CellValue AvailValues[AVAIL_VALUES_MAX];

void clear(Board B)/>;
bool isValid(Board b, int row, int col, CellValue value);
// returns AvailValues size
int loadAvailValues(Board b, int row, int col, AvailValues av);
bool fillRandom(Board b, int row, int col);
bool fillRandomBox(Board b, int row, int col);
bool attemptFillRandom(Board B)/>;
bool attemptFillRandomBoxOnly(Board B)/>;
int fillRandomAllRand(Board B)/>;
int fillRandomWithThreeBox(Board B)/>;
int fillRandomBoxOnly(Board B)/>;
void print(Board B)/>;


using namespace std;

int main() {
	srand(time(NULL));
	Board b;
	const int TESTS = 10, TYPES = 3;
	int totals[TYPES] = {0};
	
	cout << "All\tThree\tBox" << endl << "Rand\tBox\tOnly" << endl;
	for(int i=0; i<TESTS; i++) { 
		int tries[TYPES], tn=0;
		tries[tn++] = fillRandomAllRand(B)/>;
		tries[tn++] = fillRandomWithThreeBox(B)/>;
		tries[tn++] = fillRandomBoxOnly(B)/>;
		for(int j=0; j<TYPES; j++) {
			if (j!=0) { cout << '\t'; }
			cout << tries[j];
			totals[j] += tries[j];
		}
		cout << endl;
	}
	cout << "Avg" << endl;
	for(int j=0; j<TYPES; j++) {
		if (j!=0) { cout << '\t'; }
		cout << (totals[j]/(double)TESTS);
	}
	cout << endl;
	
	return 0;
}



All	Three	Box
Rand	Box	Only
235	8885	347
463	965	392
702	2324	339
961	286	172
68	2642	514
24	1506	170
854	7519	196
110	129	30
455	2995	276
373	897	194
Avg
424.5	2814.8	263



The OP's box method works best most of the time. I don't really want to give away too much.

But to get an idea...
bool fillRandomBox(Board b, int row, int col) {
	int rBox = (row/3)*3;
	int cBox = (col/3)*3;
	for (int r=rBox; r<rBox+3; r++) {
		for (int c=cBox; c<cBox+3; c++) {
			if (!fillRandom(b,r,c)) { return false; }
		}
	}
	return true;
}

bool attemptFillRandomBoxOnly(Board B)/> {
	clear(B)/>;
	for (int row=0; row<BOARD_ROWS; row += 3) {
		for (int col=0; col<BOARD_COLS; col += 3) {
			if (!fillRandomBox(b,row,col)) { return false; }
		}
	}
	return true;
}

int fillRandomBoxOnly(Board B)/> {
	int tries = 0;
	while(true) {
		if (attemptFillRandomBoxOnly(B)/>) { break; }
		tries++;
	}
	return tries;
}



Hope this helps.
Was This Post Helpful? 1
  • +
  • -

#10 ssharma286   User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 93
  • Joined: 04-December 10

Re: Sudoku infinite Loop...

Posted 28 December 2011 - 12:10 AM

Okay I re-did my code to randomly generate random INDIVIDUAL boxes but it is of no avail. Still stuck in an infinite loop...
#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;

char itoc(int a){
  return char(a + 48);
}              

class board{
public:
  char sudo[9][9];
  board(){clearBoard();}
  void clearBoard();
  void print();
  bool checkRow(char charx, int rowNum);
  bool checkCol(char charx,int colNum);
  bool checkBox(char charx, int boxNum);
  int boxNum(int rowNum, int colNum);
  void createBoard();
};

int board::boxNum(int rowNum, int colNum){
  int boxNum = 0;
  if(rowNum >= 3 && rowNum < 6)
    boxNum = 3;
  else if(rowNum >= 6 && rowNum < 9)
    boxNum = 6; 
  
  if(colNum >= 3 && colNum < 6)
    boxNum += 1;
  else if(colNum >= 6 && colNum < 9)
    boxNum += 2;  
  
  
  return boxNum;
}

bool board::checkRow(char charx, int rowNum){
  bool result = false;
  for(int i = 0; i < 9; i++)
    if(sudo[rowNum][i] == charx)
      result = true;
  return result;
}

bool board::checkCol(char charx,int colNum){
  bool  result = false;
  for(int i = 0; i < 9; i++){
    if(sudo[i][colNum] == charx)
      result = true;
  }
  return result;
}

bool board::checkBox(char charx, int boxNum){
  bool result = false;
  int startRow, startCol;
  if(boxNum  < 3)
    startRow = 0;
  else if(boxNum >= 3 && boxNum < 6)
    startRow = 3;
  else if(boxNum >= 6 && boxNum < 9)
    startRow = 6;
  
  
  for(int i = 0; i != boxNum+1; i++){
    if(i % 3 == 0 || i == 0) startCol= 0;
    else startCol += 3;
  }
  
  for(int i = startRow; i < (startRow + 3); i++){
    for(int j = startCol; j < (startCol + 3); j++){
      if(sudo[i][j] == charx)
        result = true;
    }
  }
  return result;
}

void board::clearBoard(){
  for(int i = 0; i < 9; i++)
    for(int j = 0; j < 9; j++)
      sudo[j][i] = ' ';  
}

void board::createBoard(){
  int boxesLeft = 81;
  while(boxesLeft !=  0){
    print();
    int methodTry = 0;
    boxesLeft = 81;
    clearBoard();
    while(boxesLeft != 0 && methodTry < 1000){
      int i = rand() % 9;
      int j = rand() % 9;
      if(sudo[i][j] == ' '){
        int numOfTries = 0;
        while(numOfTries < 25){
          methodTry++;
          numOfTries++;
          char insert = itoc((rand() % 9) +1);
          if(!checkBox(insert, boxNum(i, j))){
            if(!checkRow(insert, i)){
              if(!checkCol(insert, j)){
                sudo[i][j] = insert;
                boxesLeft--;
                break;
              }
            }
          }
          
        }
      }
    }
  }
}

void board::print(){
  cout <<           "   1  2  3  4  5  6  7  8  9" << endl;
  string board =     " ╔═══╤═══╤═══╦═══╤═══╤═══╦";
  string under =      " ┼──┼──┼──┼──┼──┼──┼──┼──┼──┼";
  cout << board << endl;
  for(int i = 0; i < 9; i++){
    cout << i+1 << "x";
    for(int j = 0; j < 9; j++){
      cout << ' ' << sudo[i][j];
      
      if(j != 0 && ((j+1) % 3 == 0))
        cout << 'l';
      else cout << "│";
    }
    cout << endl;
    if(i != 0 && ((i+1) % 3 == 0))
      cout << board << endl;
    else cout << under << endl;
  }
}


int main(){
  srand(time(NULL));
  board game;
  game.print();
  game.createBoard();
  return 0;
}



Was This Post Helpful? 0
  • +
  • -

#11 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7507
  • View blog
  • Posts: 15,558
  • Joined: 16-October 07

Re: Sudoku infinite Loop...

Posted 28 December 2011 - 06:55 AM

We're moving to C++? Excellent. First, this is messy:
bool board::checkRow(char charx, int rowNum){
  bool result = false;
  for(int i = 0; i < 9; i++)
    if(sudo[rowNum][i] == charx)
      result = true;
  return result;
}



I know it's trivial, but it's driving me nuts. It's also wasteful. You should be stopping when result is true, right?

Instead:
bool board::checkRow(char charx, int rowNum){
	for(int i = 0; i < 9; i++) {
		if(sudo[rowNum][i] == charx) { return true; }
	}
	return false;
}



I don't really understand this at all:
      int i = rand() % 9;
      int j = rand() % 9;
      if(sudo[i][j] == ' '){



You're firing the the dark. A reasonable brute force method would be iterate over each position, not just randomly pick one. Assuming your checkBox is correct ( it's hard to tell ) you might get a result. Eventually...

This is what a simple brute force method might look like. Note, there is only one rand involved.
e.g.
bool board::attemptCreateBoard(){
	clearBoard();
	for(int row=0; row<ROW; row++){
		for(int col=0; col<COLS; i++) {
			const int MAX_VALUES = 9;
			char availableValues[MAX_VALUES];
			int availableValuesCount = 0;
			/* you get to figure this part out */
			if (availableValuesCount==0) { return false; }
			sudo[row][col] = availableValues[rand() % availableValuesCount];
		}
	}
	return true;
}



My class description for this would probably look like:
class Board{
public:
	static const ROWS = 9, COLS = 9;
	static const char EMPTY = ' ';
	Board();
	void clear();
	void print() const;
	void generate();
private:
	bool isValid(char, int row, int col);
	bool attemptGenerate();
	char data[ROWS][COLS];
};



Though, to be honest, mucking about with characters is messy. I'd prefer:
class Board{
public:
	static const ROWS = 9, COLS = 9;
	static const char EMPTY = 0;
	Board();
	void clear();
	void print() const;
	void generate();
private:
	bool isValid(int, int row, int col);
	bool attemptGenerate();
	int data[ROWS][COLS];
};



Hope this helps.
Was This Post Helpful? 1
  • +
  • -

#12 ssharma286   User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 93
  • Joined: 04-December 10

Re: Sudoku infinite Loop...

Posted 28 December 2011 - 11:54 PM

int i = rand() % 9;
int j = rand() % 9;
if(sudo[i][j] == ' '){


Okay I used that code to generate a random row number (my i) and my random column number (my j).

bool board::attemptCreateBoard(){
	clearBoard();
	for(int row=0; row<ROW; row++){
		for(int col=0; col<COLS; i++) {
			const int MAX_VALUES = 9;
			char availableValues[MAX_VALUES];
			int availableValuesCount = 0;
			/* you get to figure this part out */
			if (availableValuesCount==0) { return false; }
			sudo[row][col] = availableValues[rand() % availableValuesCount];
		}
	}
	return true;
}



Okay quick question. Now that I have a box check, do I need an available values array? Also shouldn't we be making the avalableValuesCount to 9? Or are you suggesting that I make an array of all the possible values that I can put in the box(i,j) [current box]. I appreciate all your help so far! THANKS!
Was This Post Helpful? 0
  • +
  • -

#13 ssharma286   User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 93
  • Joined: 04-December 10

Re: Sudoku infinite Loop...

Posted 29 December 2011 - 12:23 AM

Well I got all 81 boxes filled finally!
I posted the code below if anyone is interested..Just a note though it can be a LOT more efficient than it is in its current state.
One more thing I had a couple of quick questions. Does using const int ROW= 9 better than using 9 itself? And you said that when I started using classes I was using c++ but in my previous codes I was using the cout command. I thought if cout was used, The code becomes a C++ program since C uses printf and stuff.
#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;

char itoc(int a){
return char(a + 48);
}              

class board{
public:
char sudo[9][9];
board(){clearBoard();}
void clearBoard();
void print();
bool validChoice(char charx, int rowNum, int colNum);
bool checkRow(char charx, int rowNum);
bool checkCol(char charx,int colNum);
bool checkBox(char charx, int boxNum);
int boxNum(int rowNum, int colNum);
bool createBoard();
};

bool board::validChoice(char charx, int rowNum, int colNum){
bool result = false;
result = !(checkBox(charx, boxNum(rowNum,colNum)));
if(result) result = !(checkCol(charx, colNum));
if(result) result = !(checkRow(charx, rowNum));
return result;
}

int board::boxNum(int rowNum, int colNum){
int boxNum = 0;
if(rowNum >= 3 && rowNum < 6)
  boxNum = 3;
else if(rowNum >= 6 && rowNum < 9)
  boxNum = 6; 

if(colNum >= 3 && colNum < 6)
  boxNum += 1;
else if(colNum >= 6 && colNum < 9)
  boxNum += 2;  


return boxNum;
}

bool board::checkRow(char charx, int rowNum){
for(int i = 0; i < 9; i++)
  if(sudo[rowNum][i] == charx)
    return true;
return false;
}

bool board::checkCol(char charx,int colNum){
for(int i = 0; i < 9; i++)
  if(sudo[i][colNum] == charx)
    return true;
return false;
}

bool board::checkBox(char charx, int boxNum){
bool result = false;
int startRow, startCol;
if(boxNum  < 3)
  startRow = 0;
else if(boxNum >= 3 && boxNum < 6)
  startRow = 3;
else if(boxNum >= 6 && boxNum < 9)
  startRow = 6;


for(int i = 0; i != boxNum+1; i++){
  if(i % 3 == 0 || i == 0) startCol= 0;
  else startCol += 3;
}

for(int i = startRow; i < (startRow + 3); i++){
  for(int j = startCol; j < (startCol + 3); j++){
    if(sudo[i][j] == charx)
      result = true;
  }
}
return result;
}

void board::clearBoard(){
for(int i = 0; i < 9; i++)
  for(int j = 0; j < 9; j++)
    sudo[j][i] = ' ';  
}

bool board::createBoard(){
clearBoard();
for(int i = 0; i < 9; i++){
  for(int j = 0; j < 9; j++){
    int numOfTries = 0;
    while(numOfTries != 30){
      char insert = itoc((rand() % 9) +1);
      numOfTries++;
      if(validChoice(insert, i, j)){
        sudo[i][j] = insert;
        break;
      }
    }
    if(numOfTries == 30)
      return false;
  }
}
return true;
}

void board::print(){
cout <<           "   1  2  3  4  5  6  7  8  9" << endl;
string board =     " ╔═══╤═══╤═══╦═══╤═══╤═══╦";
string under =      " ┼──┼──┼──┼──┼──┼──┼──┼──┼──┼";
cout << board << endl;
for(int i = 0; i < 9; i++){
  cout << i+1 << "x";
  for(int j = 0; j < 9; j++){
    cout << ' ' << sudo[i][j];
    
    if(j != 0 && ((j+1) % 3 == 0))
      cout << 'l';
    else cout << "│";
  }
  cout << endl;
  if(i != 0 && ((i+1) % 3 == 0))
    cout << board << endl;
  else cout << under << endl;
}
}



int main(){
srand(time(NULL));
board game;
game.print();
int j =0;
for(int i = 0; i < 10; i++)
 {
  while(true){
    if(game.createBoard())
      break;
    j++;
  }
  cout << "Loops taken: " << j << endl;
 }
  game.print();
return 0;
}



This post has been edited by ssharma286: 29 December 2011 - 12:24 AM

Was This Post Helpful? 0
  • +
  • -

#14 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7507
  • View blog
  • Posts: 15,558
  • Joined: 16-October 07

Re: Sudoku infinite Loop...

Posted 29 December 2011 - 07:32 AM

View Postssharma286, on 29 December 2011 - 03:23 AM, said:

Does using const int ROW= 9 better than using 9 itself?


In this case, it may not seem so. It's doesn't cost you anything. However, it makes your code more clear, because you know that ROWS is the number of rows when you see it in a loop. Also, in other programs, if a value like that changes from 9 to 3, you have less work to do. It does happen. Raw numbers in code are called "magic" because it's often hard to tell what they mean. They are just there.

View Postssharma286, on 29 December 2011 - 03:23 AM, said:

you said that when I started using classes I was using c++ but in my previous codes I was using the cout command. I thought if cout was used...


Nice catch. Yes, cout only exists in C++. However, if you're just writing functions in C++, you're not writing C++ yet; you're just writing C with benefits. Class are what C++ is about and something like a sudoku board begs for them.


View Postssharma286, on 29 December 2011 - 02:54 AM, said:

Now that I have a box check, do I need an available values array?


Well, this tells you if you have to start over, mostly. If there are no available values, you're stuck.

View Postssharma286, on 29 December 2011 - 02:54 AM, said:

Also shouldn't we be making the avalableValuesCount to 9?


It starts out at 0. Then we get a list of them. If there are none in the list, it stays zero.

View Postssharma286, on 29 December 2011 - 02:54 AM, said:

Or are you suggesting that I make an array of all the possible values that I can put in the box


Yep.


I had fun with this. Since you've got your solution, I'll share mine.
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>

class Board {
public:
	typedef unsigned char CellValue;
	static const int ROWS=9, COLS=9, MAX_VALUES=9;
	static const CellValue CELL_EMPTY=0, CELL_MIN_VALUE=1, CELL_MAX_VALUE=9, CELL_INVALID=255;
	Board();
	void clear();
	int generate(); // returns attempts
	CellValue getValue(int row, int col) const;
private:
	bool isValid(CellValue, int row, int col) const;
	bool attemptGenerate();
	CellValue data[ROWS][COLS];
};

// a board shouldn't have to worry about UI
// we'll print here
void print(const Board &);

using namespace std;

int main(){
	srand(time(NULL));
	Board board;
	// print(board);
	int attempsMade = board.generate();
	cout << "Loops taken: " << attempsMade << endl;
	print(board);
	return 0;
}


Board::Board() { clear(); }

bool Board::isValid(CellValue value, int rowPos, int colPos) const {
	if (data[rowPos][colPos]!=CELL_EMPTY) { return false; }
	for(int row=0; row<ROWS; row++) {
		if (data[row][colPos]==value) { return false; }
	}
	for(int col=0; col<COLS; col++) {
		if (data[rowPos][col]==value) { return false; }
	}
	int boxRow = (rowPos / 3) * 3;
	int boxCol = (colPos / 3) * 3;
	for(int row=boxRow; row<boxRow+3; row++){
		for(int col=boxCol; col<boxCol+3; col++) {
			if (data[row][col]==value) { return false; }
		}
	}
	return true;
}

bool Board::attemptGenerate() {
	clear();
	for(int row=0; row<ROWS; row++){
		for(int col=0; col<COLS; col++) {
			CellValue availableValues[MAX_VALUES];
			int availableValuesCount = 0;
			for(CellValue value=CELL_MIN_VALUE; value<=CELL_MAX_VALUE; value++) {
				if (isValid(value, row, col)) {
					availableValues[availableValuesCount++] = value;
				}
			}
			if (availableValuesCount==0) { return false; }
			data[row][col] = availableValues[rand() % availableValuesCount];
		}
	}
	return true;
}

void Board::clear() {
	for(int row=0; row<ROWS; row++) {
		for(int col=0; col<COLS; col++) {
			data[row][col] = CELL_EMPTY;
		}
	}
}

int Board::generate() {
	int attempts = 1;
	while(!attemptGenerate()) { attempts++; }
	return attempts;
}

Board::CellValue Board::getValue(int row, int col) const {
	if (row<0 || row>ROWS || col<0 || col>COLS) { return CELL_INVALID; }
	return data[row][col];
}

void print(const Board &B)/> {
	for(int row=0; row<Board::ROWS; row++){
		if (row==3 || row==6) { cout << "-------+-------+-------" << endl; }
		for(int col=0; col<Board::COLS; col++) {
			if (col==3 || col==6) { cout << " | "; } else { cout << ' '; }
			Board::CellValue value = b.getValue(row, col);
			if (value==Board::CELL_INVALID) {
				cout << '?';
			} else if (value==Board::CELL_EMPTY) {
				cout << '.';
			} else {
				cout << (int)value;
			}
		}
		cout << endl;
	}
}



An improvement I can think of would be to combine the isAvailable function with the isValid. There are probably more.

This post has been edited by baavgai: 29 December 2011 - 07:33 AM

Was This Post Helpful? 1
  • +
  • -

#15 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2034
  • View blog
  • Posts: 5,436
  • Joined: 27-December 05

Re: Sudoku infinite Loop...

Posted 29 December 2011 - 07:39 AM

View Postssharma286, on 29 December 2011 - 02:23 AM, said:

Does using const int ROW= 9 better than using 9 itself?

When you're using a constant value in your program, it's preferable to define a constant and use that instead of the actual number because:
(1) it makes the semantic meaning of the number clearer to a reader of the code (assuming you give the constant a name that makes its meaning clear).
(2) Often, it is necessary to change the value when circumstances change or you want to apply the program to a slightly different problem. If you've defined a constant and used it throughout the program you only have to make a single change where the constant is defined rather than search throughout the entire program (which might even be spread over multiple files) to change it every place it was used.

So the same argument could be used regarding 3 and 6 in your program. On the other hand, it's hard to envision changing the dimensions of a Soduku board to anything other than 3 3x3 blocks, so I wouldn't argue too fervently regarding any of your constants in this case.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1