[php] Kwadrat magiczny - jak stworzyc ? Opcje

[-Gość-]

Witam,
mam do Was prosbe - poszukuje nie tyle co gotowego rozwiazania, bo pisac w miare w php umiem, ale algorytmu, albo jakiegos naprowadzenia w napisaniu programu generujacego kwadrat magiczny - jednak nie taki standardowy kwadrat, tylko cos podobnego do sudoku - dla zadanego n kwadrat magiczny o wymiarach n×n (kwadrat magiczny w wierszach, kolumnach i na obu przekątnych ma permutacje ciągu 1, 2, 3, ..., N).
Za wszelka pomoc z gory dziekuje.

PS> szukalem sporo tego na necie, ale jest albo typowy kwadrat magiczny, albo kwadrat do sudoku, albo kwadrat, w ktorym nie ma uwzglednionych przekatnych.

Dla przykladu kwadrat o n=4:

----------------
| 1 | 3 | 4 | 2 |
| 4 | 2 | 1 | 3 |
| 2 | 4 | 3 | 1 |
| 3 | 1 | 2 | 4 |
----------------

[siemakuba]

ha! spróbowałem trochę :) udało mi sie stowrzyć poprawnie generujący się kwadrat o n=4 i n=5. Z pobieżnej analizy wynika, że te dwa mają tylko jedne możliwe rozwiązanie. Kwadrat o n > 5 to już trochę inna bajka, bo zaczyna pojawia się więcej możliwości ustawienia cyfr. Wystarczy jedno nietrafione podstawienie i klapa... Trzeba by zapamiętać, że w polu o takich a takich współrzędnych na pewno nie pasuje dana cyfra, i przy kolejnej próbie pomijać tę cyfrę. I tak aż do skutku.

Poszedłem taki tokiem myślenia, nie wiem czy słusznym :)
1. ustawiłem cyfy po przekątnej północy-zachód -> południowy wschód od 1 do n kolejno
2. ustawiłem cyfry po przekątnej północny-wschód -> południowy-zachód
3. podstawiałem kolejno wartości, sprawdzając czy pasują.

Stworzyłem do tego tablicę z cyframi od 1 do n, tablicę wartośc X-Y i tablicę wartości Y-X. Docierając do pustego pola o współrzędnych np. 4-3, sprawdzam po koleji każdy elemeny z zakresu (1-n) na okoliczność jego wsytąpienia na osi X i Y o współrzędnych 4 i 3. Jeżeli dany element już tam jest, sprawdzam następny. I tu właśnie pojawia się możliwość kliku poprawnych trafień...

pozdr.

[-Gość-]

@Kuba - wlasnie do takiego rozwiazania tez doszedlem - najpierw przekatne, a potem sprawdzam puste pole - najpierw sprawdzam wartosci w tej samej kolumnie i tym samym wierszu - jezeli jest jakas liczba, ktora nie wystepuje i tu i tu to wtedy ja wrzucam. Ale niestety nie zawsze to dziala :/

[siemakuba]

tak właśnie - jak pisałem, dla kwadratu o n=4 i n=5 działało bez zarzutu. Może to kwestia dobrego trafienia, chociaż wiele przypadku tu nie było bo nie robiłem żadnego losowania tylko sprawdzałem kolejne elementy sprawdzając od 1 w górę. Pierwszy pasujący wstawiam i jade dalej.

Przy kwadracie o n > 5 właściwie już ustawienie drugiej przekątnej jest problematyczne, bo chyba nie daje żadnej gwarancji że będzie OK, bo jest więcej możliwości ustawienia poprawnie samej drugiej przekątnej względem pierwszej przekątnej.

Przyszło mi do głowy zrobienie tego trochę inaczej - NIE podstawiać pierwszej pasującej cyfry, ale zebrać je do tablicy pasujące. np:

[PHP] pobierz, plaintext 
<?php
$possibilities['y'][2][6] = array(1,4,6);
?>
[PHP] pobierz, plaintext 

Po zebraniu wszystkich możliwości dla wszystkich pól przystępujemy do podstawiania. Pierwsze miejsce gdzie napotykamy na problem, że nic nie pasuje powoduje cofnięcie się do poprzedniego wstawianego elementu, wyzerowanie go i usunięcie z tablicy $possibilities tej cyfry. I od nowa. W ten sposób zawężają nam się stopniowo możliwości, i być może efekt ostateczny będzie zadowalający :)

może wieczorem jeszcze nad tym zasiąde.

pozdr.

[-Gość-]

Teraz bede probowal zrobic to w sposob taki, ze po ustawieniu przekatnych bede wrzucal do kolumn po kolei wszystkie cyfry, ktore pasuja a na koncu liczyl ich iloczyn - jezeli sie nie bedzie zgadzal to bedzie generwowal od nowa przekatne - bo one maja decydujace znaczenie. Znacznie obnizy sie wydajnosc tego programu (o ile w ogole to zadziala), ale to ma dzialac, nie koniecznie efektywnie. Takie cos w stylu brute-force bedzie - sprawdzanie wielu kombinacji.

[-Gość-]

Udalo mi sie zrobic tak, zeby generwowal losowo dobry kwadrat magiczny, jednak jedynie dla n=4 i n=5. Dla n=6 juz niestety php nie wyrabia - Fatal Error i allocated memory exceeded. Jeszcze moze mi sie udac, zeby dzialal dla n=6, ale zeby to dzialalo trzeba jakis szybszy jezyk np. C, chyba ze jest jakas inna metoda. Ale chociaz dobrze, ze tyle dziala.

[-Gość-]

OK, po delikatnych modyfikacjach juz dziala szybciej - max 8x8, jednak nie zawsze, bo czasem limit pamieci znow mu nie starcza (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) Ale dziala elegancko