sudoku2.cpp

Solve Sudoku(Game) quickly. Just need a txt file with all of the number u have, then answer out.

#include <iostream>
#include <ctime>
#include "list.cpp"

using namespace std;

class Cell
{
	friend class Table;
	int num;
	bool guess;
	int array[9];
public:
	Cell(void) 
	{
		num = 0;
		guess = true;
		for (int i = 0; i<9; i++)
			array[i] = i+1;
		return;
	}
	~Cell(void) {return;}
};

class Table
{
	Cell board[9][9];
	void rowDiagnosis (int array[][9]);
	void colDiagnosis (int array[][9]);
	void squareDiagnosis (int array [][3][9]);
public:
	Table(void) {return;}
	Table (FILE* fpIn);
	~Table(void) {return;}
	bool getNum (int num, int row, int col);
	bool checkSquare (int num, int row, int col);
	bool checkRow (int num, int row);
	bool checkCol (int num, int col);
	void printTable (void);
	int resetBoard (int array [][70]);
	void resetCell (int row, int col) {board[row][col].num = 0; return;}
	void greedy (int numBlankCell, int coor [][70]);
};

int main (void)
{
	FILE* fpIn;
	int coor [2][70];
	int numBlankCell;
	char filepath[255];
	char choice;
	int begin, end;

	cout << "This program solves any sudoku table as long as there is a solution for it. If there is no solution, the program will execute unexpectedly. Proceed at your own risk!\n\t1.Save the sudoku table in to a text file. Put each number in their mirrored position, 0 for blank cell.\n\t2. Save the text file, and enter the file directory when prompted.\n\n";

	do
	{
		cout << "Enter file path: ";
		fgets(filepath, 254, stdin);
		begin = clock();
		filepath[strlen(filepath)-1] = '\0';

		fpIn = fopen(filepath, "r");
		if(!fpIn)
			cout <<"File not found.\n";
		else
		{
			Table sudoku (fpIn);
			fclose(fpIn);

			sudoku.printTable();
			cout << endl;
			numBlankCell = sudoku.resetBoard(coor);

			sudoku.greedy(numBlankCell, coor);
			cout << endl;
			sudoku.printTable();
		}

		end = clock();
		end -= begin;
		cout << "Time: " << end << endl;

		cout << "Repeat? (Y/y for yes, other for no) ";
		cin >> choice;
		while(getchar() != '\n');
	}while(choice == 'y' || choice == 'Y');

	return 0;
}

Table :: Table (FILE* fpIn)
{
	int temp;
	int i,j;
	int rowt, colt;

	for (int row = 0; row<9; row++)
		for (int col = 0; col<9; col++)
		{
			fscanf(fpIn, "%d", &temp);
			if(temp)
			{
				getNum(temp, row, col);
				//reset row
				for (i=0; i<9; i++)
					board[row][i].array[temp-1] = 0;
				//reset col
				for (i=0; i <9; i++)
					board[i][col].array[temp-1] = 0;
				rowt = row/3*3 + 3;
				colt = col/3*3 + 3;
				for (i = rowt-3; i < rowt; i++)
					for (j = colt-3; j<colt; j++)
						board[i][j].array[temp-1] = 0;
			}
		}

	return;
}

bool Table :: getNum (int num, int row, int col)
{
	if(checkSquare(num, row, col) && checkRow (num, row) && checkCol (num, col))
	{
		board[row][col].num = num;
		board[row][col].guess = false;
		return true;
	}
	return false;
}

bool Table ::checkSquare (int num, int row, int col)
{
	row = row / 3 * 3;
	col = col / 3 * 3;
	for (int i = row; i <row+3; i++)
		for (int j = col; j<col+3; j++)
		{
			if(board[i][j].num == num)
				return false;
		}
	return true;
}

bool Table ::checkRow (int num, int row)
{
	for (int col = 0; col<9; col++)
	{
		if(board[row][col].num == num)
			return false;
	}
	return true;
}

bool Table ::checkCol (int num, int col)
{
	for (int row=0; row<9; row++)
	{
		if(board[row][col].num == num)
			return false;
	}
	return true;
}

void Table :: printTable (void)
{
	for (int row = 0; row<9; row++)
	{
		for (int col = 0; col<9; col++)
			cout << board[row][col].num << ' ';
		cout << endl;
	}

	return;
}

int Table ::resetBoard (int array [][70])
{
	int row, col;
	int numBlankCell = 0;

	for (row = 0; row < 9; row++)
		for (col = 0; col < 9; col++)
		{
			if(board[row][col].guess)
			{
				array[0][numBlankCell] = row;
				array[1][numBlankCell] = col;
				numBlankCell++;
			}
		}

	return numBlankCell;
}

void Table :: greedy (int numBlankCell, int coor[][70])
{
	int walker=0;
	bool moveon = true;
	int i;
	int row, col;
	int* prow;
	int* pcol;
	int* pTempCount;
	Stack stack;
	bool tempbool;
	int temp;
	
	while(walker < numBlankCell)
	{
		row = coor[0][walker];
		col = coor[1][walker];

		if(moveon)
		{
			pTempCount = new int (0);
			for (i = 0; i<9; i++)
			{
				if(board[row][col].array[i])
				{
					stack.push(board[row][col].array+i);
					*pTempCount += 1;
				}
			}
			stack.push(pTempCount);
			stack.push(coor[1]+walker);
			stack.push(coor[0]+walker);
		}
	
		prow = (int*)stack.pop();
		pcol = (int*)stack.pop();
		pTempCount = (int*)stack.pop();
		tempbool = false;

		for (i = 0; i < *pTempCount && !tempbool; i++)
		{
			temp = *((int*) stack.pop());
			tempbool = getNum(temp, *prow, *pcol);
		}

		if( i == *pTempCount && !tempbool)
		{
			delete pTempCount;
			resetCell(*prow, *pcol);
			walker--;
			moveon = false;
		}
		else
		{
			*pTempCount -= i;
			stack.push(pTempCount);
			stack.push(pcol);
			stack.push(prow);
			walker++;
			moveon = true;
		}
	}

	while(!stack.emptyStack())
	{
		stack.pop();
		stack.pop();
		pTempCount = (int*)stack.pop();
		for (i = 0; i<*pTempCount; i++)
			stack.pop();
		delete pTempCount;
	}

	return;
}