Singapore PM's Sodoku Solver

sodoku-solver.cpp

#include "stdio.h"


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];

int Count = 0;
int LevelCount[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()
{
     int i, j, valbit, val, Square;
     char ch;
     
     Square = 0;

     for (i = 0; i < 9; i++) {
         if (i % 3 == 0) putc('\n', stdout);
         for (j = 0; j < 9; j++) {
             if (j % 3 == 0) putc(' ', stdout);
             valbit = Entry[Square++];
             if (valbit == 0) ch = '-';
             else {
                 for (val = 1; val <= 9; val++) 
                     if (valbit == (1 << val)) {
                        ch = '0' + val;
                        break;
                     }
             }    
             putc(ch,stdout);
         }
         putc ('\n', stdout);
     }
}


void ConsoleInput()
{
     int i, j;
     char InputString[80];

     for (i = 0; i < 9; i++) {
         printf("Row[%d] : ", i + 1);
         scanf("%s", InputString);

         for (j = 0; j < 9; j++) {
             char ch = InputString[j];
             if (ch >= '1' && ch <= '9') 
                InitEntry(i, j, ch - '0');
         }
     }

     PrintArray();
}


void PrintStats()
{
    int i, j, S;

    printf("\nLevel Counts:\n\n");

    S = 0;
    while (LevelCount[S] == 0) S++;

    i = 0;

    while (S < 81) {
          int Seq = Sequence[S];
          printf("(%d, %d):%4d ", Seq / 9 + 1, Seq % 9 + 1, LevelCount[S]);
          if (i++ > 4){
             printf("\n");
             i = 0;
          }
          S++;
    }

    printf("\n\nCount = %d\n", Count);
}


void Succeed()
{
     PrintArray();
     PrintStats();
}


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)
{
    LevelCount[S]++;
    Count++;

    if (S >= 81) {
       Succeed();
       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);

          Entry[Square] = BLANK; // Could be moved out of the loop
          Block[BlockIndex] |= valbit;
          Row[RowIndex] |= valbit;
          Col[ColIndex] |= valbit;
	}

    SwapSeqEntries(S, S2);
}


int main(int argc, char* argv[])
{
	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;
        LevelCount[Square] = 0;
    }

	for (i = 0; i < 9; i++) 
		Block[i] = Row[i] = Col[i] = ONES;

    ConsoleInput();
    Place(SeqPtr);
    printf("\n\nTotal Count = %d\n", Count);

	return 0;
}

// original code: http://bit.ly/1zfIGMc

example output:

Row[1] : ---------
Row[2] : -----3-85
Row[3] : --1-2----
Row[4] : ---5-7---
Row[5] : --4---1--
Row[6] : -9-------
Row[7] : 5------73
Row[8] : --2-1----
Row[9] : ----4---9

 --- --- ---
 --- --3 -85
 --1 -2- ---

 --- 5-7 ---
 --4 --- 1--
 -9- --- ---

 5-- --- -73
 --2 -1- ---
 --- -4- --9

 987 654 321
 246 173 985
 351 928 746

 128 537 694
 634 892 157
 795 461 832

 519 286 473
 472 319 568
 863 745 219

Level Counts:

(3, 9):   1 (8, 9):   2 (4, 9):   4 (5, 9):   8 (6, 9):  15 (1, 9):  23
(3, 8):  33 (8, 8):  46 (4, 8):  79 (1, 8): 119 (5, 8): 182 (6, 8): 250
(9, 8): 287 (4, 7): 347 (6, 7): 478 (6, 5): 588 (6, 1): 732 (6, 3): 828
(6, 4): 862 (6, 6): 895 (4, 5): 795 (4, 3): 761 (5, 5): 843 (7, 5): 829
(2, 5): 616 (1, 5): 594 (2, 7): 543 (2, 3): 565 (7, 3): 551 (2, 4): 577
(3, 6): 565 (3, 4): 590 (1, 4): 572 (1, 6): 595 (7, 4): 612 (5, 4): 576
(7, 6): 476 (7, 7): 389 (7, 2): 262 (4, 2): 184 (2, 2): 140 (2, 1):  95
(5, 6):  56 (8, 7):  34 (8, 6):  18 (3, 1):  13 (8, 1):  10 (3, 7):   7
(3, 2):   8 (1, 7):  10 (5, 1):  10 (5, 2):   6 (8, 2):   4 (8, 4):   2
(9, 1):   1 (1, 1):   1 (9, 2):   1 (9, 3):   1 (9, 4):   1 (4, 1):   1
(9, 6):   1 (9, 7):   1 (1, 3):   1 (1, 2):   1

Count = 17698


Total Count = 24395

// modified version, original article: https://leetcode.com/problems/sudoku-solver/discuss/15796/Singapore-prime-minister-Lee-Hsien-Loong%27s-Sudoku-Solver-code-runs-in-1ms

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