Có một phương pháp nổi tiếng để giải quyết vấn đề này. Cho x_1, ..., x_n là các biến tương ứng với việc bạn nhấn nút n'th như một phần của giải pháp và để a_1, ..., a_n là trạng thái ban đầu.
Hãy nói rằng bạn đang giải quyết một vấn đề 3x3, và các biến được thiết lập như thế này:
x_1 x_2 x_3
x_4 x_5 x_6
x_7 x_8 x_9
và trạng thái ban đầu này là:
a_1 a_2 a_3
a_4 a_5 a_6
a_7 a_8 a_9
Bây giờ, bạn có thể viết ra một số phương trình (trong modul số học 2) mà dung dịch phải thỏa mãn.Về cơ bản, nó mã hóa quy tắc về thiết bị chuyển mạch nào gây ra một ánh sáng cụ thể để chuyển đổi.
a_1 = x_1 + x_2 + x_4
a_2 = x_1 + x_2 + x_3 + x_5
...
a_5 = x_2 + x_4 + x_5 + x_6 + x_8
...
a_9 = x_6 + x_8 + x_9
Bây giờ bạn có thể sử dụng loại bỏ gaussian để giải quyết tập phương trình đồng thời này. Bởi vì bạn đang làm việc trong modulo số học 2, nó thực sự dễ dàng hơn một chút so với phương trình đồng thời so với số thực. Ví dụ, để loại bỏ x_1 trong phương trình 2, chỉ cần thêm phương trình đầu tiên vào phương trình.
a_1 + a_2 = (x_1 + x_2 + x_4) + (x_1 + x_2 + x_3 + x_5) = x_3 + x_4 + x_5
Cụ thể, đây là thuật toán khử Gauss trong số học modulo 2:
- Chọn một phương trình với một x_1 trong đó. Đặt tên nó là E_1.
- Thêm E_1 vào mọi phương trình chưa đặt tên khác có x_1 trong đó.
- Lặp lại cho x_2, x_3, ...., x_n.
Bây giờ, E_n là phương trình chỉ chứa x_n. Bạn có thể thay thế giá trị cho x_n bạn nhận được từ điều này vào các phương trình trước đó. Lặp lại cho E_ {n-1}, ..., E_1.
Nói chung, điều này giải quyết được vấn đề trong hoạt động O (n^3).
Dưới đây là một số mã.
class Unsolvable(Exception):
pass
def switches(vs):
n, m = len(vs), len(vs[0])
eqs = []
for i in xrange(n):
for j in xrange(m):
eq = set()
for d in xrange(-1, 2):
if 0 <= i+d < n: eq.add((i+d)*m+j)
if d != 0 and 0 <= j+d < m: eq.add(i*m+j+d)
eqs.append([vs[i][j], eq])
N = len(eqs)
for i in xrange(N):
for j in xrange(i, N):
if i in eqs[j][1]:
eqs[i], eqs[j] = eqs[j], eqs[i]
break
else:
raise Unsolvable()
for j in xrange(i+1, N):
if i in eqs[j][1]:
eqs[j][0] ^= eqs[i][0]
eqs[j][1] ^= eqs[i][1]
for i in xrange(N-1, -1, -1):
for j in xrange(i):
if i in eqs[j][1]:
eqs[j][0] ^= eqs[i][0]
eqs[j][1] ^= eqs[i][1]
return [(i//m,i%m) for i, eq in enumerate(eqs) if eq[0]]
print switches(([1, 0, 0], [0, 1, 0], [0, 0, 1], [0, 0, 0]))
Bạn đặt trạng thái ban đầu cho một hàng tại một thời điểm. Nó trả về các công tắc mà bạn cần nhấn để tắt tất cả các đèn.
Điều này giải quyết được vấn đề 50x50 trong chưa đầy nửa giây trên máy tính xách tay của tôi.
Xem thêm [Tắt đèn] (http://en.wikipedia.org/wiki/Lights_Out_%28game%29). – trashgod