Pasted

/*
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.
*/