| 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 | |
|---|