#include <algorithm> #include <bitset> #include <iomanip> #include <iostream> #include <numeric> #include <vector> static const std::pair<int, int> kBishopDirections[] = { {1, 1}, {-1, 1}, {1, -1}, {-1, -1}}; static bool valid_square(int row, int col) { return row >= 0 && col >= 0 && row < 8 && col < 8; } template <typename TCont> auto relevant_squares(int square, const TCont& directions) { std::vector<int> res; int start_row = square / 8; int start_col = square % 8; for (auto direction : directions) { auto dst_row = start_row + direction.first; auto dst_col = start_col + direction.second; // If the next square in this direction is invalid, the current square // is at the board's edge and should not be added. while (valid_square(dst_row + direction.first, dst_col + direction.second)) { res.push_back(dst_row * 8 + dst_col); dst_row += direction.first; dst_col += direction.second; } } std::sort(res.begin(), res.end()); return res; } template <typename TCont, typename TOp> void for_each_bitboard(const TCont& squares, TOp op) { const auto i_max = 1ull << squares.size(); for (auto i = 0ull; i < i_max; ++i) { auto bitboard = 0ull; auto bits = i; for (const auto sq : squares) { if (bits & 1) { bitboard |= 1ull << sq; } bits >>= 1; } op(bitboard); } } template <typename TMagic, typename TBitboard> auto index(TMagic magic, TBitboard bitboard) { const auto shift = magic >> 56; return (bitboard * magic) >> shift; } template <typename TBitboard> void print_board(TBitboard bitboard) { auto reverse_8bits = [](auto b) { b = (b & 0xF0) >> 4 | (b & 0x0F) << 4; b = (b & 0xCC) >> 2 | (b & 0x33) << 2; b = (b & 0xAA) >> 1 | (b & 0x55) << 1; return b; }; for (int shift = 56; shift >= 0; shift -= 8) { auto row = reverse_8bits((bitboard >> shift) & 0xFF); std::cout << std::bitset<8>(row); if (shift) std::cout << "\n"; } } int main() { // const auto square = 2; // C1 const auto square = 62; // G8 const auto squares = relevant_squares(square, kBishopDirections); std::cout << "Relevant squares:"; for (auto wtf : squares) { std::cout << " " << wtf; } std::cout << std::endl; std::vector<int> bits(64); std::iota(bits.begin(), bits.end(), 0); std::reverse(bits.begin(), bits.end()); for (auto square : squares) { std::cout << "<<" << std::setw(2) << square << ": "; auto shifted = bits; shifted.erase(shifted.begin(), shifted.begin() + square); for (auto bit : shifted) { std::cout << std::setw(3) << bit; } std::cout << "\n"; } std::cout << "\n"; const auto magic = 0x3c007f2491c5c260; std::cout << "Magic:"; for (int i = 56; i >= 0; i -= 8) { std::cout << std::setw(9) << std::bitset<8>(magic >> i); std::cout << "(" << i << ")"; } std::cout << "\n"; for (auto square : squares) { std::cout << "<<" << std::setw(2) << square << ": "; auto str = std::bitset<64>(magic << square).to_string(); for (auto bit : str) { std::cout << std::setw(2) << bit; } std::cout << "\n"; } std::cout << "\n"; for_each_bitboard(squares, [&](auto bitboard) { print_board(bitboard); std::cout << " ==> "; std::cout << std::setw(3) << std::dec << index(magic, bitboard); std::cout << "\n\n"; }); }
Standard input is empty
Relevant squares: 17 26 35 44 53 <<17: 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 <<26: 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 <<35: 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 <<44: 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 <<53: 10 9 8 7 6 5 4 3 2 1 0 Magic: 00111100(56) 00000000(48) 01111111(40) 00100100(32) 10010001(24) 11000101(16) 11000010(8) 01100000(0) <<17: 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 <<26: 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 <<35: 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 <<44: 0 1 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 <<53: 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ==> 0 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000 ==> 15 00000000 00000000 00000000 00000000 00100000 00000000 00000000 00000000 ==> 9 00000000 00000000 00000000 00000000 00100000 01000000 00000000 00000000 ==> 9 00000000 00000000 00000000 00010000 00000000 00000000 00000000 00000000 ==> 8 00000000 00000000 00000000 00010000 00000000 01000000 00000000 00000000 ==> 8 00000000 00000000 00000000 00010000 00100000 00000000 00000000 00000000 ==> 2 00000000 00000000 00000000 00010000 00100000 01000000 00000000 00000000 ==> 1 00000000 00000000 00001000 00000000 00000000 00000000 00000000 00000000 ==> 5 00000000 00000000 00001000 00000000 00000000 01000000 00000000 00000000 ==> 5 00000000 00000000 00001000 00000000 00100000 00000000 00000000 00000000 ==> 14 00000000 00000000 00001000 00000000 00100000 01000000 00000000 00000000 ==> 14 00000000 00000000 00001000 00010000 00000000 00000000 00000000 00000000 ==> 14 00000000 00000000 00001000 00010000 00000000 01000000 00000000 00000000 ==> 14 00000000 00000000 00001000 00010000 00100000 00000000 00000000 00000000 ==> 7 00000000 00000000 00001000 00010000 00100000 01000000 00000000 00000000 ==> 7 00000000 00000100 00000000 00000000 00000000 00000000 00000000 00000000 ==> 4 00000000 00000100 00000000 00000000 00000000 01000000 00000000 00000000 ==> 4 00000000 00000100 00000000 00000000 00100000 00000000 00000000 00000000 ==> 13 00000000 00000100 00000000 00000000 00100000 01000000 00000000 00000000 ==> 13 00000000 00000100 00000000 00010000 00000000 00000000 00000000 00000000 ==> 13 00000000 00000100 00000000 00010000 00000000 01000000 00000000 00000000 ==> 13 00000000 00000100 00000000 00010000 00100000 00000000 00000000 00000000 ==> 6 00000000 00000100 00000000 00010000 00100000 01000000 00000000 00000000 ==> 6 00000000 00000100 00001000 00000000 00000000 00000000 00000000 00000000 ==> 10 00000000 00000100 00001000 00000000 00000000 01000000 00000000 00000000 ==> 10 00000000 00000100 00001000 00000000 00100000 00000000 00000000 00000000 ==> 3 00000000 00000100 00001000 00000000 00100000 01000000 00000000 00000000 ==> 3 00000000 00000100 00001000 00010000 00000000 00000000 00000000 00000000 ==> 3 00000000 00000100 00001000 00010000 00000000 01000000 00000000 00000000 ==> 3 00000000 00000100 00001000 00010000 00100000 00000000 00000000 00000000 ==> 12 00000000 00000100 00001000 00010000 00100000 01000000 00000000 00000000 ==> 12