ปัญหา: N×N Binary Matrix (0=Empty, 1=Blocked) เลือก N Empty Cells ทำให้ทุก Row และทุก Column มี Chosen Cell อย่างน้อย 1 ตัว หาจำนวนวิธี Mod 10⁹+7
Observation: เลือก N Cells, N Rows, N Cols → ต้องเลือก **พอดี 1 Cell ต่อ Row และ 1 Cell ต่อ Column** = **Permutation Matrix** บน Empty Cells
อัลกอริทึม: Backtracking + Bitmask
- Row-by-Row: พยายามวาง Queen (Chosen Cell) ในแต่ละ Row
- Bitmask `bs`: Track Columns ที่ใช้แล้ว (Bit i = 1 → Col i ใช้แล้ว)
- Base Case: `i == n` → Found Valid Configuration (Return 1)
- Recursive: ลองทุก Column `j` ที่ `matrix[i][j]==0` และ `bs` ยังไม่มี Bit j
การติดตั้ง
class Solution:
def solve(self, matrix):
n = len(matrix)
MOD = 10**9 + 7
def dfs(row, used_cols_mask):
if row == n:
return 1
total = 0
for col in range(n):
# Check: Empty Cell และ Column ยังไม่ถูกใช้
if matrix[row][col] == 0 and not (used_cols_mask & (1 << col)):
total = (total + dfs(row + 1, used_cols_mask | (1 << col))) % MOD
return total
return dfs(0, 0)
# Test
ob = Solution()
matrix = [
[0, 0, 0],
[0, 0, 0],
[0, 1, 0]
]
print(ob.solve(matrix)) # 4
คำอธิบาย
DFS Row 0 → n-1
Bitmask `used_cols_mask`: Bit i = 1 หมายถึง Column i ถูกเลือกแล้ว
`(1 << col)`: Bitmask ของ Column `col`
`used_cols_mask & (1 << col) == 0`: Column `col` ว่าง
`used_cols_mask | (1 << col)`: ตั้ง Bit `col` ให้เป็น 1
ตัวอย่าง Matrix 3×3
Row 0: [0, 0, 0] → เลือก Col 0, 1, หรือ 2 ได้
Row 1: [0, 0, 0] → เลือก Col ที่เหลือได้
Row 2: [0, 1, 0] → Col 1 Blocked, เลือก Col 0 หรือ 2 ที่เหลือ
Valid Permutations (Column per Row):
[0, 1, 2] → Row2 Col2 Blocked ✗
[0, 2, 1] → Row2 Col1 Blocked ✗
[1, 0, 2] → Row2 Col2 OK ✓
[1, 2, 0] → Row2 Col0 OK ✓
[2, 0, 1] → Row2 Col1 Blocked ✗
[2, 1, 0] → Row2 Col0 OK ✓
[0, 2, ?] ... (Total 4 Valid)
Complexity
- Time: O(n!) Worst Case (All Empty) → Practical สำหรับ n ≤ 10-12
- Space: O(n) Recursion Stack
- Optimization: DP + Bitmask (Held-Karp) O(n × 2ⁿ) สำหรับ n ≤ 20
DP + Bitmask Version (เร็วกว่าสำหรับ n ≤ 20)
def solve_dp(matrix):
n = len(matrix)
MOD = 10**9 + 7
# dp[mask] = ways to fill first popcount(mask) rows with columns in mask
dp = [0] * (1 << n)
dp[0] = 1
for mask in range(1 << n):
row = bin(mask).count('1') # Next row to fill
if row >= n:
continue
for col in range(n):
if matrix[row][col] == 0 and not (mask & (1 << col)):
new_mask = mask | (1 << col)
dp[new_mask] = (dp[new_mask] + dp[mask]) % MOD
return dp[(1 << n) - 1]
Note: ปัญหานี้คือ **Counting Perfect Matchings in Bipartite Graph** (Rows ↔ Columns, Edge = Empty Cell) = **Permanent of 0-1 Matrix** (Permanent คล้าย Determinant แต่ไม่มี Sign)
