Wrong output in Sudoku Solver?

[ECEsasha]

Hi! I'm trying to make an NxN sudoku solver. I haven't finished the code yet. So far, it should be printing the solved sudoku when the board is blank. Also, I'm going to have the stack reversed and use the stack to print out the board later on. I know that since I assign the values to the board vector, my stack isn't necessary. I just want practice using stacks.
But for now, I just want to make sure that my functions work.
I'm getting this error twice in line 120 of isLegal() and I'm not sure what it means:
invalid operands of types 'int' and '___gnu_cxx::___enable_if<true,double>::__type {aka double}' to binary operator%

EDIT: Alright, now I changed root to int root = static_cast<int> (sqrt(N)); to fix the error above and my code compiles, but my output is the sudoku board full of zeros!

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>

using namespace std;

/* FUNCTION PROTOTYPES: */
bool solveSudoku(vector< vector<int> > &board);
bool findRemainingSlots(vector< vector<int> > &board, int &row, int &column);
bool checkingRow(vector< vector<int> > &board, int row, int value);
bool checkingColumn(vector< vector<int> > &board, int column, int value);
bool checkingBox(vector< vector<int> > &board, int box_row, int box_column, int value);
bool isLegal(vector< vector<int> > &board, int row, int column, int value);

stack<int> solvedSudokuNumbers;	// Stack holding the found values of the solved sudoku board
vector< vector<int> > board;
int N;

/* MAIN FUNCTION */
int main(int argc, char** argv){

	/* For error in inputs */
	if ((argc == 1) || (argc%3 != 2)){
		cout << "Please enter either N, or N followed by multiples of (x,y,value)\n";
		return 1;	// 1 is returned because the number of arguments is incorrect.
	}

	int N = atoi(argv[1]);	// The first input is N, which chooses an NxN sudoku grid
	vector< vector<int> > board(N, vector<int>(N, 0));	// Initializing all values of the sudoku board to 0

	int root = sqrt(N);	// 'root' is the square root of N's nearest integer
	if(root != sqrt(N)){	// If the square root of N is not exactly that integer, a sudoku grid cannot be constructed
		cout << "Your input cannot create a valid Sudoku board";
		return 2;	// 2, returned, means a sudoku grid was not able to be created.
	}


	solveSudoku(board);

	for(int row = 0; row < N; row++){
		for(int column = 0; column < N; column++){
			cout << board[row][column] << " ";
		}
		cout << '\n';
	}

	return 0;
}

bool solveSudoku(vector< vector<int> > &board){	// Function solveSudoku() takes in a vector of integers representing the board.

	int row, column;

	if(!(findRemainingSlots(board, row, column))){	// If there are no 0 values left on the sudoku board,
		return true;	// All the values have been assigned to their appropriate slots!
	}

	for(int value = 1; value <= N; value++){	// Iterating through each possible value!
		if(isLegal(board, row, column, value)){	// If the value is legal for that sudoku board spot,
			board[row][column] = value;	// we assign the value to that location in the board vector
			solvedSudokuNumbers.push(value);	// Putting that number on the top of the solved sudoku spot!
			if(solveSudoku(board)){	// If solveSudoku returns true for every value in the vector board,
				return true;	// then we can finally return true. This is a recursive loop so that solveSudoku will keep calling itself until the value for the whole board is true
			}
		}
	}
	solvedSudokuNumbers.pop();	// If solveSudoku is not true, we get rid of the last number in the stack.
	return false;	// The code reaches here if the solveSudoku is not true yet. This triggers the backtracking! So it will go back and reassign numbers to the previous values.
}

bool findRemainingSlots(vector< vector<int> > &board, int &row, int &column){

	for(row = 0; row < N; row++){				// Double for loop iterates through the sudoku board vector
		for(column = 0; column < N; column++){
			if(board[row][column] == 0){		// If the spot on the board has a value of 0, it doesn't have a value assigned to it yet!
				return true;	// Return true because it's a remaining slot
			}
		}
	}
	return false;	// Return false because there are no remaining slots
}


bool checkingRow(vector< vector<int> > &board, int row, int value){

	for(int column = 0; column < N; column++){	// Iterating through the column...
		if(board[row][column] == value){	// If the value at the column is equal to the current value,
			return true;					// we return true because the value is found and used in the row already
		}
	}
	return false;	// Returns false because the value is not anywhere else in the row
}

bool checkingColumn(vector< vector<int> > &board, int column, int value){

	for(int row = 0; row < N; row++){	// Iterating through the row...	
		if(board[row][column] == value){	// If the value at the row is equal to the current value,
			return true;					// we return true because the value is found and used in the column already.
		}
	}
	return false;	// Returns false because the value is not anywhere else in the column
}

bool checkingBox(vector< vector<int> > &board, int box_row, int box_column, int value){

	for(int row = 0; row < sqrt(N); row++){							// Double for loop iterates through the small boxes of the sudoku board
		for(int column = 0; column < sqrt(N); column++){
			if(board[row+box_row][column+box_column] == value){	// If the value is matched to any of the existing values in the small box of the sudoku board,
				return true;									// we return true because the value is found and used in the small box already.
			}
		}
	}
	return false;	// Returns false because the value is not anywhere else in the small box
}

bool isLegal(vector< vector<int> > &board, int row, int column, int value){

	bool state = (!checkingRow(board, row, value) && !checkingColumn(board, row, value) && !checkingBox(board, row-row%(sqrt(N)), column-column%(sqrt(N))));	// If the value has not been used in the corresponding row, column, and box,
	return state;	// we return true. If not, we return false.

}

[TheIdeasMan]

hi,

Is sqrt(N) returning a double, which you haven't cast to an int?

[ECEsasha]

Ah, it was!

I changed root to int root = static_cast<int> (sqrt(N));, declared it globally, and used root in isLegal. It compiles now! Thanks :D

However, now my code is printing the sudoku board of zeros and I'm not sure why.

[TheIdeasMan]

declared it globally

Don't do that.

However, now my code is printing the sudoku board of zeros and I'm not sure why.

line 56, row & column are not initialised.

HTH

[ECEsasha]

Alrighty! Thanks for the tip :D


Hm, I initialized row and column to 1 and I'm still getting the same output. I'm stumped...

Here is my updated code (ignore the global declaration of root. I haven't changed that yet. I want the functions to work before tweaking):

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>

using namespace std;

/* FUNCTION PROTOTYPES: */
bool solveSudoku(vector< vector<int> > &board);
bool findRemainingSlots(vector< vector<int> > &board, int &row, int &column);
bool checkingRow(vector< vector<int> > &board, int row, int value);
bool checkingColumn(vector< vector<int> > &board, int column, int value);
bool checkingBox(vector< vector<int> > &board, int box_row, int box_column, int value);
bool isLegal(vector< vector<int> > &board, int row, int column, int value);

stack<int> solvedSudokuNumbers;	// Stack holding the found values of the solved sudoku board
vector< vector<int> > board;
int N;
int root;

/* MAIN FUNCTION */
int main(int argc, char** argv){

	/* For error in inputs */
	if ((argc == 1) || (argc%3 != 2)){
		cout << "Please enter either N, or N followed by multiples of (x,y,value)\n";
		return 1;	// 1 is returned because the number of arguments is incorrect.
	}

	int N = atoi(argv[1]);	// The first input is N, which chooses an NxN sudoku grid
	vector< vector<int> > board(N, vector<int>(N, 0));	// Initializing all values of the sudoku board to 0

	int root = static_cast<int> (sqrt(N));	// 'root' is the square root of N's nearest integer

	if(root != sqrt(N)){	// If the square root of N is not exactly that integer, a sudoku grid cannot be constructed
		cout << "Your input cannot create a valid Sudoku board";
		return 2;	// 2, returned, means a sudoku grid was not able to be created.
	}

	solveSudoku(board);

	for(int row = 0; row < N; row++){
		for(int column = 0; column < N; column++){
			cout << board[row][column] << " ";
		}
		cout << '\n';
	}

	return 0;
}

bool solveSudoku(vector< vector<int> > &board){	// Function solveSudoku() takes in a vector of integers representing the board.

	int row = 1;
	int column = 1;

	if(!(findRemainingSlots(board, row, column))){	// If there are no 0 values left on the sudoku board,
		return true;	// All the values have been assigned to their appropriate slots!
	}

	for(int value = 1; value <= N; value++){	// Iterating through each possible value!
		if(isLegal(board, row, column, value)){	// If the value is legal for that sudoku board spot,
			board[row][column] = value;	// we assign the value to that location in the board vector
			solvedSudokuNumbers.push(value);	// Putting that number on the top of the solved sudoku spot!
			if(solveSudoku(board)){	// If solveSudoku returns true for every value in the vector board,
				return true;	// then we can finally return true. This is a recursive loop so that solveSudoku will keep calling itself until the value for the whole board is true
			}
		}
	}
	solvedSudokuNumbers.pop();	// If solveSudoku is not true, we get rid of the last number in the stack.
	return false;	// The code reaches here if the solveSudoku is not true yet. This triggers the backtracking! So it will go back and reassign numbers to the previous values.
}

bool findRemainingSlots(vector< vector<int> > &board, int &row, int &column){

	for(row = 0; row < N; row++){				// Double for loop iterates through the sudoku board vector
		for(column = 0; column < N; column++){
			if(board[row][column] == 0){		// If the spot on the board has a value of 0, it doesn't have a value assigned to it yet!
				return true;	// Return true because it's a remaining slot
			}
		}
	}
	return false;	// Return false because there are no remaining slots
}


bool checkingRow(vector< vector<int> > &board, int row, int value){

	for(int column = 0; column < N; column++){	// Iterating through the column...
		if(board[row][column] == value){	// If the value at the column is equal to the current value,
			return true;					// we return true because the value is found and used in the row already
		}
	}
	return false;	// Returns false because the value is not anywhere else in the row
}

bool checkingColumn(vector< vector<int> > &board, int column, int value){

	for(int row = 0; row < N; row++){	// Iterating through the row...	
		if(board[row][column] == value){	// If the value at the row is equal to the current value,
			return true;					// we return true because the value is found and used in the column already.
		}
	}
	return false;	// Returns false because the value is not anywhere else in the column
}

bool checkingBox(vector< vector<int> > &board, int box_row, int box_column, int value){

	for(int row = 0; row < sqrt(N); row++){							// Double for loop iterates through the small boxes of the sudoku board
		for(int column = 0; column < sqrt(N); column++){
			if(board[row+box_row][column+box_column] == value){	// If the value is matched to any of the existing values in the small box of the sudoku board,
				return true;									// we return true because the value is found and used in the small box already.
			}
		}
	}
	return false;	// Returns false because the value is not anywhere else in the small box
}

bool isLegal(vector< vector<int> > &board, int row, int column, int value){

	bool state = (!checkingRow(board, row, value) && !checkingColumn(board, row, value) && !checkingBox(board, row-row%(root), column-column%(root), value));	// If the value has not been used in the corresponding row, column, and box,
	return state;	// we return true. If not, we return false.

}

[TheIdeasMan]

should row & column be passed as arguments to the solveSudoku function? Otherwise you set them to 1 each time. And they are not being incremented anywhere I can see.

There is another sqrt(N) on lines 110 & 111. Use your root variable there as well.

You have this:

if(root != sqrt(N))

just after working out the value of root, this will always be true. Unless N is zero :+D if N is 9.0 say, then sqrt(N) might be 3.0 + 2e-16 therefore not equal to 3.0, and it is still the wrong type.

Have a go at using a debugger, you can step through your code 1 line a t a time, keep an eye on the value of all your variables, deduce where it all goes wrong.

[ECEsasha]

I feel like it should be so simple, but I'm so stumped as to how I would increment row and column with solveSudoku.

[TheIdeasMan]

Shouldn't you iterate the whole board like you do on lines 77 & 78? Look at your comments on lines 64 & 66

findRemainingSlots finds the first remaining spot, not all of them - do you need another array to store those? Same for the other functions, you return too early.

I am worried about your entire approach to this, I saw some VB code to do this a few years back: It was much more involved than this. You might be able to find that VB code via Google, and look at it's algorithm.

When I do sudoku, firstly I establish the candidate list for each spot: Can it be a 1?, Can it be a 2?, ...... by checking it's row, column & box.

Also have look out for locked pairs & triples, only spot row, only spot column, only spot box etc. When the value for a spot is established, one has to update all it's dependant row, columns & box, to remove the value from the candidate list for each of those spots.

HTH