75 lines · cpp
1// RUN: %clang_cc1 -std=c++11 -fsyntax-only %s2// RUN: %clang_cc1 -std=c++11 -fsyntax-only -fexperimental-new-constant-interpreter %s3 4typedef unsigned long uint64_t;5 6struct 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 36constexpr Board buildBoardRecurse(int N, int Col, const Board &B);37constexpr Board buildBoardScan(int N, int Col, int Row, const Board &B);38constexpr 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}42constexpr 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}49constexpr Board buildBoardRecurse(int N, int Col, const Board &B) {50 return Col == N ? B : buildBoardScan(N, Col, 0, B);51}52constexpr Board buildBoard(int N) {53 return buildBoardRecurse(N, 0, Board());54}55 56constexpr Board q8 = buildBoard(8);57 58constexpr bool Board::check(const char *p, int Row, int Col) const {59 return60 *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}66static_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