golang 解数独

题目

编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则:

数字 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")
	}
}

运行结果