Szukanie optimum a zero-zmiany

[Borneq]

Jest pierwszy , łatwiejszy problem: mamy na ogromnej szachownicy rozmiaru NxN N hetmanów, które nie mają sobie zagrażać.
Jedno rozwiązanie dla małych N jest na rosetta-code w C++: rekurencyjne szukanie wielu (wszystkich) rozwiązań. Mnie interesuje jedno rozwiązanie, za to dla dużych N. Ponieważ w jednym wierszu, może być tylko jeden hetman, cały wiersz wystarczy przedstawić jako jedną liczbę- kolumnę na której jest. W innym wierszu jest inna kolumna, więc mamy problem kombinatoryczny. Robię tak: inicjuję kolumny (licząc od 1) 1,2,3,..N, robię tasowanie: np otrzymując 5,1,4,2,..7. Jest to początkowy stan, ma wiele konfliktów, które zliczam. Losowo wybieram dwa wiersze i zamieniam gdy ilość konfliktów maleje lub się nie zmienia. Dla tego łatwiejszego problemu dobrze działa, N może pzekraczać 1000. Czy robiąc swap wierszy, nie otrzymam wszystkich kombinacji?
Czasem wpada w lokalne optimum, zwłaszcza przy ilości kolizji=1. Wtedy (po niezdefiniowanym okresie powtórzeń) robię rotację o 1 i zamiast 5,1,4,2,..7.mam 1,4,2,..7,5. Rotacja powoduje pogorszenie ilości kolizji, ale ruszenie z miejsca. Inne sposoby na wydobycie się z miejsca nie działały: np. rotacja nie o 1, ale o numer minimalnych kolizji: minimalne są zwykle dla plus minus 1, gdy dopuszczałem rotację minus 1, zapętlało się : raz w jedną stronę, raz w drugą. Gdy chciałem ruszyć wymianą trzech wierszy - dużo wzrastała ilość kolizji, a gdy chciałem zrobić swap, który minimalnie pogorszałby - nastęþny swap wracal na miejsce, potem znowu tamten i zapętlenie.
Teraz trudniejszy problem: nie tylko dwa nie mogą lezeć na tym samym wierszu, kolumnie czyprzekątnej, ale każde 3 nie mogą leżeć na tej samej prostej pod dowolnym kątem np. 23.7 stopnia.
Minimalna ilośc N dla hemtanów to 4, tutaj minimalny N=9, np "5 2 4 9 7 3 1 6 8"
Tutaj testuję dla N=50
Robię rotację po 1000*N czyli 50 tysiącach dopiero i nie wiem jak dla większych N.Chciałem zrobić tak:zbieram wszystkie pary, dla N=50 będzie to 1225 czyli \(\displaystyle{ \frac{n(n-1)}{2}}\). To znacznie mniej niż 50 tysięcy, ale jest problem, gdy to zrobiłem , były częste rotacje, ale duzo tych rotacji , tak że wcale nie mógl ukończyć pracy. Serie, po których nie było rotacji, ale w końcu zmniejszała się ilość kolizji, też były znacznie dłuższe niż 1225
Dlaczego? W końcu doszedłem że za to odpowiadają zero-zmiany. Gdy ilość kolizji się zwiększa, nie ma swapu (jest tylko swap próbny), gdy się zmniejsza, ustawiany jest licznik, ale może być taka sama, jest to w istocie częstsze niz zmniejszenie ilości kolizji (choć o wiele cześciej zwiększa się ilość kolizji)
Teraz chcę zrobić tak: generuję 1225 par, są wypróbowane, gdy się zwiększa - omija, gdy zmniesza się ilość kolizji - wykonanie i koniec. A gdy bez zmian - nie robię swapu, tylko wrzucam parę do listy, która będzie wykonana na końcu. Na końcu jest kilka możliwośći zero-zmian.Jednak dla po wykonaiu takiej zero-zmiany, lista par powinna zostać 1). unieważniona i wygenerowana na nowo., 2) w tej nowej liście nie powinno być pary, która wraca do poprzedniego stanu, bo nastąpi zapętlenie.
Pytanie: jak tu napisać algorytm, by nie następiło zapętlenie? z jednych zero - zmian, mogą wynikać nastęþne i następne, i moze być powrót do poprzedniej niebezpośredni?
Czy dobrym oznaczeniem stanu tabeli będzie hasz? Ale jaki? nie operuję na bajtach ale liczbach np. około 1000. Hasz potrzebny do tego, aby sprawdzic czy przez któreś zero nie wracam do stanu poprzedniego. Mógłby byc prosty 32 lub 64 bitowy hasz.

Dodano po 6 godzinach 46 minutach 48 sekundach:
Hasz, jak pisałem w sąsiednim wątku: suma iloczynu danych i ich pozycji powiększonej o 1

[Borneq]

Czy algorytmy genetyczne są równoważne takiemu szukaniu, czy może lepiej działają? Choć sam nie wiem, jak można by w tym przypadku zaostosować algorytm genetyczny, kiedy mamy pewien stan, i prawie wszystkie inne stany są gorsze, nieliczne takie same, a prawie wcale nie ma lepszych.

[Borneq]

Jaki jest minimalny rozmar planszy dla hetmanów? Dla 8 najszybicjej wylicza, ale nie zawiesza sie również dla 7, choć trudniej to wylicza niż dla 8:
czy nie ma błedu?

Kod: Zaznacz cały

..*....
....*..
......*
.*.....
...*...
.....*.
*......

[kerajs]

Mniejsze:
\(\displaystyle{ OOXO\\
XOOO\\
OOOX\\
OXOO\\
\\
------------------\\
\\
OOOXO\\
XOOOO\\
OOXOO\\
OOOOX\\
OXOOO}\)