สมมติว่าเรามีเมทริกซ์ n×n ที่มีค่าจาก 0 ถึง n โดย 0 แทนช่องว่าง เราต้องตรวจสอบว่าเราสามารถเติมช่องว่างได้หรือไม่ เพื่อให้แต่ละแถวและแต่ละคอลัมน์มีตัวเลข 1 ถึง n ครั้งละครั้ง (Latin Square)
ตัวอย่างเช่น เมทริกซ์:
0 0 2 2 0 1 1 2 3สามารถเติมได้เป็น:
3 1 2 2 3 1 1 2 3ดังนั้นผลลัพธ์คือ True
ขั้นตอนการแก้ปัญหา (Backtracking)
find_empty_cell(matrix, n): หาช่องที่มีค่า 0 คืนค่า (i, j) หรือ (-1, -1) หากไม่มีis_feasible(matrix, i, j, x): ตรวจสอบว่าวาง x ที่ (i, j) ได้หรือไม่ (ไม่ซ้ำในแถวและคอลัมน์)is_complete(matrix, n): ตรวจสอบว่าเมทริกซ์สมบูรณ์และถูกต้องหรือไม่- ฟังก์ชันหลัก
solve(matrix):- หาช่องว่าง ถ้าไม่มี ให้ตรวจสอบ
is_complete - ลองวาง x = 1 ถึง n หาก
is_feasibleให้วางและเรียก solve() recursive - หากล้มเหลว ให้ backtrack (ล้างค่าเป็น 0)
- คืนค่า True/False
- หาช่องว่าง ถ้าไม่มี ให้ตรวจสอบ
ตัวอย่างโค้ด Python
class Solution:
def solve(self, matrix):
n = len(matrix)
def find_empty_cell(matrix, n):
for i in range(n):
for j in range(n):
if matrix[i][j] == 0:
return (i, j)
return (-1, -1)
def is_feasible(matrix, i, j, x):
if x in matrix[i]:
return False
if x in [row[j] for row in matrix]:
return False
return True
def is_complete(matrix, n):
for row in matrix:
if set(row) != set(range(1, n + 1)):
return False
for col in range(n):
if set(row[col] for row in matrix) != set(range(1, n + 1)):
return False
return True
(i, j) = find_empty_cell(matrix, n)
if (i, j) == (-1, -1):
return is_complete(matrix, n)
for x in range(1, n + 1):
if is_feasible(matrix, i, j, x):
matrix[i][j] = x
if self.solve(matrix):
return True
matrix[i][j] = 0
return False
ob = Solution()
matrix = [
[0, 0, 2],
[2, 0, 1],
[1, 2, 3]
]
print(ob.solve(matrix)) # Output: True
อินพุต
matrix = [[0, 0, 2], [2, 0, 1], [1, 2, 3]]
เอาต์พุต
True
