前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >37. Sudoku Solver

37. Sudoku Solver

作者头像
Dylan Liu
发布2019-07-01 12:01:12
3230
发布2019-07-01 12:01:12
举报
文章被收录于专栏:dylanliu
Description

tags: backtrack,hash table difficulty: hard

代码语言:javascript
复制
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 '.'.
代码语言:javascript
复制
A sudoku puzzle...


...and its solution numbers marked in red.
代码语言:javascript
复制
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
代码语言:javascript
复制
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,在判断是否是有效值时浪费了时间,并不是一种最优的方案。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Description
  • Solution
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档