using System;

using System.Collections.Generic;

public class Program

{

    //"You may assume that the given Sudoku puzzle will have at least one solution"

    private static char[] GAME_PIECES = {'1','2','3','4','5','6','7','8','9' };

    private static char[] GAME_PIECES_HARD = {'1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G' };

    public static void Main()

    {

        SudokuBoard board = SetupBoard();

        PrintSudokuBoard(board);

        Console.WriteLine(String.Format("Solved board: {0}", Environment.NewLine));

        PrintSudokuBoard(SolveBoardHelper(board));

    }

    // helper function -- returns a completed board or states a solution wasnt found: 

    public static SudokuBoard SolveBoardHelper(SudokuBoard board) {

        List<char> pieces = new List<char>(GAME_PIECES);

        if (board.BoardDifficulty == Difficulty.BG1 || board.BoardDifficulty == Difficulty.BG2 || board.BoardDifficulty == Difficulty.BG3)

            pieces = new List<char>(GAME_PIECES_HARD);

        if (IsSolved(board, pieces))

            return board;

        Console.WriteLine("Board does not have solution");

        return board;

    }

    // recursive function -- checks if board is solved backtracking whenever a potential value isn't valid

    public static bool IsSolved(SudokuBoard board, List<char> pieces) {

        bool foundValue = false;

        Cell loc = new Cell(-1,-1);

        //iterate over the board to get next empty cell to try:

        for (int i = 0; i < board._ROWS; i++) {

            for (int j = 0; j < board._COLS; j++) {

                if (board.BoardArray[i,j] == '.') {

                    loc = new Cell(i,j);

                    foundValue = true;

                    break;

                }

            }

            if (foundValue) 

                break;

        }

        if (loc.ROW == -1 || loc.COL == -1)//we checked the board and there is not an empty cell left

            return true;

        for (int n = 0; n < pieces.Count; n++)

        {

            char val = pieces[n];

            if (IsSafePlacement(board, val, loc.ROW, loc.COL)) 

            {

                board.BoardArray[loc.ROW, loc.COL] = val;

                if (IsSolved(board, pieces))

                    return true;

                else

                    board.BoardArray[loc.ROW,loc.COL] = '.';//backtrack

            }

        }

        return false;

    }

    //This function determines if a possible choice(val) is a valid play - if the play is safe update the BoardArray, else backtrack

    public static bool IsSafePlacement(SudokuBoard board, char val, int row, int col) 

    {

        //iterate the rows of the target column:

        for (int i = 0; i < board._ROWS; i++)

            if (board.BoardArray[i, col] == val)

                return false;

​

        //iterate the columns of the target row:

        for (int j = 0; j < board._COLS; j++)

            if (board.BoardArray[row, j] == val)

                return false;

​

        //iterate the 3x3 or 4x4 subgrid:

        int boardLen = 3;

        if (board.BoardDifficulty == Difficulty.BG1 || board.BoardDifficulty == Difficulty.BG2 || board.BoardDifficulty == Difficulty.BG3) 

            boardLen = 4;

​

        //get topleftmost corner - this was the bit of code that was breaking my backtracking on first submission:

        //int tlR = (row <= boardLen) ? 0 : (row - (row % boardLen));

        //int tlC = (col <= boardLen) ? 0 : (col - (col % boardLen));

        int tlR = row - row % boardLen; 

        int tlC = col - col % boardLen;

        for (int x = tlR; x < (tlR + boardLen); x++) {

            for (int y = tlC; y < (tlC + boardLen); y++) {

                if(board.BoardArray[x,y] == val)

                    return false;

            }

        }

        return true;

    }

    // CLASSES & HELPERS:

    public static SudokuBoard SetupBoard() {

        SudokuBoard board = new SudokuBoard();

        board._ROWS = 9;

        board._COLS = 9;

        Console.Write("Welcome to Sudoku - Enter grid (1 = Easy, 2 = Medium, 3 = Hard, 4-6  = Big Grids): ");

        string input = Console.ReadLine();

        int diff = 1;

        board.BoardDifficulty = Difficulty.Easy;//default

        if(Int32.TryParse(input, out diff))

        {

            switch(diff)

            {

                case 1:

                    break;

                case 2:

                    board.BoardDifficulty = Difficulty.Medium;

                    break;

                case 3:

                    board.BoardDifficulty = Difficulty.Hard;

                    break;

                //extra credit boards:

                case 4:

                    board.BoardDifficulty = Difficulty.BG1;

                    board._ROWS = 16;

                    board._COLS = 16;

                    break;

                case 5:

                    board.BoardDifficulty = Difficulty.BG2;

                    board._ROWS = 16;

                    board._COLS = 16;

                    break;

                case 6:

                    board.BoardDifficulty = Difficulty.BG3;

                    board._ROWS = 16;

                    board._COLS = 16;

                    break;

                default:

                    break;

            }

        }

        board.BoardArray = BuildBoardArrayFromDifficulty(board.BoardDifficulty);

        return board;

    }

    public static char[, ] BuildBoardArrayFromDifficulty(Difficulty difficulty)

    {

        char[, ] arr = new char[9,9] { {'5','3','.','.','7','.','.','.','.'}, {'6','.','.','1','9','5','.','.','.'}, {'.','9','8','.','.','.','.','6','.'}, {'8','.','.','.','6','.','.','.','3'}, {'4','.','.','8','.','3','.','.','1'}, {'7','.','.','.','2','.','.','.','6'}, {'.','6','.','.','.','.','2','8','.'}, {'.','.','.','4','1','9','.','.','5'}, {'.','.','.','.','8','.','.','7','9'} };     

        switch(difficulty)

        {

            case Difficulty.Easy:

                Console.WriteLine("Generating Easy Board...");

                return arr;

            case Difficulty.Medium:

                Console.WriteLine("Generating Medium Board...");

                return new char[9,9] { {'.','.','.','.','6','.','.','.','.'}, {'.','5','.','.','.','.','9','7','.'}, {'.','.','2','.','.','5','.','.','.'}, {'.','.','.','2','.','.','.','8','.' }, {'.','7','4','.','.','.','.','.','.'}, {'.','8','5','.','4','.','2','.','1'}, {'.','.','1','.','.','7','.','.','.'}, {'6','.','.','.','.','4','.','.','.'}, {'9','2','.','6','.','.','1','.','.'} };

            case Difficulty.Hard:

                Console.WriteLine("Generating Hard Board...");

                return new char[9,9] { {'.','.','.','.','.','.','.','.','.'}, {'.','.','.','.','.','.','9','.','.'}, {'9','7','.','3','.','.','.','.','.'}, {'.','1','.','.','6','.','5','.','.'}, {'.','.','4','7','.','8','.','.','2'}, {'.','.','.','.','.','2','.','.','6'}, {'.','3','1','.','.','4','.','.','.'}, {'.','.','.','8','.','.','1','6','7'}, {'.','8','7','.','.','.','.','.','.'} };

            case Difficulty.BG1:

                Console.WriteLine("Generating Big Grid 1...");

                return new char[16,16] { {'.','9','.','.','2','.','3','8','A','.','.','.','.','.','.','.'},{'.','1','.','6','.','.','D','.','.','.','8','.','F','.','B','5'},{'.','.','.','3','.','B','.','.','.','5','.','.','G','.','.','.'},{'7','.','.','F','.','.','.','A','.','.','G','1','.','4','.','.'},{'G','.','.','.','.','.','.','D','.','A','C','7','.','.','.','F'},{'.','.','.','.','1','3','.','F','.','B','.','8','.','.','.','.'},{'1','8','.','A','.','.','.','E','.','.','.','.','2','.','.','6'},{'5','.','.','.','.','.','.','.','.','D','.','.','E','G','4','1'},{'9','.','.','.','E','.','.','.','7','1','.','.','.','A','.','4'},{'.','.','.','.','.','.','1','.','.','9','.','E','C','.','8','.'},{'.','2','C','D','.','.','7','.','4','.','.','.','.','E','5','.'},{'.','4','.','.','.','.','.','.','.','.','D','6','.','.','.','G'},{'.','.','.','.','F','8','B','4','.','.','.','2','A','.','.','.'},{'E','3','.','.','9','7','.','.','6','.','.','.','.','.','.','.'},{'.','F','8','4','.','.','A','.','.','.','5','.','6','.','.','9'},{'.','.','.','.','.','2','.','1','8','.','.','B','.','.','.','D'} };

            case Difficulty.BG2:

                Console.WriteLine("Generating Big Grid 2...");

                return new char[16,16] {{'1','8','7','.','.','.','.','5','A','.','.','.','.','.','.','4'},{'.','.','.','.','B','F','.','4','.','6','3','.','.','.','.','.'},{'D','.','.','.','.','.','1','.','.','.','.','C','.','7','.','.'},{'F','.','.','.','.','7','.','.','2','G','.','4','3','.','.','.'},{'.','.','B','.','3','E','.','.','.','5','.','.','9','1','.','.'},{'.','.','.','C','.','8','.','.','B','.','2','.','E','.','4','G'},{'5','.','E','.','.','.','.','.','.','.','.','.','6','C','.','.'},{'.','.','.','.','F','.','.','1','.','9','.','3','7','.','.','.'},{'G','6','.','E','.','.','7','A','C','.','.','.','.','.','8','B'},{'C','.','.','2','.','.','D','.','5','.','B','.','.','A','.','.'},{'.','.','.','5','.','.','4','3','.','1','.','.','C','6','.','.'},{'.','D','.','9','.','5','.','.','.','.','.','.','.','4','.','2'},{'.','B','.','6','E','D','.','9','G','.','.','.','.','.','2','.'},{'.','.','.','.','.','.','C','.','.','2','.','.','.','.','.','F'},{'E','5','.','.','G','.','2','.','1','3','.','A','.','.','.','D'},{'3','.','.','.','.','.','.','B','7','.','.','8','.','.','6','.'}};

            case Difficulty.BG3:

                Console.WriteLine("Generating Big Grid 3...");

                return new char[16,16] {{'9','.','.','.','.','.','6','.','B','.','.','D','4','8','.','.'},{'4','7','.','.','F','8','.','.','G','.','.','2','.','.','E','C'},{'8','.','.','.','.','7','A','.','.','1','.','.','F','3','.','.'},{'.','.','F','6','.','.','.','B','.','9','5','.','2','.','.','.'},{'.','3','.','C','.','9','.','.','.','.','.','.','.','4','.','7'},{'.','B','.','.','.','.','.','.','.','C','.','6','.','.','.','.'},{'.','9','.','.','8','.','1','7','.','4','.','.','B','.','G','E'},{'.','.','4','G','.','F','5','C','.','3','1','.','8','.','.','.'},{'.','6','.','.','.','4','C','.','3','8','.','.','E','2','.','5'},{'.','.','3','.','.','.','.','2','D','.','E','.','.','7','.','.'},{'.','.','.','F','.','G','.','.','.','.','4','9','.','.','.','3'},{'E','.','.','.','.','.','.','.','2','.','.','7','9','.','8','.'},{'6','.','.','3','.','5','2','E','.','.','.','.','.','.','.','.'},{'.','8','.','.','D','.','.','4','A','.','.','G','C','.','5','.'},{'.','.','5','4','.','.','.','.','.','.','D','.','7','.','.','.'},{'C','2','.','.','.','6','.','.','.','E','9','F','.','.','.','A'}};

            default:

                Console.WriteLine("Invalid difficulty...defaulting to easy grid");

                break;

        }

        return arr;

    }

    // Prints human-readable representation of board:

    static void PrintSudokuBoard(SudokuBoard board) {

        string output = "[" + System.Environment.NewLine;

        for (int i = 0; i < board._ROWS; i++) 

        {

            output += "[";

            for (int j = 0; j < board._COLS; j++) 

            {

                if (j == board._COLS - 1)

                    output += ("'" + board.BoardArray[i,j] + "'");

                else

                    output += ("'" + board.BoardArray[i,j] + "', ");

            }

            if (i == board._ROWS - 1)

                output += ("]" + System.Environment.NewLine);

            else

                output += ("]," + System.Environment.NewLine);

        }

        Console.WriteLine(output += "]");

    }

​

    public class SudokuBoard {

        public int _ROWS, _COLS;

        public char[, ] BoardArray;

        public Difficulty BoardDifficulty;

    }

    public class Cell {

        public int ROW;

        public int COL;

        public Cell(int row, int col)

        {

            this.ROW = row;

            this.COL = col;

        }

    }

    public enum Difficulty {

        Easy,

        Medium,

        Hard,

        BG1,

        BG2,

        BG3

    }

}