Sudoku Solver

## Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

## Solution

### My solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 `````` ``````func solveSudoku(board [][]byte) { setNumber(&board, 0) } func setNumber(board *[][]byte, index int) bool { row := int(index / 9) col := index % 9 if index >= 81 { return true } canbe := getPossibleNumbers(*board, row, col) if len(canbe) == 0 { return false } reset := (*board)[row][col] ok := true for _, num := range canbe { (*board)[row][col] = num ok = setNumber(board, index + 1) if ok { break } } if !ok { (*board)[row][col] = reset } return ok } func getPossibleNumbers(board [][]byte, i, j int) []byte { num := board[i][j] if num != '.' { // skip this position return []byte{num} } canbe := map[byte]struct{}{ '1': struct{}{}, '2': struct{}{}, '3': struct{}{}, '4': struct{}{}, '5': struct{}{}, '6': struct{}{}, '7': struct{}{}, '8': struct{}{}, '9': struct{}{}, } // check row-i, remove number from 'canbe' which have been set to other postion for col := 0; col < 9; col++ { if col == j { continue } if removeFromPossibleNumber(&canbe, board[i][col]) == 0 { return []byte{} } } // check col-j, remove number from 'canbe' which have been set to other postion for row := 0; row < 9; row++ { if row == i { continue } if removeFromPossibleNumber(&canbe, board[row][j]) == 0 { return []byte{} } } // check the little sudoku block left := 3 * int(i / 3) top := 3 * int(j / 3) for l := 0; l < 3; l++ { for t := 0; t < 3; t++ { index_i := left + l index_j := top + t if index_i == i && index_j == j { continue } if removeFromPossibleNumber(&canbe, board[index_i][index_j]) == 0 { return []byte{} } } } var n byte var result []byte for n = '1'; n <= '9'; n++ { if _, ok := canbe[n]; ok { result = append(result, n) } } return result } func removeFromPossibleNumber(canbe *map[byte]struct{}, key byte) int { if _, ok := (*canbe)[key]; ok { delete(*canbe, key) } return len(*canbe) }``````

### Pretty solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 `````` ``````func solveSudoku(board [][]byte) { setNumber(&board, 0) } func setNumber(board *[][]byte, index int) bool { row := int(index / 9) col := index % 9 if index >= 81 { return true } if (*board)[row][col] == '.' { var c byte for c = '1'; c <= '9'; c++ { (*board)[row][col] = c if valid(board, row, col) && setNumber(board, index + 1) { return true } (*board)[row][col] = '.' } return false } else { return setNumber(board, index + 1) } } func valid(board *[][]byte, row, col int) bool { num := (*board)[row][col] // check row for i := 0; i < 9; i++ { if i == row { continue } if (*board)[i][col] == num { return false } } // check col for j := 0; j < 9; j++ { if j == col { continue } if (*board)[row][j] == num { return false } } // check the little sudoku block left := 3 * int(row / 3) top := 3 * int(col / 3) for i := left; i < left + 3; i++ { for j := top; j < top + 3; j++ { if i == row && j == col { continue } if (*board)[i][j] == num { return false } } } return true }``````

36. Valid-Sudoku