52. N-Queens II

Problem

Tags: Backtracking

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

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

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 9

Code

GO

// 52. N-Queens II (2/19/53378)
// Runtime: 0 ms (91.59%) Memory: 1.92 MB (39.25%) 

import "fmt"

var result int
var queens_col [9]int
var n int

func abs(a int) int {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

func attacked(row int, col int) bool {
	for i := 0; i < row; i++ {
		enemy_row, enemy_col := i, queens_col[i]
		relative_x, relative_y := abs(enemy_row-row), abs(enemy_col-col)

		if relative_x == relative_y || col == enemy_col {
			return true
		}
	}
	return false
}

func place_queen(row int) {
	if row == n {
		result++
	}

	for i := 0; i < n; i++ {
        if !attacked(row, i) {
			queens_col[row] = i
			place_queen(row + 1)
			queens_col[row] = -1
		}
	}
}

func totalNQueens(sn int) int {
    result = 0
    queens_col = [9]int{-1,-1,-1,-1,-1,-1,-1,-1,-1}
    n = sn

	place_queen(0)

	return result
}

JS

// 52. N-Queens II (1/14/53378)
// Runtime: 76 ms (72.13%) Memory: 38.63 MB (94.43%) 

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function (n) {
    // 這一題有個特點，就是他 n 只有 1 ~ 9 ，所以用 testcase 跑完就可以知道答案了 XD
    // return [1, 0, 0, 2, 10, 4, 40, 92, 352][n - 1];

    // 正確的方法是用遞迴跑完所有結果

    // 可行方法數
    let result = 0;

    // 皇后所在的行數
    const queens_col = Array(n).fill(-1);

    function valid(row, col) {
        // 確認該格是否可放
        for (let i = 0; i < row; i++) {
            // 第 i 列皇后位置
            const prev_row = i;
            const prev_col = queens_col[i];

            const relative_x = Math.abs(prev_row - row);
            const relative_y = Math.abs(prev_col - col);

            // relative_x === relative_y: 位於已放皇后之斜線上, prev_col === col: 位於已放皇后之同行
            if (relative_x === relative_y || prev_col === col) return false;
        }
        return true;
    }

    function place_queen(row) {
        // 最後一列可行的話（最深遞迴），可行方法數 += 1
        if (row === n) result++;

        for (let col = 0; col < n; col++) {
            // 去跑每行
            if (valid(row, col)) {
                // 如果那行可以放就放，然後找放這行接下來的可能性
                queens_col[row] = col;
                place_queen(row + 1);
                // 找完放這行的可能性之後要清掉，要不然下個 validation 可能會錯
                queens_col[row] = -1;
            }
        }
    }

    // 從第一列開始放皇后
    place_queen(0);

    return result;
};