]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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 | } | |
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"), ""); |