W dniu 2013-05-12 01:59, M.M. pisze:

[...]

> Mozna troche przerobic Twoje spostrzezenie. Kazdy klik pewne pola zapala a
> inne gasi. Niech to bedzie klik x. Wiec klik x determinuje kliki ktore
> musza zgasic to co on zapalil. Jesli kolejnosc jest niewazna, to klik x
> moze determinowac je jako kliki w nastepnej kolejnosci. Wiec kazde pole moze
> miec zapamietany numer+1 rekurencyjnego wywolania w ktorym zostalo zapalone
> lub jeden jesli bylo dane w ukladzie poczatkowym. Algorytm w kazdym
> kroku musi zgasic dowolne pole o najmniejszym numrze. To na pewno zmniejszy
> breanch-faktor.

W skrócie, to wyszedłem z takiego założenia:
1. działa to jak XOR, czyli jest naprzemienne
2. skoro kolejność nie ma znaczenia, to ja ją (na swoje potrzeby)
uporządkuję np. od góry, do dołu
3. po wykonaniu wszystkich klików pierwszego wiersza już do niego nie
wracam, zatem w wierszu drugim MUSZĘ ustawić pożądany stan wiersza
pierwszego, klikając POD polami (i TYLKO POD nimi), które mają ów stan
niewłaściwy. W kolejnym wierszu już takiej szansy nie będzie, więc nie
zostanie spełniony warunek zadania.

np. gdy pierwszy rząd po testowym klikaniu wygląda tak:
11010001 to muszę kliknąć pod nim: --x-xxx- (gdzie "x" to click, a "-"
jego brak, nie chcę używać 0/1 żeby się komuś clicki i stany nie myliły :)),
rząd 1 wówczas wygląda już tak: 11111111,
nastąpiły zmiany w rzędzie 2 oraz 3, ale tu już iteracyjnie powtarzamy
aż do ostatniego, po czym badamy, czy on też przyjął postać 11111111.

> Pozostaje kwestia czy mozna jakos uniknac spamietywania?

Trzymając się dalej tablicy np. 8 x 1024, musimy wykonać najwyżej 256
iteracji, od 00000000(bin) do 11111111(bin), czyli np. zwykłą pętlą od 0
do 255 sobie polecieć. Licznik pętli ma już sam z siebie na sobie
zapisane wszystkie układy "klików" do przetestowania.
Gdy kombinacja dla pierwszego wiersza jest dobra, to mamy sukces (i
możemy prościutko odtworzyć wszystkie pola wymagające kliknięcia).

> Algorytm z spamietywaniem jest prosty Jesli docieramy do ukladu ktory byl
> wczesniej, to wnioskujemy ze zaczyna sie petlic. Ale takie podejscie
> wymagaloby sporo pamieci.

Tu, poza tablicą wejściową, masz licznik + 2 bufory o rozmiarze
krótszego boku każdy, wszystko na bitach. Nazwa pliku zajmie więcej
pamięci ;)

> Moze wystarczy zapamietac z kazdym polem, ze juz bylo raz zapalone i potem
> zgaszone? Intuicja podpowiada, ze nie ma sensu zapalac danego pola dwa razy.
> Nie wiem czy moja intuicja sie nie myli, ale jesli to prawda, to algortym
> moze przerwac przeszukiwanie danej galezi, jesli nie da sie zgasic jakiegos
> pola bez zapalania tych pol, ktore juz wczesniej byly zgaszone.

Jeszcze raz: iteracyjnie XOR-ujesz licznik z pierwszym rzędem i drugim,
pamiętając, że XOR w rzędzie klikniętym to nie zwykły XOR, ale również
odwrócenie sąsiadujących bitów.
Tak swoją drogą, to znalezienie nieiteracyjnego algorytmu (lub formuły),
które dla danego ciągu bitów zwróca ciąg z którym wystarczy RAZ wykonać
"zwykły XOR" (czyli: 0001 => 0011, 0010 => 0111, 0011 => 0100 itd.) to
też fajna rozrywka, ale to takie "podzadanie" w zadaniu raczej :)
Kontynuując:
Po wykonaniu testowanej serii klików na pierwszym rzędzie (pamiętaj,
pierwszy wiersz zmienia się "nieco magicznie", drugi to już zwykły XOR,
poprzez negację wiersza pierwszego otrzymujemy mapę kliknięć do
wykonania na następnym wierszu. I tak z każdym kolejnym wierszem aż do
ostatniego. I albo się udało (po "magicznym XOR" mam same jedynki), albo
przechodzimy do kolejnej kombinacji kliknięć w pierwszy rząd.