# Validity of a given sudoku problem?

Discussion in 'C' started by jackspa, Mar 20, 2009.

1. ### jackspaNew Member

Joined:
Feb 20, 2009
Messages:
11
0
Trophy Points:
0
Hi, I am attaching an easy sudoku solving program.there are some conditions of input in which the program goes in infinite loop.How do i check that given example is a valid one?
Here is an example when program hangs:
1,2,3,
4,5,6,
0,0,0,8
here as 8 is not possible in the first 3*3 square,program hangs.But the input is valid according to my validity checks.:crazy:
I want to use better environment for that.HowQ do i do that? How do one rate a program?:shout:

Code:
```#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<dos.h>
#define ROW(x) ((j-rs)%x)
#define COL(x) ((i-cs)%x)
int a[9][9],b[9][9];
getkey()/*up 72 down 80 left 75 right 77 esc 1*/
{
union REGS i,o;
while(!kbhit())
;
i.h.ah=0;
int86(22,&i,&o);
return(o.h.ah);
}
void display(int rs,int cs)
{
int i,j;
for(i=rs;i<=(rs+16);i+=2)
for(j=cs;j<=(cs+16);j+=2)
{
gotoxy(j,i);
if(b[i/2-(rs/2)][j/2-(cs/2)])
printf("%d",b[i/2-(rs/2)][j/2-(cs/2)]);
else
printf(" ");
}
}
void input(int rs,int cs)
{
int i=cs,j=rs,k;
gotoxy(33,32);printf("Del  : Delete");
gotoxy(33,34);printf("Enter: Solve");
gotoxy(33,36);printf("Esc  : Exit");
while(1)
{
display(rs,cs);
gotoxy(i,j);
k=getkey();
switch(k)
{
case 72://Up
if(j==rs){j+=16;break;}
j-=2;
break;
case 80://Down
if(j==rs+16){j=rs;break;}
j+=2;
break;
case 75://Left
if(i==cs){i+=16;break;}
i-=2;
break;
case 77://Right
if(i==cs+16){i=cs;break;}
i+=2;
break;
case 1: //Exit
exit();
case 28://Input complete
return;
case 2:case 3:case 4:case 5:case 6:case 7:
case 8:case 9:case 10://Enter 1 to 9
if(valid(k-1,(j/2-(rs/2)),(i/2-(cs/2))))//Assign only if valid
b[j/2-(rs/2)][i/2-(cs/2)]=k-1;
break;
case 83://Delete wrong entry
b[j/2-(rs/2)][i/2-(cs/2)]=0;
break;
default:
printf("\a");
}
}
}
void frame(int rs,int cs)//Draws 9*9 grid, rs and cs given starting coordinates
{
int i,j,k,ce=cs+18,re=rs+18;
clrscr();
for(i=cs;i<=ce;i++)
for(j=rs;j<=re;j++)
{
gotoxy(i,j);
if((j==rs)&&(i==cs))k=201;
else if((j==rs)&&(i==ce))k=187;
else if((j==re)&&(i==cs))k=200;
else if((j==re)&&(i==ce))k=188;
else if(ROW(2)&&!COL(6))k=186;
else if(ROW(2)&&!COL(2))k=179;
else if(!ROW(6)&&COL(2))k=205;
else if(!ROW(2)&&COL(2))k=196;
else if((i==cs)&&ROW(6))k=199;
else if((i==cs)&&!ROW(6))k=204;
else if((i==ce)&&ROW(6))k=182;
else if((i==ce)&&!ROW(6))k=185;
else if((j==re)&&COL(6))k=207;
else if((j==re)&&!COL(6))k=202;
else if((j==rs)&&COL(6))k=209;
else if((j==rs)&&!COL(6))k=203;
else if(!ROW(6)&&COL(6))k=216;
else if(ROW(6)&&!COL(6))k=215;
else if(!ROW(6)&&!COL(6))k=206;
else if(!ROW(2)&&!COL(2))k=197;
else k=32;
printf("%c",k);
}
input(rs+1,cs+1);
}
void zero(int *i,int *j,int add)//Finds next or previous zero in reference matrix a
do
{
if(*j==-1||*j==9)
{
}
}
while(a[*i][*j]);
}
int valid(int k,int r,int c)//Checks if given no. is valid in corrosponding
{                           //row or column or 3*3 square
int i,j,l=0,rs=(r/3)*3,cs=(c/3)*3,re=rs+2,ce=cs+2;
for(i=0;i<9;i++)
if(k==b[i][c]||k==b[r][i])
l++;
for(i=rs;i<=re;i++)
for(j=cs;j<=ce;j++)
if(k==b[i][j])
l++;
return(!l?1:0);
}
int assign(int i,int j,int k)//assigns first valid no. from array e[9]
{                            //to b[i][j], if no no. is possible returns 1
int e[9]={1,2,3,4,5,6,7,8,9};
if(k==9)return 1;
while(!valid(e[k],i,j))
{
k++;
if(k==9)return 1;
}
b[i][j]=e[k];
return 0;
}
void solve()
{
int i,j,k=0,rs=0,cs=-1,re=8,ce=9;
zero(&rs,&cs,1);i=rs;j=cs;
zero(&re,&ce,-1);
while(1)
{
if(assign(i,j,k))//Put 1st valid no. at b[i][j]
{
b[i][j]=0;//No no. is possible, so make that field 0
zero(&i,&j,-1);//Go to previous zero
if(i<=rs&&j<cs)
{
i=rs;j=cs;
}
k=b[i][j];
continue;
}
if(i==re&&j==ce)break;//Solved
k=0;
zero(&i,&j,1);//Go to next zero
}
}
void main()
{
int i,j;
float t1,t2;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
b[i][j]=a[i][j]=0;
frame(11,30);
for(i=0;i<9;i++)
for(j=0;j<9;j++)
a[i][j]=b[i][j];
t1=clock()/CLK_TCK;
solve();
t2=clock()/CLK_TCK;
display(12,31);
gotoxy(25,32);printf("Time taken to solve= %fs",t2-t1);
gotoxy(31,34);printf("Enter: Solve Another");
gotoxy(26,36);printf("Press any other key to exit...");
if(getkey()==28)main();
}```

Last edited by a moderator: Mar 20, 2009

Joined:
Jul 12, 2004
Messages:
15,292
365
Trophy Points:
83
Moved the attachment into the posts

3. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,012
203
Trophy Points:
0
Occupation:
Senior Support Engineer
Location:
England
Where exactly does it hang?

4. ### jackspaNew Member

Joined:
Feb 20, 2009
Messages:
11
0
Trophy Points:
0
My program can solve a sudoku with any no. of problem no.s from 0 to 80.

If you run this program, you get a 9*9 grid.In that you go to places using navigation keys.And you enter the numbers.
Go to following locations and try entering following input:
row col no.
0 0 1
0 1 2
0 2 3
1 0 4
1 1 5
1 2 6
2 3 8
And hit enter that is you want to solve this problem.The program goes in infinite loop.This is because in first 3*3 square 8 is possible nowhere.:undecided

My validity check checks if a number user trying to enter is unique in corrosponding row and column and 3*3 square.

So the above input passes validity check.But as can be seen it's not a valid problem.

I want some help with validity check, which can detect errors such as in above given input.

5. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,012
203
Trophy Points:
0
Occupation:
Senior Support Engineer
Location:
England
Yes, I understand all that. Where exactly does it go into an infinite loop?

One technique I use when debugging (and not using a debugger for whatever reason) is to liberally sprinkly printf statements around the code, saying where it is up to, what the value of certain variables is, and that can be very helpful.

What's the point of the e array in assign()? e[k]=k-1 if k>=0 and k<=8, so you could just do "k-1" instead of "e[k]".

If I were debugging then as an example I might put at the start of assign():
Code:
```int assign(int i,int j,int k)//assigns first valid no. from array e[9]
{                            //to b[i][j], if no no. is possible returns 1
printf("Entering assign(i=%d, j=%d, k=%d)\n",i,j,k);
int e[9]={1,2,3,4,5,6,7,8,9};
if(k==9)return 1;
```
One and two letter variable names make it impossible to understand what your code is doing. Yes, YOU know what k, ce, a, b, i, cs and so on all do, but that doesn't help anyone else. Often a code reviewer can work out what code is supposed to do (even if it isn't doing that) if meaningful variable names are used, whereas if the variable names are meaningless then just like if I were to use meaningless one/two letter word replacements, u wd he a cu wa he fk I' gi on bu. OK, you CAN work out what that means, but imagine if my whole update were written like that, or worse still if the letters bore no relation to the word at all. Uq nr kk jl mk ni ni ni pp rz!

6. ### jackspaNew Member

Joined:
Feb 20, 2009
Messages:
11
0
Trophy Points:
0
Ok.I understand the problems which I have created for someone else to understand the program.From here onwards I will take care that.

Now, it seems that you went through the program. Thank you.

Also how do rate this program?I mean to say where does it stand compared to other programs?Did you like it?

7. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,012
203
Trophy Points:
0
Occupation:
Senior Support Engineer
Location:
England

I thought I was. This is what I'm responding to:

> The program goes in infinite loop

So it seems to me that the first thing to do is find out where it goes into the infinite loop, then to find out why it goes into an infinite loop, then rethink the logic once you know exactly what it's doing wrong. The printf technique I outlined gets you answers to the first two parts.

> Also how do rate this program?

Not an easy question to answer really. Apart from the variable naming issue it's not a bad start, although it's very compiler specific (which means I can't run the program). When it has had the bugs ironed out and performs the task it was written for then it will be as good as anything anyone has written.

You might be interested in Simple Sudoku (google it) - this is a free program that generates sudokus and helps you solve them. I've played it a lot.

8. ### jackspaNew Member

Joined:
Feb 20, 2009
Messages:
11
0
Trophy Points:
0
I have developed this program on turbo c++ 3.0 version. This version is available on net at