Caut o solutie la o mica problema de .... matematica sau programare

[Corbu']

Pentru ce mai stiu din matematica e cam complicat ce vreau eu, eventual cine stie sa faca un mic programel ce cauta cea mai buna varianta ar fi ideal. In ce consta problema:

Se da un tabel de 5 x 5 (adica in total 25 campuri) si tabelul trebuie completat cu cifrele 1,2,3,4 astfel incat suma cifrelor din el (adica 1,2,3 si 4) sa fie cat mai mare. Cum trebuie aranjate cifrele:
1- se poate pune oriunde
2- se poate pun doar daca intr-un patrat vecin se afla 1 (nu in diagonala, doar vecin la 90 grade)
3- se poate pune doar daca in patratele vecine exista 1 si 2 (la fel doar 90 grade)
4- se poate pune doar daca are vecini pe 1, 2 si 3 (obligatoriu toate 3, iar vecinii sa fie doar la 90 grade, nu si pe diagonala).

Banuiesc ca un program da cel mai repede solutia, nu stiu cum se poate afla chestia asta doar din matematica pura, treaba e ca nu ma pricep la programat. Cine are solutia il rog sa o posteze aici. Multumesc !

P.S. Pentru cine e curios la ce imi trebuie, raspunsul este AICI (http://www.funny-games.biz/towerbloxx.html). Am jocul pe telefon si e addictive :D.

[mimed]

backtracking scrie pe tine, cauta un automatist sau cibernetician :)

[Alice]

Sunt 2^50 combinatii posibile, s-ar putea sa te cam plictisesti un pic :)

[mimed]

asta daca abordezi o maniera greedy. daca faci backtraking, elimini mai rapid variantele care nu intrunesc conditiile pana sa construiesti toata matricea de 5x5.

[blue_led]

conform enuntului, ca sa supravietuiasca un 4 trebuie sa fie invecinat cu 3, 2 si 1 . deci suprafata unui "4" este 4 si are valoare 10 .
locul de joaca are suprafata 25 deci putem planta int ( 25 / 4) = 6 nuclee de "4" . ramine o casuta in care putem spera sa plantam un 4 daca exista o combinatie favorabila de vecini .
maxim teoretic ( empiric ) = 64 .

[mimed]

mai mult de 5 cifre 4 pe terenul de 5x5 nu vad unde ar intra. un 4 nu poate intra la colt etc.

[blue_led]

6 x 4
numai 59 puncte

[Corbu']

blue led, asta e cea mai buna combinatie, cea mai buna varianta :) ? Nu ma trimiteti la automatist ca nu cunosc pe nimeni, sper sa aibe cineva dintre voi o idee. Ma gandeam ca se poate face destul de usor un program sa tot caute pe combinatii......pentru cine stie sa programeze.

[Alice]

Neah, se poate si mai bine. Am pornit de la varianta lui blue:


2 4 1 4 2
1 3 2 3 1
2 4 1 4 2
3 2 1 3 4
1 3 4 2 1

Probabil ca nu este cea mai buna varianta.
Doar ca dureaza muuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu uuult sa iti verifice toate combinatiile ;)

[Corbu']

Quad Core + OC a la CrazyPC. Care isi pune calculatorul sa munceasca la o treaba serioasa? Hai ca facem apoi benchmark, cine gaseste solutia cea mai buna in timpul cel mai scurt :D.

[Alice]

Nu ajuta quad pt. ca nu e multi-thread aplicatia.
Pe un C2D@1.66 verifica ~10.000 variante / secunda.
Sa zicem ca ar verifica 100.000 pe unul super o/c.
Tot ar ajunge la 11258999068 sec. Adica vreo 357 de ani :)

[Corbu']

:( ... toata super tehnica de astazi, super procesoare, super frecvente pe X core-uri si sunt ingenuncheate de o banala problema de matematica. Suntem departe ....

10x Alice.

Daca cineva are o varianta mai buna il rog sa o posteze.

[mache]

Alice - merge "spart" frumos numarul de iteratii prin limitarile impuse din ipoteza
- se poate folosi faptul urmator: suma tuturor elementelor trebuie sa fie in intervalul 30 ..100 (mai mare strict ca 30 si mai mic strict ca 100) si d-aci poti baga si un divide et impera (cred) pentru a "filtra" rezultatele generarii

As incerca un algoritm da' nu stiu cat de eficient il pot scrie :icon_wall

[Alice]

Nu are absolut nicio legatura divide et impera cu problema de aici.
De conditiile de la inceput iar nu prea vad cum te-ai putea lega pentru a genera o matrice.

[blue_led]

@alice : nu era cea mai buna varianta :evil: . vroiam sa demonstrez lui atreides ca se pot plasa 6 patrari . mi-a placut simetria solutiei .
se observa ca problema se poate reduce la 3x3 cu conditii suplimentare .

[blue_led]

bariera de 60 trecuta .
uite un FSB 61 ( F*** Square Board ) :D

LE: color !
demonstratie nematematica pentru maxim posibil 64 .

[Corbu']

10x blue led. 64 is max. Notat. Acum sa ma pun pe joaca :D.

[mimed]

bravo, continuati, poate gasiti si fsb 64 :)

[blue_led]

notam:numarul de "1" cu a , "2" cu b ....
a+b+c+d=25 ( numarul total de patratele )
un 4 are 3 vecini ( 3,2,1)
un 3 are 2 vecini ( 2,1)
2 se multumeste cu 1
1 ... vaduv
avem 3d+2c+b <= 40 numarul de "garduri" intre vecini
in ultima inecuatie adunam in ambii membrii a+b+c+d si obtinem :
a+2b+3c+4d <= 40+a+b+c+d
dar a+2b+3c+4d reprezinta valoarea careului iar 40+a+b+c+d = 40+25
deci
a+2b+3c+4d <=65
idealul matemetic, ce nu tine cont de faptul ca "4" are doar 3 vecini la 4 laturi ( garduri ) , efectele de margine ( unde nu se poate plasa doi de "4" lipiti ) si colt ( unde se poate plasa maxim "3" conditionat de existenta "1" si "2 " ca vecini )
se observa ca 4 este o piesa ineficienta deci trebuie sa stea la margine, singura ! sau sa stea in interiorul careului lipit alt "4" . in aceasta din urma situatie se pierde o vecinatate din maxim 40 posibile .
avem 4 colturi unde se poate plasa plasa o piesa de valoare maxima 3 in loc de 4
din valoarea maxima ( ideala ) putem scadea 4 unitati reprezentind "pierderea" de 1 unitate per colt . deci valoarea maxima este 61

[himself]

http://images6.theimagehosting.com/respect.139.th.gif (http://server6.theimagehosting.com/image.php?img=respect.139.gif)
2 blue

[Corbu']

OK, in primul rand mesaj pentru Dios. Nu am primit reply notification pe mail de la topicul asta si pana acum nici nu mi-a aparut la New Post desi verific zilnic. :( Eu am propus mai acum ceva vreme, dar propun iarasi: RSS pe forum; este muuuult mai elegant si nu se scapa nimic. Comunitatea e totusi mica dar destul de unita, mare trafic nu s-ar face pe server.

Acum back on topic. blue_led U're tha man !!! :bow2:. Si multumesc ca ti-au batut neuronii sa gaseasca solutia.