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