51. N-Queens

Problem

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Problem Summary

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens placement, where 'Q' and '.' represent a queen and an empty space respectively.

Solution Approach

• Solve the n-queens problem.
• Use the col array to record column information; col has n columns. Use dia1 and dia2 to record information for the diagonals from bottom-left to top-right and from top-left to bottom-right; dia1 and dia2 each have 2*n-1 entries.
• The rule for dia1 diagonals is that i + j is a constant. For example, [0,0] is 0; [1,0] and [0,1] are 1; [2,0], [1,1], and [0,2] are 2.
• The rule for dia2 diagonals is that i - j is a constant. For example, [0,7] is -7; [0,6] and [1,7] are -6; [0,5], [1,6], and [2,7] are -5. To make them start from 0, offset i - j + n - 1 to start from 0, so the rule for dia2 is that i - j + n - 1 is a constant.
• There is also a bit-operation method. Since each row can only choose one position to place a queen, traverse the possible positions for each row. How can we efficiently determine which points cannot have a queen? The approach here is quite clever: store all previously chosen points in order, and then, based on the distance from each previously chosen point to the current row, quickly determine whether there will be a conflict. For example: in the 4-queens problem, suppose the first and second rows have already chosen positions [1, 3]. Then when choosing for the third row, first of all columns 1 and 3 cannot be chosen again. For the third row, 1 is at a distance of 2, so it will affect columns -1 and 3. Similarly, 3 is in the second row, and its distance to the third row is 1, so 3 will affect columns 2 and 4. From the results above, we know that -1 and 4 are out of bounds and can be ignored, and the other points that cannot be chosen are 1, 2, and 3, so the third row can only choose 0. In the code implementation, before each traversal, an occupied value can be generated based on the previous choices to record, for the current row, positions that have already been chosen and positions that cannot be chosen because they are within the attack range of previous queens; then only legal positions are chosen to enter the next level of recursion. In addition, strings for placing a queen in different positions are preprocessed, so these strings can be reused in memory when returning the results, saving a little memory.

Code

package leetcode

// Solution 1 DFS
func solveNQueens(n int) [][]string {
	col, dia1, dia2, row, res := make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1), []int{}, [][]string{}
	putQueen(n, 0, &col, &dia1, &dia2, &row, &res)
	return res
}

// Try to place the queen in row index in an n-queens problem
func putQueen(n, index int, col, dia1, dia2 *[]bool, row *[]int, res *[][]string) {
	if index == n {
		*res = append(*res, generateBoard(n, row))
		return
	}
	for i := 0; i < n; i++ {
		// Try to place the queen in row index in column i
		if !(*col)[i] && !(*dia1)[index+i] && !(*dia2)[index-i+n-1] {
			*row = append(*row, i)
			(*col)[i] = true
			(*dia1)[index+i] = true
			(*dia2)[index-i+n-1] = true
			putQueen(n, index+1, col, dia1, dia2, row, res)
			(*col)[i] = false
			(*dia1)[index+i] = false
			(*dia2)[index-i+n-1] = false
			*row = (*row)[:len(*row)-1]
		}
	}
	return
}

func generateBoard(n int, row *[]int) []string {
	board := []string{}
	res := ""
	for i := 0; i < n; i++ {
		res += "."
	}
	for i := 0; i < n; i++ {
		board = append(board, res)
	}
	for i := 0; i < n; i++ {
		tmp := []byte(board[i])
		tmp[(*row)[i]] = 'Q'
		board[i] = string(tmp)
	}
	return board
}

// Solution 2 Binary operation method Signed-off-by: Hanlin Shi [email protected]
func solveNQueens2(n int) (res [][]string) {
	placements := make([]string, n)
	for i := range placements {
		buf := make([]byte, n)
		for j := range placements {
			if i == j {
				buf[j] = 'Q'
			} else {
				buf[j] = '.'
			}
		}
		placements[i] = string(buf)
	}
	var construct func(prev []int)
	construct = func(prev []int) {
		if len(prev) == n {
			plan := make([]string, n)
			for i := 0; i < n; i++ {
				plan[i] = placements[prev[i]]
			}
			res = append(res, plan)
			return
		}
		occupied := 0
		for i := range prev {
			dist := len(prev) - i
			bit := 1 << prev[i]
			occupied |= bit | bit<<dist | bit>>dist
		}
		prev = append(prev, -1)
		for i := 0; i < n; i++ {
			if (occupied>>i)&1 != 0 {
				continue
			}
			prev[len(prev)-1] = i
			construct(prev)
		}
	}
	construct(make([]int, 0, n))
	return
}