func solveSudoku(board [][]byte) {
tryOnce(board)
//printarry(board)
}
func tryOnce(board [][]byte)bool{
//printarry(board)
for i:=0;i<9;i++{
for j:=0;j<9;j++{
if board[i][j]=='.'{
val:=choice(board,i,j)
for k:=0;k<len(val);k++{
board[i][j]=byte(val[k])+'0'
if isValidSudoku(board)&&tryOnce(board){
return true
}else{
board[i][j]='.'
}
}
return false
}
}
}
return true
}
func choice(board [][]byte,row int,col int)[]int{
var sig[]bool=make([]bool,10)
var ret[]int=make([]int,0)
for i:=0;i<9;i++{
if board[row][i]!='.'{
sig[board[row][i]-'0']=true
}
if board[i][col]!='.'{
val:=board[i][col]
sig[val-'0']=true
}
}
var rl,rr int
if row%3==0{
rl=row
rr=row+2
}else if row%3==1{
rl=row-1
rr=row+1
}else {
rr=row
rl=row-2
}
var cl,cr int
if col%3==0{
cl=col
cr=col+2
}else if col%3==1{
cl=col-1
cr=col+1
}else{
cl=col-2
cr=col
}
for i:=rl;i<=rr;i++{
for j:=cl;j<=cr;j++{
if board[i][j]!='.'{
sig[board[i][j]-'0']=true
}
}
}
for i:=1;i<len(sig);i++{
if !sig[i]{
ret=append(ret,i)
}
}
return ret
}
func isValidSudoku(board [][]byte) bool {
for i:=0;i<9;i++{
if !isValidSub(board,0,8,i,i){
return false
}
if !isValidSub(board,i,i,0,8){
return false
}
}
for i:=0;i<3;i++{
for j:=0;j<3;j++{
if !isValidSub(board,3*j,3*j+2,3*i,3*i+2){
return false
}
}
}
return true
}
func isValidSub(board [][]byte,ri int,rj int ,ci int ,cj int)bool{
var sig[]bool=make([]bool,10)
for i:=ri;i<=rj;i++{
for j:=ci;j<=cj;j++{
if board[i][j]=='.'{
continue
}
val:=board[i][j]-'0'
if sig[val]{
return false
}else {
sig[val]=true
}
}
}
return true
}