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(); }
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.
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!
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?
> 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.
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?
