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:

每一个点的位置都有1-9种可能性，但是不是每一个都满足需求，因此通过回溯建立了最终的解。这个解法没有用到Hash Table，在判断是否是有效值时浪费了时间，并不是一种最优的方案。