62 lines Accepted recursive C# Solution to get ALL Result List (Multiple results if possible)


  • 0
    L
    public class Solution {
        public void SolveSudoku(char[,] board) {
            if (board.GetLength(0) != 9) return;
            if (board.GetLength(1) != 9) return;
            int[,] startIndex = new int[,]{{0, 0}};
            List<char[,]> boards = new List<char[,]>();
            boards.Add(board);
            List<char[,]> results = RecursiveSolver(boards, startIndex);
            if(results.Count > 0)
                Array.Copy(results[0], board, 81);
        }
        private static List<char[,]> RecursiveSolver(List<char[,]> boards, int[,] charIndex)
        {
            List<char[,]> result = new List<char[,]>();
            int[,] newCharIndex = new int[1,2];
            Array.Copy(charIndex, newCharIndex, 2);
            foreach(char[,] b in boards)
            {
                int i = newCharIndex[0, 0];
                int j = newCharIndex[0, 1];
                while (b[i, j] != '.' && i < 9)
                {
                    j = j == 8 ? 0 : j + 1;
                    i = j == 0 ? i + 1 : i;
                    if (i == 9)
                    {
                        result.Add(b);
                        return result;
                    }
                }
                newCharIndex[0, 0] = i;
                newCharIndex[0, 1] = j;
                //Fill out valid numbers
                List<int> validNums = new List<int>();
                int k;
                for (k = 1; k < 10; k++)
                    validNums.Add(k);
                //Remove existing nums from horizontal,vertical,rectangle
                //1) Horizontal
                for (k = 0; k < 9; k++)
                    if (b[i, k] != '.' && validNums.Contains(int.Parse(b[i, k].ToString())))
                        validNums.Remove(int.Parse(b[i, k].ToString()));
                //2) Vertical
                for (k = 0; k < 9; k++)
                    if (b[k, j] != '.' && validNums.Contains(int.Parse(b[k, j].ToString())))
                        validNums.Remove(int.Parse(b[k, j].ToString()));
                //3) Rectangle
                for (k = (i / 3) * 3; k < (i / 3 + 1) * 3; k++)
                    for (int l = (j / 3) * 3; l < (j / 3 + 1) * 3; l++)
                        if (b[k, l] != '.' && validNums.Contains(int.Parse(b[k, l].ToString())))
                            validNums.Remove(int.Parse(b[k, l].ToString()));
                List<char[,]> newresult = new List<char[,]>();
                foreach (int n in validNums)
                {
                    char[,] tmp = new char[9, 9];
                    Array.Copy(b, tmp, 81);
                    tmp[i, j] = n.ToString()[0];
                    newresult.Add(tmp);
                }
                result.AddRange(RecursiveSolver(newresult, newCharIndex));
            }
            return result;
        }
    
    }

Log in to reply
 

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