clang/test/SemaCXX/constexpr-nqueens.cpp

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