Sharing my 2ms C++ solution with comments and explanations.


  • 59
    0

    Update: there's a follow-up 0ms solution which is even more optimized

    This is one of the fastest Sudoku solvers I've ever written. It is compact enough - just 150 lines of C++ code with comments. I thought it'd be interesting to share it, since it combines several techniques like reactive network update propagation and backtracking with very aggressive pruning.

    The algorithm is online - it starts with an empty board and as you add numbers to it, it starts solving the Sudoku.

    Unlike in other solutions where you have bitmasks of allowed/disallowed values per row/column/square, this solution track bitmask for every(!) cell, forming a set of constraints for the allowed values for each particular cell. Once a value is written into a cell, new constraints are immediately propagated to row, column and 3x3 square of the cell. If during this process a value of other cell can be unambiguously deduced - then the value is set, new constraints are propagated, so on.... You can think about this as an implicit reactive network of cells.

    If we're lucky (and we'll be lucky for 19 of 20 of Sudokus published in magazines) then Sudoku is solved at the end (or even before!) processing of the input.

    Otherwise, there will be empty cells which have to be resolved. Algorithm uses backtracking for this purpose. To optimize it, algorithm starts with the cell with the smallest ambiguity. This could be improved even further by using priority queue (but it's not implemented here). Backtracking is more or less standard, however, at each step we guess the number, the reactive update propagation comes back into play and it either quickly proves that the guess is unfeasible or significantly prunes the remaining search space.

    It's interesting to note, that in this case taking and restoring snapshots of the compact representation of the state is faster than doing backtracking rollback by "undoing the moves".

    class Solution {
    	struct cell // encapsulates a single cell on a Sudoku board
    	{
    		uint8_t value; // cell value 1..9 or 0 if unset
    		// number of possible (unconstrained) values for the cell
    		uint8_t numPossibilities;
    		// if bitset[v] is 1 then value can't be v
    		bitset<10> constraints;
    		cell() : value(0), numPossibilities(9),constraints() {};
    	};
    	array<array<cell,9>,9> cells;
    
    	// sets the value of the cell to [v]
    	// the function also propagates constraints to other cells and deduce new values where possible
    	bool set(int i, int j, int v)
    	{ 
    		// updating state of the cell
    		cell& c = cells[i][j];
    		if (c.value == v)
    			return true;
    		if (c.constraints[v])
    			return false;
    		c.constraints = bitset<10>(0x3FE); // all 1s
    		c.constraints.reset(v);
    		c.numPossibilities = 1;
    		c.value = v;
    
    		// propagating constraints
    		for (int k = 0; k<9; k++) {
    			// to the row: 
    			if (i != k && !updateConstraints(k, j, v))
    				return false;
    			// to the column:
    			if (j != k && !updateConstraints(i, k, v))
    				return false;
    			// to the 3x3 square:
    			int ix = (i / 3) * 3 + k / 3;
    			int jx = (j / 3) * 3 + k % 3;
    			if (ix != i && jx != j && !updateConstraints(ix, jx, v))
    				return false;
    		}
    		return true;
    	}
    	// update constraints of the cell i,j by excluding possibility of 'excludedValue'
    	// once there's one possibility left the function recurses back into set()
    	bool updateConstraints(int i, int j, int excludedValue)
    	{
    		cell& c = cells[i][j];
    		if (c.constraints[excludedValue]) {
    			return true;
    		}
    		if (c.value == excludedValue) {
    			return false;
    		}
    		c.constraints.set(excludedValue);
    		if (--c.numPossibilities > 1)
    			return true;
    		for (int v = 1; v <= 9; v++) {
    			if (!c.constraints[v]) {
    				return set(i, j, v);
    			}
    		}
    		assert(false);
    	}
    
    	// backtracking state - list of empty cells
    	vector<pair<int, int>> bt;
    
    	// find values for empty cells
    	bool findValuesForEmptyCells()
    	{
    		// collecting all empty cells
    		bt.clear();
    		for (int i = 0; i < 9; i++) {
    			for (int j = 0; j < 9; j++) {
    				if (!cells[i][j].value)
    					bt.push_back(make_pair(i, j));
    			}
    		}
    		// making backtracking efficient by pre-sorting empty cells by numPossibilities
    		sort(bt.begin(), bt.end(), [this](const pair<int, int>&a, const pair<int, int>&b) {
    			return cells[a.first][a.second].numPossibilities < cells[b.first][b.second].numPossibilities; });
    		return backtrack(0);
    	}
    
    	// Finds value for all empty cells with index >=k
    	bool backtrack(int k)
    	{
    		if (k >= bt.size())
    			return true;
    		int i = bt[k].first;
    		int j = bt[k].second;
    		// fast path - only 1 possibility
    		if (cells[i][j].value)
    			return backtrack(k + 1);
    		auto constraints = cells[i][j].constraints;
    		// slow path >1 possibility.
    		// making snapshot of the state
    		array<array<cell,9>,9> snapshot(cells);
    		for (int v = 1; v <= 9; v++) {
    			if (!constraints[v]) {
    				if (set(i, j, v)) {
    					if (backtrack(k + 1))
    						return true;
    				}
    				// restoring from snapshot,
    				// note: computationally this is cheaper
    				// than alternative implementation with undoing the changes
    				cells = snapshot;
    			}
    		}
    		return false;
    	}
    public:
    	void solveSudoku(vector<vector<char>> &board) {
    		cells = array<array<cell,9>,9>(); // clear array
    		// Decoding input board into the internal cell matrix.
    		// As we do it - constraints are propagated and even additional values are set as we go
    		// (in the case if it is possible to unambiguously deduce them).
    		for (int i = 0; i < 9; i++)
    		{
    			for (int j = 0; j < 9; j++) {
    				if (board[i][j] != '.' && !set(i, j, board[i][j] - '0'))
    					return; // sudoku is either incorrect or unsolvable
    			}
    		}
    		// if we're lucky we've already got a solution,
    		// however, if we have empty cells we need to use backtracking to fill them
    		if (!findValuesForEmptyCells())
    			return; // sudoku is unsolvable
    
    		// copying the solution back to the board
    		for (int i = 0; i < 9; i++)
    		{
    			for (int j = 0; j < 9; j++) {
    				if (cells[i][j].value)
    					board[i][j] = cells[i][j].value + '0';
    			}
    		}
    	}
    };
    

  • 1
    O

    2ms, is extremely fast


  • 0
    L

    OMG, super fast!!!


  • -2
    S

    a more concise solution present here

    class Solution {
    public:
        void solveSudoku(vector<vector<char>>& board) {
            vector<pair<int,int>> vect;
            for(int i=0;i<board.size();i++)
                for(int j=0;j<board[0].size();j++)
                    if(board[i][j]=='.')
                        vect.push_back({i,j});
            solve(board,vect,0);
        }
        
        bool solve(vector<vector<char>>&board,vector<pair<int,int>> pos,int cur){
            if(cur>=pos.size())return true;
            else{
                int x=pos[cur].first,y=pos[cur].second;
                for(int i=0;i<9;i++){//try each
                    int ok=1;
                    char c=i+'1';
                    for(int j=0;j<9;j++)
                        if(board[x][j]==c||board[j][y]==c){ok=0;break;}
                    int xs=x/3*3,ys=y/3*3;
                    for(int z=xs;z<xs+3;++z)
                        for(int w=ys;w<ys+3;++w)
                            if(board[z][w]==c)
                                ok=0;
                    if(ok){
                        board[x][y]=c;
                        if(solve(board,pos,cur+1))return true;
                        board[x][y]='.';
                    }
                }
            }
            return false;
        }
    };

  • 0
    K

    I submitted it and it runs 0ms


  • 0
    Z

    terrific!!!!!!!!!!!!!!!


  • 0
    0

    terrific!!!!!!!!!!!!!!!

    Thank you.

    See also a follow-up solution, which is an optimized version of this one:
    https://leetcode.com/discuss/59649/yet-another-0ms-c-solution

    I submitted it and it runs 0ms

    Yes, I think LeetCode improved both hardware and runtime since the moment when this was published for the first time.


  • 0
    Z

    thanks a lot!!!


  • 0
    X

    Fantastic ~~~!!!!!!!


  • 0
    Z

    @stealflowercow good algorithm!I like it!


  • 0

    Amazing solution for this problem!


  • 0

    @stealflowercow really concise and brilliant one!


  • 0
    M

    @0xF4 I'm trying to come up with a Python version of this program but am going wrong somewhere. I spent hours on this. Can you help?

    class Cell:    
        def __init__(self):
            self.numPossibilities = 9
            self.notPossible = [0] * 10
            self.value = 0
        
    class Solution(object):
        def setCell(self, i, j, val, cells):
    
            if cells[i][j].value == val:
                return True
            if cells[i][j].notPossible[val]:
                return False
            cells[i][j].notPossible = [1] * 10
            cells[i][j].notPossible[val] = 0
            cells[i][j].value = val
            cells[i][j].numPossibilities = 1
             
            for k in range(9):
                if i != k and not self.updatePossibilities(k, j, val, cells):           
                    return False
                if j != k and not self.updatePossibilities(i, k, val, cells):      
                    return False
                bRow = (i / 3) * 3 +  k / 3
                bCol = (j / 3) * 3 + k % 3
                if i != bRow and j != bCol and not self.updatePossibilities(bRow, bCol, val, cells):
                    return False
    
            return True
    
    def updatePossibilities(self, row, col, v, cells):
        #for i in range(9):
            #for j in range(9):
                #if cells[i][j].value:
                    #print cells[i][j].value  
        
        print row, col, v
        if cells[row][col].notPossible[v]:
            return True
        if cells[row][col].value == v:
            return False
        cells[row][col].notPossible[v] = 1
        cells[row][col].numPossibilities -= 1
    
        if cells[row][col].numPossibilities > 1:
            return True
        for d in range(1, 10):
           
            if not cells[row][col].notPossible[d]:
                return self.setCell(row, col, d, cells)
                    
    
    
    def findEmptyCellValues(self, cells):
        emptyCells = []
        for i in range(9):
            for j in range(9):
                if not cells[i][j].value:
                    emptyCells.append((i, j))
    
        emptyCells.sort(key = lambda tup: cells[tup[0]][tup[1]].numPossibilities)    
        #for tup in emptyCells:
            #print tup
        return self.solveBacktrack(0, emptyCells, cells)
    
    def solveBacktrack(self, idx, emptyCells, cells):
    
        if idx == len(emptyCells):
            return True      
        row = emptyCells[idx][0]
        col = emptyCells[idx][1]
        if cells[row][col].value:
            return self.solveBacktrack(idx+1, emptyCells, cells)
        deep = copy.deepcopy(cells)
        for k in range(1, 10):        
            if not cells[row][col].notPossible[k]:
                if self.setCell(row, col, k, cells):
                    if self.solveBacktrack(idx+1, emptyCells, cells):
                        return True
                cells = deep
    
        return False
    
            
        
        
        
    def solveSudoku(self, board):
        cells = [[Cell() for i in range(9)] for j in range(9)]
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.' and not self.setCell(i, j, ord(board[i][j]) - ord("0"), cells):                   
                    return 
    
        if not self.findEmptyCellValues(cells):
    
            return
        
        for i in range(9):
            for j in range(9):
                if cells[i][j].value:
                    board[i][j] = str(cells[i][j].value)
        return
    

  • 0
    S

    Amazing! Thank you!


  • 0
    S

    A way in which you can make the algorithm even faster is by going through each cell and picking the cell with the fewest number of possibilities first in the tree. You're kind of already doing this by setting all the cells that have 1 valid option left to become such number. But (especially for large problems) by looking up the cell with the higher number of constraints (aka fewer options), the solution will require exponentially fewer computations.


Log in to reply
 

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