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
BoardBoard10 constexpr Board() : State(0), Failed(false) {}
BoardBoard11 constexpr Board(const Board &O) : State(O.State), Failed(O.Failed) {}
BoardBoard12 constexpr Board(uint64_t State, bool Failed = false) :
13 State(State), Failed(Failed) {}
addQueenBoard14 constexpr Board addQueen(int Row, int Col) const {
15 return Board(State | ((uint64_t)Row << (Col * 4)));
16 }
getQueenRowBoard17 constexpr int getQueenRow(int Col) const {
18 return (State >> (Col * 4)) & 0xf;
19 }
okBoard20 constexpr bool ok(int Row, int Col) const {
21 return okRecurse(Row, Col, 0);
22 }
okRecurseBoard23 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 }
atBoard30 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);
tryBoard(const Board & Try,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 }
buildBoardScan(int N,int Col,int Row,const Board & B)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 }
buildBoardRecurse(int N,int Col,const Board & B)49 constexpr Board buildBoardRecurse(int N, int Col, const Board &B) {
50 return Col == N ? B : buildBoardScan(N, Col, 0, B);
51 }
buildBoard(int N)52 constexpr Board buildBoard(int N) {
53 return buildBoardRecurse(N, 0, Board());
54 }
55
56 constexpr Board q8 = buildBoard(8);
57
check(const char * p,int Row,int Col) const58 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"), "");
75