#include <algorithm>
#include <iomanip>
#include <ios>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const char symbolSet9[9] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
const char symbolSet16X[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
const char symbolSet16A[16] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P'};
const char symbolSet25[25] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y'};

int n;
int N;
const char* symbolSet;

string game;
int** neighborLists;
vector<char>* candidateLists;

int boxIndexOf(int index)
{
    return index / N / n * n + index % N / n;
}

bool validate()
{
	// Check length
	if (game.length() != N * N) {
		return false;
	}

	// Check characters
	for (int i = 0; i < N * N; i++) {
		if (game[i] != '.') {
			bool flag = true;

			for (int j = 0; j < N; j++) {
				if (game[i] == symbolSet[j]) {
					flag = false;
					break;
				}
			}
			if (flag) {
				return false;
			}
		}
	}

	// Check positions
	for (int i = 0; i < N * N; i++) {
		for (int j = 0; j < N * N; j++) {
			if (game[i] == '.' || game[j] == '.' || i == j) {
				continue;
			}
            if (i / N == j / N || i % N == j % N || boxIndexOf(i) == boxIndexOf(j)) {
                if (game[i] == game[j]) {
                    return false;
                }
            }
		}
	}
	return true;
}

void makeNeighborLists()
{
	neighborLists = new int*[N * N];

    for (int i = 0; i < N * N; i++) {
		int* list = new int[N * 3 - n * 2 - 1];
		int index = 0;

        for (int j = N * (i / N); j < N * (i / N + 1); j++) {
			if (i == j) {
				continue;
			}
			list[index++] = j;
        }
        for (int j = i % N; j < N * N; j = j + N) {
			if (i == j) {
				continue;
			}
			list[index++] = j;
        }
        for (int j = n * ((i / N) / n); j < n * (((i / N) / n) + 1); j++) {
            for (int k = n * ((i % N) / n); k < n * (((i % N) / n) + 1); k++) {
				if ((i == N * j + k) || (i / N == (N * j + k) / N) || (i % N == (N * j + k) % N)) {
					continue;
				}
                list[index++] = N * j + k;
            }
        }
		sort(list, list + index);
		neighborLists[i] = list;
    }
}

void makeCandidateList(int index)
{
	candidateLists[index].clear();
	if (game[index] == '.') {
		for (int i = 0; i < N; i++) {
			bool flag = true;

			for (int j = 0; j < N * 3 - n * 2 - 1; j++) {
				if (game[neighborLists[index][j]] == symbolSet[i]) {
					flag = false;
					break;
				}
			}
			if (flag) {
				candidateLists[index].push_back(symbolSet[i]);
			}
		}
	}
}

void makeCandidateLists()
{
	candidateLists = new vector<char>[N * N];

	for (int i = 0; i < N * N; i++) {
		vector<char> candidateList;
		candidateList.reserve(N);
		candidateLists[i] = candidateList;
		makeCandidateList(i);
    }
}

bool updateCandidateLists(int cellIndex, int candidateIndex)
{	
	game[cellIndex] = candidateLists[cellIndex][candidateIndex];
	candidateLists[cellIndex].clear();

	for (int i = 0; i < N * 3 - n * 2 - 1; i++) {
		int neighbor = neighborLists[cellIndex][i];

        if (game[neighbor] == '.') {
			vector<char>::iterator iter = candidateLists[neighbor].begin();
			vector<char>::iterator end = candidateLists[neighbor].end();
			iter = find(iter, end, game[cellIndex]);
			if (iter != end) {
				candidateLists[neighbor].erase(iter);
			}

			if (candidateLists[neighbor].empty()) {
                return false;
            }
        }
    }
    return true;
}

void recoverCandidateLists(int index)
{
	char prev = game[index];
	game[index] = '.';
    makeCandidateList(index);

    for (int i = 0; i < N * 3 - n * 2 - 1; i++) {
        if (game[neighborLists[index][i]] == '.') {
			makeCandidateList(neighborLists[index][i]);
        }
    }
}

int uniqueSearch()
{
    for (int i = 0; i < N * N; i++) {
        if (game[i] == '.') {
			for (int j = 0, m = candidateLists[i].size(); j < m; j++) {
				char c = candidateLists[i][j];
				bool row = true;
				bool column = true;
				bool box = true;

				// Scan on rows
				for (int k = N * (i / N); k < N * (i / N + 1); k++) {
					if (game[k] != '.' || k == i) {
						continue;
					}
					for (int q = 0, r = candidateLists[k].size(); q < r; q++) {
						if (candidateLists[k][q] == c) {
							row = false;
							goto next1;
						}
					}
				}
				if (row) {
					candidateLists[i].clear();
					candidateLists[i].push_back(c);
					return i;
				}

next1:
				// Scan on columns
				for (int k = i % N; k < N * N; k = k + N) {
					if (game[k] != '.' || k == i) {
						continue;
					}
					for (int q = 0, r = candidateLists[k].size(); q < r; q++) {
						if (candidateLists[k][q] == c) {
							column = false;
							goto next2;
						}
					}
				}
				if (column) {
					candidateLists[i].clear();
					candidateLists[i].push_back(c);
					return i;
				}

next2:
				// Scan on boxes
				for (int k = n * ((i / N) / n); k < n * ((i / N) / n + 1); k++) {
					for (int l = n * ((i % N) / n); l < n * ((i % N) / n + 1); l++) {
						if (game[N * k + l] != '.' || N * k + l == i) {
							continue;
						}
						for (int q = 0, r = candidateLists[N * k + l].size(); q < r; q++) {
							if (candidateLists[N * k + l][q] == c) {
								box = false;
								goto end;
							}
						}
					}
				}
				if (box) {
					candidateLists[i].clear();
					candidateLists[i].push_back(c);
					return i;
				}

end:
				;
			}
		}
    }
    return -1;
}

void printGame()
{
	if (game == "") {
        cout << "No game was set." << endl;
        return;
    }
    cout << "+";
    for (int i = 1; i < (N + n) * 2 + 1; i++) {
        cout << (i % (n * 2 + 2) == 0 ? "+" : "-");
    }
    cout << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << (j % n == 0 ? "| " : "") << game[N * i + j] << " ";
        }
        cout << "|" << endl;
        if (i % n == n - 1) {
            cout << "+";
            for (int j = 1; j < (N + n) * 2 + 1; j++) {
                cout << (j % (n * 2 + 2) == 0 ? "+" : "-");
            }
            cout << endl;
        }
    }
}

bool solve()
{
    // Search the empty cell that has minimum candidate characters.
    int numCandidates = N + 1;
    int cellIndex = -1;

    for (int i = 0, n = 0; i < N * N; i++) {
        if (game[i] != '.') { // The cell of index i is not empty.
            continue;
        }
		if ((n = candidateLists[i].size()) < numCandidates) {
            numCandidates = n;
            cellIndex = i;
        }
        if (numCandidates == 1) { // best-case
            break;
        }
    }

    // If all cells are not empty, the solution is get.
    if (cellIndex == -1) {
		cout << endl << "Solution: " << endl;
        printGame();
        return true;
    }

	// Scan further if the searching is not best-case.
    if (numCandidates > 1) {
        int newCellIndex = uniqueSearch();

        if (newCellIndex != -1) {
            cellIndex = newCellIndex;
            numCandidates = 1;
        }
    }

    // Allocate the candidate characters to cell one by one.
    // Call solve() recursively if the allocation successes.
    // Retreat if not.
    for (int candidateIndex = 0; candidateIndex < numCandidates; candidateIndex++) {
        if (updateCandidateLists(cellIndex, candidateIndex)) {
            if (solve()) {
                return true;
            } else {
                recoverCandidateLists(cellIndex);
            }
        } else {
            recoverCandidateLists(cellIndex);
        }
    }
    return false;
}

int main()
{
	cout << endl << "***** Sudoku Solver C++ version beta *****" << endl << endl
		<< "TYPE CODE: " << endl
		<< "\t0\t9 by 9, {'1', '2', ..., '9'}" << endl
		<< "\t1\t16 by 16, {'0', '1', ..., '9', 'A', 'B', ..., 'F'}" << endl
		<< "\t2\t16 by 16, {'A', 'B', ..., 'P'}" << endl
		<< "\t3\t25 by 25, {'A', 'B', ..., 'Y'}" << endl << endl
		<< "Enter the type code: ";
	
	int typeCode;
	cin >> typeCode;

	switch (typeCode) {
		case 0:
			n = 3;
			N = 9;
			symbolSet = symbolSet9;
			break;
		case 1:
			n = 4;
			N = 16;
			symbolSet = symbolSet16X;
			break;
		case 2:
			n = 4;
			N = 16;
			symbolSet = symbolSet16A;
			break;
		case 3:
			n = 5;
			N = 25;
			symbolSet = symbolSet25;
			break;
		default:
			cout << "Invalid type code." << endl;
			return 1;
	}

	cout << endl << "Enter the game('.' for empty): " << endl;
	cin >> game;

	if (!validate()) {
		cout << "Invalid game." << endl;
		return 1;
	}

	makeNeighborLists();
	makeCandidateLists();

	if (!solve()) {
		cout << "Cannot solve the game." << endl;
	}
	return 0;
}