题解 | #Sudoku# go#acm模式
Sudoku
http://www.nowcoder.com/practice/78a1a4ebe8a34c93aac006c44f6bf8a1
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func check(matrix [][]int, row, col, value int) bool {
/*
检测在(row,col)放value是否合适
1.每行含1-9,不含重复值value
2.每列含1-9,不含重复值value
3.3*3区块含1-9,不含重复值value
*/
for j := 0; j < 9; j ++ {
// 检测每行
if matrix[row][j] == value {
return false
}
// 检测每列
if matrix[j][col] == value {
return false
}
}
// 检测元素所在3*3区域
area_row := (row / 3) * 3
area_col := (col / 3) * 3
for i := area_row; i < area_row +3; i ++ {
for j := area_col; j < area_col +3; j ++ {
if matrix[i][j] == value {
return false
}
}
}
return true
}
func solveSudoku(matrix [][]int, count int) bool {
if count == 81 {
return true
}
row := count / 9 // 行标
col := count % 9 // 列表
if matrix[row][col] != 0 { // 已填充
return solveSudoku(matrix, count+1)
}
for i := 1; i < 10; i++ {
if check(matrix, row, col, i) { // 找到可填充的数
matrix[row][col] = i
if solveSudoku(matrix, count+1) {
return true
}
matrix[row][col] = 0
}
}
return false
}
func main() {
r := bufio.NewScanner(os.Stdin)
matrix := make([][]int, 0)
for {
r.Scan()
str := r.Text()
if str == "" {
break
}
n := make([]int, 0, 9)
for _, v := range strings.Split(str, " ") {
s, _ := strconv.Atoi(v)
n = append(n, s)
}
matrix = append(matrix, n)
}
solveSudoku(matrix, 0)
for _, v := range matrix {
res := ""
for _, j := range v {
res += fmt.Sprintf("%d ", j)
}
fmt.Println(res)
}
}
投递众安保险等公司10个岗位 >
