3.6 Backtracking

1. What Is Backtracking

• At each step, choose a path and move forward. If it works, continue; if it does not, return to the previous step (backtrack) and try another path

2. Eight Queens Problem

• 

2.1. Idea

• Brute force
  • Choose any 8 squares from 64 squares to place queens, and check whether each placement is valid
    • There are possible placements
  • If each row can contain only one queen, there are only possible placements
• Backtracking + pruning

2.2. Implementation

package 回溯

import (
	"fmt"
	"my_algorithm/util"
)

type NQueens struct {
	// Stores the position of each queen
	// The index is the queen in row, and the value is the column where it is placed
	queensLocation []int
	// Total number of placements
	ways int
	// Number of queens
	n int
}

func NewNQueens(n int) *NQueens {
	return &NQueens{
		n:              n,
		queensLocation: make([]int, n, n),
		ways:           0,
	}
}

func (n *NQueens) placeQueens() {
	if n.n < 1 {
		return
	}

	n.place(0)
}

// Place the row-th queen, also placing it in row row
func (n *NQueens) place(row int) {
	// All queens have been placed, so ways +1
	if row == len(n.queensLocation) {
		n.ways++
		return
	}

	// Try every column and check whether it is valid
	for col := 0; col < len(n.queensLocation); col++ {
		if n.isValid(row, col) {
			// Place the queen in row row at column col
			n.queensLocation[row] = col
			// Continue placing the queen in the next row
			n.place(row + 1)
		}
	}
}

// Two queens cannot be in the same row, same column, or same diagonal
func (n *NQueens) isValid(row int, col int) bool {
	for i := 0; i < row; i++ {
		// Same column
		// If a previous queen has already been placed in column col, it cannot be placed here
		if n.queensLocation[i] == col {
			return false
		}

		// Same diagonal
		// The queen in row i and the square at row row, column col are on the same diagonal
		// 45-degree diagonal: y-y0 = (x-x0), so (y-y0)/(x-x0) = 1
		if util.Abs(col-n.queensLocation[i]) == row-i {
			return false
		}
	}

	return true
}

func (n *NQueens) String() string {
	s := fmt.Sprintf("ways=%v, data={\n", n.ways)
	for row := 0; row < len(n.queensLocation); row++ {
		for col := 0; col < len(n.queensLocation); col++ {
			if n.queensLocation[row] == col {
				s += "1 "
			} else {
				s += "0 "
			}
		}
		s += "\n"
	}
	s += "}"
	return s
}

2.2.1. Test

func TestEightQueens(t *testing.T) {
	fmt.Println(NewNQueens(4))
}

3. References

• Backtracking and Pruning: Eight Queens and N-Queens - CSDN