I have an assignment, to create a program that solves 9x9 sudoku puzzle. The specifications are the following:
argv[0] isn't necessary, just need to input from keyboard with scanf function)My program allocates a 2D array dynamically, then allocates space to save the filename, then opens the binary file to read data. Using printf to debug my program it seems that data gets saved to importedData array appropriately and when assigning those data on sudoku puzzle, either the program crashes, or doesn't assign the values properly. Here is my code:
Sudoku.c
#include <stdio.h>
#include <stdlib.h>
#include "sudokulib.h"
#define MALLOC_ERROR 0xFF
#define FILE_NOT_FOUND 0xFFF
int main(int argc,char ** argv)
{
char **matrix;
int i,j;
int row,column,num;
FILE * fp;
char * filename;
char * importedData;
matrix=(char **)malloc(9*sizeof(char *));
if (!matrix)
exit(MALLOC_ERROR);
for (i=0;i<9;++i)
{
matrix[i]=(char *)malloc(9*sizeof(char));
if (!matrix[i])
exit(MALLOC_ERROR);
}
initSudoku(matrix);
printf ("Give me the name of data file: ");
filename=(char *)malloc(100*sizeof(char));
if (!filename)
exit(MALLOC_ERROR);
scanf("%s",filename);
fp=fopen(filename,"rb");
if (!fp)
{
printf ("File not found\n");
exit(FILE_NOT_FOUND);
}
importedData=(char *)malloc(sizeof(char)*81*3);
if (!importedData)
exit (MALLOC_ERROR);
fread(importedData,1,243,fp);
i=0;
while (importedData[i] != ' ' && importedData[i+1] != ' ' && importedData[i+2] != ' ' && importedData[i] >= '1' && importedData[i+1] >= '1' && importedData[i+2] >= '1' && importedData[i] <= '9' && importedData[i+1] <= '9' && importedData[i+2] <= '9')
{
row=importedData[i] - 48; /* Convert from ascii code to number */
column=importedData[i+1] - 48;
num=importedData[i+2] - 48;
matrix[row][column]=num;
i=i+3;
}
printf("Sudoku after importing data:\n\n");
printSudoku(matrix);
system("pause");
if (solvePuzzle(matrix))
{
printSudoku(matrix);
}
else
printf ("Puzzle has no solution\n");
fclose(fp);
free(filename);
for (i=0;i<9;++i)
{
free(matrix[i]);
}
free(matrix);
return 0;
}
Sudokulib.h
#include <stdlib.h>
#include <stdio.h>
/* Function Prototypes Begin Here */
void printSudoku(char **);
void initSudoku(char **);
int checkRow(char **,int,int);
int checkCol(char **,int,int);
int check3x3(char **,int,int,int);
int checkIfEmpty(char **,int*,int*);
int solvePuzzle (char **);
/* Function Prototypes End Here */
void printSudoku(char ** Mat)
{
int i,j;
for (i=0;i<9;++i)
{
printf ("-------------------\n");
printf("|");
for (j=0;j<9;++j)
{
printf("%d|",Mat[i][j]);
}
printf("\n");
}
printf ("-------------------\n");
}
void initSudoku(char ** Mat)
{
int i,j;
for (i=0;i<9;++i)
for (j=0;j<9;++j)
Mat[i][j]=0;
}
int checkRow (char ** Mat,int row, int num) // if row is free returns 1 else returns 0
{
int col;
for (col = 0; col < 9; col++)
{
if (Mat[row][col] == num-48)
return 0;
}
return 1;
}
int checkCol (char ** Mat,int col , int num) // if column is free returns 1 else returns 0
{
int row;
for (row = 0; row < 9; row++)
{
if (Mat[row][col] == num-48)
return 0;
}
return 1;
}
int check3x3 (char ** Mat, int row, int col, int num) // if number doesnt exist in the 3x3 grid returns 1 else returns 0
{
row = (row/3) * 3; // set to first row in the grid
col = (col/3) * 3; // set to first col in the grid
int i;
int j;
for (i = 0; i < 3; i++) // grid is 3x3
{
for (j = 0; j < 3; j++)
{
if (Mat[row+i][col+j] == num-48)
return 0;
}
}
return 1;
}
int checkIfEmpty(char ** Mat, int *row, int *col) // if a block of the entire puzzle is empty returns 1 else returns 0 also saves the target row and column it found empty
{
for (*row = 0; *row < 9; *row++)
{
for (*col = 0; *col < 9; *col++)
{
if (Mat[*row][*col] == 0)
return 1;
}
}
return 0;
}
int solvePuzzle (char ** Mat)
{
int num;
int row;
int col;
row = 0;
col = 0;
if (!checkIfEmpty(Mat,&row,&col)) // if puzzle is solved return 1
return 1;
for (num = 1; num < 9; num++)
{
if (checkRow (Mat,row,num) && checkCol (Mat,col,num) && check3x3 (Mat,row,col,num))
{
Mat[row][col] = num-48;
}
if (solvePuzzle (Mat))
{
return 1;
}
Mat[row][col] = 0;
}
return 0;
}
Any help to resolve the aforementioned issue is appreciated.
Also keep in mind that int solvePuzzle() is not quite finished and any suggestions to improve this function are welcome.
EDIT: Here are the contents of binary file data2.bin that causes wrong assignment
142156177191216228257289311329364375418422441484534546562579625663682698739743787794824855883896
Output:
Give me the name of data file: data2.bin
Sudoku after importing data:
-------------------
|0|0|0|0|0|0|0|0|0|
-------------------
|0|0|0|0|2|6|0|7|0|
-------------------
|0|6|8|0|0|7|0|0|9|
-------------------
|0|1|9|0|0|0|4|5|0|
-------------------
|0|8|2|0|1|0|0|0|4|
-------------------
|0|0|0|4|6|0|2|9|0|
-------------------
|0|0|5|0|0|0|3|0|2|
-------------------
|0|0|0|9|3|0|0|0|7|
-------------------
|0|0|4|0|0|5|0|0|3|
-------------------
Press any key to continue . . .
EDIT 2: Found out that if a very small binary file is used that contains very few data e.g. 123245321 works fine, but if data exceed 9 bytes, then the puzzle gets messed up.
Notice that arrays are zero indexed. So you need to subtract one more to get the correct index, example:
row=importedData[i] - 48 - 1;
Also notice that you have too few numbers in your file. There is only 96 but you need 243.
Further...
Look at this:
importedData=(char *)malloc(sizeof(char)*81*3);
...
fread(importedData,1,243,fp);
now you have 243 chars in importedData (something that you should check by looking at the return code from fread. In your case the file only has 96 chars (bad...) but let's just assume it worked).
Then you do:
i=0;
while (importedData[i] != ' ' &&
importedData[i+1] != ' ' &&
importedData[i+2] != ' ' &&
importedData[i] >= '1' &&
importedData[i+1] >= '1' &&
importedData[i+2] >= '1' &&
importedData[i] <= '9' &&
importedData[i+1] <= '9' &&
importedData[i+2] <= '9')
{
....
}
So if the 243 chars that you read all made the condition above true, you'll keep on reading beyond the memory allocated for importedData. So you have undefined behavior.
You need to add:
&& i < 243;
to the condition.
BTW: All these hard code numbers are bad. Use a #define instead.
BTW: Don't do
row=importedData[i] - 48 -1;
but
row=importedData[i] - '0' - 1;