Sudoku Solver not working SEG FAULT.?

[CisntEZ]

Hello, I am writing a Sudoku solver and the program does not run and no compiler errors are thrown. All i get is the exe stopped working. The program takes in a string as input and converts it into a 2D char array and then attempts to solve Sudoku. Any help or direction in where my program is failing would help a ton. Thank you.
*EDIT* APPEARS TO BE SEG FAULT LINE 76 why..?

Main.cpp

#include <iostream>
#include <string>

#include "PuzzleClass.h"

int main()
{
	Sudoku game;
	char **board = game.GetInput();

	if (game.Solver(board))
	{
		game.printBoard(board);
	}

	else
	{
		std::cout << "No solution found";
	}

	game.freeBoard(board);

	system("pause");
	return 0;
}

PuzzleClass.h

#pragma once
#include <iostream>
#include <string>
#define NUM_ROWS 9
#define NUM_COLS 9


class Sudoku
{
	public:
		char ** GetInput();
		void freeBoard(char **board);
		void printBoard(char **board);
		bool Solver(char ** board);
		bool FindEmptySquares(char ** board, int &row, int &col);
		bool NotPlayed(char ** board, int row, int col, int number);
		bool UsedInRow(char ** board, int row, int number);
		bool UsedInCol(char ** board, int col, int number);
		bool UsedInBox(char **board, int startingRow, int startingCol, int number);
};

bool Sudoku::UsedInBox(char ** board, int startingRow, int startingCol, int number)
{
	for (int row = 0; row < 3; ++row)
	{
		for (int col = 0; col < 3; ++col)
		{
			if (board[row + startingRow][col + startingCol] == '0' + number)
			{
				return true;
			}
		}
	}
	return false;
}

bool Sudoku::UsedInCol(char ** board, int col, int number)
{
	for (int row = 0; row < NUM_ROWS; ++row)
	{
		if (board[row][col] == '0' + number)
		{
			return true;
		}
	}
	return false;
}
bool Sudoku::UsedInRow(char ** board, int row, int number)
{
	for (int col = 0; col < NUM_COLS; ++col)
	{
		if (board[row][col] == '0' + number)
		{
			return true;
		}
	}
	return false;
}
bool Sudoku::NotPlayed(char ** board, int row, int col, int number)
{
	if ((UsedInRow(board, row, number) && UsedInCol(board, col, number) &&
		UsedInBox(board, row - row % 3, col - col % 3, number)))
	{
		return false;
	}

	return true;
}

bool Sudoku::FindEmptySquares(char ** board, int &row, int &col)
{
	for (int i = 0; row < NUM_ROWS; ++i)
	{
		for (int j = 0; j < NUM_COLS; ++j)
		{
			if (board[i][j] == '0')
			{
				row = i;
				col = j;
				return true;
			}
		}
	}
	return false;
}

bool Sudoku::Solver(char **board)
{
	int row, col;
	char empty = '0';

	if (!FindEmptySquares(board, row, col))
	{
		return true;
	}
	// Check for numbers 1-9
	for (int number = 1; number <= 9; ++number)
	{
		if (NotPlayed(board, row, col, number))
		{
			// Make an assignment tentatively
			board[row][col] = '0' + number;
			
			// If successful return true
			if (Solver(board))
			{
				return true;
			}
			// Else failure, assign an "empty" square and try again
			else
			{
				board[row][col] = empty;
			}
		}
	}
    return false; // trigger backtracking
}

char ** Sudoku::GetInput()
{
	std::string input;
	char **board = new char*[NUM_ROWS];

	//std::cout << "Enter the board, 0 being an empty square" << std::endl;
	//std::cin >> input;

	input = "306508400520000000087000031003010080900863005050090600130000250000000074005206300";
	//input = "007401680186300040900806710609040530070085902850039004090070806268904007005260091";
	for (int row = 0; row < NUM_ROWS; ++row)
	{
		board[row] = new char[NUM_ROWS];
		for (int col = 0; col < NUM_COLS; ++col)
		{
			 board[row][col] = input[col + (row * NUM_COLS)];
		}
	}
	return board;
}

void Sudoku::printBoard(char **board)
{
	for (int row = 0; row < 9; row++)
	{
		for (int col = 0; col < 9; col++)
			std::cout << board[row][col];
		std::cout << "\n";
	}

}

void Sudoku::freeBoard(char **board)
{
	for (int i = 0; i < 81; ++i)
	{
		delete[] board[i];
	}
	delete[] board;
}

[TheIdeasMan]

and no compiler errors are thrown.

I used the cpp.sh compiler with all 3 warnings levels on, pay attention to the last 2 especially:

4:9: warning: #pragma once in main file In member function 'bool Sudoku::UsedInBox(char**, int, int, int)':
27:29: warning: statement has no effect [-Wunused-value]
At global scope:
25:43: warning: unused parameter 'startingRow' [-Wunused-parameter]
In member function 'bool Sudoku::UsedInCol(char**, int, int)':
43:29: warning: statement has no effect [-Wunused-value]
In member function 'bool Sudoku::UsedInRow(char**, int, int)':
55:29: warning: statement has no effect [-Wunused-value]
At global scope: 75:51: warning: unused parameter 'row' [-Wunused-parameter]
75:61: warning: unused parameter 'col' [-Wunused-parameter]
In member function 'bool Sudoku::Solver(char**)':
105:30: warning: statement has no effect [-Wunused-value]
106:13: warning: 'row' may be used uninitialized in this function [-Wmaybe-uninitialized]
102:3: warning: 'col' may be used uninitialized in this function [-Wmaybe-uninitialized]

Btw, avoid using new, invsetigate using an STL container like std::array, this will be easier than 2 levels of pointers. Google RAII.

Also investigate using a debugger, there might be a GUI one in your IDE.

[lastchance]

Part of the problem may be lines 72 to 85. This WON'T return row and col, because you have created new variables with the same names that hide them.

Haven't looked beyond that yet.

[CisntEZ]

Thank you both. dumb mistakes on my part. That helped get to the next step of debugging.

[CisntEZ]

And thank IdeasMan. That is strange I have no warnings. I am using MS visual studio

[MikeyBoy]

Check your options, and increase your warning levels. Level 3 (/W3) is common.

I'd also recommend enabling the option to treat all warnings as errors, because then you're forced to deal with them.

[lastchance]

Are you sure that you want to delete the content of 81 rows on lines 153 to 156?

	for (int i = 0; i < 81; ++i)    // <====== ????   9, not 81
	{
		delete[] board[i];
	}

Personally, I'd use vector<vector<int>> rather than your char**


Also, how are you distinguishing the numbers that were fixed at input (line127ff), since you wouldn't be allowed to empty these (line 112)?

[TheIdeasMan]

I would also recommend having the ability to store up to 9 possible candidates for each cell. By removing the candidates 1 by 1, you then are eventually left with a solution for that cell. Remember that when a cell is solved, one must propagate that through the remaining candidates.

By having 9 candidates for each of the 81 cells, this makes 4 layers of pointers a difficult solution. I hope you are not using pointers because of the new

There are more complex concepts such as locked pairs and locked triples and others, which a program needs to use to solve.

Also be aware there is more than 1 solution for some of the more difficult problems. I have heard of up to 27 separate solutions.

Programs I have seen were about 600 LOC IIRC.

Good Luck

[CisntEZ]

@lastchance Thanks for that I changed it to 9. And the the empty on line 112 just reassigns one of the characters in the array with a zero. Why wouldn't I be allowed to do that?

[lastchance]

CisntEZ wrote:

And the the empty on line 112 just reassigns one of the characters in the array with a zero. Why wouldn't I be allowed to do that?

Sudoku puzzles start with a grid with some of the numbers filled in. These initial ones are fixed. You aren't allowed to change them to zero. However, you may be OK, since (I think) you are only attempting to start from the empty spots. So, it was probably a red herring and you can ignore my comment there.


Incidentally, another reason for using vector<vector<int>> is that you aren't obliged to have 9 by 9 Sudoku grids, but if you have 16 by 16, say, you are going to have trouble if you use char. (But your input would have to deliberately use 0 for a space, rather than '.')

Anyway, my 140 lines of code gave this for your puzzle:

Original
+---+---+---+
|3.6|5.8|4..|
|52.|...|...|
|.87|...|.31|
+---+---+---+
|..3|.1.|.8.|
|9..|863|..5|
|.5.|.9.|6..|
+---+---+---+
|13.|...|25.|
|...|...|.74|
|..5|2.6|3..|
+---+---+---+

Result:
+---+---+---+
|316|578|492|
|529|134|768|
|487|629|531|
+---+---+---+
|263|415|987|
|974|863|125|
|851|792|643|
+---+---+---+
|138|947|256|
|692|351|874|
|745|286|319|
+---+---+---+

[CisntEZ]

Also, I wanted to use an int array[][] or the 2D vector but did not because I wasnt sure how to convert my string input into them.

[CisntEZ]

Thanks. And I will look around and see if I can some how parse my string into a 2D vector.

[CisntEZ]

Do you know of any ways on how I can parse that input string into a 2D vector? I cant see to get it. Thank you.

[Thomas1965]

const int N = 2;

  int num[N][N];  
  /*
    row / col => index
    num[0][0] => 0
    num[0][1] => 1
    num[1][0] => 2
    num[1][1] => 3
  */
  int index = 3;
  int row = index / N;
  int col = index % N;

If you like video tuts have a look at:
https://www.youtube.com/watch?v=IX3qHsLGvq8
https://www.youtube.com/watch?v=P9_F7kuHU90

[CisntEZ]

Thanks. Also it appears I am getting a seg fault on line 76 no idea why

[MikeyBoy]

Look at line 72. Can you see why that loop will never end, and why i will keep incrementing forever, until it causes you to try and access memory beyond the end of the array?

[lastchance]

@CisntEZ,
Please don't change earlier code in the thread once it has been discussed. It makes it impossible to follow the thread, especially regarding line numbers.

Also note that it is better if you upload as a single file, so that we can run it in CPP shell (the little icon to top of a runnable code sample). You can soon separate the headers off into different files later. Please note that it is not conventional to put function definitions in what are expected to be header files (.h).

Cisnt wrote:

Thanks. Also it appears I am getting a seg fault on line 76 no idea why

MikeyBoy has pointed out your confusion over i and row in (what is currently) line 72. Also, the last version of code you have actually posted still has

for (int i = 0; i < 81; ++i)
	{
		delete[] board[i];
	}

As stated earlier, there are NOT 81 rows.

CisntEZ wrote:

Do you know of any ways on how I can parse that input string into a 2D vector?

#include <iostream>
#include <string>
#include <vector>
using namespace std;

using matrix = vector< vector<int> >;

matrix stringToGrid( string s, int n, char blank )
{
   matrix grid( n, vector<int>( n, 0 ) );
   int pos = 0;
   for ( int i = 0; i < n; i++ )
   {
      for ( int j = 0; j < n; j++ )
      {
         if ( s[pos] != blank ) grid[i][j] = s[pos] - '0';
         pos++;
      }
   }

   return grid;
}


int main()
{
  const int N = 9;
  string s{ "306508400520000000087000031003010080900863005050090600130000250000000074005206300" };

  matrix grid = stringToGrid( s, N, '0' );

  for ( auto row : grid )
  {
     for ( auto e : row ) cout << e;
     cout << '\n';
  }
}

306508400
520000000
087000031
003010080
900863005
050090600
130000250
000000074
005206300

Please make your corrections and then post updated code:
- as a SINGLE file;
- BELOW this post.

[CisntEZ]

@Mikeyboy thank you!! I had to change the variables earlier and missed one. The program now runs desired output is not correct but its a start.

@lastchance thank you. and my apologies I thought I was being helpful by updating it but I see now how that can cause an issue.

[CisntEZ]

Here is the updated code. I changed it and put it all in one file so everyone can run it easier.

#include <iostream>
#include <string>

#define NUM_ROWS 9
#define NUM_COLS 9

// Preprocessor directives
char ** GetInput();
void freeBoard(char **board);
void printBoard(char **board);
bool Solver(char ** board);
bool FindEmptySquares(char ** board, int &row, int &col);
bool NotPlayed(char ** board, int row, int col, int number);
bool UsedInRow(char ** board, int row, int number);
bool UsedInCol(char ** board, int col, int number);
bool UsedInBox(char **board, int startingRow, int startingCol, int number);

int main()
{
	char **board = GetInput();

	//game.printBoard(board);
	if (Solver(board))
	{
	    printBoard(board);
	}

	else
	{
		std::cout << "No solution found";
	}

	freeBoard(board);

	//system("pause");
	return 0;
}



bool UsedInBox(char ** board, int startingRow, int startingCol, int number)
{
	for (int row = 0; row < 3; ++row)
	{
		for (int col = 0; col < 3; ++col)
		{
			if (board[row + startingRow][col + startingCol] == '0' + number)
			{
				return true;
			}
		}
	}
	return false;
}

bool UsedInCol(char ** board, int col, int number)
{
	for (int row = 0; row < NUM_ROWS; ++row)
	{
		if (board[row][col] == '0' + number)
		{
			return true;
		}
	}
	return false;
}
bool UsedInRow(char ** board, int row, int number)
{
	for (int col = 0; col < NUM_COLS; ++col)
	{
		if (board[row][col] == '0' + number)
		{
			return true;
		}
	}
	return false;
}
bool NotPlayed(char ** board, int row, int col, int number)
{
	if ((UsedInRow(board, row, number) && UsedInCol(board, col, number))) //&&
		//UsedInBox(board, row - row % 3, col - col % 3, number)))
	{
		return false;
	}

	return true;
}

bool FindEmptySquares(char ** board, int &row, int &col)
{
	char mychar = '0';
	for (int i = 0; i < NUM_ROWS; ++i)
	{
		for (int j = 0; j < NUM_COLS; ++j)
		{
			if (board[i][j] == mychar)
			{
				row = i;
				col = j;
				return true;
			}
		}
	}
	return false;
}

bool Solver(char **board)
{
	int row = 0;
	int col = 0;
	char empty = '0';
	
	if (!FindEmptySquares(board, row, col))
	{
		return true;
	}
	// Check for numbers 1-9
	for (int number = 0; number <= 9; ++number)
	{
		if (NotPlayed(board, row, col, number))
		{
			// Make an assignment tentatively
			board[row][col] = '0' + number;
			
			// If successful return true
			if (Solver(board))
			{
				return true;
			}
			// Else failure, assign an "empty" square and try again
			else
			{
				board[row][col] = empty;
			}
		}
	}
    return false; // trigger backtracking
}

char ** GetInput()
{
	std::string input;
	char **board = new char*[NUM_ROWS];

	//std::cout << "Enter the board, 0 being an empty square" << std::endl;
	//std::cin >> input;

    input = "306508400520000000087000031003010080900863005050090600130000250000000074005206300";

	//input = "007401680186300040900806710609040530070085902850039004090070806268904007005260091";
	
	for (int row = 0; row < NUM_ROWS; ++row)
	{
		board[row] = new char[NUM_ROWS];
		for (int col = 0; col < NUM_COLS; ++col)
		{
			 board[row][col] = input[col + (row * NUM_COLS)];
		}
	}
	


	return board;
}

void printBoard(char **board)
{
	for (int row = 0; row < 9; row++)
	{
		for (int col = 0; col < 9; col++)
			std::cout << board[row][col];
		std::cout << "\n";
	}
}

void freeBoard(char **board)
{
	for (int i = 0; i < 9; ++i)
	{
		delete[] board[i];
	}
	delete[] board;
}

[lastchance]

In your "NotPlayed()" routine you need OR (||), not AND (&&). Try:
if ( UsedInRow(board, row, number) || UsedInCol(board, col, number) || UsedInBox(board, row - row % 3, col - col % 3, number) )


On line 118 you should be placing numbers 1 to 9, not 0 to 9; so:
for (int number = 1; number <= 9; ++number)


Make those two changes and it gives the same result as my solver.