1
// SPDX-License-Identifier: Unlicense
2
pragma solidity ^0.8.17;
3

4
import "../interfaces/IPuzzle.sol";
5

6
/// @title 2 × 4 = 8
7
/// @custom:subtitle Sodoku
8
/// @author fiveoutofnine
9
/// @notice A modified version of the classic Sodoku puzzle, for an 8 × 8 grid.
10
/// As usual, each row and column must contain [1, ..., 8] exactly once.
11
/// However, unlike in regular Sodoku, we now check for 2 × 4 subgrids, rather
12
/// than 3 × 3 subgrids.
13
contract TwoTimesFourIsEight is IPuzzle {
14
    /// @notice A mapping of from indices to which checks must be performed at
15
    /// that index.
16
    /// @dev We reserve 3 bits for each check as follows:
17
    ///     * 0th bit is `1`: check subgrid;
18
    ///     * 1st bit is `1`: check column;
19
    ///     * 2nd bit is `1`: check row.
20
    ///
21
    /// For clarity, the following table lays out the bitpacked values:
22
    ///             | Index | Row     | Column  | Subgrid | Value |
23
    ///             |-------+---------+---------+---------+-------|
24
    ///             |     0 |       1 |       1 |       1 | 0b111 |
25
    ///             |     1 |       0 |       1 |       0 | 0b010 |
26
    ///             |     2 |       0 |       1 |       0 | 0b010 |
27
    ///             |     3 |       0 |       1 |       0 | 0b010 |
28
    ///             |     4 |       0 |       1 |       1 | 0b011 |
29
    ///             |     5 |       0 |       1 |       0 | 0b010 |
30
    ///             |     6 |       0 |       1 |       0 | 0b010 |
31
    ///             |     7 |       0 |       1 |       0 | 0b010 |
32
    ///             |     8 |       1 |       0 |       0 | 0b100 |
33
    ///             |    16 |       1 |       0 |       1 | 0b101 |
34
    ///             |    20 |       0 |       0 |       1 | 0b001 |
35
    ///             |    24 |       1 |       0 |       0 | 0b100 |
36
    ///             |    32 |       1 |       0 |       1 | 0b101 |
37
    ///             |    36 |       0 |       0 |       1 | 0b001 |
38
    ///             |    40 |       1 |       0 |       0 | 0b100 |
39
    ///             |    48 |       1 |       0 |       1 | 0b101 |
40
    ///             |    52 |       0 |       0 |       1 | 0b001 |
41
    ///             |    56 |       1 |       0 |       0 | 0b100 |
42
    uint256 private constant CHECKS =
43
        0x400010005000000040001000500000004000100050000000422232227;
44

45
    /// @notice A bitpacked value that indicates how many bits to shift by to
46
    /// get to the next value in the row.
47
    /// @dev We reserve 6 bits for each value, and the following are packed
48
    // left-to-right: `[4, 4, 4, 4, 4, 4, 4, 4]`.
49
    uint256 private constant ROW_SHIFTS = 0x104104104104;
50

51
    /// @notice A bitpacked value that indicates how many bits to shift by to
52
    /// get to the next value in the column.
53
    /// @dev We reserve 6 bits for each value, and the following are packed
54
    // left-to-right: `[32, 32, 32, 32, 32, 32, 32, 32]`.
55
    uint256 private constant COL_SHIFTS = 0x820820820820;
56

57
    /// @notice A bitpacked value that indicates how many bits to shift by to
58
    /// get to the next value in the 2 × 4 subgrid.
59
    /// @dev We reserve 6 bits for each value, and the following are packed
60
    // left-to-right: `[4, 4, 4, 20, 4, 4, 4, 4]`.
61
    uint256 private constant SUBGRID_SHIFTS = 0x104104504104;
62

63
    /// @notice A bitmap to denote that each of [1, ..., 8] has been seen.
64
    /// @dev Bits 1-8 should be set to 1, with everything else set to 0 (i.e.
65
    /// `0b111111110 = 0xFE`).
66
    uint256 private constant FILLED_BITMAP = 0x1FE;
67

68
    /// @inheritdoc IPuzzle
69
    function name() external pure returns (string memory) {
70
        return unicode"2 × 4 = 8";
71
    }
72

73
    /// @inheritdoc IPuzzle
74
    function generate(address _seed) external pure returns (uint256) {
75
        uint256 seed = uint256(keccak256(abi.encodePacked(_seed)));
76
        uint256 puzzle;
77

78
        // We use this to keep track of which indices [0, ..., 63] have been
79
        // filled. See the next comment for why the value is initialized to
80
        // `1 << 64`.
81
        uint256 bitmap = 1 << 64;
82
        // Note that the bitmap only intends on reserving bits 0-63 to represent
83
        // the slots that have been filled. Thus, if we set `index` to 64, it
84
        // is a sentinel value that will always yield 0 when using it to
85
        // retrieve from the bitmap.
86
        uint256 index = 64;
87
        // We fill the puzzle randomly with 1 of [1, ..., 8]. This way, every
88
        // puzzle is solvable.
89
        for (uint256 i = 1; i < 9; ) {
90
            // We have exhausted the seed, so stop iterating.
91
            if (seed == 0) break;
92

93
            // Loop through until we find an unfilled index.
94
            while ((bitmap >> index) & 1 == 1 && seed != 0) {
95
                // Retrieve 6 random bits from `seed` to determine which index
96
                // to fill.
97
                index = seed & 0x3F;
98
                seed >>= 6;
99
            }
100
            // Set the bit in the bitmap to indicate that the index has
101
            // been filled.
102
            bitmap |= 1 << index;
103

104
            // Place the number into the slot that was just filled.
105
            puzzle |= (i << (index << 2));
106
            index = 64;
107
            unchecked {
108
                ++i;
109
            }
110
        }
111

112
        return puzzle;
113
    }
114

115
    /// @inheritdoc IPuzzle
116
    function verify(uint256 _start, uint256 _solution)
117
        external
118
        pure
119
        returns (bool)
120
    {
121
        // Iterate through the puzzle.
122
        for (uint256 index; index < 256; ) {
123
            // Check that the starting position is included in the solution.
124
            if (_start & 0xF != 0 && _start & 0xF != _solution & 0xF)
125
                return false;
126

127
            // Retrieve how many checks to perform.
128
            uint256 checks = (CHECKS >> index) & 7;
129
            if (checks & 4 == 4 && !check(_solution, ROW_SHIFTS)) return false;
130
            if (checks & 2 == 2 && !check(_solution, COL_SHIFTS)) return false;
131
            if (checks & 1 == 1 && !check(_solution, SUBGRID_SHIFTS))
132
                return false;
133

134
            _start >>= 4;
135
            _solution >>= 4;
136
            unchecked {
137
                index += 4;
138
            }
139
        }
140

141
        return true;
142
    }
143

144
    /// @notice Checks whether a row, column, or box is filled in a valid way.
145
    /// @param _shifted The puzzle shifted to the index it should start checking
146
    /// from.
147
    /// @param _shifts A bitpacked value that indicates how many bits to shift
148
    /// by after each iteration in the loop.
149
    /// @return Whether the check is valid.
150
    function check(uint256 _shifted, uint256 _shifts)
151
        internal
152
        pure
153
        returns (bool)
154
    {
155
        uint256 shifted = _shifted;
156
        // Used to keep track of which numbers [1, ..., 8] have been seen.
157
        uint256 bitmap;
158

159
        while (_shifts != 0) {
160
            // Set the bit in the bitmap to indicate that the number has been
161
            // seen.
162
            bitmap |= 1 << (shifted & 0xF); // `shifted & 0xF` reads the number.
163
            // Retrieve 6 bits from `_shifts` to determine how many bits to
164
            // shift the puzzle by.
165
            shifted >>= (_shifts & 0x3F);
166
            _shifts >>= 6;
167
        }
168

169
        return bitmap == FILLED_BITMAP;
170
    }
171
}
172