#include <iostream>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <assert.h>
#include <stdio.h>

using namespace std;

const int kSize = 160;

const string words[] = {
"CHEVALIER", "RAYEARTH", "LANCELOT", "CHIVALRY", "PULLIAM",
"MICHAEL", "HOLLAND", "GALAHAD", "GABRIEL", "CAMELOT",
"SQUIRE", "RITTER", "RIDDER", "RAMUNE", "KESHIA",
"GOTHAM", "GLADYS", "GAWAIN", "ERRANT", "BATMAN",
"ARTHUR", "WHITE", "WAYNE", "TABLE", "SWORD",
"SPEAR", "ROUND", "RIFLE", "QUEST", "NOBLE",
"MOVES", "MOVES", "LANCE", "GREEN", "FIRST",
"BLACK", "ARMOR", "TOUR", "TALE", "PAGE",
"KING", "JEDI", "HELM", "DARK", "TED",
"SIR",
};

class WordPlacement {
 public:
  int score;
  int index;
  int dir;
  int startpos;

  WordPlacement(const int idx, const int sp,
                const int d, const int sc) :
    index(idx), startpos(sp), dir(d), score(sc) {
  }
  void print() const {
    printf("WP %d %s %d %d %d\n", index, words[index].c_str(),
       score, startpos, dir);
  }
};

struct wpcomp {
  bool operator()(const WordPlacement w1, const WordPlacement w2) const {
    if (w1.score != w2.score) return w1.score > w2.score;
    if (w1.index != w2.index) return w1.index < w2.index;
    if (w1.dir != w2.dir) return w1.dir < w2.dir;
    return w1.startpos < w2.startpos;
  }
};

struct wpcompns {
  bool operator()(const WordPlacement w1, const WordPlacement w2) const {
    if (w1.index != w2.index) return w1.index < w2.index;
    if (w1.dir != w2.dir) return w1.dir < w2.dir;
    return w1.startpos < w2.startpos;
  }
};

typedef set<WordPlacement, wpcompns> wpnsset;
typedef set<WordPlacement, wpcomp> wpset;

typedef pair<int,int> coords;

coords getCoords(const int val) {
  return coords(val/kSize,val%kSize);
}

int getVal(const coords co) {
  return co.first*kSize+co.second;
}

class Grid {
 public:
  static const int origin = kSize*kSize/2 + kSize/2;
  static const int offsets[8];
     
  char contents[kSize*kSize];
  set<int> wordsused[kSize*kSize];
  vector<coords> min, max;
  multiset<int> ccd[26];

  Grid() {
    for (int i=0; i<kSize*kSize; ++i) {
      contents[i] = '.';
    }
    coords temp(kSize/2,kSize/2);
    min.push_back(temp);
    max.push_back(temp);
  }

  void addCoords(const coords c) {
    int row = min.back().first;
    int col = min.back().second;
    if (c.first < row) row = c.first;
    if (c.second < col) col = c.second;
    min.push_back(coords(row,col));
    row = max.back().first;
    col = max.back().second;
    if (c.first > row) row = c.first;
    if (c.second > col) col = c.second;
    max.push_back(coords(row,col));
  } 

  void dropCoords() {
    min.pop_back();
    max.pop_back();
  }

  static int expanse(const int mins, const int maxs, 
                     const int v1, const int v2) {
    assert(mins < maxs);
    if (v1 > v2) return expanse(mins,maxs,v2,v1);
    if (v1 > mins) return expanse(mins,maxs,mins,v2);
    if (v2 < maxs) return expanse(mins,maxs,v1,maxs);
    return (mins - v1 + v2 - maxs);
  }

  int coordScore(const int p1, const int p2) {
    coords c1 = getCoords(p1);
    coords c2 = getCoords(p2);
    int rowOff = expanse(min.back().first, max.back().first,
                         c1.first, c2.first);
    int colOff = expanse(min.back().second, max.back().second,
                         c1.second, c2.second);
    return (50 - rowOff - colOff);
  }

  void place(const char c, const int pos) {
    if (contents[pos] != '.')
      assert(contents[pos] == c);
    contents[pos] = c;
    coords co = getCoords(pos);
    addCoords(co);
    ccd[c - 'A'].insert(pos);
  }

  char unplace(const int pos) {
    const char val = contents[pos];
    assert (val >= 'A');
    multiset<int> &v = ccd[val - 'A'];   
    assert( v.size() > 0);
    assert(v.find(pos) != v.end());
    v.erase(v.find(pos));
    if (v.find(pos) == v.end()) {
      contents[pos] = '.';
    }
    dropCoords();
    return val;
  }

  void place(const int index, const int startpos, 
             const int dir, const int offset = 0 ) {
    const string s = words[index];
    int pos = startpos - offsets[dir] * offset;
    for (int i=0; i < s.length(); ++i) {
      place(s[i],pos);
      wordsused[pos].insert(index);
      pos += offsets[dir];
    }
  }
 
  void place(const WordPlacement wp) {
    place(wp.index, wp.startpos, wp.dir);
  }

  void unplace(const WordPlacement wp) {
    unplace(wp.index, wp.startpos, wp.dir);
  }

  int score(const string s, const int startpos, 
             const int dir, const int offset = 0 ) {
    // a negative score means "doesn't fit"
    set<int> hits;
    int pos = startpos - offsets[dir] * offset;
    int tscore = coordScore(pos, startpos
        + offsets[dir] * (s.length() - offset - 1))*100;
    for (int i=0; i < s.length(); ++i) {
      if (contents[pos] != '.' &&
          contents[pos] != s[i]) return -1;
      if (contents[pos] != '.') {
        const set<int> &wu = wordsused[pos];
        for (set<int>::iterator it = wu.begin();
             it != wu.end(); ++it) {
          if (hits.find(*it) != hits.end())
            return -2;
          hits.insert(*it);
        }
        tscore += 30;
      }
      pos += offsets[dir];
    }
    return tscore * s.length();
  }

  void unplace(const int index, const int startpos, 
             const int dir, const int offset = 0 ) {
    const string s = words[index];
    int pos = startpos + offsets[dir] * (s.size() - 1 - offset);
    for (int i = s.size() -1 ; i >= 0; --i) {
      const char c = unplace(pos);
      assert ( c == s[i] );
      wordsused[pos].erase(index);
      pos -= offsets[dir];
    }
  }

  void print() const {
    for (int r=min.back().first; r<=max.back().first; ++r) {
      for (int c=min.back().second; c<=max.back().second; ++c) {
        cout << contents[getVal(coords(r,c))];
      }
      cout << "\n";
    }
    cout << "\n";
  }

  wpset findCandidates(const set<int> toplace) {
    wpset answer;
    for (set<int>::iterator it = toplace.begin();
         it != toplace.end(); ++it) {
      const int index = *it;
      const string& word = words[index];
      for (int i=0; i<word.length(); ++i) {
        const char letter = word[i];
        const multiset<int>& group = ccd[letter-'A'];
        for (multiset<int>::iterator it2 = group.begin();
             it2 != group.end(); ++it2) {
          for (int dir=0; dir<8; ++dir) {
            const int sc = score(word, *it2, dir, i);
            if (sc > 0) {
              int startpos = *it2 - offsets[dir] * i;
              answer.insert(WordPlacement(index, startpos, dir, sc));
            }
          }
        }
      }
    }
    return answer;
  }

};

const int Grid::offsets[8] = 
    { kSize + 2,  kSize - 2,
     -kSize + 2, -kSize - 2,
     -2*kSize + 1, -2*kSize - 1,
      2*kSize + 1,  2*kSize - 1 };

int bestscore = 0;
int ccc = 0;
int rollbackcounter = 0;
bool rollback = false;

void printc(vector<int*>* const countdown) {
  for (vector<int*>::iterator it = countdown->begin();
       it != countdown->end(); ++it) {
    cout << **it << ",";
  }
  cout << "\n";
}

void recurse(Grid* const g, set<int>* const toplace,
             vector<wpnsset*>* const historical, const int score,
             vector<int*>* const countdown) {
  ++rollbackcounter;
  if (rollbackcounter > 1000000) {
    rollbackcounter = 0;
    rollback = true;
  }
  if (rollback && (toplace->size() < 20)) {
    return;
  }
  rollback = false;
  wpset wp = g->findCandidates(*toplace);

  wpnsset my_historical;
  historical->push_back(&my_historical);

  int my_counter = wp.size();
  countdown->push_back(&my_counter);

  for (wpset::iterator it = wp.begin();
       it != wp.end(); ++it) {
    --my_counter;
    bool seen = false;
    for (vector<wpnsset*>::iterator it2 = historical->begin();
         it2 != historical->end(); ++it2) {
      if ((*it2)->find(*it) != (*it2)->end()) {
        seen = true;
      }
    }
    if (!seen) {
      const int newscore = score + score+(it->score);
      const bool doprint = (newscore >= bestscore);
      if (newscore >= bestscore) bestscore = newscore;
      g->place(*it);
      toplace->erase(it->index);
      my_historical.insert(*it);
      if (doprint) cout << "Score is " << newscore << "\n";
      if (doprint) it->print();
      if (doprint) g->print();
      recurse(g,toplace,historical,newscore,countdown);
      toplace->insert(it->index);
      g->unplace(*it);
    }
    ccc++;
    if (ccc > 100000) {
      ccc = 0;
      printc(countdown);
    }
  }

  historical->pop_back();
  countdown->pop_back();
}

int main() {
  Grid g;

  g.place(0,g.origin,0);
  g.print();

  set<int> toplace;
  for (int i=1;i<46;++i) toplace.insert(i);

  vector<wpnsset*> historical;
  vector<int*> countdown;

  recurse(&g, &toplace, &historical, 0, &countdown);

}