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.
bool mySudoku::CheckRow(int row, int number){ for(int i=0; i< SIZE; i++) { if(Data[row][i] == number)
{
return true;
}
}
return false;
}
Here is my .cpp file
#include "mySudoku.h"
#include <cstdlib>
#include <iostream>
using namespace std;
mySudoku::mySudoku(){ for(int row=0; row < SIZE; row++)
{
for(int col=0; col < SIZE; col++)
{
Data[row][col] = 0;
}
}
}
mySudoku::mySudoku(int anArray[][SIZE]){ 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){
}
mySudoku::~mySudoku(){
}
void mySudoku::ReadPuzzle(){ 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(){ 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){ for(int i=0;i< SIZE; i++) { if(Data[i][col] == number)
{
return true;
}
}
return false;
}
bool mySudoku::CheckRow(int row, int number){ for(int i=0; i< SIZE; i++) { if(Data[row][i] == number)
{
return true;
}
}
return false;
}
bool mySudoku::CheckSubBox(int row, int col, int number){ int startIndexRow = row-row%3; int startIndexCol = col-col%3;
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() { for(int i=0; i<SIZE;i++) { for(int j=0; j<SIZE; j++)
{
if(Data[i][j] == 0)
{
return false;
}
}
}
return true;
}
int mySudoku::SolvePuzzle(int iterations){ int counter=0; while(iterations != 0) {
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
#include <cstdlib>
#include <iostream>
#include "mySudoku.h"
using namespace std;
int main(int argc, char** argv) {
int testArray[9][9];
for(int row=0; row<9; row++)
{
for(int col=0; col<9; col++)
{
testArray[row][col] = 0;
}
}
mySudoku Stest1;
mySudoku Stest2(testArray);
Stest1.ReadPuzzle(); Stest1.CheckCol(1,3); Stest1.CheckRow(1,3); Stest1.CheckSubBox(4,4,5); cout << " iteration: " << Stest1.SolvePuzzle(-1) << endl; Stest1.PrintPuzzle(); cout << "\n";
Stest2.PrintPuzzle();
return 0;
}
And my .h file
#ifndef MYSUDOKU_H
#define MYSUDOKU_H
const int SIZE(9);
class mySudoku {
public:
mySudoku(); mySudoku(int anArray[][SIZE]); mySudoku(const mySudoku& orig);
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 */