# 37. Sudoku Solver

#### Description

tags: backtrack,hash table difficulty: hard

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.```
```A sudoku puzzle...

...and its solution numbers marked in red.```
```Note:

The given board contain only digits 1-9 and the character '.'.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.```

#### Solution

```package main

import "fmt"

func main() {
board := [][]byte{{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}}
solvedBoard := [][]byte{{'5','3','4','6','7','8','9','1','2'},{'6','7','2','1','9','5','3','4','8'},{'1','9','8','3','4','2','5','6','7'},{'8','5','9','7','6','1','4','2','3'},{'4','2','6','8','5','3','7','9','1'},{'7','1','3','9','2','4','8','5','6'},{'9','6','1','5','3','7','2','8','4'},{'2','8','7','4','1','9','6','3','5'},{'3','4','5','2','8','6','1','7','9'}}
fmt.Println(solvedBoard)
solveSudoku(board)
fmt.Println(board)
}

func solveSudoku(board [][]byte)  {
backtrack(board,0,0)
}

func threeThreeLoc(i,j,r int)(int, int){
if i <= 2 && j <= 2 {
return r / 3, r % 3
} else if i <=2 && j <= 5 {
return r / 3 , r%3 + 3
} else if i<= 2{
return r / 3 , r%3 + 6
}

if i <= 5 && j <=2 {
return r/3+3 , r%3
} else if i <=5 && j <=5 {
return r/3+3 , r%3 + 3
} else if i<=5{
return r/3+3, r%3 +6
}
if i <= 9 && j <=2 {
return r/3+6 , r%3
} else if i <=9 && j <=5 {
return r/3+6 , r%3 + 3
} else {
return r/3+6, r%3 +6
}
}

func backtrack(board [][]byte, i, j int) bool {
m,n := nextBlank(board, i, j)
if m >=9 || n >=9 {
return true
}

for _, value := range []int{1,2,3,4,5,6,7,8,9} {
if value <= 0 || !isValidPlace(board, m, n, value){
continue
}

board[m][n] = byte(value) + '0'
if backtrack(board, m, n){
return true
}
board[m][n] = '.'
}
return false
}

func isValidPlace(board [][] byte, i, j, value int) bool {
for r:=0;r<9;r++{
if int(board[i][r]-'0') == value {
return false
}
if int(board[r][j] - '0') == value {
return false
}
m,n := threeThreeLoc(i, j, r)
if int(board[m][n] - '0') == value {
return false
}

}
return true
}

func nextBlank(board [][]byte, i, j int) (int, int){
for loc := i * 9 + j; loc < 81; loc++ {
m,n := loc / 9, loc % 9
if board[m][n] == '.' {
return m,n
}
}
return 10,10
}```

Note:

0 条评论

• ### LeetCode53-Maximum Subarray

tags : Divide And Conquer Dynamic Programming Array

• ### JMX in action第二篇

其实一看到Dynamic这个词就基本上确定了，就是反射那一套，不外乎属性获取，设定，方法调用等等,但是这个在使用中是至关重要的，因为现有系统如果都想把接...

• ### android自定义状态栏颜色

我们知道IOS上的应用，状态栏的颜色总能与应用标题栏颜色保持一致，用户体验很不错，那安卓是否可以呢？若是在安卓4.4之前，答案是否定的，但在4.4之后，谷歌允...

• ### leetcode502. IPO

Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

• ### POJ--1936 All in All（水题，暴力即可）

All in All Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 3...

• ### 【大三操作系统实验】 请求页式管理中的置换算法

（1）FIFO算法总是选择在内存驻留时间最长的一页将其淘汰。FIFO算法认为调入内存的页不再被可能性要比其他页大，因而选择最先调入内存的页换出。

• ### 如何给SAP Cloud for Customer UI上的字段添加自定义校验逻辑

There is a good blog SAP Cloud for Customer Phone Number Parsing and Formatting ...

• ### 当JSON.parse”遇上”非键值对

在json大行其道并作为前后端主要通讯的数据格式之一时，对json本身的使用和了解多少人都会有些概念，当然随之而来的也是对json的对象以及其字符串形式的互相转...

• ### Java Integer源码解读

1、引言 public class IntegerDemo { public static void main(String[] args){ ...

AmazonSDE II