#include <iostream>
#include <cstring>
#include <vector>
#include <fstream>
#include <string>
#include <cerrno>


int example [9][9] = {
     {0,5,7,4,2,0,0,0,0},
     {0,4,0,0,7,1,0,9,0},
     {2,0,0,0,8,0,0,0,0},
     {0,3,0,7,0,4,2,0,0},
     {0,6,5,8,0,0,3,0,0},
     {0,8,0,9,0,3,0,5,4},
     {8,0,0,0,0,0,7,4,6},
     {9,1,4,0,0,0,0,0,5},
     {5,0,0,0,0,0,0,0,0}
 };


static bool checkint(const char *my_string){
	size_t stringlength = strlen(my_string);
	size_t j;
	for (j=0; j<stringlength; j++)
		if((int)my_string[j] < '0' || (int)my_string[j] > '9') 
			return false;

	return true;
}
 
static int possibleValues(int field[][9], int x, int y, std::vector<int> &ret){
	int existing[9];
	memset(existing, 0, sizeof(int)*9);
	for(int i=0;i<9;i++){
		if(field[y][i])
			existing[field[y][i]-1] = 1;
		if(field[i][x])
			existing[field[i][x]-1] = 1;
	}
	x = (x<3) ? 0 : ((x<6) ? 3 : 6);
	y = (y<3) ? 0 : ((y<6) ? 3 : 6);
	
	for(int i=0; i<3; i++)
		for(int j=0; j<3; j++){
			if(field[y+i][x+j])
				existing[field[y+i][x+j]-1] = 1;
		}
	for(int i=0; i<9; i++){
		if (!existing[i]){
			ret.push_back(i+1);
		}
	}
	return ret.size();
}


static bool getNext(int field[][9], int x, int y, int *new_x, int *new_y){
	x++;
	if(x>8){
		x=0;
		y++;
		if(y>8){
			return false;
		}
	}
	for(int i=y; i<9; i++){
		for(int j=x; j<9; j++){
			x=0;
			if(!field[i][j]){
				*new_x=j;
				*new_y=i;
				return true;
			}
		}
	}	
	return false;
}


static bool solve(int field[][9], int x, int y){
	if(field[y][x]){
		return false; //shouldn't happen
	}
	std::vector<int> pos;
	possibleValues(field, x, y, pos);
	if(pos.size() == 0){
		return false;
	}
	int newx=0;
	int newy=0;
	bool next = getNext(field, x, y, &newx, &newy);

	for(std::vector<int>::iterator it=pos.begin(); it != pos.end(); it++){
		field[y][x] = *it;
		if (!next){
			return true;
		}	
		if(solve(field, newx, newy)){
			return true;
		}
	}
	field[y][x] = 0;

	return false;
}

void printSudoku(int field[][9]){
	std::cout << "---------" << std::endl;
	for(int i=0; i<9; i++){
		for (int j=0; j<9; j++){
			std::cout << field[i][j];
		}
		std::cout << std::endl;
	}
	std::cout << "---------" << std::endl;
}


bool solveSudoku(int field[][9]){
	int startx, starty;
	if(field[0][0] == 0){
		startx = starty = 0;
	} else {
		if(!getNext(field, 0, 0, &startx, &starty)){
			return true; // already solved
		}
	}
	std::cout << "Trying to solve: " << std::endl;
	printSudoku(field);
	std::cout << "    |" << std::endl;
	std::cout << "    V" << std::endl;
	return solve(field, startx, starty);
}


int processFile(char *fname){
	std::string line;
	int buffer[9][9];
	std::ifstream myfile(fname);
	int y=0;
	if (myfile.is_open()) {
		while ( myfile.good()){
			std::getline (myfile, line);
			if (line.empty() || (line.length() != 9 && line.front() != '-')){
				return EINVAL;
			}
			if(y>8){
				if(solveSudoku(buffer)){
					printSudoku(buffer);
				}else{
					std::cout << "Cannot solve :-(" << std::endl;
					std::cout << "---------" << std::endl;
				}
			}
			if(line.front() == '-'){
				y=0;
				continue;
			}
			if(!checkint(line.c_str())){
				std::cerr << "Invalid line: " << line << std::endl;
				return EINVAL;
			}	
			for (int i=0; i<9; i++){
				buffer[y][i] = line.c_str()[i] - '0';
			}
			y++;
		}
		myfile.close();
	} else {
		std::cerr << "Unable to open file" << std::endl;
		return EINVAL;
	}

}


int main(int argc, char **argv) {
	if(argc > 1){
		processFile(argv[1]);
	} else {
		if (solveSudoku(example)){
			std::cout << "First solution found:" << std::endl;
		} else {
			std::cout << "Cannot solve:" << std::endl;
		}
		printSudoku(example);
	}
}