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   

Need help programing sudoku on C++

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

Joined: 07 Nov 2008
Posts: 7
:

Items
PostPosted: Fri Nov 07, 2008 5:55 am    Post subject: Need help programing sudoku on C++ Reply with quote
Hi everyone, i need to program a sudoku, but i really dont know all the "facts" i need to put on the code...
if someone know the algoritm and can post it, i qould apreciate it a lot...

heres what I've got so far...

Quote:
#include<conio>
#include<stdlib>
#include<stdio>
#define MAX 9



void main (void)
{
clrscr();
randomize();
int matriz[MAX][MAX];






for(int i=0;i<MAX;i++)
{
matriz[0][i]=(rand()%9)+1;
for(int j=1;j<MAX;j++)
{
if(matriz[0][i]==matriz[0][i-j])
{i--;}
}
}

for(i=0;i<3;i++)
{
matriz[1][i]=(rand()%9)+1;
for(int j=1;j<4;j++)
{
if(matriz[1][i]==matriz[1][i-j]||matriz[1][i]==matriz[0][0]||matriz[1][i]==matriz[0][1]||matriz[1][i]==matriz[0][2])
{i--;}
}
}


for(i=0;i<2;i++)
{
matriz[2][i]=(rand()%9)+1;
if(matriz[2][i]==matriz[2][i-1]||matriz[2][i]==matriz[0][0]||matriz[2][i]==matriz[0][1]||matriz[2][i]==matriz[0][2]||matriz[2][i]==matriz[1][0]||matriz[2][i]==matriz[1][1]||matriz[2][i]==matriz[1][2])
{i--;}
matriz[2][2]=(45-(matriz[0][0]+matriz[0][1]+matriz[0][2]+matriz[1][0]+matriz[1][1]+matriz[1][2]+matriz[2][0]+matriz[2][1]));
}




for(i=0;i<MAX;i++)
{
for(int j=0;j<MAX;j++)
{
printf("%d\t",matriz[i][j]);
}
printf("\n");
}



getch();
}


I need this program for november 29th...
i think with the solved randomized sudoku is all i need to have the full project, if someone can help me, thx =)...
Back to top
View user's profile Send private message MSN Messenger
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Fri Nov 07, 2008 4:37 pm    Post subject: Reply with quote
Quote:
Hi everyone, i need to program a sudoku, but i really dont know all the "facts" i need to put on the code...
if someone know the algoritm and can post it, i qould apreciate it a lot...

What do you mean by you need to program a sudoku?
Do you need a solver? a generator?....
I have done mine in c++ too but I used wxWidgets instead. A lot easier.

Mark
Back to top
View user's profile Send private message
darkfalco

Joined: 07 Nov 2008
Posts: 7
:

Items
PostPosted: Fri Nov 07, 2008 8:14 pm    Post subject: Reply with quote
I need a generator on C++
but i dont know what even is a widget...
so if someone can help me on a C++ generator, thx =)...
Back to top
View user's profile Send private message MSN Messenger
darkfalco

Joined: 07 Nov 2008
Posts: 7
:

Items
PostPosted: Mon Nov 10, 2008 7:23 am    Post subject: Reply with quote
Ok... i already made a new idea for the generator...
consists on 9 arrays on 9 ints...
heres the code I've got so far...
if someone can help me validating i would appreciate it a lot =)...

Code:
#include<conio>
#include<stdlib>
#include<stdio>
#define MAX 9


int sud1[MAX],sud2[MAX],sud3[MAX],sud4[MAX],sud5[MAX],sud6[MAX],sud7[MAX],sud8[MAX],sud9[MAX];

void gen_sudoku(void);
void fun2(void);
void fun3(void);
void fun4(void);
void fun5(void);
void fun6(void);
void fun7(void);
void fun8(void);
void fun9(void);



void main (void)
{
clrscr();            
randomize();     
      
gen_sudoku();

for(int i=0;i<MAX;i++)
  {
   printf("%d ",sud1[i]);
  }
printf("\n");
for(i=0;i<MAX;i++)
  {
   printf("%d ",sud2[i]);
  }
printf("\n");
for(i=0;i<MAX;i++)
  {
   printf("%d ",sud3[i]);
  }
printf("\n");
for(i=0;i<MAX;i++)
  {
   printf("%d ",sud4[i]);
  }
printf("\n");
for(i=0;i<MAX;i++)
  {
   printf("%d ",sud5[i]);
  }
printf("\n");
for(i=0;i<MAX;i++)
  {
   printf("%d ",sud6[i]);
  }
printf("\n");
for(i=0;i<MAX;i++)
  {
   printf("%d ",sud7[i]);
  }
printf("\n");
for(i=0;i<MAX;i++)
  {
   printf("%d ",sud8[i]);
  }
printf("\n");
for(i=0;i<MAX;i++)
  {
   printf("%d ",sud9[i]);
  }







getch();
}




void gen_sudoku(void)
{
for(int i=0;i<MAX;i++)         
  {
   sud1[i]=(rand()%9)+1;
   for(int j=1;j<9;j++)         
     {
      if(sud1[i]==sud1[i-j])
   {i--;}
     }
  }
fun2();
}



void fun2(void)
{
for(int j=0,i=0;i<MAX;i++)         
  {
   sud2[i]=(rand()%9)+1;
   for(j=1;j<9;j++)              {
      if(sud2[i]==sud2[i-j])
   {
    if((i-j)<0)
     {break;}
    else
     {i--;
     break;}
   }
     }
  }
for(i=0;i<3;i++)
  {
   if(sud2[i]==sud1[0]||sud2[i]==sud1[1]||sud2[i]==sud1[2])
    {fun2();}
  }
for(i=3;i<6;i++)
  {
   if(sud2[i]==sud1[3]||sud2[i]==sud1[4]||sud2[i]==sud1[5])
    {fun2();}

  }
for(i=6;i<9;i++)
  {
   if(sud2[i]==sud1[6]||sud2[i]==sud1[7]||sud2[i]==sud1[8])
    {fun2();}
  }

fun3();
}




void fun3(void)
{
for(int j=0,i=0;i<MAX;i++)           {
   sud3[i]=(rand()%9)+1;
   for(j=1;j<9;j++)              {
      if(sud3[i]==sud3[i-j])
   {
    if((i-j)<0)
     {break;}
    else
     {i--;
     break;}
   }
     }
  }
for(i=0;i<3;i++)
  {
   if(sud3[i]==sud1[0]||sud3[i]==sud1[1]||sud3[i]==sud1[2]||sud3[i]==sud2[0]||sud3[i]==sud2[1]||sud3[i]==sud2[2])
    {fun3();}
  }
for(i=3;i<6;i++)
  {
   if(sud3[i]==sud1[3]||sud3[i]==sud1[4]||sud3[i]==sud1[5]||sud3[i]==sud2[3]||sud3[i]==sud2[4]||sud3[i]==sud2[5])
    {fun3();}

  }
for(i=6;i<9;i++)
  {
   if(sud3[i]==sud1[6]||sud3[i]==sud1[7]||sud3[i]==sud1[8]||sud3[i]==sud2[6]||sud3[i]==sud2[7]||sud3[i]==sud2[8])
    {fun3();}
  }
//fun4();
}








/*

void fun4(void)
{
for(int j=0,i=0;i<MAX;i++)           {
   sud4[i]=(rand()%9)+1;
   for(j=1;j<9;j++)              {
      if(sud4[i]==sud4[i-j])
   {
    if((i-j)<0)
     {break;}
    else
     {i--;
     break;}
   }
     }
  }

for(i=0;i<MAX;i++)
  {
   if(sud4[i]==sud1[i]||sud4[i]==sud2[i]||sud4[i]==sud3[i])
  {fun4();}
  }


//fun5();
}




*/






/*
void fun4(void)
{
for(int i=0;i<MAX;i++)           {
   sud4[i]=(rand()%9)+1;
   for(int j=1;j<9;j++)              {
      if(sud4[i]==sud4[i-j])
   {i--;}
     }
  }
fun5();
}

void fun5(void)
{
for(int i=0;i<MAX;i++)           {
   sud5[i]=(rand()%9)+1;
   for(int j=1;j<9;j++)              {
      if(sud5[i]==sud5[i-j])
   {i--;}
     }
  }
fun6();
}




void fun6(void)
{
for(int i=0;i<MAX;i++)           {
   sud6[i]=(rand()%9)+1;
   for(int j=1;j<9;j++)              {
      if(sud6[i]==sud6[i-j])
   {i--;}
     }
  }
fun7();
}


void fun7(void)
{
for(int i=0;i<MAX;i++)           {
   sud7[i]=(rand()%9)+1;
   for(int j=1;j<9;j++)              {
      if(sud7[i]==sud7[i-j])
   {i--;}
     }
  }
fun8();
}


void fun8(void)
{
for(int i=0;i<MAX;i++)           {
   sud8[i]=(rand()%9)+1;
   for(int j=1;j<9;j++)              {
      if(sud8[i]==sud8[i-j])
   {i--;}
     }
  }
fun9();
}


void fun9(void)
{
for(int i=0;i<MAX;i++)           {
   sud9[i]=(rand()%9)+1;
   for(int j=1;j<9;j++)              {
      if(sud9[i]==sud9[i-j])
   {i--;}
     }
  }
}


*/


you can copy paste on TC... please i need some help...
29 november X_x...
Back to top
View user's profile Send private message MSN Messenger
darkfalco

Joined: 07 Nov 2008
Posts: 7
:

Items
PostPosted: Mon Nov 10, 2008 11:57 pm    Post subject: Reply with quote
ok i already made a NEW "algoritm" for create a random sudoku, it have just a few errors

creating a line... if it gives a random number, and that number cant be placed on a section, it return and create another random number untill it can be placed, but theres some times it CANT be placed any number, so it have to generate a new line, if im ok just tell me YES and if you know how to solve it, thx... heres my code...
i hope anyone can help me a little bit =)...

P.S.
Code/algoritm for generate a random solved sodoku

Code:
#include<conio>
#include<stdlib>
#include<stdio>
#define MAX 9

void iniciar();
void sudoku(void);
void imprimir(void);
int columna(int,int,int);
int fila(int,int,int);
int seccion(int,int,int);

int sud[MAX][MAX];

void main (void)
{
clrscr();
randomize();

iniciar();
sudoku();
imprimir();


printf("hola sudoku...");
getch();
}




void sudoku(void)
{
int x;
  for(int i=0;i<MAX;i++)
   {
    //crear linea "volver a crear si se "traba" en determinado momento"
    for(int j=0;j<MAX;j++)
     {
      x=(rand()%9)+1;
      sud[i][j]=x;
      x=columna(i,j,x);
      if(x==10)
       {j--;}
      else
       {
       x=fila(i,j,x);
       if(x==10)
   {j--;}
   else
    {
    x=seccion(i,j,x);
    if(x==10)
    {j--;}
    }
        }
      }
   }
}




int columna(int k,int l,int y)
{
 int f=y;
 for(int n=0;n<MAX;n++)
  {
   if((k-n)!=k)
    {
     if((k-n)<0)
      {n=10;}
     else
      {
       if(sud[k][l]==sud[k-n][l])
   {f=10;}
      }
    }
  }
return f;
}





int fila(int k,int l,int y)
{
 int f=y;
 for(int n=0;n<MAX;n++)
  {
   if((l-n)!=l)
    {
     if((l-n)<0)
      {n=10;}
     else
      {
       if(sud[k][l]==sud[k][l-n])
   {f=10;}
      }
    }
  }
return f;
}




int seccion(int k,int l,int y)
{
 int f=y;

//seccion 1
if(k<=2&&l<=2)
 {
  for(int m=0;m<=2;m++)
   {
    for(int n=0;n<=2;n++)
     {
      if(m!=k&&n!=l)
       {
   if(n<0)
         {n=10;}
   else
         {
     if(sud[k][l]==sud[m][n])
           {f=10;}
    }
       }
     }
    }
  }

//seccion 2
if(k<2>2&&l<6)
 {
  for(int m=0;m<=2;m++)
   {
    for(int n=3;n<=5;n++)
     {
      if(m!=k&&n!=l)
       {
   if(n<3)
         {n=10;}
   else
    {
     if(sud[k][l]==sud[m][n])
           {f=10;}
    }
       }
     }
    }
  }


//seccion 3
if(k<2>5&&l<9)
 {
  for(int m=0;m<=2;m++)
   {
    for(int n=6;n<=8;n++)
     {
      if(m!=k&&n!=l)
       {
   if(n<6)
         {n=10;}
   else
    {
     if(sud[k][l]==sud[m][n])
           {f=10;}
    }
       }
      }
    }
  }


//seccion 4
if(k<5>2&&l<3)
 {
  for(int m=3;m<=5;m++)
   {
    for(int n=0;n<=2;n++)
     {
      if(m!=k&&n!=l)
       {
   if(n<0)
         {n=10;}
   else
    {
     if(sud[k][l]==sud[m][n])
           {f=10;}
    }
       }
      }
    }
  }

//seccion 7
if(k<8>5&&l<3)
 {
  for(int m=5;m<=8;m++)
   {
    for(int n=0;n<=2;n++)
     {
      if(m!=k&&n!=l)
       {
   if(n<0)
         {n=10;}
   else
    {
     if(sud[k][l]==sud[m][n])
           {f=10;}
    }
       }
      }
    }
  }

//seccion 5
if(k<5>2&&l<5>2)
 {
  for(int m=3;m<=5;m++)
   {
    for(int n=3;n<=5;n++)
     {
      if(m!=k&&n!=l)
       {
   if(n<3)
         {n=10;}
   else
    {
     if(sud[k][l]==sud[m][n])
           {f=10;}
    }
       }
      }
    }
  }


//seccion 6
if(k<5>2&&l<8>5)
 {
  for(int m=3;m<=5;m++)
   {
    for(int n=5;n<=8;n++)
     {
      if(m!=k&&n!=l)
       {
   if(n<5)
    {n=10;}
   else
    {
     if(sud[k][l]==sud[m][n])
      {f=10;}
    }
       }
      }
    }
  }

//seccion 8
if(k<8>5&&l<5>2)
 {
  for(int m=5;m<=8;m++)
   {
    for(int n=3;n<=5;n++)
     {
      if(m!=k&&n!=l)
       {
   if(n<3)
    {n=10;}
   else
    {
     if(sud[k][l]==sud[m][n])
      {f=10;}
    }
       }
      }
    }
  }


//seccion 9
if(k<8>5&&l<8>5)
 {
  for(int m=5;m<=8;m++)
   {
    for(int n=5;n<=8;n++)
     {
      if(m!=k&&n!=l)
       {
   if(n<5)
    {n=10;}
   else
    {
     if(sud[k][l]==sud[m][n])
      {f=10;}
    }
       }
      }
    }
  }




return f;
}





void iniciar(void)
{
for(int i=0;i<MAX;i++)
  {
   for(int j=0;j<MAX;j++)
    {
     sud[i][j]=0;
    }
  }
}




void imprimir(void)
{
for(int i=0;i<MAX;i++)
  {
   for(int j=0;j<MAX;j++)
    {
     printf("%d  ", sud[i][j]);
    }
   printf("\n");
  }
printf("\n");
}
Back to top
View user's profile Send private message MSN Messenger
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Thu Nov 13, 2008 6:22 pm    Post subject: Reply with quote
Quote:
creating a line... if it gives a random number, and that number cant be placed on a section, it return and create another random number untill it can be placed, but theres some times it CANT be placed any number, so it have to generate a new line, if im ok just tell me YES

YES, but i doubt that generating a new line will be enough in all the cases.
Generating a new line if the next line allways fails is some sort of backtracking, but sometimes it could be that you will have to regenerate more than one line.

You must consider that you will often produce cells where ANY value is NO longer possible, we call that an empty cell. So placing a value who don't conflict in its row, column or box is just the easy part of the work. You have to check, after placing a value, if this results in an empty cell, and if so, your generator has to backtrack, and this backtracking must be able to cover the whole grid. Since your code is randomly generating values, implementing backtracking will not be easy. You could keep a variable who will count the times you had to regenerate the same line over and over again to no avail, and if it occurs to many, you can regenerate an extra line, and so on...but...

In my humble opinion, you need another, better approach.

Now, consider the 4 line brute force solver (see topic: four line sudoku solver ) where rwaddilove wrote:

Quote:
Sudoku puzzles can be solved with just 4 lines of code. Here's it is:

1 sp(cell(ptr))=(sp(cell(ptr)) + 1) mod 10
2 if sp(cell(ptr))=0 then ptr=ptr+1:goto 1
3 if countnum(cell(ptr))=3 then ptr=ptr-1
4 if ptr>-1 then goto 1

Of course, it needs a bit of explanation. This is a brute force method, but it is so short and simple that it is very fast. You need to create two arrays and a pointer like this:

sp(80) is the sudoku puzzle - 9 x 9 grid, 81 cells, numbered 0-80
cell(80) is a list of blank cells - when you read in the puzzle, store the blank cell numbers here
ptr=points to the last blank cell in the list

One other thing you need is a countnum() function. This counts how many times a number appears. It should appear once in a row, once in a column and once in a block, hence the if countnum()=3 then...

That's it. You want to see some real code? Here it is in Visual Basic - I dislike goto so the structured version is a little longer:
Code:

While ptr > -1
  sp(cell(ptr)) = (sp(cell(ptr)) + 1) Mod 10
  If sp(cell(ptr)) = 0 Then
    ptr = ptr + 1
  Else
    If CountNum(cell(ptr)) = 3 Then ptr = ptr - 1
  End If
Wend

That's the main program loop that solves the puzzle in sp() - just print out the array afterwards to see the solution. The CountNum() function just counts the occurances like this:
Code:

Function CountNum(ByVal n As Integer) As Integer
Dim i, j, k, r, c As Integer

k = 0   'count

'check the row and column
r = n \ 9   'row 0-8
c = n Mod 9   'column 0-8
For i = 0 To 8
  If sp(r * 9 + i) = sp(n) Then k = k + 1   'row
  If sp(c + i * 9) = sp(n) Then k = k + 1   'column
Next

'check the block
c = 3 * (c \ 3)   'left column of block 0/3/6
r = 3 * (r \ 3)    'top row of block 0/3/6
For i = 0 To 2
  For j = c To c + 2
    If sp((r + i) * 9 + j) = sp(n) Then k = k + 1
  Next
Next
CountNum = k

End Function

This function could be made faster by checking the row and exiting if there's more than one, then checking the column and exiting if more than one, then checking the block. It would save some checking. However, it seems fast enough as it is. VB isn't particularly quick, but simple puzzles are solved instantaneously and the hard ones only take 5 or 10 seconds.


With this approach you can solve sudokus by brute force, but you can generate a solved grid starting from scratch as well, consider it as a sudoku with no clues. It's obvious that you allways will generate the same solved grid over and over again, but this can be ommitted by randomly changing the order of the cells to solve that are kept in the array cell()

So after filling the array cell(), and before invoking the brute force you can mix up the content of cell() by randomly picking two cells and switch their contents, and do this more than once, let's say 500 times.

It could look like this:
Code:
'first fill the array cell()
for n = 0 to 80
    cell(n) = n
next n

'initiate the random generator
Randomize

'now mix up the contents of that array
For n = 1 To 500 'this will be enough to mix it up
    i = Int(81 * Rnd) 'generate a random number between 0 and 80
    j = Int(81 * Rnd) 'generate another random number between 0 and 80
    dummie = cell(i) 'copy content of cell(i) to dummie
    cell(i) = cell(j) 'copy content of cell(j) to cell(i)
    cell(j) = dummie 'copy content of cell(i) (previously kept in dummie) to cell(j)
Next n

_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
darkfalco

Joined: 07 Nov 2008
Posts: 7
:

Items
PostPosted: Thu Nov 13, 2008 8:55 pm    Post subject: Reply with quote
Wow, a lot of thx Lunatic, i been thinking on a new form to solve the "sudoku generator" problem... heres the code i made, this already work well...

I hope poeple who need this code would give me thx for it xDD...
im a C++ noob programmer... so =(...
this was the best i could, if someone can "masterize it" go ahead...



CODE:
http://galeon.com/darkfalco/sudokbydarkfalco.cpp

http://www.anim-arte.com/comunidad/623-club-de-programacion-anim-arte-dudas-4.html#post49052
Back to top
View user's profile Send private message MSN Messenger
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