Singapore prime minister Lee Hsien Loong's Sudoku Solver code runs in 1ms


  • 36

    Singapore's prime minister Lee Hsien Loong showcased his Sudoku Solver C code. You can read his original Facebook post here and another news reporting it here.

    I have made some slight modification to adapt it so it can be tested on LeetCode OJ. It passed all 6/6 test cases with a runtime of 1 ms. Pretty impressive for a prime minister, huh?

    // Original author: Hsien Loong Lee (http://bit.ly/1zfIGMc)
    // Slight modification by @1337c0d3r to adapt to run on LeetCode OJ.
    // https://leetcode.com/problems/sudoku-solver/
    int InBlock[81], InRow[81], InCol[81];
    
    const int BLANK = 0;
    const int ONES = 0x3fe; 	// Binary 1111111110
    
    int Entry[81];	// Records entries 1-9 in the grid, as the corresponding bit set to 1
    int Block[9], Row[9], Col[9];	// Each int is a 9-bit array
    
    int SeqPtr = 0;
    int Sequence[81];
    
    
    
    void SwapSeqEntries(int S1, int S2)
    {
         int temp = Sequence[S2];
         Sequence[S2] = Sequence[S1];
         Sequence[S1] = temp;
    }
    
    
    void InitEntry(int i, int j, int val)
    {
    	 int Square = 9 * i + j;
    	 int valbit = 1 << val;
         int SeqPtr2;
    
         // add suitable checks for data consistency
         
    	 Entry[Square] = valbit;
    	 Block[InBlock[Square]] &= ~valbit;
    	 Col[InCol[Square]] &= ~valbit; // Simpler Col[j] &= ~valbit;
    	 Row[InRow[Square]] &= ~valbit; // Simpler Row[i] &= ~valbit;
    
         SeqPtr2 = SeqPtr;
         while (SeqPtr2 < 81 && Sequence[SeqPtr2] != Square)
               SeqPtr2++ ;
    
         SwapSeqEntries(SeqPtr, SeqPtr2);
         SeqPtr++;
    }
    
    
    void PrintArray(char **board)
    {
         int i, j, valbit, val, Square;
         char ch;
         
         Square = 0;
    
         for (i = 0; i < 9; i++) {
             for (j = 0; j < 9; j++) {
                 valbit = Entry[Square++];
                 if (valbit == 0) ch = '-';
                 else {
                     for (val = 1; val <= 9; val++) 
                         if (valbit == (1 << val)) {
                            ch = '0' + val;
                            break;
                         }
                 }    
                 board[i][j] = ch;
             }
         }
    }
    
    
    int NextSeq(int S)
    {
        int S2, Square, Possibles, BitCount;
        int T, MinBitCount = 100;
    
        for (T = S; T < 81; T++) {
            Square = Sequence[T];
            Possibles = Block[InBlock[Square]] & Row[InRow[Square]] & Col[InCol[Square]];
            BitCount = 0;
            while (Possibles) {
               Possibles &= ~(Possibles & -Possibles);
               BitCount++;
            }
    
            if (BitCount < MinBitCount) {
               MinBitCount = BitCount;
               S2 = T;
            }
        }
    
        return S2;
    }
    
    
    void Place(int S, char** board)
    {
        if (S >= 81) {
            PrintArray(board);
            return;
        }
    
        int S2 = NextSeq(S);
        SwapSeqEntries(S, S2);
    
        int Square = Sequence[S];
    
        int 	BlockIndex = InBlock[Square],
    			RowIndex = InRow[Square],
    			ColIndex = InCol[Square];
    
        int 	Possibles = Block[BlockIndex] & Row[RowIndex] & Col[ColIndex];
        while (Possibles) {
              int valbit = Possibles & (-Possibles); // Lowest 1 bit in Possibles
              Possibles &= ~valbit;
              Entry[Square] = valbit;
              Block[BlockIndex] &= ~valbit;
              Row[RowIndex] &= ~valbit;
              Col[ColIndex] &= ~valbit;
    				
              Place(S + 1, board);
    
              Entry[Square] = BLANK; // Could be moved out of the loop
              Block[BlockIndex] |= valbit;
              Row[RowIndex] |= valbit;
              Col[ColIndex] |= valbit;
    	}
    
        SwapSeqEntries(S, S2);
    }
    
    void solveSudoku(char **board, int m, int n) {
        SeqPtr = 0;
        int i, j, Square;
    
    	for (i = 0; i < 9; i++)
    		for (j = 0; j < 9; j++) {
    			Square = 9 * i + j;
    			InRow[Square] = i;
    			InCol[Square] = j;
    			InBlock[Square] = (i / 3) * 3 + ( j / 3);
    		}
    
    
    	for (Square = 0; Square < 81; Square++) {
            Sequence[Square] = Square;
    		Entry[Square] = BLANK;
        }
        
    	for (i = 0; i < 9; i++) 
    		Block[i] = Row[i] = Col[i] = ONES;
        
        for (int i = 0; i < 9; ++i)
           for (int j = 0; j < 9; ++j) {
               if ('.' != board[i][j])
                    InitEntry(i, j, board[i][j] - '0');
           }
           
        Place(SeqPtr, board);
    }
    

  • 0
    B

    That is very impressive!


  • 0
    K

    seeing so many bit ops makes me nauseous, but i'm very impressed by 1ms performance


  • 4
    Z

    I can't understand...


  • 0
    K

    The idea is pretty efficient, especially bit manipulation and sequence selecting.


  • 0

  • 0
    B

    I think it is really difficult to understand......


  • 0
    O

    @gschengcong It can't open....


Log in to reply
 

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