/*
Below is a complete Console program (single file) that:

builds a valid, fully-solved Sudoku by recursive backtracking,

removes numbers while keeping the puzzle uniquely solvable, and

prints both the puzzle and the solution in the console.

You can paste this into a new Console App (Program.cs) and run.
*/

using System;
using System.Collections.Generic;

class Program
{
    static readonly int Size = 9;
    static readonly int Box = 3;
    static readonly Random Rng = new Random();

    static void Main()
    {
        // 1) Create an empty grid
        int[,] solution = new int[Size, Size];

        // 2) Fill it with a complete valid Sudoku (backtracking)
        if (!FillGrid(solution))
        {
            Console.WriteLine("Failed to generate a full Sudoku solution.");
            return;
        }

        // Make a copy to keep the solution
        int[,] puzzle = CopyGrid(solution);

        // 3) Ask for a difficulty (how many cells to remove)
        Console.Write("Choose difficulty (E=Easy, M=Medium, H=Hard) [default M]: ");
        string diff = (Console.ReadLine() ?? "").Trim().ToUpperInvariant();
        int removeTarget = diff switch
        {
            "E" => 30, // ~30 blanks (51 clues)
            "H" => 50, // ~50 blanks (31 clues)
            _   => 40  // Medium ~40 blanks (41 clues)
        };

        // 4) Carve out cells while keeping uniqueness
        MakePuzzleWithUniqueSolution(puzzle, removeTarget);

        // 5) Print results
        Console.WriteLine();
        Console.WriteLine("=== PUZZLE ===");
        PrintGrid(puzzle);

        Console.WriteLine();
        Console.WriteLine("=== SOLUTION ===");
        PrintGrid(solution);

        Console.WriteLine();
        Console.WriteLine("Press any key to exit...");
        Console.ReadKey();
    }

    // -------------------- Sudoku generation --------------------

    // Fill the grid fully using backtracking (random order for variety)
    static bool FillGrid(int[,] grid)
    {
        int row, col;
        if (!FindEmpty(grid, out row, out col))
        {
            // No empty cell: solved
            return true;
        }

        // Try numbers 1..9 in random order
        foreach (int num in ShuffledNumbers())
        {
            if (IsSafe(grid, row, col, num))
            {
                grid[row, col] = num;
                if (FillGrid(grid)) return true;
                grid[row, col] = 0; // backtrack
            }
        }

        return false; // trigger backtracking
    }

    // Check if placing num at [row,col] obeys Sudoku rules
    static bool IsSafe(int[,] grid, int row, int col, int num)
    {
        // Row
        for (int c = 0; c < Size; c++)
            if (grid[row, c] == num) return false;

        // Column
        for (int r = 0; r < Size; r++)
            if (grid[r, col] == num) return false;

        // 3x3 box
        int r0 = (row / Box) * Box;
        int c0 = (col / Box) * Box;
        for (int r = 0; r < Box; r++)
            for (int c = 0; c < Box; c++)
                if (grid[r0 + r, c0 + c] == num) return false;

        return true;
    }

    // Find the next empty cell (0 = empty). Returns false if none.
    static bool FindEmpty(int[,] grid, out int row, out int col)
    {
        for (int r = 0; r < Size; r++)
            for (int c = 0; c < Size; c++)
                if (grid[r, c] == 0)
                {
                    row = r;
                    col = c;
                    return true;
                }

        row = -1;
        col = -1;
        return false;
    }

    // Return numbers 1..9 in random order
    static IEnumerable<int> ShuffledNumbers()
    {
        List<int> nums = new List<int>(9);
        for (int i = 1; i <= 9; i++) nums.Add(i);
        for (int i = nums.Count - 1; i > 0; i--)
        {
            int j = Rng.Next(i + 1);
            (nums[i], nums[j]) = (nums[j], nums[i]);
        }
        return nums;
    }

    // -------------------- Puzzle carving with uniqueness --------------------

    static void MakePuzzleWithUniqueSolution(int[,] puzzle, int removeTarget)
    {
        // Create a list of all positions [0..80] and shuffle
        List<int> positions = new List<int>(Size * Size);
        for (int i = 0; i < Size * Size; i++) positions.Add(i);

        // Fisher–Yates shuffle
        for (int i = positions.Count - 1; i > 0; i--)
        {
            int j = Rng.Next(i + 1);
            (positions[i], positions[j]) = (positions[j], positions[i]);
        }

        int removed = 0;

        foreach (int pos in positions)
        {
            if (removed >= removeTarget) break;

            int row = pos / Size;
            int col = pos % Size;

            if (puzzle[row, col] == 0) continue; // already empty

            int backup = puzzle[row, col];
            puzzle[row, col] = 0;

            // Check uniqueness: count solutions up to 2
            int solutions = CountSolutions(CopyGrid(puzzle), 2);
            if (solutions == 1)
            {
                removed++;
            }
            else
            {
                // not unique — revert
                puzzle[row, col] = backup;
            }
        }
    }

    // Backtracking solver that counts how many solutions exist (up to 'limit')
    static int CountSolutions(int[,] grid, int limit)
    {
        int count = 0;
        SolveAndCount(grid, ref count, limit);
        return count;
    }

    static void SolveAndCount(int[,] grid, ref int count, int limit)
    {
        if (count >= limit) return; // early stop if enough found

        int row, col;
        if (!FindEmpty(grid, out row, out col))
        {
            // Found one solution
            count++;
            return;
        }

        // Try 1..9 (ordered or random — ordered is slightly faster here)
        for (int num = 1; num <= 9; num++)
        {
            if (IsSafe(grid, row, col, num))
            {
                grid[row, col] = num;
                SolveAndCount(grid, ref count, limit);
                if (count >= limit) return; // early stop
                grid[row, col] = 0;
            }
        }
    }

    // -------------------- Utilities --------------------

    static int[,] CopyGrid(int[,] src)
    {
        int[,] dst = new int[Size, Size];
        for (int r = 0; r < Size; r++)
            for (int c = 0; c < Size; c++)
                dst[r, c] = src[r, c];
        return dst;
    }

    static void PrintGrid(int[,] grid)
    {
        for (int r = 0; r < Size; r++)
        {
            if (r % 3 == 0)
                Console.WriteLine("+-------+-------+-------+");

            for (int c = 0; c < Size; c++)
            {
                if (c % 3 == 0) Console.Write("| ");

                int val = grid[r, c];
                Console.Write(val == 0 ? ". " : (val.ToString() + " "));
            }
            Console.WriteLine("|");
        }
        Console.WriteLine("+-------+-------+-------+");
    }
}
/*
How the algorithm works (step-by-step, in plain words)

1. Board representation
We use a 9x9 int array. 0 means “empty”.

2. Rules as code
A helper IsSafe(row, col, num) checks whether num can be placed at [row,col] (no duplicates in row, column, or 3×3 box).

3. Build a full solution (recursion + backtracking)

Find the next empty cell (top-to-bottom, left-to-right).

Try candidates 1..9 in random order.

If a candidate fits (IsSafe), place it and recurse to the next cell.

If we get stuck, backtrack: remove the number and try the next one.
This eventually fills the board with a valid solution.

4. Make a puzzle by removing numbers

Randomize all 81 cell positions.

Try to remove one cell (set it to 0).

Check uniqueness: run a solution counter (a solver that stops after it finds 2 solutions).

If there’s still exactly 1 solution → keep it removed.

Otherwise restore the number.

Continue until we removed enough numbers for the chosen difficulty (e.g., 40 empties).

5. Print nicely
A helper prints the grid with lines every 3 rows/columns.
*/