Sudoku - using go

Sudoku_.go

package main

// Space: either O(1) or O(n)
// Time: upper bound O(9^n) is actually much less than this
func SudokuSolve(board [][]string) bool {
  return dfs(0, 0, board)
}

// structure is not clear - 
// make clear DFS
// base case
// recurrence later 
// sx == 9 return true -> 9 * 9 - 0 - 


func dfs(sx, sy int, board [][]string) bool {
  
  for y := sy; y < len(board); y++ {
    var startX = 0
    if y == sy {
      startX = sx
    }
    for x := sx; x < len(board); x++ { // Remember to optimise this
      if board[y][x] != "." {
        continue
      }
      var possibles = possibleNumbers(x, y, board)
      for _, p := range possibles {
        board[y][x] = p
        if SudokuSolve(board) {
          return true
        }
        
        // back tracking 
        board[y][x] = "."
      }
      return false
    }
  }
  return true
}

func possibleNumbers(x, y int, board [][]string) []string {
  var found = make(map[string]struct{})
  for i := range board[0] {
    if _, ok := found[board[y][i]]; !ok && board[y][i] != "." {
      found[board[y][i]] = struct{}{}
    }
  }
  for i := range board {
    if _, ok := found[board[i][x]]; !ok && board[i][x] != "." {
      found[board[i][x]] = struct{}{}
    }
  }
  var startX, startY int    x / 3  y / 3   startX = (x/3)+1
  if x < 3 {
    startX = 0
  } else if x < 6 {
    startX = 3
  } else {
    startX = 6
  }
  
  if y < 3 {
    startY = 0
  } else if y < 6 {
    startY = 3
  } else {
    startY = 6
  }
  for yi := startY; yi < startY+3; yi++ {
    for xi := startX; xi < startX+3; xi++ {
      if _, ok := found[board[yi][xi]]; !ok && board[yi][xi] != "." {
        found[board[yi][xi]] = struct{}{}
      }
    }    
  }
  var possible = make([]string, 0)
  for _, b := range []string{"1", "2", "3", "4", "5", "6", "7", "8", "9"} {
    if _, ok := found[b]; !ok {
      possible = append(possible, b)
    }
  }
  return possible
}

func main() {
}

// 9 ^ how many space elements - 
// 9 * 8 * 7 * 6 * 5 * 4 ... - first row 9!
// 8 * 7                     - second row 8!
// ... 
// tight upper bound -> 9! 8! ... 1!
// elements of programming interview