/*********************************************************

Problem:  (Ingo Alth"ofer, Jena, 31. Jan 1995)
--------
 
Arrange the four letters {A,B,C,D} into a 5x5 square.
You have to use 9*A, 6*B, 5*C, and 5*D.
 
Adjacent letters get a cost shown in the following table:
 
 Cost Phi:     A  B  C  D
             +-----------
           A | 0  0  1  4
           B | 0  3  2  2
           C | 1  2  0  0
           D | 4  2  0  0
 
The cost table is symmetric.
 
Determine all arrangements which give the minimal total
cost according the cost function Phi.

Program:  Udo Sprute
          mailto:sprute@hrz.uni-bielefeld.de

*********************************************************/

#include <iostream.h> 
#include <stdlib.h> 

enum symbol {Kreuz, Karo, Kreis, Kerze}; 
unsigned pieces [] = {9, 6, 5, 5}; 
char sign [] = "ABCD"; 

const unsigned types = 4; 
unsigned Kosten [types][types] = { 
   {0, 0, 1, 4}, 
   {0, 3, 2, 2}, 
   {1, 2, 0, 0}, 
   {4, 2, 0, 0} 
}; 

const unsigned size = 5; 
symbol Kammer [size][size]; 

unsigned best = 6; 
unsigned sum = 0; 

extern void fill (unsigned, unsigned); 

void Druckkammer (unsigned value) 
{ 
   for (unsigned i=0; i<size; i++) { 
      for (unsigned j=0; j<size; j++) 
         cout << sign[Kammer[i][j]]; 
      cout << endl; 
   } 
   cout << value << endl; 
} 

inline void insert (unsigned i, unsigned j, symbol k) 
{ 
   if (pieces[k]) { 
      if (i) 
         sum += Kosten[Kammer[i-1][j]][k]; 
      if (j) 
         sum += Kosten[Kammer[i][j-1]][k]; 
      if (sum <= best) { 
         Kammer[i][j] = k; 
         pieces[k]--; 
         if (j < size-1) 
            fill (i, j+1); 
         else if (i < size-1) 
            fill (i+1, 0); 
         else 
            Druckkammer (best = sum); 
         pieces[k]++; 
      } 
      if (i) 
         sum -= Kosten[Kammer[i-1][j]][k]; 
      if (j) 
         sum -= Kosten[Kammer[i][j-1]][k]; 
   } 
} 

void fill (unsigned i, unsigned j) 
{ 
   insert (i, j, Kreuz); 
   insert (i, j, Karo); 
   insert (i, j, Kreis); 
   insert (i, j, Kerze); 
} 

int main (int argc, char ** argv) 
{ 
   if (argc == 2) { 
      best = atoi (argv[1]); 
      fill (0, 0); 
      return 0; 
   } else { 
      cerr << "Usage: " << argv[0] << " "; 
      cerr << "<genehmigte Kosten>" << endl; 
      return 1; 
   } 
}