5 Replies - 3128 Views - Last Post: 07 August 2012 - 09:34 AM Rate Topic: -----

#1 Roonil Wazlib  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 30
  • Joined: 03-August 12

Generating sudokus in C++

Posted 03 August 2012 - 09:16 AM

I'm a guy in 12th grade, and am studying something that is positively ancient, Turbo C++. My knowledge about C++ is, therefore, limited to whatever we're being taught at school (and looking around, I can see that I've missed out on a lot of stuff). I'd be grateful if you could keep that in mind if you look at my code (which will probably horrify you, because I've been trying to use my extremely limited knowledge to try to create what I want).

For my end of term project, I've been working on a program that allows you to play sudoku, store your scores and times, create profiles, save and load games, the works. Starting off with the most basic bit, i.e. creating valid sudokus which are unique everytime the project is executed, I've been running into loads of problems.

Finally, I've made something that looks as if it'll work, and I wanted to have experienced eyes look over my program for generating sudokus for things that could be improved, and all. My basic outline was:

  • Fill valid values randomly in the top and bottom row of the sudoku.
  • Use a brute force while loop to fill in the rest of the values.
  • Hide some values (randomly selected), and display the rest (60 for easy, 50 for medium, 40 for hard).
  • Allow the user to solve it.

I've been working on generating full, unique sudokus at home, while the rest of my stuff is in my school computer. Originally, I was trying to fill valid values in every cell (by using random()), and not using the brute force thing at all. However, that was taking too long (because the values so filled couldn't make a valid sudoku game, and the computer would have to try near infinite combinations to get a valid game). So, in interests of expediency, I filled the top and bottom rows (so that sufficiently unique values could be generated without making the program go kaboom), and used the brute force thing. Unfortunately, sometimes, it still seems to go in 'forever calculating' mode.

I'm wondering: Is there a concept I could've applied that would've made things a lot easier? Is there something I've missed? Should I assign just one row instead of two, or something else? Would something do better than brute force?

I'd be grateful if you guys could help me answer this question.

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

class sudoku
{
public:
int arr[9][9];
int ch[9][9];

	sudoku()
	{
		for(int x=0; x<9; x++)
		{	for(int y=0; y<9; y++)
			{arr[x][y]=0;
			ch[x][y]=0;}
		}
	}

	void dis()
	{
		for(int x=0; x<9; x++)
		{
			for(int y=0; y<9; y++)
			{cout<<" "<<arr[x][y]<<" ";}
		cout<<"\n\n";
		}
	}

	int comp(int num, int r, int c)
	{

		for(int x=0; x<9; x++)
		{
			if(arr[r][x]==num||arr[x][c]==num)
			{return 0;}

		}

		int row, col;
                //This stuff is for checking the 3x3 cell. 
		if(r>=0&&r<=2)
		{row=0;}

		else if(r>=3&&r<=5)
		{row=3;}

		else if(r>=6&&r<=8)
		{row=6;}

		if(c>=0&&c<=2)
		{col=0;}

		else if(c>=3&&c<=5)
		{col=3;}

		else if(c>=6&&c<=8)
		{col=6;}


			for(x=row; x<row+3; x++)
			{
				for(int y=col; y<col+3; y++)
				{if(arr[x][y]==num)
				{	if(x!=r&&y!=c)
					{
					return 0;
					}
				}
				}
			}
	return 1;
	}

	void assign()
	{
	randomize();
	int row=0, col=0;
	int a;


		for(col=0; col<9; col++)
		{
					while(ch[row][col]==0)
					{a=random(9)+1;
					if(comp(a,row,col)==1)
					{arr[row][col]=a;
					ch[row][col]=a;
					break;
					}
					}
		}

		row=8; //I know, I could've used a dual for loop instead of this madness. Stupid me.

		for(col=0; col<9; col++)
		{
					while(ch[row][col]==0)
					{
					a=random(9)+1;
					if(comp(a,row,col)==1)
					{
					arr[row][col]=a;
					ch[row][col]=a;
					break;
					}

					}
		}
	}

	void brute()
        {

        int i=0,x,y;
        int flag; 
            while(i<81)
            { 
            flag=2;
	    x = i/9; y = i%9;
	    if(ch[x][y]==0)
	    {
	    flag=0; 
	    for(int j=arr[x][y]+1;j<10;j++)
	    {


		if(comp(j,x,y)==1)
		{
		    arr[x][y]=j;
		    flag=1;
		    break; 
		}

	    }
	    }

	if(flag==0)
	{   arr[x][y]=0;
	    i--;}

	else
	{    i++;}

	if(i==-1)
	{    break;}
}

}
};


void main()
{       int p=0;
	while(p<10)//This is just something I'm using to see how the code's working. Sometimes it works perfectly all 10 times, sometimes it goes into 'forever calculating mode' on the third try.
	{
	clrscr();
	sudoku a;

	a.assign();
	a.dis();
	getch();
	clrscr();
	a.brute();
	a.dis();
	getch();
	p++;
	}
}




Is This A Good Question/Topic? 0
  • +

Replies To: Generating sudokus in C++

#2 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1635
  • View blog
  • Posts: 3,111
  • Joined: 30-May 10

Re: Generating sudokus in C++

Posted 03 August 2012 - 09:50 AM

https://encrypted.go...erating+sudokus
Some research is in order.
Was This Post Helpful? 0
  • +
  • -

#3 Roonil Wazlib  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 30
  • Joined: 03-August 12

Re: Generating sudokus in C++

Posted 04 August 2012 - 02:37 AM

Well, thanks. I'd tried it earlier, but maybe there's something I missed.
Was This Post Helpful? 0
  • +
  • -

#4 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1327
  • View blog
  • Posts: 4,552
  • Joined: 19-February 09

Re: Generating sudokus in C++

Posted 05 August 2012 - 08:33 PM

In your loop for the bottom row, if you printed the random number, you would see that sometimes it loops forever.

This can happen when the last number to be entered is equal to the last number on the top row. The program is caught in a trap.
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5796
  • View blog
  • Posts: 12,631
  • Joined: 16-October 07

Re: Generating sudokus in C++

Posted 06 August 2012 - 05:49 AM

Simply, you need to create an isValid function. Period.

Your isValid checks the three possible blocking values. That is, isInRow, isInCol, isInBox. If you are filling, you run that function for 1..9. You then randomly pick from that list. If you need to fill in a cell and there are no values in that list, you're done, start over.

The sanest way to do this is probably to look at the cells with that currently have the least possibilities and fill those first.

This will not stop you from generating yourself into a corner. But, it's a start.

I have no clue why you have both arr and ch in your class. You seem to be doing some validation checks, but only after you've chosen a value.
Was This Post Helpful? 0
  • +
  • -

#6 Roonil Wazlib  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 30
  • Joined: 03-August 12

Re: Generating sudokus in C++

Posted 07 August 2012 - 09:34 AM

#define: I read that post, and then I stared at it for the next 10 minutes, thinking 'I'm a friggin' idiot.'. I get that now, and I've changed it up from filling the entire last row to just filling the last cell. It's been working properly, even though I'm still feeling ridiculously stupid.

baavgai: Thanks for taking a look, and yeah, your way makes a lot more sense than mine does. I'll try to add that in. About the arr and ch arrays: it had something to do with the display and getting values from the user.

Thanks a lot! :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1