Click here to Skip to main content
15,846,038 members
Please Sign up or sign in to vote.
2.00/5 (1 vote)
See more:
My apologies if there is a better way to submit all this information or if this is the wrong forum, I am new to this site.

I have created a Sudoku Solver in C++ which can solve a 9x9 Sudoku for n number of iterations or solve until the puzzle is complete by providing a negative number. The user has the ability to manually input the numbers for the Sudoku puzzle or input a sudoku puzzle text file using file redirection.
$user ./a.out < input.txt

The problem I am facing is that my solver will solve for some puzzles but for others it returns segmentation fault (core dumped).

I am having trouble understanding what could cause this error.

It can solve these two puzzles
2 0 7 0 9 0 4 0 6     
0 4 0 2 6 7 0 5 3
5 0 0 3 8 4 0 0 0
6 0 0 5 2 8 3 0 7
8 2 5 0 3 1 0 0 9
0 0 1 9 4 6 0 2 0
4 0 2 6 1 9 7 0 8
9 1 3 8 0 0 0 0 4
7 0 0 0 5 3 1 9 2

0 0 5 7 1 0 6 8 2
0 3 6 0 4 0 0 7 5
7 0 0 5 8 6 3 4 9
9 8 4 0 5 7 2 0 0
1 5 0 0 0 0 7 9 8
6 7 2 8 0 0 0 0 4
0 6 8 2 0 9 0 1 0
3 4 9 1 0 0 8 2 0
0 1 7 0 3 0 9 0 6


but for example these two puzzles it will return segmentation fault (core dumped)
3 0 0 2 0 0 0 0 0
0 0 0 1 0 7 0 0 0
7 0 6 0 3 0 5 0 0
0 7 0 0 0 9 0 8 0
9 0 0 0 2 0 0 0 4
0 1 0 8 0 0 0 5 0
0 0 9 0 4 0 3 0 1
0 0 0 7 0 2 0 0 0
0 0 0 0 0 8 0 0 6


0 0 0 0 0 3 0 1 7
0 1 5 0 0 9 0 0 8
0 6 0 0 0 0 0 0 0
1 0 0 0 0 7 0 0 0
0 0 9 0 0 0 2 0 0 
0 0 0 5 0 0 0 0 4
0 0 0 0 0 0 0 2 0
5 0 0 6 0 0 3 4 0 
3 4 0 2 0 0 0 0 0


When using a debugger ( with the puzzles that don't work ) the program stops at my first check method in my solve function and returns the error.

C++
//where the debugger returns the error 
bool mySudoku::CheckRow(int row, int number){ //check row for user inputted number 
    	for(int i=0; i< SIZE; i++)            //return true if number is found
	{                                     //false if not
            if(Data[row][i] == number)
            {
				return true;
            }
	}
    return false;
}


Here is my .cpp file
C++
#include "mySudoku.h"
#include <cstdlib>
#include <iostream> 

using namespace std;

mySudoku::mySudoku(){ //default constructor 
    for(int row=0; row < SIZE; row++)
    {
        for(int col=0; col < SIZE; col++)
        {
            Data[row][col] = 0;
        }
    }
    //initalize Array's data to all 0's
}

mySudoku::mySudoku(int anArray[][SIZE]){ //alternate constructor 
    for(int row=0; row < SIZE; row++)
    {
        for(int col=0; col < SIZE; col++)
        {
            Data[row][col] = anArray[row][col];
        }
    }
}

mySudoku::mySudoku(const mySudoku& orig){ //copy constructor
    
}

mySudoku::~mySudoku(){
    //destructor
}

void mySudoku::ReadPuzzle(){  //read the puzzle 
    cout << "Please input values for grid of the puzzle" <<endl;
    for(int row=0;row< SIZE; row++)
    {
        for(int col=0; col< SIZE; col++)
        {
			cout << "Row " << row+1 << " Col " << col+1 << endl;
            cin >> Data[row][col];
        }
    }
    cout << "you have completed inputting values for the grid!" << endl;
}

void mySudoku::PrintPuzzle(){ //prints the puzzle 
    for(int row=0; row < SIZE; row++)
    {
        for(int col=0; col < SIZE; col++)
        {
            cout << Data[row][col] << " ";
        }
        
        cout << endl;
    }
}

bool mySudoku::CheckCol(int col, int number){  //check col for user inputted number
	for(int i=0;i< SIZE; i++)               //return true if number is found 
	{                                       //false if not 
            if(Data[i][col] == number)
            {
                return true;
            }
	}
    return false;
}

bool mySudoku::CheckRow(int row, int number){ //check row for user inputted number 
    	for(int i=0; i< SIZE; i++)            //return true if number is found
	{                                     //false if not
            if(Data[row][i] == number)
            {
				return true;
            }
	}
    return false;
}

bool mySudoku::CheckSubBox(int row, int col, int number){ //check sub box for user inputted number 
    int startIndexRow = row-row%3;					      //return true if number is found
    int startIndexCol = col-col%3;						  //false if not
    
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            if(Data[startIndexRow+i][startIndexCol+j] == number)
            {
                return true; 
            }
        }
    }
    return false; 
}

bool mySudoku::CheckForUnassigned() //checks for unassigned values 
{									//which are denoted by a zero 
	for(int i=0; i<SIZE;i++)		//return true if unassigned value exist 
	{								//false if not 
		for(int j=0; j<SIZE; j++)
		{
			if(Data[i][j] == 0)
			{
				return false;
			}
		}
	}
	return true;

}

int mySudoku::SolvePuzzle(int iterations){ //solves the puzzle on two conditions 
int counter=0;							   //by a certain number of iterations 
while(iterations != 0)					   //or until convergence 
{
	for(int i=0; i < SIZE; i++) 
	{
		for(int j=0; j < SIZE; j++) 
		{
			if(Data[i][j]==0)
			{
				int ansCount=0;
				int ans =0;
				for(int k=1; k < SIZE+1; k++)
				{
					if((CheckRow(i,k)==false)&&(CheckCol(j,k)==false)&&(CheckSubBox(i,j,k)==false))
					{
						ansCount++;
						ans = k;
					}
					
				}
				if(ansCount == 1)
				{
					Data[i][j] = ans;
				}
			}

		}
	}
	if(iterations > 0)
	{
		iterations--;
	}
	else if((iterations < 0) && (CheckForUnassigned()==true))
	{
		counter++; 
		return counter; 
	}
	else if((iterations < 0) && (CheckForUnassigned()==false))
	{
		counter++;
		SolvePuzzle(iterations);
	}

	counter++;

}
 return counter;

}


Here is my main file
C++
#include <cstdlib>
#include <iostream>
#include "mySudoku.h"

using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {
    //initialize test array
    int testArray[9][9]; 
    
    //populate array
    for(int row=0; row<9; row++)
    {
        for(int col=0; col<9; col++)
        {
            testArray[row][col] = 0;
        }
    }
    
    
    //define object mySudoku 
    mySudoku Stest1;
    mySudoku Stest2(testArray);
    
    
    Stest1.ReadPuzzle();    //read puzzle 
    Stest1.CheckCol(1,3);  //check column 
    Stest1.CheckRow(1,3);  //check row
    Stest1.CheckSubBox(4,4,5); //check 3x3 subbox
    cout << " iteration: " << Stest1.SolvePuzzle(-1) << endl;  //solves puzzle test 
    Stest1.PrintPuzzle();   // print puzzle 
    cout << "\n";
    Stest2.PrintPuzzle();
   
    return 0;
}



And my .h file

C++
#ifndef MYSUDOKU_H
#define	MYSUDOKU_H

const int SIZE(9); //constant 

class mySudoku {
public:
    mySudoku(); //default constructor 
    mySudoku(int anArray[][SIZE]); //alternate constructor 
    mySudoku(const mySudoku& orig);//copy constructor 

    //functions 
    void ReadPuzzle(); 
    void PrintPuzzle(); 
    int SolvePuzzle(int iterations);
    bool CheckRow(int row, int number);
    bool CheckCol(int col, int number);
    bool CheckSubBox(int row, int col, int number);
	bool CheckForUnassigned();
    
    virtual ~mySudoku();
private:
    int Data[SIZE][SIZE];
};

#endif	/* MYSUDOKU_H */
Posted
Updated 23-Oct-15 11:42am
v5
Comments
Sergey Alexandrovich Kryukov 23-Oct-15 16:28pm    
This is because you have a bug in your code. :-)
Sorry, but this is not a very good question. It's more of a request: "please do debugging of my project for me". I'm afraid, you may not find an enthusiast to do it for you. You can better luck if you just pinpoint the problem but cannot understand what's problematic in certain part of code. You could come to this part of the problems if you used a debugger; at least you could point out exact line where bad thing happens.
—SA
Alcamech 23-Oct-15 16:31pm    
I did point out the exact line. "When using a debugger ( with the puzzles that don't work ) the program stops at my first check method in my solve function and returns the error. " I honestly cannot understand what is problematic in my code.

Sergey Alexandrovich Kryukov 23-Oct-15 16:39pm    
Excuse me, where? Could you add a comment to the code and refer to this comment in your question?
—SA
Alcamech 23-Oct-15 16:44pm    
I added a comment "//where the debugger returns the error . The CheckRow function is the "first check method" I am referring to. I'm sorry for this not being such a good question. I thought inquiring about what in my code could possibly be generating the error in that section was a valid question, my apologies.
Sergey Alexandrovich Kryukov 23-Oct-15 18:36pm    
Still not clear. Look, such problems are most usually the result of trying to access some memory outside of arrays, by indexing outside of valid range. Also, by accessing memory through a pointer beyond the valid range of memory addresses.
—SA

1 solution

This exception is raised in most cases when your application goes outside of the segment it was assignment, and tries to overwrite or interact with the memory areas that it does not have access to.

I am not sure where that "SIZE" variable (or constant) comes from or what you are doing with it, be the problem is clearly an invalid access or unauthorized access to a memory location where your program does not have access to propagate. Your program may be accessing i from outside the bounds because of this SIZE variable.

You mentioned, the problem is here:

C++
if(Data[row][i] == number)
{
   return true;
}


Maybe, now do yourself a favor, and instead of going deeper in debugging. Re-read the statements,

if, ith element in rowth array of Data is equal to number, then return true.

Now, program would do the same thing. It would try to capture the ith element, from the rowth array in your Data object (where Data is a multi-dimen array). If that is accessible, then it would compare, otherwise if the memory is protected, is not available to your program, is authorized to another program, kernel would simply raise this error and program would terminate. Anyways, read the following resources to understand the problem and solve it by overcoming the causes. :-)

For more please refer to these threads:

http://stackoverflow.com/questions/19641597/what-is-segmentation-fault-core-dumped[^]
http://ubuntuforums.org/showthread.php?t=2071988[^]
http://stackoverflow.com/questions/2346806/what-is-segmentation-fault[^]

https://en.wikipedia.org/wiki/Segmentation_fault[^]
 
Share this answer
 
Comments
Alcamech 23-Oct-15 17:11pm    
The SIZE variable is a constant (9) and it comes from my .h file which I provided.
And if that was the case wouldn't it return the error on every puzzle I try to solve and not just some of them ?

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900