I try to write a sudoku solver I always get a segmentation fault after calling getPossibleElements in solveSudoku. If I delete this line the error doesnt appear.
My Code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SUDOKU_X 8
#define SUDOKU_Y 8
#define MAX_FILENAME 50
#define MAX_POSSIBILITIES 8
typedef enum bool {false, true} bool;
void printPossibilities (bool numbers[], const int pos_x, const int pos_y) {
int i = 0;
for (i = 0; i <= MAX_POSSIBILITIES; i++) {
if (numbers[i]) {
printf("%d ", (i+1));
}
}
}
void getPossibleElements (bool numbers[],int a[][SUDOKU_Y], const int pos_x, const int pos_y) {
int x = 0;
int y = 0;
int i = 0;
int j = 0;
int tmp = 0;
for (x = 0; x <= MAX_POSSIBILITIES; x++) {
numbers[x] = true;
}
/* row */
for (x = 0; x <= SUDOKU_X; x++) {
if (a[pos_y][x] > 0) {
printf("ROW->a[%d][%d]\n",pos_y,x);
printf("ROW->%d\n",a[pos_y][x]-1);
numbers[a[pos_y][x]-1] = false;
}
}
/* coloumn */
for (y = 0; y <= SUDOKU_Y; y++) {
if (a[y][pos_x] > 0) {
printf("coloumn->a[%d][%d]\n",y,pos_x);
printf("coloumn->%d\n",a[y][pos_x]-1);
numbers[a[y][pos_x]-1] = false;
}
}
/* field */
if (pos_x <= 2 && pos_y <= 2) {
x = 0;
y = 0;
}
else if (pos_x <= 5 && pos_y <= 2) {
x = 3;
y = 0;
}
else if (pos_x <= 8 && pos_y <= 2) {
x = 6;
y = 0;
}
else if (pos_x <= 2 && pos_y <= 5) {
x = 0;
y = 3;
}
else if (pos_x <= 5 && pos_y <= 5) {
x = 3;
y = 3;
}
else if (pos_x <= 8 && pos_y <= 5) {
x = 6;
y = 3;
}
else if (pos_x <= 2) {
x = 0;
y = 6;
}
else if (pos_x <= 5) {
x = 3;
y = 6;
}
else if (pos_x <= 8) {
x = 6;
y = 6;
}
printf("DB!!! x=%d y=%d\n", x,y);
for (j = y; j < (y+3); j++) {
for (i = x; i < (x+3); i++) {
if (a[j][i] > 0) {
printf("FIELD->a[%d][%d]\n",j,i);
printf("FIELD->%d\n",(a[j][i])-1);
numbers[(a[j][i])-1] = false;
}
}
}
printf("db");
}
void printSudoku (int a[][SUDOKU_Y]) {
int i = 0;
int j = 0;
printf("-------------------------------\n");
for (j = 0; j <= SUDOKU_X; j++)
{
for (i = 0; i <= SUDOKU_Y; i++) {
if (i == 0) {
printf("|");
}
printf(" %d ",a[j][i]);
if (i == 2 || i == 5 || i == 8) {
printf("|");
}
}
printf("\n");
if (j == 2 || j == 5) {
printf("|-----------------------------|\n");
}
}
printf("-------------------------------\n");
}/* printSudoku */
bool solveSudoku (int a [][SUDOKU_Y]) {
bool numbers[MAX_POSSIBILITIES];
int x = 0;
int y = 0;
printSudoku(a);
getPossibleElements(numbers,a,x,y);
printPossibilities(numbers,x,y);
return true;
}
void readFiletoArray (const char * fileName, int a[][SUDOKU_Y])
{
FILE *fp = fopen(fileName,"r");
int i = 0;
int j = 0;
int val0 = 0;
int val1 = 0;
int val2 = 0;
if( fp == NULL ) {
perror("Error while opening the file.\n");
exit(EXIT_FAILURE);
}
while(fscanf(fp, "%d %d %d", &val0, &val1, &val2) > 0) {
a[j][i++] = val0;
a[j][i++] = val1;
a[j][i++] = val2;
if (i >= 8) {
i = 0;
j++;
}
}
fclose(fp);
} /* readFiletoArray */
int main (int argc, char * argv []) {
int a[SUDOKU_X][SUDOKU_Y];
char fileName[MAX_FILENAME];
bool numbers[MAX_POSSIBILITIES];
bool success = false;
if(argc == 2) {
strncpy(fileName, argv[1], MAX_FILENAME-1);
fileName[MAX_FILENAME] = '\0';
}
else {
printf("ERROR: Invalid Parameter\n");
exit(EXIT_FAILURE);
}
readFiletoArray(fileName, a);
success = solveSudoku(a);
printf("DB");
exit(EXIT_SUCCESS);
} /* Main */
sudoku.txt (Program Parameter)
0 5 9 0 4 0 2 0 0
0 1 0 0 5 0 0 0 7
4 0 0 3 2 9 0 1 5
3 2 0 1 0 0 9 0 0
0 0 7 4 0 6 5 0 0
0 0 4 0 0 5 0 7 8
6 9 0 5 0 3 0 0 4
5 0 0 0 6 0 0 3 0
0 0 8 0 1 0 6 5 0
Thx
At a glance, this is because you are running off the end of the array in various places.
for (x = 0; x <= MAX_POSSIBILITIES; x++) { // 0,1,2...8
See that <= you have there? That's your problem.
numbers is declared as bool numbers[MAX_POSSIBILITIES];, and array indices in C start at 0 and go to length - 1. Zero through seven in this case, but you are trying to access numbers[8].
You have the same issue elsewhere. a is declared as
int a[SUDOKU_X][SUDOKU_Y]; // int a[8][8];
and in getPossibleElements you are iterating from 0 to 8 inclusive, like so:
for (x = 0; x <= SUDOKU_X; x++) {
...
for (y = 0; y <= SUDOKU_Y; y++) {
...thus running off the end of your array again.
Same deal in printPossibilities.
Change MAX_POSSIBILITIES, SUDOKU_X and SUDOKU_Y to be 9 in your #defines and iterate from 0 to 8 by doing
for (x = 0; x < SUDOKU_X; x++) { // 0,1,2...8
One more thing. You should fix your fileName stuff too. Same deal. The last index in an array is length - 1, not length. If you had warnings cranked up when you compiled, it probably would have mentioned this one.
if (argc == 2) {
strncpy(fileName, argv[1], MAX_FILENAME - 2); // was MAX_FILENAME - 1
fileName[MAX_FILENAME - 1] = '\0'; // was [MAX_FILENAME]
}