52. N-Queens II

💡

N-Queens vs N-Queens II

N-Queens yêu cầu bạn xuất ra toàn bộ các phương án (ví dụ: dạng mảng các chuỗi thể hiện từng hàng của bàn cờ).

N-Queens II chỉ cần trả về một số nguyên là tổng số phương án hợp lệ, không cần biết chi tiết từng phương án đó

Problem

Bài toán yêu cầu đếm số cách đặt n quân hậu trên bàn cờ n x n sao cho không có hai quân hậu nào ăn nhau (không cùng hàng, cột hoặc chéo)

Approach

Ý tưởng tối ưu là sử dụng backtrack

Đặt từng quân hậu lên từng hàng (hoặc cột), thử tất cả các vị trí hợp lệ

Dùng các mảng/Set/bitmask để đánh dấy cột và hai đường chéo đã bị chiếm

Khi đặt được hết n quân hây, tăng biến đếm kết quả

Các biến cần thiêt

cols : Đánh dấu các cột đã đặt quân hậu

diag1 : Đánh dấu đường chéo chính (row + col)

diag2 : Đánh dấu đường chéo phụ (col - row+ n - 1)

Time and space complexity

TC: O(n!)

Ở hàng đầu tiên, bạn có N lựa chọn đặt hậu; hàng tiếp theo còn tối đa N-1 lựa chọn (do loại trừ các cột và đường chéo bị chiếm), tiếp tục như vậy cho đến hết.

Tổng số trường hợp cần kiểm tra: n x (n - 1) x (n - 2) .... x 1 = n!

SC: O(n)

Không lưu trạng thái bàn cờ, chỉ lưu đánh dấu và call stack

Solution

typescripttypescript

1function totalNQueens(n: number): number {
2	 let count = 0;
3	 const cols = new Array(n).fill(false)
4	 const diag1 = new Array(2 * n - 1).fill(false)
5	 const diag2 = new Array(2 * n - 1).fill(false)
6	 function backtrack(row: number) {
7		 if(row === n) {
8			 count++;
9			 return;
10		 }
11		 
12		 for(let col = 0; col < n; col++) {
13			 const main_diag = row + col;
14			 const sub_diag = col - row + (n - 1)
15		 
16			 if(cols[col] || diag1[main_diag] || diag2[sub_diag]) continue;
17			 cols[col] = diag1[main_diag] = diag2[sub_diag] = true;
18			 backtrack(row + 1)
19			 cols[col] = diag1[main_diag] = diag2[sub_diag] = false;
20		 }
21	 }
22	 backtrack(0)
23	 return count;
24};

💡

Tại sao là 2 * n - 1 ?

Đường chéo chính (từ trên trái xuống dưới phải) Với một ô tại (row,col) chỉ số của đường chéo này là row + col . Giá trị này chạy từ 0 (góc trên bên trái) đến 2n - 2 (góc dưới bên phải), nên cần mảng độ dài 2n - 1

Đường chéo phụ (từ trên phải xuống dưới trái): Với một ô tại (row, col) chỉ số của đường chéo này là col - row + (n - 1) . Giá trị này chạy từ 0 (góc bên trái) đến 2n - 2 (góc dưới bên phải mảng), nên cần mảng độ dài 2n - 1

Loading content...

1function totalNQueens(n: number): number { 2 let count = 0; 3 const cols = new Array(n).fill(false) 4 const diag1 = new Array(2 * n - 1).fill(false) 5 const diag2 = new Array(2 * n - 1).fill(false) 6 function backtrack(row: number) { 7 if(row === n) { 8 count++; 9 return; 10 } 11 12 for(let col = 0; col < n; col++) { 13 const main_diag = row + col; 14 const sub_diag = col - row + (n - 1) 15 16 if(cols[col] || diag1[main_diag] || diag2[sub_diag]) continue; 17 cols[col] = diag1[main_diag] = diag2[sub_diag] = true; 18 backtrack(row + 1) 19 cols[col] = diag1[main_diag] = diag2[sub_diag] = false; 20 } 21 } 22 backtrack(0) 23 return count; 24};

52. N-Queens II

Related Posts

Related Posts

52. N-Queens II

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists