Help with Sudoku code

Question

1.00/5 (1 vote)

See more:

Hey there. I wrote a program that solves Sudoku puzzles but I am not able to execute it properly. The program does not respond after I've fed it input;i.e, the program does not proceed.

Here's the code:

C++

#include<stdio.h>

int rowChk(int grid[][9],int row,int val)
{
	int x;
	for(x=0;x<9;x++)
		if(grid[row][x]==val)
			return 0;
	return 1;
}

int colChk(int grid[][9],int col,int val)
{
	int x;
        for(x=0;x<9;x++)
                if(grid[x][col]==val)
                        return 0;
        return 1;
}

int boxChk(int grid[][9],int row,int col,int val)
{
	row=(row/3)*3;
	col=(col/3)*3;
	for(;row<(row+3);row++)
		for(;col<(col+3);col++)
			if(grid[row][col]==val)
				return 0;
	return 1;
}

void solve(int grid[][9])
{
	int i,j,ch1,ch2,ch3,k,status;
	k=1;
	status=0;
	for(i=0;i<9;i++)
	{	for(j=0;j<9;j++)
		{
			if(grid[i][j]==0 || !status)
			{
				if(k>9)
					k=k%9;
				grid[i][j]=k++;
			}
			ch1=rowChk(grid,i,grid[i][j]);
			ch2=colChk(grid,j,grid[i][j]);
			ch3=boxChk(grid,i,j,grid[i][j]);
			if(ch1&&ch2&&ch3)
				status=1;
			else
				j--;
		}
	}
}		

int main()
{
	int i,j,grid[10][10];
	printf("\n....Sudoku Solver....\n");
	printf("Enter the matrix:\n");
	for(i=0;i<9;i++)
		for(j=0;j<9;j++)
			scanf("%d",&grid[i][j]);
	solve(grid);
	printf("\nSolved puzzle:\n");
	for(i=0;i<9;i++)
	{	for(j=0;j<9;j++)
			printf("%d ", grid[i][j]);
		printf("\n");
	}
	return 0;
}

I tried to identify the bug using gdb...apparently the execution halts at solve() function.

Posted 30-Dec-13 2:19am

hari106

Updated 30-Dec-13 3:21am

Richard MacCutchan

v2

Add a Solution

Comments

ZurdoDev 30-Dec-13 8:20am

Can you step through it and debug it?

[no name] 30-Dec-13 8:43am

The j-- in solve() has the potential to create an endless loop. I would rework this function.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2013-12-30T03:43:00

You need to start gathering information: at present all you have given us is "the program does not proceed" and "apparently the execution halts at solve() function".
This isn't a lot - it's like saying "my car won't start" - it isn't enough to solve the problem, which could be anything from a lack of petrol, through a flat battery, to the engine having exploded ten minutes earlier.

So... you need to work out where it is sitting in the solve function.
So, put a breakpoint on the first for loop in solve, and run your program. When it hits the breakpoint, your program will stop and wait for you before continuing.
Tell it to continue. Does it hit the breakpoint again? If so, it has got through the first iteration of the inner loop, so keep running it until it doesn't come back. Now you know it's one of the passes - and you can kill it, run it again and this time follow it though. You do the same thing when it doesn't come back the first time.

When you know it's going to stop, you start looking for why not - single step through, using the debugger to look at the variables and working out what the line of code it is about to execute will do before it does it. Did it do what you expected? If not, why not?

Gather info, and that tells you what is going on. Without it, you can't fix your problem at all...

nv3 · Answer 2 · 2013-12-30T04:19:00

The reason for the infinte loop in the solve function is that your algorithm has a principal problem. The approach you have take could be described as follows:

Find the next free cell and try entering the digits 1 ... 9 into the cell until there is no conflict in its row, column, and box. Then continue with the next free cell.

The problem with this approach is that the digit you find in this way might be not the only conflict free solution for this cell. And after you have entered a couple of digits in this manner you might have created a situation that is plainly wrong. You won't be able to find a digit for the next free cell without creating a conflict and this is when your program starts to loop.

Also: The handling of your status variable is wrong. It is never being reset.

Help with Sudoku code

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0