Number puzzle help

[dile]

I need to figure out a way to check for conflicts in a Number Puzzle. This is how the number puzzle works....

It has a 1D array of size 81. It is filled with integers from 1-9.
When the user enters a number i need to make sure it's valid by checking if for conflicts with the rest of the grid. this is how the grid looks like:

| 5 7 4 | 6 9 1 | 8 3 2 |
| 9 3 2 | 7 8 5 | 4 6 1 |
| 8 6 1 | 4 2 3 | 5 7 9 |
|-------+-------+-------|
| 1 2 5 | 9 6 8 | 7 4 3 |
| 6 4 3 | 5 7 2 | 1 9 8 |
| 7 8 9 | 1 3 4 | 2 5 6 |
|-------+-------+-------|
| 3 5 7 | 8 1 9 | 6 2 4 |
| 4 9 8 | 2 5 6 | 3 1 7 |
| 2 1 6 | 3 4 7 | 9 8 5 |

So if the user puts a number into the 2nd Row and 3rd column I have to check for conflicts by:
1) make sure that number is not already there on the 2nd row.
2) the number is not already there on the 3rd column
3) and the number isn't there on the 3*3 subregion it's in --> in this case it's the first 3 rows and the first 3 columns.

I know how to check the 1st two parts in a one dimensional array but I don't know how to check the last part.

Any ideas would be greatly appreciated. :)

[BruceWilson512]

You already know how to check parts 1 and 2. You are searching the row and column.

Part 3 is just a hybred of the two. The check for the second row of the 3X3 region is just a smaller subset of when you were doing the row checking.

You might post your code.

Take care,
Bruce

[dile]

I was thinking of changing it into a 2D array and then checking it. Would it be easier to check it like that or just keep it in a 1D array?

[shre86]

i really think it ll be mch easier for you to work with a 2D array..
in case u r using a 1D array u ll have to do some computations to find out which positions to search for..
that should not be very difficult..
just read below..
consider that the positions are from 0-80
ur row pos is x and col pos is y
then use 9*x+y to check for the positons..
where x will be 0,1,2 or 3,4,5 or 6,7,8 depending upon the pos no. is entered and y will be also be 0,1,2 or 3,4,5 or 6,7,8 dependin upon pos entered..
tht shud solve ur prob

[BruceWilson512]

I would do it as a 2D array.

[dile]

i keep getting two errors saying "implicit declaration of function" for the two functions i have. I went through all the code....but i can't figure out where i went wrong. Maybe the way i sent my parameters are wrong?...

int main(int argc, char *argv[])
{
	char letter;

	char *grid;

	FILE *f_read;

	int i,t,p = 0;

	grid = (char *)malloc(sizeof(char) * 9 * 9);

	for( t=0; t <82; t++){
		grid[t]= ' ';
	}
      		
 	if((f_read = fopen(argv[1], "r"))!= NULL) /*checks if file can be opened*/   	
         {
		/*store all characters from file to tempGrid w/out white space*/
            	while ((letter = fgetc(f_read)) != EOF) 
            	{
			/*Store in grid if it's a number*/
               		if (letter != ',' && letter != ' '&& letter != '\t'&& letter != '\n'&& letter !='\r')
			{	
				/*Checks if it's a valid number*/
				if ( grid[i] == ' ')
				{
					grid[i] = letter;
				}
				
				else{ /*Not a valid number. Print error and exit.*/
					fprintf(stderr, "Can't read file.");
					exit(1);
				}
			} 
			/*store a space between two commas*/
			else if (letter == ',')
			{
				i++;
			}

			if (i > 82){
				fprintf(stderr, "Too much data!");
				exit(1);
			}
            	}
         }
   
 	for ( p = 0; p < 82; p++){
		printf("%c",grid[p]);
		if ( p%9 == 0){
			printf("\n");
		}
	}

	checkConflicts(grid); /*check for conflicts in the grid*/

	return 0;
}


/*fuction to check for conflicts in the grid. Pass in a pointer to the grid.*/
void checkConflicts(char *startGrid[]){
 	int row, col = 0;
	int checked = 0;
	int len, conflicts = 0;
	int convert;
	int checkNum[11]; 
	
	initArray(checkNum); /*initialize the array*/

	/*check for conflicts in rows*/
	while( len < 81){
		for (row = 0; row <10; row ++){
			convert = (int)startGrid[len];
			if (checkNum[convert] == 0){
				checkNum[convert]= convert;
			}
			else{
				conflicts++;
			}
			len ++;
		}
		row = 0;
		initArray(checkNum);
	}	

	/*Check for conflicts in columns*/
	for ( col =0; col < 10; col++){
		convert = startGrid[col];
		while (checked < 10){
			if(checkNum[convert] == 0){
				checkNum[convert] = convert;
				checked++;
			}	
			else{
				conflicts++;
				checked++; 
			}
		}
		checked = 0;
		initArray(checkNum);
	}
	

	if (conflicts > 0){
		printf("GRID CONFLICT");
	}
	else{
		printf("NO CONFLICTS");
	}
}


/*function to initialize all elements of an array to zero.*/
void initArray(int *a[]){

	int check = 0;

	/*initialize all values of array to zero*/	
	for ( check = 0; check< 11; check ++){
		a[check] = 0;
	}
}

The error is for the two functions checkConflicts() and initArray()

[BruceWilson512]

dile,

Please include the entire file. For example, I don't see any include files.

Take care,
Bruce

[Dave Sinkula]

If a prototype is not found before the function is called, then you are implicitly defining the function.

[oboler]

Yip. That last post was right. At the very top of your file add:

void checkConflicts(char *startGrid[]);

And magic should happen and everything works.

[oboler]

Ah... you don't have the code for the final check yet in there either.

Doing it should be easy... doing it well on the other hand is an entirely different story.

Here's my idea... I haven't spent very long on this so other might want to propose a more efficient solution...
1) Make a funtion to check the square, it takes an array of 9 digits and returns 1 (ok) or 0 (not ok)
2) in your function make another array checker[9] initialised to 0.
3) Read your input array in order and use the value you read to set that index (-1 ofcourse!) of checker to 1 (true).
4) When you've reached the end, loop over all value sin checker adding them together. If they total 9 you're fine, return 1. Otherwise return 0.

Complexity: Linear time. O(3N) (do N steps for each of: Initialise, record, sum)

The simple solution is O(N^N) as you need to look at N digits N times.

Ofcourse for a program this small doing only one puzzle it's not a problem... if however you wanted to generate piles of puzzles or something it could get important. In anycase it's always better to write efficient code when you can (for the same effort).