Richard Smith | 59efe26 | 2011-11-11 04:05:33 +0000 | [diff] [blame] | 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) { |
| 14 | return Board(State | ((uint64_t)Row << (Col * 4))); |
| 15 | } |
| 16 | constexpr int getQueenRow(int Col) { |
| 17 | return (State >> (Col * 4)) & 0xf; |
| 18 | } |
| 19 | constexpr bool ok(int Row, int Col) { |
| 20 | return okRecurse(Row, Col, 0); |
| 21 | } |
| 22 | constexpr bool okRecurse(int Row, int Col, int CheckCol) { |
| 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) { |
| 30 | return getQueenRow(Col) == Row; |
| 31 | } |
| 32 | constexpr bool check(const char *, int=0, int=0); |
| 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) { |
| 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 | } |
Richard Smith | dcd2851 | 2012-02-10 10:55:13 +0000 | [diff] [blame] | 65 | static_assert(q8.check( |
Richard Smith | 59efe26 | 2011-11-11 04:05:33 +0000 | [diff] [blame] | 66 | "o-------\n" |
| 67 | "------o-\n" |
| 68 | "----o---\n" |
| 69 | "-------o\n" |
| 70 | "-o------\n" |
| 71 | "---o----\n" |
| 72 | "-----o--\n" |
Richard Smith | dcd2851 | 2012-02-10 10:55:13 +0000 | [diff] [blame] | 73 | "--o-----\n"), ""); |