From: michael@refract.com.au   
      
   Hi all,   
      
   I've got a problem trying to maximise the score for an n x n grid of   
   integers where only one value from each row and column can be chosen   
   (the score is the sum of the n chosen values). I've tried to find   
   algorithms to solve this problem by searching the web, however   
   searching for "grid optimization" or similar yields many results that   
   are irrelevant to this problem - and unfortunately I don't know how   
   else to describe it.   
      
   I'm sure it's a very common problem, but after lots of fiddling, I   
   still can't figure out whether it's solvable in less than O(n!) time   
   (ie without going through every solution and finding the maximum - or   
   reverting to a non-optimal algorithm like simulated annealing or   
   similar) - in fact, I don't even know if it's difficult enough to be   
   considered an AI problem, and if not, please let me know a more   
   appropriate forum to post to.   
      
   Here's an example grid with labelled rows and columns, where n=3:   
      
      |  X |  Y |  Z |   
    --+----+----+----+   
    A | 11 |  3 | 16 |   
    --+----+----+----+   
    B | 14 |  4 | 17 |   
    --+----+----+----+   
    C | 17 | 10 | 13 |   
    --+----+----+----+   
      
   The optimal solution is:   
   BX + CY + AZ = 14 + 10 + 16 = 40   
      
   For n=3, there are only 6 choices, so it would be trivial to just go   
   through them all and find the best, but for n=16, it gets a little   
   trickier :-)   
      
   I've tried all sorts of schemes involving differences between max   
   values for each row/column, or summing max cols/rows after making a   
   move, etc, etc - all quite quick, but fail ever so slightly for   
   special cases.   
      
   So, has anyone seen a problem similar to this or can anyone point me   
   in the correct direction to look?   
      
   Cheers,   
      
   Michael   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)