home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / exampleCode / games / seahaven / auto.c++ next >
Encoding:
C/C++ Source or Header  |  1994-08-02  |  25.0 KB  |  1,002 lines
  1. /*
  2.  * Copyright 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. #include <stream.h>
  18.  
  19.  
  20. #include <strings.h>
  21. #include <stdlib.h>
  22.  
  23. #include <sys/types.h>
  24. #include <sys/time.h>
  25.  
  26. #include <fcntl.h>
  27. //#include <osfcn.h>
  28.  
  29. //#include <stdlib.h>        // for getenv()
  30.  
  31.  
  32. #include "auto.h"
  33.  
  34.  
  35.  
  36. #undef BATCH
  37. #undef INTERACTIVE
  38. #undef VERBOSE
  39. #undef DYNAMIC
  40. #undef AUTO
  41.  
  42. #define AUTO
  43.  
  44. #ifdef BATCH
  45. int solved_count = 0;
  46. int failed_count = 0;
  47. int solved_moves = 0;
  48. int solved_moves_max = 0;
  49. int failed_moves = 0;
  50. int failed_moves_max = 0;
  51. int solved_time = 0;
  52. int failed_time = 0;
  53. #endif
  54.  
  55.  
  56. struct timezone tz;
  57. struct timeval start_time;
  58. struct timeval end_time;
  59.  
  60. typedef int Boolean;
  61.  
  62. typedef enum Suit {
  63.     SuitFirst, Hearts=SuitFirst, Diamonds, Clubs, Spades, SuitLast=Spades
  64.     } Suit;
  65.  
  66. const int NumSuits = SuitLast+1;
  67.  
  68. typedef enum Rank {
  69.     RankFirst, Ace=RankFirst, Two, Three, Four, Five, Six, Seven,
  70.     Eight, Nine, Ten, Jack, Queen, King, RankLast=King
  71.     } Rank;
  72.  
  73. const int NumRanks = RankLast+1;
  74.  
  75. void Error(char *s1 = "", char *s2 = "", char *s3 = "") {
  76.     cerr << "\n" << s1 << s2 << s3 << "\n";
  77.     exit(-1);
  78. }
  79.  
  80.  
  81.  
  82. class Tableaux;
  83.  
  84. inline unsigned short Fold(long l) { return ((l>>16)^(l&0xffff)); }
  85.  
  86. class Hash {
  87.     long l1;
  88.     long l2;
  89.     long l3;
  90.   public:
  91.     Hash(Tableaux&);
  92.     Hash() { l1 = l2 = l3 = 0; }
  93.     Hash(int i) { l1 = l2 = l3 = i; } // semi-private
  94.     Boolean operator== (Hash& h) {
  95.     return ((l1 == h.l1) && (l2 == h.l2) && (l3 == h.l3));
  96.     }
  97.     unsigned short Short()  { return Fold(l1)^Fold(l2)^Fold(l3); }
  98.     Boolean EmptyP() { return (l1 == 0) && (l2 == 0) && (l3 == 0); }
  99.     Boolean BadP() { return (l3 < 0); }
  100.     void Print(ostream &os) { os << hex(l1, 8) << hex(l2, 8) << hex(l3,8); }
  101. };
  102.  
  103. ostream& operator<< (ostream &os, Hash& h) { h.Print(os); return os; }
  104.  
  105. class HashList;
  106.  
  107. class HashTable {
  108.     int size;
  109.     int count;
  110.     int hits;
  111.     int maxDepth;
  112.     HashList *ht;
  113.   public:
  114.     HashTable(int n);
  115.     ~HashTable();
  116.     int Count() { return count; }
  117.     void Clear();
  118.     Boolean CheckAndAdd(Hash& h);
  119. /*
  120.  {
  121.     const unsigned short s = h.Short();
  122.     Boolean ret = ht[s].InP(h);
  123.     if (!ret) {
  124.         int depth = ht[s].Add(h);
  125.         if (depth > maxDepth) maxDepth = depth;
  126.         if (depth) hits++;
  127.         count++;
  128. //        if (count%1000 == 0) PrintStats();
  129. #ifdef INTERACTIVE
  130.         if (count%1000 == 0) cerr << ".";
  131. #endif
  132.     }
  133.     return ret;
  134.     }
  135. */
  136.     void Print(ostream &os);
  137.     void PrintStats(ostream& os) {
  138. #ifdef INTERACTIVE
  139.     os << "\nHash table stats - "
  140.         << "size " << size
  141.         << " count " << count
  142.             << " hits " << hits
  143.             << " max depth " << maxDepth;
  144. #endif
  145.     }
  146. };
  147.  
  148. class HashList {
  149.     HashList *next;
  150.     Hash hash;
  151.     int depth;
  152.     friend void HashTable::Clear();
  153.   public:
  154.     HashList(Hash& h, HashList* n) { hash = h; next = n; depth++; }
  155.     HashList() { hash = Hash(); next = NULL; depth = 0; }
  156.     ~HashList();
  157.     Boolean InP(Hash& h);
  158.     int Add(Hash &h); // returns depth
  159.     Hash HashVal() { return hash; }
  160.     int Depth() { return depth; }
  161.     void Print(ostream& os);
  162.     Boolean EmptyP() { return hash.EmptyP(); }
  163. };
  164.  
  165. HashTable::HashTable(int n) {
  166.     ht = new HashList[n]; size = n; count = maxDepth = hits = 0;
  167. }
  168.  
  169. HashTable::~HashTable() {
  170.     delete[size] ht;
  171. }
  172.  
  173. HashList::~HashList() {
  174.     if (next) delete next;
  175.  
  176. }
  177.  
  178. void HashList::Print(ostream &os) {
  179.     if (EmptyP()) os << "NULL";
  180.     else {
  181.     char *sep = "";
  182.     for (HashList* hlt = this; hlt != NULL; hlt = hlt->next) {
  183.         os << sep << hlt->hash;
  184.         sep = " ";
  185.     }
  186.     }
  187. }
  188.  
  189. ostream& operator<< (ostream &os, HashList& hl) { hl.Print(os); return os; }
  190.  
  191. Boolean HashList::InP(Hash& h) {
  192.     for (HashList *hlt = this; hlt != NULL; hlt = hlt->next) {
  193.     if (hlt->HashVal() == h) return 1;
  194.     }
  195.     return 0;
  196. }
  197.  
  198. int HashList::Add(Hash& h) {
  199.     if (!this) Error("Add to NULL HashList.");
  200.     if (HashVal().EmptyP()) hash = h;
  201.     else next = new HashList(h, next);
  202.     return depth++;
  203. }
  204.  
  205. ostream& operator<< (ostream& os, HashTable& ht) { ht.Print(os); return os; }
  206.  
  207. void HashTable::Clear() {
  208.     for (int i=0; i<size; i++) {
  209.     if (ht[i].next) delete ht[i].next;
  210.     ht[i] = HashList();
  211.     }
  212.     count = maxDepth = hits = 0;
  213. }
  214.  
  215. Boolean HashTable::CheckAndAdd(Hash& h) {
  216.     const unsigned short s = h.Short();
  217.     Boolean ret = ht[s].InP(h);
  218.     if (!ret) {
  219.     int depth = ht[s].Add(h);
  220.     if (depth > maxDepth) maxDepth = depth;
  221.     if (depth) hits++;
  222.     count++;
  223. #ifdef INTERACTIVE
  224.     if (count%1000 == 0) cerr << ".";
  225. #endif
  226.     }
  227.     return ret;
  228. }
  229.  
  230. void HashTable::Print(ostream &os) {
  231.     HashList* hll = &ht[size];
  232.     for (HashList* hlt = ht; hlt != hll; hlt++)
  233.     if (! hlt->EmptyP())
  234.         os << "\n" << dec(hlt-ht,5) << ": " << *hlt;
  235. }
  236.  
  237. static HashTable hashTable(65536);
  238.  
  239. // typedef unsigned char CardVal;
  240. typedef int CardVal;
  241.  
  242. class Card;
  243. class CardRange;
  244.  
  245. class Dest {
  246.   public:
  247.     void MoveTo(Card&);
  248.     void MoveTo(CardRange&);
  249. };
  250.  
  251. void Dest::MoveTo(Card&) { Error("Dest::MoveTo(Card&)"); }
  252. void Dest::MoveTo(CardRange&) { Error("Dest::MoveTo(CardRange&)"); }
  253.  
  254. typedef void (Dest::* MoveCardToMemberFunction)(Card&);
  255. typedef void (Dest::* MoveCardRangeToMemberFunction)(CardRange&);
  256.  
  257. class Card : public Dest {
  258.     Suit thisSuit;
  259.     Rank thisRank;
  260.     Boolean empty;
  261.   public:
  262.     Card(Suit suit, Rank rank) {
  263.     if ((suit < SuitFirst) || (suit > SuitLast))
  264.         Error("Bad suit ", dec(suit), " in Card constructor.");
  265.     if ((rank < RankFirst) || (rank > RankLast))
  266.         Error("Bad rank ", dec(rank), " in Card constructor.");
  267.     thisSuit = suit; thisRank = rank; empty = 0;
  268.     }
  269.     Card(char *st);
  270.     Card() { // create an "empty" card
  271.     thisSuit = SuitFirst; thisRank = RankFirst; empty = 1;
  272.     } 
  273.     Suit suit() const { return thisSuit; }
  274.     Rank rank() const { return thisRank; }
  275.     Card Next(int delta = 1) const { return Card(suit(), Rank(rank()+delta)); }
  276.     Card Prev(int delta = 1) const { return Card(suit(), Rank(rank()-delta)); }
  277.     Boolean NextP(Card c) const {
  278.     return ((suit() == c.suit()) && rank()+1 == c.rank());
  279.     }
  280.     Boolean operator== (Card &c) {
  281.     return (EmptyP()
  282.         ? c.EmptyP()
  283.         : ((! c.EmptyP())
  284.            && (suit() == c.suit())
  285.            && (rank() == c.rank())));
  286.     }
  287.     Boolean operator!= (Card &c) { return (! operator==(c)); }
  288.     Boolean EmptyP() const { return empty; }
  289.     CardVal Value() const { return thisSuit*NumRanks+thisRank; }//semi-private.
  290.     void Print(ostream& os) const;
  291. };
  292.  
  293. static char *rankName = "A23456789TJQK";
  294. static char *suitName = "HDCS";
  295.  
  296. void Card::Print(ostream &os) const {
  297.     if (EmptyP()) os << "--";
  298.     else os << chr(rankName[rank()]) << chr(suitName[suit()]);
  299. }
  300.  
  301. Card::Card(char* st) {
  302.     char *c;
  303.     c = index(suitName, st[1]);
  304.     if (! c) Error("Bad suit ", chr(st[1]), " in Card string constructor.");
  305.     thisSuit = Suit(c-suitName);
  306.     c = index(rankName, st[0]);
  307.     if (! c) Error("Bad rank ", chr(st[0]), " in Card string constructor.");
  308.     thisRank = Rank(c - rankName);
  309.     empty = 0;
  310. }
  311.  
  312. ostream& operator<< (ostream& os, Card c) { c.Print(os); return os; }
  313.  
  314. typedef Card Deck[NumSuits*NumRanks];
  315.  
  316. // typedef unsigned char Count;
  317. typedef int Count;
  318.  
  319. class CardRange : public Dest {
  320.     Card thisCard;
  321.     Count thisCount;
  322.     void Init(Card c, Count count) { thisCard = c; thisCount = count; }
  323.   public:
  324.     CardRange(Suit s, Rank rank1, Rank rank2) {
  325.     if (rank2 < rank1) Error("rank2 < rank1 in CardRange constructor.");
  326.     Init(Card(s, rank1), rank2-rank1+1);
  327.     }
  328.     CardRange(Suit s, Rank rank, Count count = 1) {
  329.     Init(Card(s, rank), count);
  330.     }
  331.     CardRange(Card c, Count count = 1) { Init(c, count); }
  332.     CardRange() { Init(Card(), 0); }
  333. //    CardRange(char *st) { Init(Card(st), 1); }
  334.     Suit suit() const { return thisCard.suit(); }
  335.     Card First() const { return thisCard; }
  336.     Card Last() const { return thisCard.Next(thisCount-1); }
  337.     Card Next() const { return thisCard.Next(thisCount); }
  338.     Count Count() const { return thisCount; }
  339.     void Prepend(const CardRange& cr) {
  340.     if (!cr.NextP(First())) Error("CardRange::Prepend, not next.");
  341.     thisCount += cr.Count();
  342.     thisCard = cr.First();
  343.     }
  344.     Boolean NextP(Card c) const {
  345.     return ((suit() == c.suit()) && (First().rank()+Count() == c.rank()));
  346.     }
  347.     Boolean EmptyP() const { return thisCard.EmptyP(); }
  348.     void Print(ostream& os) const;
  349. };
  350.  
  351. void CardRange::Print(ostream &os) const {
  352.     if (EmptyP()) os << "--   ";
  353.     else {
  354.     os << First();
  355.     if (Count() == 1) os << "   ";
  356.     else os << "-" << Last();
  357.     }
  358. }
  359.  
  360. ostream& operator<< (ostream& os, CardRange c) { c.Print(os); return os; }
  361.  
  362.  
  363. #ifdef AUTO
  364. SolutionLog solutionhead = NULL;
  365.  
  366. overload LogSolution();
  367.  
  368. static void LogOneSolution(Card card, int dest) {
  369.     SolutionLog temp = new SolutionLogRec;
  370.     temp->rank = card.rank();
  371.     temp->suit = card.suit();
  372.     temp->dest = dest;
  373.     temp->next = solutionhead;
  374.     solutionhead = temp;
  375. }
  376.  
  377. static void LogBoundary() {
  378.     SolutionLog temp = new SolutionLogRec;
  379.     temp->rank = 0;
  380.     temp->suit = 0;
  381.     temp->dest = -999;
  382.     temp->next = solutionhead;
  383.     solutionhead = temp;
  384. }    
  385.  
  386. static void LogSolution(Card card, int dest) {
  387.     LogBoundary();
  388.     LogOneSolution(card, dest);
  389. }
  390.  
  391. static void LogSolution(CardRange range, int dest) {
  392.     if (range.EmptyP()) return;
  393.     LogBoundary();
  394.     Suit suit = range.suit();
  395.     Rank first = range.First().rank();
  396.     Rank last = range.Last().rank();
  397.     int i;
  398.     if (dest != -99) {
  399. //    for (i=first ; i<last ; i++) LogOneSolution(Card(suit, i), dest);
  400.     for (i=(int)first ; i<(int)last ; i++) LogOneSolution(Card(suit, (Rank) i), dest);
  401.     }
  402.     LogOneSolution(Card(suit, last), dest);
  403. //    for (i=Rank(last-1) ; i>=first ; i--) LogOneSolution(Card(suit, i), -99);
  404.     for (i=(int)Rank(last-1) ; i>=(int)first ; i--) LogOneSolution(Card(suit, (Rank) i), -99);
  405. }
  406. #endif
  407.  
  408.  
  409. const int NumCardRangesInPile = 5;
  410.  
  411. class Pile : public Dest {
  412.     CardRange data[NumCardRangesInPile];
  413.     int ti;
  414.   public:
  415.     Pile() { ti = 4; }
  416.     CardRange& operator[] (int i) { return data[i]; }
  417.     void Set(int i, const CardRange cr) { data[i] = cr; }
  418.     CardRange& top() { return data[ti]; }
  419.     int topIndex() { return ti; }
  420.     CardRange& pop() { return data[ti--]; }
  421.     Boolean EmptyP() { return (ti < 0); }
  422.     void Test(CardRange& from);
  423.     void MoveToPile(CardRange& from) {
  424.     top().Prepend(from);
  425.     from = CardRange();
  426.     }
  427.     void MoveToPile(Card& from) {
  428.     top().Prepend(from);
  429.     from = Card();
  430.     }
  431.     void MoveCardRangeToPile(CardRange& from);
  432.     void MoveTo(CardRange& from);
  433.     void MoveTo(Card& from);
  434. };
  435.  
  436. void Pile::MoveTo(CardRange& from) { MoveToPile(from); }
  437.  
  438. void Pile::MoveCardRangeToPile(CardRange& from) { MoveToPile(from); }
  439.  
  440. void (Pile::* foo)(CardRange&) = &Pile::MoveCardRangeToPile;
  441. //MoveCardRangeToMemberFunction foo = &Pile::MoveCardRangeToPile;
  442.  
  443. const int NumSpaces = 4;
  444.  
  445. class Spaces : public Dest {
  446.     Card data[NumSpaces];
  447.   public:
  448.     Card& operator[] (int i) { return data[i]; }
  449.     Card* FirstFree() {
  450.     return (data[0].EmptyP() ? &data[0] :
  451.         data[1].EmptyP() ? &data[1] :
  452.         data[2].EmptyP() ? &data[2] :
  453.         data[3].EmptyP() ? &data[3] :
  454.         NULL);
  455.     }
  456.     void Spaces::MoveToSpace(CardRange& from) {
  457.     // move all of the cards in range to spaces
  458.     for (int i = 0 ; i < from.Count(); i++) {
  459.         *FirstFree() = from.First().Next(i);
  460.     }
  461.     from = CardRange();
  462.     }
  463.     void Spaces::MoveTo(CardRange& from);
  464.     void Spaces::MoveTo(Card&);
  465. };
  466.  
  467. void Spaces::MoveTo(CardRange& from) { MoveToSpace(from); }
  468. void Spaces::MoveTo(Card&) { Error("Spaces::MoveTo(Card&)"); };
  469.  
  470. const int NumPiles = 10;
  471.  
  472. class Aces : public Dest {
  473.     Card data[NumSuits];
  474.   public:
  475.     Card& operator[] (int i) { return data[i]; }
  476.     void MoveToAce(Card& from) {
  477.     data[from.suit()] = Card(from);
  478.     from = Card();
  479.     }
  480.     void MoveToAce(CardRange& from) {
  481.     data[from.suit()] = from.Last();
  482.     from = CardRange();
  483.     }
  484.     void MoveTo(Card& from) { MoveToAce(from); }
  485.     void MoveTo(CardRange& from) { MoveToAce(from); }
  486. };
  487.  
  488. class Kings : public Dest {
  489.     Card data[NumSuits];
  490.   public:
  491.     Card& operator[] (int i) { return data[i]; }
  492.     void MoveToKing(Card& from) {
  493.     data[from.suit()] = Card(from);
  494.     from = Card();
  495.     }
  496.     void MoveToKing(CardRange& from) {
  497.     data[from.suit()] = from.First();
  498.     from = CardRange();
  499.     }
  500.     void MoveTo(Card& from) { MoveToKing(from); }
  501.     void MoveTo(CardRange& from) { MoveToKing(from); }
  502. };
  503.  
  504. class Tableaux {
  505.   private:
  506.     Hash hashVal;
  507.     void CanonicalForm();
  508.   public:
  509.     Pile piles[NumPiles];
  510.     Spaces spaces;
  511.     Aces aces;
  512.     Kings kings;
  513.     Boolean Solve();
  514.     Hash HashVal() { return hashVal; }
  515.     Boolean WonP();
  516.     void Print(ostream& os);
  517.     void Dump();
  518.     void Read(istream& is);
  519.     Tableaux(Card *deck);
  520.     Tableaux(char *st);
  521.     Tableaux(istream& is) { Read(is); }
  522.     Boolean CheckAces(Card &c) {
  523.     return (((c.rank() == Ace)
  524.         || (c.rank() == aces[c.suit()].Next().rank()))
  525.         ? FillAces()
  526.         : 0);
  527.     }
  528.     Boolean FillAces(); // move all cards to aces that can be
  529. };
  530.  
  531. class Move {
  532.   protected:
  533.     Dest& dest;
  534.   public:
  535.     Move(Dest& d) : dest(d) { }
  536.     virtual void DoIt() { Error("Move::DoIt()"); };
  537. };
  538.  
  539. class MoveCard : public Move {
  540.     Card& from;
  541.     MoveCardToMemberFunction mcmf;
  542.   public:
  543.     MoveCard(Card& f, Dest& d, MoveCardToMemberFunction mf)
  544.     : (d), from(f), mcmf(mf) { }
  545.     void MoveCard::DoIt() { dest.MoveTo(from); }
  546. //    void MoveCard::DoIt() { dest.*mcmf(from); }
  547. };
  548.  
  549. class MoveCardRange : public Move {
  550.     CardRange& from;
  551.   public:
  552.     MoveCardRange(CardRange& f, Dest& d) : (d), from(f) { }
  553.     void DoIt() {dest.MoveTo(from);} 
  554. };
  555.  
  556. ostream& operator<< (ostream& os, Tableaux &t) { t.Print(os); return os; }
  557. istream& operator>> (istream& is, Tableaux &t) { t.Read(is); return is; }
  558.  
  559. void Tableaux::Dump() { Print(cout); }
  560.  
  561. Hash::Hash(Tableaux& t) {
  562.  
  563.     // there are 5 possible tops, and 13 possible values for the number of
  564.     // cards in the top "group". These two values uniquely determine what's in
  565.     // that pile. Each pile starts with five groups, that number never grows.
  566.     // You can only move a group by either removing it (to a space or an ace)
  567.     // or moving it to the end of another group (which merely lengthens that
  568.     // group). So the number of groups in a pile is monotone non-increasing.
  569.     // An implication of this is that the *suit* of each position in the pile
  570.     // stays fixed, and so is derivable from the initial position (i.e.  adds
  571.     // no information) thus we can ignore the suit in computing the hash. This
  572.     // means that there are 66 possible hash values for each pile. 5*13
  573.     // possible top+count values + empty.
  574.     // 66^5 < 2^32 so we can store the hash for 10 piles in two 32 bit numbers
  575.     // We also need to store information about the kings. I'm lazy so I just
  576.     // store it in one long.
  577.  
  578.     // Note: Hash 0 would imply all empty piles, which will never happen!
  579.  
  580.     l3 = (((((t.kings[0].Value() << 8)
  581.          + t.kings[1].Value()) << 8)
  582.        + t.kings[2].Value()) << 8)
  583.     + t.kings[3].Value();
  584.  
  585.     l1 = 0;
  586.     Pile *p;
  587.     for (p=t.piles; p < t.piles+5; p++) {
  588.     const int count = p->top().Count();
  589.     if (count >= 6) {
  590.         const Suit s = p->top().suit();
  591.         const Rank r = p->top().First().rank();
  592.         for (CardRange* cr = &(p->top()); cr >= &((*p)[0]); cr--) {
  593.         if (cr->suit() != s) continue;
  594.         if (cr->First().rank() < r) {
  595.             l1 = l2 = l3 = -1;
  596.             return;
  597.         }
  598.         }
  599.     }
  600.     l1 = l1*66 + (p->EmptyP() ? 0 : (p->topIndex()*13+count-1)+1);
  601.     }
  602.  
  603.     l2 = 0;
  604.     for (p = t.piles+5 ; p < t.piles+NumPiles; p++) {
  605.     const int count = p->top().Count();
  606.     if (count >= 6) {
  607.         const Suit s = p->top().suit();
  608.         const Rank r = p->top().First().rank();
  609.         for (CardRange* cr = &(p->top()); cr >= &((*p)[0]); cr--) {
  610.         if (cr->suit() != s) continue;
  611.         if (cr->First().rank() < r) {
  612.             l1 = l2 = l3 = -1;
  613.             return;
  614.         }
  615.         }
  616.     }
  617.     l2 = l2*66 + (p->EmptyP() ? 0 : (p->topIndex()*13+count-1)+1);
  618.     }
  619.  
  620.     if ((l1==0)&&(l2==0)&&(l3==0))
  621.     Error("Tableaux hashes to NULL.");
  622. }
  623.  
  624. Boolean Tableaux::WonP() {
  625.     return ((aces[0].rank() == King)
  626.         && (aces[1].rank() == King)
  627.         && (aces[2].rank() == King)
  628.         && (aces[3].rank() == King));
  629. }
  630.  
  631. Boolean Tableaux::FillAces() {
  632.     int found;
  633.     do {
  634.     found = 0;
  635.     int dests[NumSuits];
  636.  
  637.     int numFull = 0;
  638.  
  639. //    for (Suit s = SuitFirst; s <= SuitLast; s++) {
  640.     Suit s;
  641.     int i;
  642.     for (i = (int)SuitFirst; i <= (int)SuitLast; i++) {
  643.         s = (Suit) i;
  644.         if (aces[s].EmptyP()) dests[s] = Ace;
  645.         else {
  646.         numFull += (aces[s].rank() == King);
  647.         dests[s] = aces[s].rank()+1;
  648.         }
  649.     }
  650.     if (numFull == NumSuits) return 1;
  651.  
  652.     // check piles
  653.     for (Pile* p = piles; p < piles+NumPiles; p++) {
  654.         if (p->EmptyP()) continue;
  655.         Card& first = p->top().First();
  656.         if (dests[first.suit()] == first.rank()) {
  657.         aces.MoveToAce(p->pop());
  658.         found = 1;
  659. #ifdef VERBOSE
  660.         cerr << "+";
  661. #endif
  662.         }
  663.     }
  664.     
  665.     // check spaces
  666.     for (Card *c = &spaces[0]; c < &spaces[NumSpaces]; c++) {
  667.         if (c->EmptyP()) continue;
  668.         if (dests[c->suit()] == c->rank()) {
  669.         aces.MoveToAce(*c);
  670.         found = 1;
  671. #ifdef VERBOSE
  672.         cerr << "+";
  673. #endif
  674.         }
  675.     }
  676.     
  677.     // check kings
  678. //    for (Suit s1 = SuitFirst; s1 <= SuitLast; s1++) {
  679.     Suit s1;
  680.     for (i = (int)SuitFirst; i <= (int)SuitLast; i++) {
  681.         s1 = (Suit) i;
  682.         if (kings[s1].EmptyP()) continue;
  683.         if (dests[s1] == kings[s1].rank()) {
  684.         Card tempKing = Card(s1, King);
  685.         aces.MoveToAce(tempKing);
  686.         kings[s1] = Card();
  687.         found = 1;
  688. #ifdef VERBOSE
  689.         cerr << "!";
  690. #endif
  691.         }
  692.     }
  693.     } while (found);
  694.     return 0;
  695. }
  696.  
  697. Boolean Tableaux::Solve() {
  698.  
  699.     hashVal = Hash(*this);
  700.  
  701.     if (hashTable.CheckAndAdd(HashVal())) return 0;
  702.  
  703.     Tableaux savedTab = *this;
  704.  
  705. #ifdef VERBOSE
  706.     cerr << ".";
  707. #endif
  708. #ifdef DYNAMIC
  709.     cout << "[;H" << *this;
  710. #endif
  711.  
  712.     // pre-calculate useful bits of info - how many empty spaces are there
  713.     // how many empty piles there are
  714.  
  715.     int empty_space_count = 0;
  716.     Card *c;
  717.     for (c = &spaces[0]; c < &spaces[NumSpaces]; c++)
  718.     empty_space_count += c->EmptyP();
  719.  
  720.     int empty_pile_count = 0;
  721.     Pile* p;
  722.     for (p = piles; p < piles+NumPiles; p++) empty_pile_count += p->EmptyP();
  723.  
  724.     Suit s;
  725.     int i;
  726. //    for (s = SuitFirst; s <= SuitLast; s++)
  727.     for (i = (int)SuitFirst; i <= (int)SuitLast; i++) {
  728.     s = (Suit) i;
  729.     empty_pile_count -= !kings[s].EmptyP();
  730.     }
  731.  
  732.     // generate legal moves, check each one
  733.     // all legal moves are either
  734.     // 1) an entire top sequence onto the top of a pile (shortcut 3+2)
  735.     // 2) a card from a space onto the top of a pile
  736.     // 3) an entire top sequence onto a space or spaces
  737.     // 4) an entire king based sequence onto an empty pile (shortcut 3+5+2)
  738.     // 5) a king from a space onto an empty pile
  739.  
  740.     // another way of looking at it is that all moves are onto one of
  741.     // tops of piles
  742.     // empty piles (kings)
  743.     // spaces
  744.  
  745.     int destTable[NumSuits*NumRanks];
  746.  
  747.     memset((char*)destTable,0,sizeof(destTable));
  748.  
  749.     // enumerate destination piles
  750.     for (p = piles; p < piles+NumPiles; p++) {
  751.     if (p->EmptyP()) continue;
  752.     destTable[p->top().First().Prev().Value()] = (p-piles)+1;
  753.     }
  754.  
  755.     // enumerate destination kings
  756. //    for (s = SuitFirst; s <= SuitLast; s++) {
  757.     for (i = (int)SuitFirst; i <= (int)SuitLast; i++) {
  758.     s = (Suit) i;
  759.     if (kings[s].EmptyP()) {
  760.         if (empty_pile_count) destTable[Card(s,King).Value()] = s+11;
  761.     } else {
  762.         destTable[kings[s].Prev().Value()] = s+11;
  763.     }
  764.     }
  765.  
  766.     Move* movesMakingEmptyPiles[10];
  767.     int movesMakingEmptyPilesCount = 0;
  768.  
  769.     Move* movesMakingUnmovableRange[10];
  770.     int movesMakingUnMovableRange= 0;
  771.  
  772.     // look for moves from spaces
  773.     for (Card *from = &spaces[0]; from < &spaces[NumSpaces]; from++) {
  774.     if (from->EmptyP()) continue;
  775.     const int dest = destTable[from->Value()];
  776.     if (!dest) continue;
  777.     if (dest < 11) piles[dest-1].MoveToPile(*from);
  778.     else kings.MoveToKing(*from);
  779.     if (Solve()) {
  780.         *this = savedTab;
  781. #ifdef AUTO
  782.         LogSolution(*from, dest);
  783. #endif
  784. #ifdef INTERACTIVE
  785.         cout << "\n" << *from << "(S) -> ";
  786.         if (dest < 11) cout << piles[dest-1].top();
  787.         else cout << "(K)" << kings[dest-11];
  788. #endif
  789.         return 1;
  790.     } else {
  791.         *this = savedTab;
  792.         if (dest < 11) return 0; // It never costs to move something from
  793.                      // a space to a pile (unless it's a king)
  794.     }
  795.     }
  796.  
  797.     // look for moves from piles
  798.     for (p = piles; p < piles+NumPiles; p++) {
  799.     if (p->EmptyP()) continue;
  800.     CardRange& from = p->top();
  801.     if (from.Count()-1 > empty_space_count) continue;
  802.     int const dest = destTable[from.Last().Value()];
  803.     if (!dest) continue;
  804.     // legal move!
  805. /*
  806.     if (p->topIndex() == 0) {
  807.         if (dest < 11) {
  808.         movesMakingEmptyPiles[movesMakingEmptyPilesCount++] =
  809.             new Move();
  810.         } else {
  811.         }
  812.     } else {
  813. */
  814.         if (dest < 11) {
  815.         piles[dest-1].MoveToPile(p->pop());
  816.         // did we uncover a king?
  817.         if ((p->topIndex() == 0) && (p->top().Last().rank() == King))
  818.             kings.MoveToKing(p->pop());
  819.         } else {
  820.         kings.MoveToKing(p->pop());
  821.         }
  822. /*
  823.     }
  824. */
  825.     if ((!p->EmptyP()) && CheckAces(p->top().First()) || Solve()) {
  826. #ifdef AUTO
  827.         *this = savedTab;
  828.         LogSolution(from, dest);
  829. #endif
  830. #ifdef INTERACTIVE
  831.         *this = savedTab;
  832.         cout << "\n" << from << " -> ";
  833.         if (dest < 11) cout << piles[dest-1].top();
  834.         else cout << "(K)" << kings[dest-11];
  835. #endif
  836.         return 1;
  837.     }
  838.     *this = savedTab;
  839.     }
  840.  
  841.     // look for moves into spaces
  842.     for (p = piles; p < piles+NumPiles; p++) {
  843.     if (p->EmptyP()) continue;
  844.     CardRange& tp = p->top();
  845.     if (tp.Count() > empty_space_count) continue;
  846.     spaces.MoveToSpace(p->pop());
  847.     if (((!p->EmptyP()) && CheckAces(p->top().First())) || Solve()) {
  848. #ifdef AUTO
  849.         *this = savedTab;
  850.         LogSolution(tp, -99);
  851. #endif 
  852. #ifdef INTERACTIVE
  853.         *this = savedTab;
  854.         cout << "\n" << tp << " -> space";
  855. #endif
  856.         return 1;
  857.     }
  858.     *this = savedTab;
  859.     }
  860.  
  861.     return 0;
  862. };
  863.  
  864. void Tableaux::CanonicalForm() {
  865.     // find all sequences and compress them
  866.     for (int i = 0; i < NumPiles; i++) {
  867.     Pile& p = piles[i];
  868.     int k = 0;
  869.     for (int j = 1; j < NumCardRangesInPile; j++)
  870.         if (p[j].NextP(p[k].Last())) p[k].Prepend(p[j].First());
  871.         else p.Set(++k, p[j]);
  872.  
  873.     for (k++; k < NumCardRangesInPile; k++) {
  874.         p.Set(k,CardRange());
  875.         p.pop();
  876.     }
  877.     }
  878.  
  879. /*
  880.     for (Pile* p = piles; p < piles+NumPiles; p++) {
  881.     CardRange *nextPos = &(*p)[0];
  882.     for (CardRange *c = &(*p)[1]; c < &(*p)[NumCardRangesInPile]; c++) {
  883.         if (c->NextP(nextPos->Last())) nextPos->Prepend(*c);
  884.         else *(++nextPos) = *c;
  885.     }
  886.     for (nextPos++; nextPos < &(*p)[NumCardRangesInPile]; nextPos++)
  887.         *nextPos = CardRange();
  888.     }
  889. */
  890.  
  891.     FillAces();
  892. }
  893.  
  894. Tableaux::Tableaux(char* st) {
  895.     static int deck[NumSuits][NumRanks];
  896.  
  897.     Card c;
  898.  
  899.     c = st; deck[c.suit()][c.rank()]++;
  900.     spaces[1] = c;
  901.     st += 2;
  902.     c = st; deck[c.suit()][c.rank()]++;
  903.     spaces[2] = c;
  904.     st += 2;
  905.  
  906.  
  907.     for (Pile* p = piles; p < piles+NumPiles; p++)
  908.     for (CardRange* cr = &(*p)[0]; cr < &(*p)[NumCardRangesInPile]; cr++) {
  909.         c = st; deck[c.suit()][c.rank()]++;
  910.         *cr = c;
  911.         st += 2;
  912.     }
  913.  
  914. //    for (Suit s = SuitFirst; s <= SuitLast; s++)
  915. //    for (Rank r = RankFirst; r <= RankLast; r++)
  916.     Suit s;
  917.     Rank r;
  918.     int i, j;
  919.     for (i = (int)SuitFirst; i <= (int)SuitLast; i++) {
  920.     s = (Suit) i;
  921.     for (j = (int)RankFirst; j <= (int)RankLast; j++) {
  922.         r = (Rank) j;
  923.         if (deck[s][r] != 1) {
  924.         cerr << "\n" << Card(s, r) << " count is " << deck[s][r];
  925.         Error();
  926.         }
  927.     }
  928.     }
  929.  
  930.     CanonicalForm();
  931.  
  932. }
  933.  
  934. void Tableaux::Print(ostream& os) {
  935.     os << "\n";
  936.     os << aces[0]   << "    " << aces[1]   << "          "
  937.        << spaces[0] << "    " << spaces[1] << "    "
  938.        << spaces[2] << "    " << spaces[3] << "          "
  939.        << aces[2]   << "    " << aces[3];
  940.     os << "\n";
  941.     for (int j = 0; j < NumCardRangesInPile; j++) {
  942.     char *sep = "\n";
  943.     for (int i = 0; i < NumPiles; i++) {
  944.         os << sep << piles[i][j];
  945.         sep = " ";
  946.     }
  947.     }
  948.     os << "\n";
  949.     os << kings[0] << " " << kings[1] << " " << kings[2] << " " << kings[3];
  950.     os << "\n";
  951. }
  952.  
  953. void Tableaux::Read(istream& is) {
  954.     int won, lost, streak, longest_won, longest_lost, dummy;
  955.     is >> won >> lost >> streak >> longest_won >> longest_lost >> dummy;
  956.     for (int i = 0; i < NumCardRangesInPile; i++)
  957.     for (int j = 0; j < NumPiles; j++) {
  958.         int s, r;
  959.         is >> s >> r;
  960.         piles[j].Set(i, CardRange(Card(Suit(s),Rank(r))));
  961.     }
  962.     int s, r;
  963.     is >> s >> r;
  964.     spaces[1] = Card(Suit(s),Rank(r));
  965.     is >> s >> r;
  966.     spaces[2] = Card(Suit(s),Rank(r));
  967.  
  968.     CanonicalForm();
  969.  
  970. }
  971.  
  972. Tableaux::Tableaux(Card *deck) {
  973.     for (int i = 0; i < NumCardRangesInPile; i++)
  974.     for (int j = 0; j < NumPiles; j++) {
  975.         piles[j].Set(i, CardRange(*(deck++)));
  976.     }
  977.     spaces[1] = *(deck++);
  978.     spaces[2] = *(deck++);
  979.  
  980.     CanonicalForm();
  981.  
  982. }
  983.  
  984.  
  985. #ifdef AUTO
  986. int AutoPlay() {
  987.  
  988.     char savefile[500];
  989.  
  990.     sprintf(savefile, "%s/.seahavensave", getenv("HOME"));
  991.  
  992.     istream in = istream(open(savefile, O_RDONLY));
  993.     Tableaux t(in);
  994.  
  995.     solutionhead = NULL;
  996.     int result = t.Solve();
  997.  
  998.     hashTable.Clear();
  999.     return result;
  1000. }
  1001. #endif
  1002.