Maybe the fastest and most Object-oriented solution


  • 0
    C

    The problem is pretty primitive, it promised there's just one answer, so what you need to do is backtracing. Filling all the blank cells and checking its validation.

    Optimization:

    • if there's no number could be placed into a blank cell, cut the sub-search-tree
    • everytime, find a blank cell which has the minimum probability to place number. In other words, this blank cell has the maximum probability to help you cut your sub-search-tree

    For the optimization tip 2, I call it fillStrategy. Which blank cell will I go to place number? The answer is given by fillStrategy.Maybe there's lots of strategies, but I think the easiest one is by finding a row(or col or rectangle) which has already been placed the most number than any other rows(or cols or rectangles).
    To implement the strategy, I just set some counters to record the total number each row has been placed so that I can find that blank cell by traversing all the counters.
    A better way is using heap rather than an array of counters, because each time you want to know is just the maximum or minimum...

    So the process may look like:

    1. initialization
    2. call fillStrategy to get a cell
    3. try to place a number in that cell
    4. check the validation
    5. if invalid, backtrace
    6. if ok, jump to step 2

    Here's my 0ms solution:

    type fillType byte
    
    const (
    	_ fillType = iota
    	cFillCol
    	cFillRow
    	cFillSquare
    )
    
    type sudokuState struct {
    	flagCol, flagRow, flagSquare    [9][10]bool
    	countCol, countRow, countSquare [9]byte
    	grid                            [9][9]byte
    	counter                         int
    }
    
    func (state *sudokuState) fillNumber(i, j, number int) bool {
    	if !state.canFill(i, j, number) {
    		return false
    	}
    	state.update(i, j, number)
    	return true
    }
    
    func (state *sudokuState) finished() bool {
    	return state.counter == 81
    }
    
    func (state *sudokuState) canFill(i, j, number int) bool {
    	if state.grid[i][j] != 0 {
    		return false
    	}
    	if number == 0 {
    		return true
    	}
    	return !(state.flagCol[i][number] || state.flagRow[j][number] || state.flagSquare[state.getSquare(i, j)][number])
    }
    
    func (state *sudokuState) update(i, j, number int) {
    	state.flagCol[i][number] = true
    	state.flagRow[j][number] = true
    	square := state.getSquare(i, j)
    	state.flagSquare[square][number] = true
    	state.countCol[i]++
    	state.countRow[j]++
    	state.countSquare[square]++
    	state.counter++
    	state.grid[i][j] = byte(number)
    }
    
    func (state *sudokuState) undo(i, j, number int) {
    	state.flagCol[i][number] = false
    	state.flagRow[j][number] = false
    	square := state.getSquare(i, j)
    	state.flagSquare[square][number] = false
    	state.countCol[i]--
    	state.countRow[j]--
    	state.countSquare[square]--
    	state.counter--
    	state.grid[i][j] = 0
    }
    
    func (state *sudokuState) getSquare(i, j int) int {
    	return i/3*3 + j/3
    }
    
    func (state *sudokuState) fillStrategy() (fillType, int) {
    	var max byte
    	which := 0
    	var fType fillType
    	for i := 0; i < 9; i++ {
    		if state.countCol[i] > max && state.countCol[i] < 9 {
    			max = state.countCol[i]
    			which = i
    		}
    	}
    	for i := 0; i < 9; i++ {
    		if state.countRow[i] > max && state.countRow[i] < 9 {
    			max = state.countRow[i]
    			which = i
    			fType = cFillRow
    		}
    	}
    	for i := 0; i < 9; i++ {
    		if state.countSquare[i] > max && state.countSquare[i] < 9 {
    			max = state.countSquare[i]
    			which = i
    			fType = cFillSquare
    		}
    	}
    	return fType, which
    }
    
    func newSudokuState(board [][]byte) *sudokuState {
    	s := &sudokuState{}
    	for i := 0; i < 9; i++ {
    		for j := 0; j < 9; j++ {
    			if board[i][j] == '.' {
    				continue
    			}
    			s.update(i, j, int(board[i][j]-'0'))
    		}
    	}
    	return s
    }
    
    func solveSudoku(board [][]byte) {
    	state := newSudokuState(board)
    	solve(state)
    	for i := 0; i < 9; i++ {
    		for j := 0; j < 9; j++ {
    			board[i][j] = state.grid[i][j] + '0'
    		}
    	}
    }
    
    func solve(state *sudokuState) {
    	if state.finished() {
    		return
    	}
    	fType, which := state.fillStrategy()
    	try2Fill(fType, which, state)
    }
    
    func try2Fill(fType fillType, which int, state *sudokuState) {
    	fill := fillCol
    	switch fType {
    	case cFillRow:
    		fill = fillRow
    	case cFillSquare:
    		fill = fillSquare
    	}
    	fill(which, state)
    }
    
    func fillRow(which int, state *sudokuState) {
    	var row int
    	for i := 0; i < 9; i++ {
    		if state.canFill(i, which, 0) {
    			row = i
    			break
    		}
    	}
    	for number := 1; number <= 9; number++ {
    		if state.fillNumber(row, which, number) {
    			solve(state)
    			if !state.finished() {
    				state.undo(row, which, number)
    			}
    		}
    	}
    }
    
    func fillCol(which int, state *sudokuState) {
    	var col int
    	for i := 0; i < 9; i++ {
    		if state.canFill(which, i, 0) {
    			col = i
    			break
    		}
    	}
    	for number := 1; number <= 9; number++ {
    		if state.fillNumber(which, col, number) {
    			solve(state)
    			if !state.finished() {
    				state.undo(which, col, number)
    			}
    		}
    	}
    }
    
    func fillSquare(which int, state *sudokuState) {
    	startI, startJ := getSquareStart(which)
    	endI, endJ := startI+3, startJ+3
    	var row, col int
    	for i := startI; i < endI; i++ {
    		for j := startJ; j < endJ; j++ {
    			if state.canFill(i, j, 0) {
    				row = i
    				col = j
    				break
    			}
    		}
    	}
    	for number := 1; number <= 9; number++ {
    		if state.fillNumber(row, col, number) {
    			solve(state)
    			if !state.finished() {
    				state.undo(row, col, number)
    			}
    		}
    	}
    }
    
    func getSquareStart(which int) (int, int) {
    	switch which {
    	case 0:
    		return 0, 0
    	case 1:
    		return 0, 3
    	case 2:
    		return 0, 6
    	case 3:
    		return 3, 0
    	case 4:
    		return 3, 3
    	case 5:
    		return 3, 6
    	case 6:
    		return 6, 0
    	case 7:
    		return 6, 3
    	default:
    		return 6, 6
    	}
    }
    

Log in to reply
 

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