Simple C# Solution that uses HashSets to track current state


  • 0
    F

    The basic idea is to first scan the input board and remember the locations which are already marked. In this scan, we also note the location of the points that are open (the Entry class).

    The heart of the solution is a recursive backtracking algorithm, which tries every possible value for each of the open points, until a solution is found. We use hashSets to track numbers that are already marked within a row, column and the local 3x3 square. The possibilities at any given point therefore should exclude values that are already marked for that point's row, column or local square. ExceptWith on the Set provides a convenient (and efficient) way to do this.

    We do sacrifice O(9^2) (arguably constant) additional space to make this happen.

    public class Entry
    {
        public int row;
        public int col;
    }
    
    public class Solution
    {
        public void SolveSudoku(char[,] board)
        {
            var points = new List<Entry>();
            var rowMap = new List<HashSet<int>>();
            var colMap = new List<HashSet<int>>();
            // localMap tracks the current 3 x 3 square
            var localMap = new List<HashSet<int>>();
    
           Initialize(board, points, rowMap, colMap, localMap);
           SolveSudokuHelper(board, points, rowMap, colMap, localMap, 0);
        }
    
    private bool SolveSudokuHelper(char[,] board, List<Entry> points, List<HashSet<int>> rowMaps, List<HashSet<int>> colMaps, List<HashSet<int>> lMap, int pointIndex)
    {
        var i = points[pointIndex].row;
        var j = points[pointIndex].col;
        var rowMap = rowMaps[i];
        var colMap = colMaps[j];
        var possible = new HashSet<int>(Enumerable.Range(1, 9));
        possible.ExceptWith(rowMap);
        possible.ExceptWith(colMap);
        possible.ExceptWith(lMap[GetLIndex(i, j)]);
    
        if (!possible.Any()) { return false; }
    
        foreach (var elem in possible)
        {
            Mark(elem, i, j, board, rowMap, colMap, lMap[GetLIndex(i, j)]);
            if (pointIndex == points.Count - 1) return true;
            var retval = SolveSudokuHelper(board, points, rowMaps, colMaps, lMap, pointIndex + 1);
            if (retval == true) return true;
            // Assumption - 1 unique solution.
            UnMark(elem, i, j, board, rowMap, colMap, lMap[GetLIndex(i, j)]);
        }
    
        return false;
    }
    
    // Outputs an identifier for the local 3x3 square in range 0 - 8 (both inclusive)
    private int GetLIndex(int i, int j)
    {
        return (3 * (i / 3) + j / 3);
    }
    
    private void Mark(int e, int i, int j, char[,] board, HashSet<int> rowMap, HashSet<int> colMap, HashSet<int> lMap)
    {
        board[i, j] = (char)(e + 0x30);
        rowMap.Add(e);
        colMap.Add(e);
        lMap.Add(e);
    }
    
    private void UnMark(int e, int i, int j, char[,] board, HashSet<int> rowMap, HashSet<int> colMap, HashSet<int> lMap)
    {
        board[i, j] = '.';
        rowMap.Remove(e);
        colMap.Remove(e);
        lMap.Remove(e);
    }
    
    private void Initialize(char[,] board, List<Entry> points, List<HashSet<int>> rowMaps, List<HashSet<int>> colMaps, List<HashSet<int>> lMap)
    {
        for (int i = 0; i < 9; i++)
        {
            lMap.Add(new HashSet<int>());
            rowMaps.Add(new HashSet<int>());
            colMaps.Add(new HashSet<int>());
        }
    
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
            {
                if (board[i, j] == '.')
                {
                    points.Add(new Entry() { row = i, col = j });
                }
                else
                {
                    rowMaps[i].Add((int) board[i, j] - 0x30);
                    colMaps[j].Add((int) board[i, j] - 0x30);
                    lMap[GetLIndex(i, j)].Add(board[i, j] - 0x30);
                }
            }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.