题目
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
输入：board = [[“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″]]
输出：[[“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”]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
代码
package main
import (
"fmt"
"strings"
"reflect"
)
func main() {
const BLANK = "."
board := [][]string{
{"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"}}
target := [][]string{
{"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"}}
getAllSet := func() map[string]int {
return map[string]int{
"1": 1, "2": 1, "3": 1, "4": 1, "5": 1, "6": 1, "7": 1, "8": 1, "9": 1,
}
}
getRowSet := func(board [][]string, row, col int) map[string]int {
ans := make(map[string]int)
for index := 0; index < len(board[0]); index++ {
if board[row][index] == BLANK {
continue
}
if value, ok := ans[board[row][index]]; ok {
ans[board[row][index]] = value + 1
} else {
ans[board[row][index]] = 1
}
}
return ans
}
getColSet := func(board [][]string, row, col int) map[string]int {
ans := make(map[string]int)
for index := 0; index < len(board[0]); index++ {
if board[index][col] == BLANK {
continue
}
if value, ok := ans[board[index][col]]; ok {
ans[board[index][col]] = value + 1
} else {
ans[board[index][col]] = 1
}
}
return ans
}
getSmallBoardSet := func(board [][]string, row, col int) map[string]int {
startRow, endRow := row/3*3, (row/3+1)*3
startCol, endCol := col/3*3, (col/3+1)*3
ans := make(map[string]int)
for i := startRow; i < endRow; i++ {
for j := startCol; j < endCol; j++ {
if board[i][j] == BLANK {
continue
}
if value, ok := ans[board[i][j]]; ok {
ans[board[i][j]] = value + 1
} else {
ans[board[i][j]] = 1
}
}
}
return ans
}
getPossibleSet := func(RowSet, ColSet, SmallBoardSet map[string]int) map[string]int {
allSet := getAllSet()
for key, _ := range allSet {
_, ok1 := RowSet[key]
_, ok2 := ColSet[key]
_, ok3 := SmallBoardSet[key]
if ok1 || ok2 || ok3 {
// 已经出现过，要删除这个key
delete(allSet, key)
}
}
return allSet
}
choiceCnt := func(m map[string]int) int {
return len(m)
}
getNextOption := func(board [][]string) (int, int, map[string]int) {
i, j, row, col, ans, find := 0, 0, 0, 0, make(map[string]int), false
for i = 0; i < len(board[0]); i++ {
for j = 0; j < len(board[0]); j++ {
if board[i][j] != BLANK {
continue
}
possibleSet := getPossibleSet(
getRowSet(board, i, j),
getColSet(board, i, j),
getSmallBoardSet(board, i, j))
if !find && len(possibleSet) > 0 {
// 第一次找到有可选的
ans, row, col, find = possibleSet, i, j, true
continue
}
// 找到选择更少的空格
if choiceCnt(ans) > len(possibleSet) && choiceCnt(possibleSet) > 0 {
ans, row, col = possibleSet, i, j
}
}
}
// 没有可选的
if !find {
return 0, 0, nil
}
return row, col, ans
}
isDeadLoad := func(nextOption map[string]int) bool {
if len(nextOption) <= 0 {
return true
}
return false
}
gameOver := func(board [][]string) bool {
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if board[i][j] == BLANK {
return false
}
}
}
return true
}
var solveBoard func(board [][]string) bool
solveBoard = func(board [][]string) bool {
if gameOver(board) {
return true
}
row, col, option := getNextOption(board)
if isDeadLoad(option) {
return false
}
for key, _ := range option {
board[row][col] = key
if gameOver(board) {
return true
} else if solveBoard(board) {
return true
} else {
// 回退，尝试下一种
board[row][col] = BLANK
}
}
return false
}
if solveBoard(board) {
for i := 0; i < len(board); i++ {
fmt.Printf("%v\n", board[i])
}
if reflect.DeepEqual(board, target) {
fmt.Printf("right answer.\n")
} else {
fmt.Printf("wrong answer.\n")
}
} else {
fmt.Printf("no ans found. \n")
}
}运行结果
