Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Validity of a given sudoku problem? (http://www.go4expert.com/forums/validity-sudoku-t16604/)

jackspa 20Mar2009 15:56

Validity of a given sudoku problem?
 
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();
}


shabbir 20Mar2009 16:55

Re: Validity of a given sudoku problem?
 
Moved the attachment into the posts

xpi0t0s 20Mar2009 17:26

Re: Validity of a given sudoku problem?
 
Where exactly does it hang?

jackspa 21Mar2009 14:15

Re: Validity of a given sudoku problem?
 
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.

xpi0t0s 21Mar2009 17:09

Re: Validity of a given sudoku problem?
 
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!

jackspa 21Mar2009 22:08

Re: Validity of a given sudoku problem?
 
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?

xpi0t0s 22Mar2009 02:11

Re: Validity of a given sudoku problem?
 
> 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.

jackspa 22Mar2009 21:41

Re: Validity of a given sudoku problem?
 
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?


All times are GMT +5.5. The time now is 06:15.