Jump to content
  • Singapore prime minister Lee Hsien Loong's Sudoku Solver code runs in 1ms

    aum

    • 491 views
    • 3 minutes
     Share


    • 491 views
    • 3 minutes

    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);
    }

     

    Source

     

    Edited by Karlston


    User Feedback

    Recommended Comments

    There are no comments to display.



    Join the conversation

    You can post now and register later. If you have an account, sign in now to post with your account.
    Note: Your post will require moderator approval before it will be visible.

    Guest
    Add a comment...

    ×   Pasted as rich text.   Paste as plain text instead

      Only 75 emoji are allowed.

    ×   Your link has been automatically embedded.   Display as a link instead

    ×   Your previous content has been restored.   Clear editor

    ×   You cannot paste images directly. Upload or insert images from URL.


  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...