This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging

A valid array

Determine if a 9×9 sudoku is valid. Just verify that the entered numbers are valid according to the following rules.

  1. digital1-9It can only occur once per line.
  2. digital1-9It can only occur once per column.
  3. digital1-9In each with a thick solid line separated3x3It can only occur once in utero. (Please refer to the sample diagram)

The Spaces in sudoku sections have been filled in with numbers, and the Spaces are represented by ‘.’.

Note:

  • A valid sudoku (partially filled) is not necessarily solvable.
  • You just need to verify that the entered numbers are valid according to the above rules.

This question requires us to judge whether a sudoku is currently valid, that is, whether there has been an error in the current filling in the numbers (the same number appears in 3*3 or the same number in the same line or column).

Because the data amount is small (n=9), according to 3*3 nine grid traversal once, to determine whether there is duplication, again row traversal once, again to determine whether there is duplication, if there is duplication, return false immediately, if the whole verification is correct, return true. The time complexity is O(n^2).

The code is as follows:

func isValidSudoku(board [][]byte) bool {
   for i := 0; i < 3; i++ {
      for j := 0; j < 3; j++ {
         m := make(map[byte]int)
         for a := 0; a < 3; a++ {
            for b := 0; b < 3; b++ {
               if m[board[a+3*i][b+3*j]] ! =0 && board[a+3*i][b+3*j] ! ='. ' {
                  return false
               }
               m[board[a+3*i][b+3*j]]++
            }
         }
      }
   }
   for i := 0; i < 9; i++ {
      m1 := make(map[byte]int)
      m2 := make(map[byte]int)
      for j := 0; j < 9; j++ {
         ifm1[board[i][j]] ! =0&& board[i][j] ! ='. ' {
            return false
         }
         m1[board[i][j]]++
         ifm2[board[j][i]] ! =0&& board[j][i] ! ='. ' {
            return false
         }
         m2[board[j][i]]++
      }
   }
   return true
}
Copy the code

In this case, we can use space for time, using only one traversal to complete the judgment:

Simply merge the top and bottom: keep the bottom part unchanged, and the nine squares are stored in a map array of length 9.

The index of map array is calculated as follows:

index := (i / 3) * 3 + j / 3

Return false if the character is repeated, and true if it is true.

Through optimization, the time complexity is still O(n^2), but it is better than before.

The code is as follows:

func isValidSudoku(board [][]byte) bool {
   boxM := make([]map[byte]int.9)

   for i := 0; i < 9; i++ {
      rowM := make(map[byte]int)
      columnM := make(map[byte]int)
      for j := 0; j < 9; j++ {
         index := (i / 3) * 3 + j / 3
         ifboxM[index][board[i][j]] ! =0&& board[i][j] ! ='. ' {
            return false
         }
         boxM[index][board[i][j]]++

         ifrowM[board[i][j]] ! =0&& board[i][j] ! ='. ' {
            return false
         }
         rowM[board[i][j]]++

         ifcolumnM[board[j][i]] ! =0&& board[j][i] ! ='. ' {
            return false
         }
         columnM[board[j][i]]++

      }
   }
   return true
}
Copy the code