C# DFS Backtracking with some bit manipulation (beats 100%)


  • 0

    Just used bit masks to handle the possible options for a given empty slot.

    public class Solution {
        const int allOnes = (1 << 9) -1; // 9 bits are set;
        public void SolveSudoku(char[,] board) {
            int[] rowsFixed = new int[9];
            int[] colsFixed = new int[9];
            int[] boxFixed = new int[9];
            List<Tuple<int,int>> emptySlots = new List<Tuple<int,int>>();
            for(int i = 0; i < 9; i++)
            {
                int boxX = i / 3;
                for(int j = 0; j < 9; j++)
                {
                    if (board[i,j] != '.')
                    {
                        int boxY = j / 3;
                        int boxIdx = (3 * boxX) + boxY;
                        int boardVal = board[i,j] - '0';
                        int flag = 1 << (boardVal-1);
                        colsFixed[j] |= flag;
                        rowsFixed[i] |= flag;
                        boxFixed[boxIdx] |= flag;
                    }
                    else {
                        emptySlots.Add(new Tuple<int, int>(i, j));
                    }
                }
            }
            
            BackTrack(0, emptySlots, rowsFixed, colsFixed, boxFixed, board);
        }
        
        public bool BackTrack(int curSlotIdx, List<Tuple<int, int>> slots, int[] rowsFixed, int[] colsFixed, int[] boxFixed, char[,] board)
        {
            if (curSlotIdx == slots.Count())
            {
                return true;
            }
            
            var curSlot = slots.ElementAt(curSlotIdx);
            int boxIdx = 3 * (curSlot.Item1 / 3) + (curSlot.Item2 / 3);
            int slotOptions = allOnes ^ (rowsFixed[curSlot.Item1] | colsFixed[curSlot.Item2] | boxFixed[boxIdx]); 
                    
            for(int i = 0; i < 9; i++)
            {
                if ((slotOptions & (1 << i)) != 0)
                {
                    // set
                    int mask = (1 << i), negMask = ~(1 << i);
                    
                    board[curSlot.Item1, curSlot.Item2] = (char)('0' + (i + 1));
                    colsFixed[curSlot.Item2] |= mask;
                    rowsFixed[curSlot.Item1] |= mask;
                    boxFixed[boxIdx] |= mask;
                    if (BackTrack(curSlotIdx + 1, slots, rowsFixed, colsFixed, boxFixed, board))
                    {
                        return true;
                    }
                    
                    // Unset
                    board[curSlot.Item1, curSlot.Item2] = '.';
                    colsFixed[curSlot.Item2] &= negMask;
                    rowsFixed[curSlot.Item1] &= negMask;
                    boxFixed[boxIdx] &= negMask;
                }
            }
            
            return false;
        }
    }
    

Log in to reply
 

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