Home | History | Annotate | Download | only in SemaCXX 
      1 // RUN: %clang_cc1 -std=c++11 -fsyntax-only %s
      2 
      3 typedef unsigned long uint64_t;
      4 
      5 struct Board {
      6   uint64_t State;
      7   bool Failed;
      8 
      9   constexpr Board() : State(0), Failed(false) {}
     10   constexpr Board(const Board &O) : State(O.State), Failed(O.Failed) {}
     11   constexpr Board(uint64_t State, bool Failed = false) :
     12     State(State), Failed(Failed) {}
     13   constexpr Board addQueen(int Row, int Col) const {
     14     return Board(State | ((uint64_t)Row << (Col * 4)));
     15   }
     16   constexpr int getQueenRow(int Col) const {
     17     return (State >> (Col * 4)) & 0xf;
     18   }
     19   constexpr bool ok(int Row, int Col) const {
     20     return okRecurse(Row, Col, 0);
     21   }
     22   constexpr bool okRecurse(int Row, int Col, int CheckCol) const {
     23     return Col == CheckCol ? true :
     24            getQueenRow(CheckCol) == Row ? false :
     25            getQueenRow(CheckCol) == Row + (Col - CheckCol) ? false :
     26            getQueenRow(CheckCol) == Row + (CheckCol - Col) ? false :
     27            okRecurse(Row, Col, CheckCol + 1);
     28   }
     29   constexpr bool at(int Row, int Col) const {
     30     return getQueenRow(Col) == Row;
     31   }
     32   constexpr bool check(const char *, int=0, int=0) const;
     33 };
     34 
     35 constexpr Board buildBoardRecurse(int N, int Col, const Board &B);
     36 constexpr Board buildBoardScan(int N, int Col, int Row, const Board &B);
     37 constexpr Board tryBoard(const Board &Try,
     38                          int N, int Col, int Row, const Board &B) {
     39   return Try.Failed ? buildBoardScan(N, Col, Row, B) : Try;
     40 }
     41 constexpr Board buildBoardScan(int N, int Col, int Row, const Board &B) {
     42   return Row == N ? Board(0, true) :
     43          B.ok(Row, Col) ?
     44          tryBoard(buildBoardRecurse(N, Col + 1, B.addQueen(Row, Col)),
     45                   N, Col, Row+1, B) :
     46          buildBoardScan(N, Col, Row + 1, B);
     47 }
     48 constexpr Board buildBoardRecurse(int N, int Col, const Board &B) {
     49   return Col == N ? B : buildBoardScan(N, Col, 0, B);
     50 }
     51 constexpr Board buildBoard(int N) {
     52   return buildBoardRecurse(N, 0, Board());
     53 }
     54 
     55 constexpr Board q8 = buildBoard(8);
     56 
     57 constexpr bool Board::check(const char *p, int Row, int Col) const {
     58   return
     59     *p == '\n' ? check(p+1, Row+1, 0) :
     60     *p == 'o' ? at(Row, Col) && check(p+1, Row, Col+1) :
     61     *p == '-' ? !at(Row, Col) && check(p+1, Row, Col+1) :
     62     *p == 0 ? true :
     63     false;
     64 }
     65 static_assert(q8.check(
     66     "o-------\n"
     67     "------o-\n"
     68     "----o---\n"
     69     "-------o\n"
     70     "-o------\n"
     71     "---o----\n"
     72     "-----o--\n"
     73     "--o-----\n"), "");
     74