`energy`

function is pretty straightforward: just the sum of the squared difference between current ball (and gap) indices and the target ones.[update]

It looks that simulated annealing have hard time with this problem (well, at least, I had hard time trying to find a good energy function...).

The following just takes long time in order to compute suboptimal solutions.

I'm not happy with it, but, nevertheless I post it here hoping it could somehow help.

C#

using System; namespace SA { class Ball { public readonly int targetIndex; public readonly string id; public Ball(string id, int targetIndex) { this.id = id; this.targetIndex = targetIndex; } public int energy( int index) { int d = (targetIndex-index)*2; int e = d*d; // 'basic' enrgy: squared distance from target index if ( targetIndex < 3 ) { if ( index >= 3) e += 1000; // sum a noticeable energy when 'on the wrong side' } else if ( targetIndex == 3) { e += d*d*d*d*1000; // sum big energy if the gap is in wrong position } else { if ( index <= 3) e += 1000; // sum a noticeable energy when 'on the wrong side' } return e; } } class Test { static int energy( Ball [] ball) { int e = 0; for (int n=0; n< ball.Length; ++n) { e += ball[n].energy(n); } return e; } static double probability(int energy, double temperature) { if (energy <=0) return 1.0; double p = Math.Exp(-(double)energy/temperature); return p; } static void dump( Ball [] ball, int energy, double temperature) { foreach (var b in ball) { Console.Write("{0} ", b.id); } Console.WriteLine("{0} {1}", energy, temperature); } // Driver method public static void Main() { const double THot=300000; const double TCold=30000; const double TSub=2.0; double t = THot; Random rnd = new Random(); Ball [] ball = new Ball[8]; ball[0] = new Ball("B1", 4); ball[1] = new Ball("B2", 5); ball[2] = new Ball("B3", 6); ball[3] = new Ball("B4", 7); ball[4] = new Ball("GP", 3); ball[5] = new Ball("W1", 0); ball[6] = new Ball("W2", 1); ball[7] = new Ball("W3", 2); int cur_gp_index = 4; int cur_energy = energy(ball); while ( t > TCold) { const int Iterations = 250; for (int n=0; n<Iterations; ++n) { int new_gp_index; int new_energy; for (;;) { int r = rnd.Next(-2,3); // <- Fixed a blunder, thanks to Luc Pattyn new_gp_index = cur_gp_index + r; if ( new_gp_index != cur_gp_index && new_gp_index >=0 && new_gp_index<=7) break; } // swap Ball temp = ball[new_gp_index]; ball[new_gp_index] = ball[cur_gp_index]; ball[cur_gp_index] = temp; new_energy = energy(ball); if ( probability( new_energy - cur_energy, t) > .95) { //dump (ball, new_energy, t); cur_energy=new_energy; cur_gp_index = new_gp_index; } else { temp = ball[new_gp_index]; ball[new_gp_index] = ball[cur_gp_index]; ball[cur_gp_index] = temp; } } t-=TSub; } dump (ball, cur_energy, t); Console.WriteLine("done."); Console.ReadLine(); } } }

[/update]

"but the function is stuck."Then unstick it. Seriously, you can not expect anyone here to guess what your code is doing. Please use the Improve question link above and provide some proper details.