This is the 17th day of my participation in the August Text Challenge.More challenges in August

Their independence

Write a program to solve a sudoku problem by filling in the blanks.

The solution of sudoku must follow the following rules:

  1. digital1-9You can only appear once in each line.
  2. digital1-9You can only appear once in each column.
  3. digital1-9In each one separated by a thick solid line3x3You can only be in the palace once.

Numbers have been filled in the blank space of sudoku, and the blank space is represented by ‘.’.

Tip:

  • board.length == 9
  • board[i].length == 9
  • board[i][j]It’s a digit or'. '
  • The problem data guarantees that the input sudoku has only one solution

This is a classic checkerboard search problem, which requires the backtracking algorithm to perform exhaustive recursive filling for each vacancy. The so-called backtracking algorithm is to add a verification operation on the basis of recursion. If a number is filled in the recursion, the state of board loses its correctness, then backtracking one step upward, clearing the number in the previous step, and trying to fill in other numbers. If there is no number to fill in, continue backtracking until you get a viable solution.

For the convenience of demonstration, the row and column conflict is not taken into account, and only one nine grid is considered. The algorithm process is shown as the blue arrow:

On the validation of the current state is legal, and a valid sudoku differ again (of course also can directly use, is the high time complexity will be a lot of), determine whether can insert before insertion, namely the judge peers, columns, and within the same scratchable latex have the same number, if not then on to the next number of judgment.

The difficulty of this problem is the implementation of backtracking and recursion:

We need to determine whether a particular branch to find the right conditions, so the recursive function return value should be a bool type, if return to return true, that the branch current can continue, otherwise there is no further need, simply discard this branch, and dealing with back (return true don’t need to go back, This path may still be correct).

The code is as follows:

func solveSudoku(board [][]byte) {
    insert(&board)
}

func insert(board *[][]byte) bool {
    for i := 0; i < 9; i++ {
	for j := 0; j < 9; j++ {
            if(*board)[i][j] ! ='. ' {
		continue
            }
	for k := '1'; k <= '9'; k++ {
            if isValid(i, j, byte(k), *board) {
                (*board)[i][j] = byte(k)
		if insert(board) {
                    return true
                }
		(*board)[i][j] = '. '}}return false}}return true
}

func isValid(row int, col int, val byte, board [][]byte) bool {
	for i := 0; i < 9; i++ {
            if board[row][i] == val {
		return false
            }
            if board[i][col] == val {
		return false
            }
	}
	a := (row / 3) * 3
	b := (col / 3) * 3
	for i := a; i < a + 3; i++ {
		for j := b; j < b + 3; j++ {
			if board[i][j] == val {
				return false}}}return true
}
Copy the code

Submission Results: