专栏首页dylanliu37. Sudoku Solver

37. Sudoku Solver

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,在判断是否是有效值时浪费了时间,并不是一种最优的方案。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode53-Maximum Subarray

    tags : Divide And Conquer Dynamic Programming Array

    Dylan Liu
  • JMX in action第二篇

    其实一看到Dynamic这个词就基本上确定了,就是反射那一套,不外乎属性获取,设定,方法调用等等,但是这个在使用中是至关重要的,因为现有系统如果都想把接...

    Dylan Liu
  • log4j conversion pattern各格式含义

    Dylan Liu
  • android自定义状态栏颜色

    我们知道IOS上的应用,状态栏的颜色总能与应用标题栏颜色保持一致,用户体验很不错,那安卓是否可以呢?若是在安卓4.4之前,答案是否定的,但在4.4之后,谷歌允...

    xiangzhihong
  • leetcode502. IPO

    Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

    眯眯眼的猫头鹰
  • POJ--1936 All in All(水题,暴力即可)

    All in All Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 3...

    ShenduCC
  • 【大三操作系统实验】 请求页式管理中的置换算法

    (1)FIFO算法总是选择在内存驻留时间最长的一页将其淘汰。FIFO算法认为调入内存的页不再被可能性要比其他页大,因而选择最先调入内存的页换出。

    用户7886150
  • 如何给SAP Cloud for Customer UI上的字段添加自定义校验逻辑

    There is a good blog SAP Cloud for Customer Phone Number Parsing and Formatting ...

    Jerry Wang
  • 当JSON.parse”遇上”非键值对

    在json大行其道并作为前后端主要通讯的数据格式之一时,对json本身的使用和了解多少人都会有些概念,当然随之而来的也是对json的对象以及其字符串形式的互相转...

    RobinsonZhang
  • Java Integer源码解读

    1、引言 public class IntegerDemo { public static void main(String[] args){ ...

    程裕强

扫码关注云+社区

领取腾讯云代金券