using System;
using System.IO;



namespace SudokuBruteForceSolver {
	internal class Program {
		private static byte[,] puzzle = new byte[9,9];
		private static int callCount = 0;
		private static int solutionCount = 0;
		private static string outputFilename;

		private static void Main (string[] args) {
			Console.Clear();
			string filename;
			if (args.Length > 0) filename = args[0];
			else {
				Console.Write("Please enter input file/path: ");
				filename = Console.ReadLine();
			}

			StreamReader inputFile = File.OpenText(filename);
			for (byte i = 0; i < 9; ++i) {
				string line = inputFile.ReadLine();
				if (line.Length != 9) throw new FormatException();
				for (byte j = 0; j < 9; ++j)
					if (Char.IsDigit(line[j])) puzzle[i, j] = (byte)Convert.ToInt32(line[j].ToString());
					else puzzle[i, j] = 0;
			}
			inputFile.Close();
			inputFile.Dispose();

			Console.Write("Please enter output file/path: ");
			outputFilename = Console.ReadLine();
			File.Create(outputFilename).Close();

			Execute();

			Console.Write("Press any key to continue... ");
			Console.ReadKey(true);
		}

		private static bool validDigit (byte a, byte b, byte digit) {
			byte a0 = (byte)(a - a%3), b0 = (byte)(b - b%3);
			for (byte c = 0; c < 9; ++c)
				if (puzzle[a, c] == digit || puzzle[c, b] == digit ||
				    puzzle[a0 + c/3, b0 + c%3] == digit) return false;
			return true;
		}

		// this is my old function that only found one solution
		private static bool solved () {
			Console.SetCursorPosition(0, 1);
			Console.WriteLine("Number of function calls: " + ++callCount);
			for (byte a = 0; a < 9; ++a) {
				for (byte b = 0; b < 9; ++b) {
					if (puzzle[a, b] == 0) Console.Write(' ');
					else Console.Write(puzzle[a, b]);
				}
				Console.Write('\n');
			}
			for (byte a = 0; a < 9; ++a) {
				for (byte b = 0; b < 9; ++b) {
					if (puzzle[a, b] == 0) {
						for (byte digit = 1; digit <= 9; ++digit) {
							if (validDigit(a, b, digit)) {
								puzzle[a, b] = digit;
								if (solved()) return true;
							}
						}
						puzzle[a, b] = 0;
						return false;
					}
				}
			}
			return true;
		}

		// redundant post-calculation check function, checks for summing to 45
		private static bool IsValidSolution() {
			for (byte a = 0; a < 9; ++a) {
				int count1 = 0x1FF, count2 = 0x1FF, count3 = 0x1FF;
				for (byte b = 0; b < 9; ++b) {
					count1 ^= 1 << (puzzle[a, b] - 1);
					count2 ^= 1 << (puzzle[b, a] - 1);
					count3 ^= 1 << (puzzle[3*(a/3) + (b/3), 3*(a%3) + (b%3)] - 1);
				}
				if ((count1 | count2 | count3) != 0) return false;
			}
			return true;
		}

		// output results
		private static void FoundSolution () {
			StreamWriter outputFile = File.AppendText(outputFilename);
			Console.Write("solutions: " + ++solutionCount + ";  calls: " + callCount + "; sudoku: ");
			for (byte a = 0; a < 9; ++a) {
				for (byte b = 0; b < 9; ++b) {
					if (puzzle[a, b] == 0) {
						Console.Write(' ');
						outputFile.Write(' ');
					}
					else {
						Console.Write(puzzle[a, b]);
						outputFile.Write(puzzle[a, b].ToString());
					}
				}
				//Console.Write('\n');
			}
			Console.WriteLine("; valid solution: " + IsValidSolution() + "; END.");
			outputFile.WriteLine("; END.");
			outputFile.WriteLine();
			outputFile.Close();
			outputFile.Dispose();
		}

		// recursive solution finder function
		private static bool Execute () {
			callCount++;
			for (byte a = 0; a < 9; ++a) for (byte b = 0; b < 9; ++b) {
					if (puzzle[a, b] == 0) {
						for (byte digit = 1; digit <= 9; ++digit) {
							if (validDigit(a, b, digit)) {
								puzzle[a, b] = digit;
								if (Execute()) FoundSolution();
							}
						}
						puzzle[a, b] = 0;
						return false;
					}
			}
			return true;
		}

	}
}