W dniu 2013-05-11 09:14, M.M. pisze:
> W dniu piątek, 10 maja 2013 20:15:52 UTC+2 użytkownik Vax napisał:
>
>> to może ktoś się podejmie oszacować złożoność obliczeniową takiego
>> problemu: [...] Chyba nie za trudne? ;)

Z innego serwera:

> to może ktoś się podejmie oszacować złożoność obliczeniową takiego
> problemu:
>
> Mamy prostokątną tablicę M x N z dwustanowymi komórkami. Przełączenie
> wskazanej komórki powoduje automatyczne przełączenie komórek
> sąsiadujących od góry, dołu, z lewej i prawej (o ile takie
> występują). Modelem może być szachownica zapełniona bierkami z
> reversi, ruch posiada dwie fazy - odwracasz wybraną bierkę, a
> następnie jej najbliższych sąsiadów (poza tymi po przekątnych).
>
> Należy dla zastanego stanu (w szczególnym przypadku wszystkie komórki
> w stanie "0") odnaleźć sekwencję ruchów, która wszystkie komórki
> doprowadzi do stanu "1" lub stwierdzić, że taka sekwencja nie
> istnieje.
>
> Chyba nie za trudne?

Było niedawno na pl.sci.matematyka
From: "J.F" <j...@p...onet.pl>
Newsgroups: pl.sci.matematyka
Subject: szachownica xor
Date: Tue, 5 Mar 2013 19:09:02 +0100
Message-ID: <513634bf$0$1218$65785112@news.neostrada.pl>


W skrócie, parzysta liczba 'kliknięć' w pole jest redukowana
do zera. Kolejność klikania też nie ma znaczenie.
Możesz więc klikną raz lub w ogole. Stąd też wiadomo,
że kliknięć nie będzie więcej niż pol szachownicy.


Zapisz kliknięcia jako wektor v. Wtedy stan danego pola możesz
opisać jakio w = A*v
gdzie A to niezbyt gęsta macierz (mniej niż 5*n*m elementów).
Oba wektory mają długość m*n, maciesrz siłą rzeczy (m*n)x(m*n).
Wszytko dzieje się modulo 2.

Konfiguracja zapalająca czy konfiguracja gasząca to to samo,
więc szykamy v, takiego, że w to nasz stan początkowy i
w = A*v

Po pierwsze, da się rozwiązać, kiedy w siedzi w przestrzeni rozpiętej
przez kolumny A (jest a obrazie A, dość trywialny wniosek).
Ponieważ obraz A będzie duży, łatwiej do algorytmu wyznaczyć kojądro*)
i sprawdzać, czy aby nasza oczekiwana konfiguracja sie z nim nie
przecina (iloczynem skalarnym).

Wiecej szczegółow.
http://www.math.ksu.edu/~dmaldona/math551/lights_out
.pdf

*) tutaj macierz A budujemy tsak, by była symetryczna A^T=A,
więc kojądro i jądro (null space) to to samo.

Ok, rozwiążemy równanie macierzowe w Z^2 (n*m)^3 ?
Ale nie musi być to rozwiązanie optymalne, do rozwiązania
możemy zawsze dorzucić wektor z jądra, i to może dać
mniej jedynek w rozwiązaniu.
Np dla tablicy 19x19 wymiar jądra to 16, więc trzeba by
sprawdzić 65 tysiecy przypadków:/
Czy istnieje jakiś lepszy sposób na przeszukanie takiego zestawu?

Jeszcze mniej formalny link z wątku z matematyki:

http://www.jaapsch.net/puzzles/lights.htm


pzdr
bartekltg