Solves sudoku

sudokuSolver.go

// A solution for https://leetcode.com/problems/sudoku-solver/

type Cache struct {
  row [9][9]bool
  column [9][9]bool
  box [9][9]bool
}

var oneCode = "1"[0]
var dotCode = "."[0]

func solveSudoku(board [][]byte)  {
  cache := makeInitialCache(board)
  fillWhileDefined(board, &cache)
  if !isSolved(board) {
    copyBoard(trySolutionBranches(board, &cache), board)
  }
}

// Warning! The sets store numbers in ranges [0..8]
func makeInitialCache(board [][]byte) Cache {
  cache := Cache{}
  
  for row := 0; row < 9; row++ {
    for column := 0; column < 9; column++ {
      if board[row][column] == dotCode {
        continue
      }
      num := board[row][column] - oneCode
      cache.row[row][num] = true
      cache.column[column][num] = true
      cache.box[getBoxIndex(row, column)][num] = true
    }
  }
  
  return cache
}

// Tries to fill the board with certain numbers as much as possible
func fillWhileDefined(board [][]byte, cache *Cache) bool {
  solvers := [](func (board [][]byte, cache *Cache) int){
    tryFillRows,
    tryFillColumns,
    tryFillBoxes,
    tryFillCells,
  }

  for {
    hasSet := false
    for _, solver := range solvers {
      status := solver(board, cache)
      if status == -1 {
        return false
      } else if status == 1 {
        hasSet = true
      }
    }
    if !hasSet {
      break
    }
  }

  return true
}

// When no certain numbers have left, tries putting different numbers into the first empty cell and tries to solve further.
// If a guess is incorrect, rolls back and tries another number.
func trySolutionBranches(board [][]byte, cache *Cache) [][]byte {
  for row := 0; row < 9; row++ {
    for column := 0; column < 9; column++ {
      if board[row][column] != dotCode {
        continue // The cell is occupied already
      }
      
      for num := 0; num < 9; num++ {
        if cache.row[row][num] || cache.column[column][num] || cache.box[getBoxIndex(row, column)][num] {
          continue // The number is already in this row, column or box
        }
        
        altBoard := createEmptyBoard()
        copyBoard(board, altBoard)
        altCache := *cache // The struct and the underlying arrays are copied intrinsically
        setNumber(altBoard, row, column, num, &altCache)
        
        unsolvable := !fillWhileDefined(altBoard, &altCache)
        if unsolvable {
          continue
        }
        if isSolved(altBoard) {
          return altBoard
        }
        childSolution := trySolutionBranches(altBoard, &altCache)
        if childSolution != nil {
          return childSolution
        }
      }
      
      return nil
    }
  }
  
  panic("The board is solved already")
}

func tryFillRows(board [][]byte, cache *Cache) int {
  status := 0
  
  for row := 0; row < 9; row++ {
    numLoop:
    for num := 0; num < 9; num++ {
      if cache.row[row][num] {
        continue // The number is already put
      }
      
      potentialColumn := -1
      
      for column := 0; column < 9; column++ {
        if board[row][column] != dotCode {
          continue // The cell is occupied already
        }
        if cache.column[column][num] || cache.box[getBoxIndex(row, column)][num] {
          continue // The number is already in this column or box
        }
        if potentialColumn != -1 {
          continue numLoop // There are many possible cells for the number
        }
        potentialColumn = column
      }
      
      if potentialColumn == -1 {
        // fmt.Printf("Unsolvable at row %d for num %d\n", row + 1, num + 1)
        return -1
      }
      
      setNumber(board, row, potentialColumn, num, cache)
      status = 1
    }
  }
  
  return status
}

func tryFillColumns(board [][]byte, cache *Cache) int {
  status := 0
  
  for column := 0; column < 9; column++ {
    numLoop:
    for num := 0; num < 9; num++ {
      if cache.column[column][num] {
        continue // The number is already put
      }
      
      potentialRow := -1
      
      for row := 0; row < 9; row++ {
        if board[row][column] != dotCode {
          continue // The cell is occupied already
        }
        if cache.row[row][num] || cache.box[getBoxIndex(row, column)][num] {
          continue // The number is already in this row or box
        }
        if potentialRow != -1 {
          continue numLoop // There are many possible cells for the number
        }
        potentialRow = row
      }
      
      if potentialRow == -1 {
        // fmt.Printf("Unsolvable at column %d for num %d\n", column + 1, num + 1)
        return -1
      }
      
      setNumber(board, potentialRow, column, num, cache)
      status = 1
    }
  }

  return status
}

func tryFillBoxes(board [][]byte, cache *Cache) int {
  status := 0
  
  for box := 0; box < 9; box++ {
    numLoop:
    for num := 0; num < 9; num++ {
      if cache.box[box][num] {
        continue // The number is already put
      }
      
      potentialRow := -1
      potentialColumn := -1
      
      for index := 0; index < 9; index++ {
        row, column := resolveBoxIndex(box, index)
        if board[row][column] != dotCode {
          continue // The cell is occupied already
        }
        if cache.row[row][num] || cache.column[column][num] {
          continue // The number is already in this row or column
        }
        if potentialRow != -1 {
          continue numLoop // There are many possible cells for the number
        }
        potentialRow, potentialColumn = row, column
      }
      
      if potentialRow == -1 {
        // fmt.Printf("Unsolvable at box %d for num %d", box + 1, num + 1)
        return -1
      }
      
      setNumber(board, potentialRow, potentialColumn, num, cache)
      status = 1
    }
  }
  
  return status
}

func tryFillCells(board [][]byte, cache *Cache) int {
  status := 0
  
  for row := 0; row < 9; row++ {
    columnLoop:
    for column := 0; column < 9; column++ {
      if board[row][column] != dotCode {
        continue // The cell is occupied already
      }
      
      potentialNum := -1

      for num := 0; num < 9; num++ {
        if cache.row[row][num] || cache.column[column][num] || cache.box[getBoxIndex(row, column)][num] {
          continue // The number is already in this row, column or box
        }
        if potentialNum != -1 {
          continue columnLoop // There are many possible numbers for the cell
        }
        potentialNum = num
      }
      
      if potentialNum == -1 {
        // fmt.Printf("Unsolvable at row %d column %d", row + 1, column + 1)
        return -1
      }
      
      setNumber(board, row, column, potentialNum, cache)
      status = 1
    }
  }

  return status
}

func getBoxIndex(row, column int) int {
  boxRow := row / 3 // implicit floor()
  boxColumn := column / 3 // implicit floor()
  return boxRow * 3 + boxColumn
}

func resolveBoxIndex(boxIndex, inBoxIndex int) (row int, column int) {
  row = (boxIndex / 3) * 3 + (inBoxIndex / 3) // implicit floor() 2 times
  column = (boxIndex % 3) * 3 + (inBoxIndex % 3)
  return
}

func setNumber(board [][]byte, row, column, num int, cache *Cache) {
  board[row][column] = byte(num) + oneCode
  cache.row[row][num] = true
  cache.column[column][num] = true
  cache.box[getBoxIndex(row, column)][num] = true
}

func isSolved(board [][]byte) bool {
  for row := 0; row < 9; row++ {
    for column := 0; column < 9; column++ {
      if board[row][column] == dotCode {
        return false
      }
    }
  }
  return true
}

func createEmptyBoard() [][]byte {
  board := make([][]byte, 9)
  for i := 0; i < 9; i++ {
    board[i] = make([]byte, 9)
  }
  return board
}

func copyBoard(from [][]byte, to [][]byte) {
  for i := 0; i < 9; i++ {
    copy(to[i], from[i])
  }
}

func printBoard(board [][]byte) {
  left := [9]string{"┏━","┃ ","┃ ","│ ","│ ","│ ","┃ ","┃ ","┗━"}
  center := [9]string{"━┳━"," ┃ "," ┃ "," │ "," │ "," │ "," ┃ "," ┃ ","━┻━"}
  right := [9]string{"━┓"," ┃"," ┃"," │"," │"," │"," ┃"," ┃","━┛"}
  for i, row := range board {
    fmt.Printf(left[i])
    for j, cell := range row {
      if j > 0 && j % 3 == 0 {
        fmt.Printf(center[i])
      }
      fmt.Printf("%c", cell)
    }
    fmt.Printf(right[i])
    fmt.Printf("\n")
  }
}