1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Validity of a given sudoku problem?

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

  1. jackspa

    jackspa New Member

    Joined:
    Feb 20, 2009
    Messages:
    11
    Likes Received:
    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:
    Please help.
    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
    {                               //if add=1, finds next; if add=-1, finds previous
    	do
    	{
    		*j+=add;
    		if(*j==-1||*j==9)
    		{
    			*i+=add;*j=9-(*j)*add;
    		}
    	}
    	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
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,285
    Likes Received:
    364
    Trophy Points:
    83
    Moved the attachment into the posts
     
  3. xpi0t0s

    xpi0t0s Mentor

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

    jackspa New Member

    Joined:
    Feb 20, 2009
    Messages:
    11
    Likes Received:
    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. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    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. jackspa

    jackspa New Member

    Joined:
    Feb 20, 2009
    Messages:
    11
    Likes Received:
    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.

    But you are saying nothing about the validity check I am asking for.Please help.

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

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    > But you are saying nothing about the validity check I am asking for.Please help.

    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. jackspa

    jackspa New Member

    Joined:
    Feb 20, 2009
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    I have developed this program on turbo c++ 3.0 version. This version is available on net at
    "http://www.dei.isep.ipp.pt/~ana/Prog_II/turboc.htm this link.Try running it.

    Also, I am trying to find out where it goes in infinite loop.Thank you for your help.

    If you successfully run it, I am eager to hear any comments.

    Where can I learn other techniques or algorithms of programming? What is this technique of mine called?
     

Share This Page