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

4
import {IPuzzle} from "../interfaces/IPuzzle.sol";
5

6
/// @title Last One Standing
7
/// @custom:subtitle 4 × 4 Chess Puzzle.
8
/// @author fiveoutofnine
9
/// @notice The goal of the puzzle is to make a series of moves such that only
10
/// the white king remains on the board. Each move must capture another piece,
11
/// and the black king may be captured. Checks do not matter, but the white king
12
/// can not be captured by any black piece. The starting position must have
13
/// all the pieces a standard game of chess has, except for the pawns.
14
contract Chess is IPuzzle {
15
    // -------------------------------------------------------------------------
16
    // Pieces
17
    // -------------------------------------------------------------------------
18
    // Let `pieceType` be `piece & 7` (i.e. the last 3 bits). Then, the
19
    // formulation below allows for the following checks:
20
    //     * `(pieceType & 3) == 1` is only true for kings and knights;
21
    //       equivalently, if `!= 1`, the piece must be a sliding piece.
22
    //     * A knight must move 2 squares in one direction and 1 square in the
23
    //       other direction. The square of these is 5 (`2**2 + 1**2`), and
24
    //       there are no other pair of numbers whose squares sum to 5. This
25
    //       gives rise to a very nice way to validate knight moves:
26
    //       `xDiff * xDiff + yDiff * yDiff == pieceType` is valid if and only
27
    //       if the move is made by a knight.
28
    //     * Unlike knights, kings have multiple "sum of squares" values: (1) a
29
    //       king may move 0 in 1 direction and 0 in another
30
    //       (`0**2 + 1**2 = 1`), or (2) a king may move 1 in both directions
31
    //       (`1**2 + 1**2 = 2`). If we wrap
32
    //       `xDiff * xDiff + yDiff * yDiff - pieceType` in an `unchecked`
33
    //       block, we can check for both of these conditions at once if we
34
    //       denote 1 as king: the expression will evaluate to 0 or 1 if the
35
    //       move is valid (note: we make use of the fact that underflows result
36
    //       in a number larger than 1). Since 6 (1 more than the value assigned
37
    //       for knights (5)) also has no other pair of numbers whose squares
38
    //       sum to it, we can extend this logic to knights! Conclusion: as
39
    //       long as we check the condition in a block where we know the piece
40
    //       is a king or a knight, we can validate the move with 1 expression.
41

42
    /// @notice Denotes an empty square.
43
    uint256 private constant EMPTY = 0;
44

45
    /// @notice Denotes a black king.
46
    uint256 private constant KING = 1;
47

48
    /// @notice Denotes a black bishop.
49
    uint256 private constant BISHOP = 2;
50

51
    /// @notice Denotes a black rook.
52
    uint256 private constant ROOK = 3;
53

54
    /// @notice Denotes a black queen.
55
    uint256 private constant QUEEN = 4;
56

57
    /// @notice Denotes a black knight.
58
    uint256 private constant KNIGHT = 5;
59

60
    /// @notice Denotes a white king.
61
    uint256 private constant WHITE_KING = (1 << 3) | KING;
62

63
    /// @notice Denotes a white bishop.
64
    uint256 private constant WHITE_BISHOP = (1 << 3) | BISHOP;
65

66
    /// @notice Denotes a white rook.
67
    uint256 private constant WHITE_ROOK = (1 << 3) | ROOK;
68

69
    /// @notice Denotes a white queen.
70
    uint256 private constant WHITE_QUEEN = (1 << 3) | QUEEN;
71

72
    /// @notice Denotes a white knight.
73
    uint256 private constant WHITE_KNIGHT = (1 << 3) | KNIGHT;
74

75
    // -------------------------------------------------------------------------
76
    // Moves
77
    // -------------------------------------------------------------------------
78
    // The following are masks to extract pieces relevant to some ray a sliding
79
    // piece traverses. If a piece is a sliding piece, the bits we retrieve by
80
    // masking the board shifted to the smaller index of the move and the
81
    // corresponding ray's mask should be 0 (i.e. there are no pieces in)
82
    // the way.
83
    //            | Ray Type                   | Mask               |
84
    //            |----------------------------+--------------------|
85
    //            | Vertical                   | 0xF000F000F000F    |
86
    //            | Horizontal                 | 0xFFFF             |
87
    //            | Diagonal towards top-right | 0xF00F00F00F       |
88
    //            | Diagonal towards top-left  | 0xF0000F0000F0000F |
89
    //
90
    // We can reserve 64 bits for each of the masks, and then bitpack it into
91
    // a single `uint256`, which will serve as a look-up table for ray check
92
    // masks:
93
    // ```
94
    // uint256 RAY_MASKS = (0xF000F000F000F << 192)
95
    //     | (0xFFFF << 128)
96
    //     | (0xF00F00F00F << 64)
97
    //     | 0xF0000F0000F0000F;
98
    // ```
99
    //
100
    // This eliminates almost all of the branching a naive implementation may
101
    // require. Let `board` be the position of the board, `minIndex` be the
102
    // smaller of the move's 2 indices, `rayMask` be the corresponding ray mask,
103
    // `idxDiff` be the difference between the 2 indices of the move, and
104
    // `minPiece` be the piece at the smaller of the 2 indices. Then, the
105
    // general condition for invalidating a sliding piece's move is:
106
    // ```
107
    // (board >> (minIndex << 2))
108
    //     & (rayMask & ((1 << (idxDiff << 2)) - 1)
109
    // ) != minPiece;
110
    // ```
111

112
    /// @notice A look-up table of ray check masks.
113
    uint256 private constant RAY_MASKS =
114
        0xF000F000F000F000000000000FFFF000000F00F00F00FF0000F0000F0000F;
115

116
    /// @notice A mask to read a ray mask from `RAY_MASKS`.
117
    uint256 private constant RAY_MASK_MASK = 0xFFFFFFFFFFFFFFFF;
118

119
    // -------------------------------------------------------------------------
120
    // Game State
121
    // -------------------------------------------------------------------------
122

123
    /// @notice The position of the board, before it is shuffled. There are the
124
    /// same number of pieces as in a regular game of chess, except for the
125
    /// pawns.
126
    /// @dev The expression below evaluates to `0x122334559AABBCDD`.
127
    uint256 private constant STARTING_BOARD =
128
        (KING << 60) |
129
            (BISHOP << 56) |
130
            (BISHOP << 52) |
131
            (ROOK << 48) |
132
            (ROOK << 44) |
133
            (QUEEN << 40) |
134
            (KNIGHT << 36) |
135
            (KNIGHT << 32) |
136
            (WHITE_KING << 28) |
137
            (WHITE_BISHOP << 24) |
138
            (WHITE_BISHOP << 20) |
139
            (WHITE_ROOK << 16) |
140
            (WHITE_ROOK << 12) |
141
            (WHITE_QUEEN << 8) |
142
            (WHITE_KNIGHT << 4) |
143
            (WHITE_KNIGHT << 0);
144

145
    /// @notice The 65th bit (from the right) indicates whose turn it is to
146
    /// play: if it is `0`, a black piece must play next; if it is `1`, a white
147
    /// piece must play next.
148
    /// @dev The expression below evaluates to `0x10000000000000000`.
149
    uint256 private constant TURN_MASK = 1 << 64;
150

151
    /// @notice A bitpacked integer that serves as a mapping from a piece type
152
    /// to the count remaining (i.e. has not been captured yet).
153
    /// @dev The expression below evaluates to `0x9A409A4`:
154
    ///            Index | 13 12 11 10 09 08 07 06 05 04 03 02 01 00
155
    ///            ------+------------------------------------------
156
    ///            Bits  | 10_01_10_10_01_00_00_00_10_01_10_10_01_00
157
    uint256 private constant STARTING_PIECE_COUNTS = 0x9A409A4;
158

159
    /// @notice By the end of the sequence of moves, the piece counts must be
160
    /// equivalent to this.
161
    /// @dev The expression below evaluates to `0x40000`: there must only be 1
162
    /// white king left, so we shift `1` left by `(WHITE_KING << 1)` bits.
163
    uint256 private constant SOLVED_PIECE_COUNTS = (1 << (WHITE_KING << 1));
164

165
    /// @inheritdoc IPuzzle
166
    function name() external pure returns (string memory) {
167
        return "Last One Standing";
168
    }
169

170
    /// @inheritdoc IPuzzle
171
    function generate(address _seed) external pure returns (uint256) {
172
        uint256 seed = uint256(keccak256(abi.encodePacked(_seed)));
173
        uint256 puzzle = STARTING_BOARD;
174

175
        // We swap until the seed is exhausted; otherwise, vanity addresses may
176
        // guarantee an easy / trivial solution to the puzzle.
177
        for (; seed != 0; seed >>= 8) {
178
            // Retrieve 8 random bits from `seed` to determine which indices to
179
            // swap.
180
            uint256 a = seed & 0xF;
181
            uint256 b = (seed >> 4) & 0xF;
182
            seed >>= 8;
183

184
            // Nothing to swap if the indices are the same.
185
            if (a == b) continue;
186

187
            puzzle = swap(puzzle, a, b);
188
        }
189

190
        // White should play first, so we initialize with `1` at the 65th bit.
191
        return TURN_MASK | puzzle;
192
    }
193

194
    /// @inheritdoc IPuzzle
195
    function verify(
196
        uint256 _start,
197
        uint256 _solution
198
    ) external pure returns (bool) {
199
        uint256 pieceCounts = STARTING_PIECE_COUNTS;
200

201
        // Apply `_solution` to `_start`.
202
        for (; _solution != 0; _solution >>= 8) {
203
            uint256 from = (_solution >> 4) & 0xF;
204
            uint256 to = _solution & 0xF;
205
            uint256 pieceFrom = (_start >> (from << 2)) & 0xF;
206
            uint256 pieceTo = (_start >> (to << 2)) & 0xF;
207

208
            // Sanity checks.
209
            if (
210
                pieceFrom == EMPTY || // No piece to move.
211
                pieceTo == EMPTY || // There must be a piece at the `to`.
212
                pieceFrom >> 3 != _start >> 64 || // It must be the correct piece's turn.
213
                pieceFrom >> 3 == pieceTo >> 3 || // Piece must be a capture.
214
                pieceTo == WHITE_KING // The white king cannot be captured.
215
            ) return false;
216

217
            // Move validation.
218
            uint256 pieceType = pieceFrom & 7;
219
            unchecked {
220
                uint256 xDiff = (to & 3) > (from & 3)
221
                    ? (to & 3) - (from & 3)
222
                    : (from & 3) - (to & 3);
223
                uint256 yDiff = (to >> 2) > (from >> 2)
224
                    ? (to >> 2) - (from >> 2)
225
                    : (from >> 2) - (to >> 2);
226

227
                if (pieceType & 3 == 1) {
228
                    // Piece is a knight or a king.
229
                    if (xDiff * xDiff + yDiff * yDiff - pieceType > 1)
230
                        return false;
231
                } else {
232
                    // Piece is a sliding piece (bishop, rook, or queen).
233
                    uint256 minIndex;
234
                    uint256 idxDiff;
235
                    {
236
                        if (to > from) {
237
                            minIndex = from;
238
                            idxDiff = to - from;
239
                        } else {
240
                            minIndex = to;
241
                            idxDiff = from - to;
242
                        }
243
                    }
244

245
                    uint256 rayMask;
246
                    {
247
                        uint256 isOrthogonal;
248
                        uint256 isDiagonal;
249
                        uint256 isVertical;
250
                        uint256 isDiagonalRight;
251
                        assembly {
252
                            // Equivalent to`xDiff * yDiff == 0 && pieceType != BISHOP`.
253
                            isOrthogonal := and(
254
                                iszero(mul(xDiff, yDiff)),
255
                                iszero(eq(pieceType, BISHOP))
256
                            )
257
                            // Equivalent to `xDiff != yDiff && pieceType != ROOK`.
258
                            isDiagonal := and(
259
                                eq(xDiff, yDiff),
260
                                iszero(eq(pieceType, ROOK))
261
                            )
262
                            // Equivalent to `xDiff == 0`.
263
                            isVertical := iszero(xDiff)
264
                            // Equivalent to `idxDiff % 3 == 0`.
265
                            isDiagonalRight := iszero(mod(idxDiff, 3))
266
                        }
267

268
                        // Piece does not move orthogonally or diagonally.
269
                        if (isOrthogonal + isDiagonal == 0) return false;
270

271
                        // Retrieve the ray mask and correctly size it.
272
                        rayMask =
273
                            (((RAY_MASKS >> (isOrthogonal << 7)) >>
274
                                (isVertical << 6)) >> (isDiagonalRight << 6)) & // `<< 7` is equivalent to `* 128`. // `<< 6` is equivalent to `* 64`. // `<< 6` is equivalent to `* 64`.
275
                            (RAY_MASK_MASK & ((1 << (idxDiff << 2)) - 1));
276
                    }
277

278
                    // Check if the ray between `from` and `to` is clear.
279
                    // Shift the board to the index to apply the ray mask.
280
                    uint256 shiftedBoard;
281
                    {
282
                        shiftedBoard = _start >> (minIndex << 2);
283
                    }
284
                    if (
285
                        (shiftedBoard & rayMask) !=
286
                        (to > from ? pieceFrom : pieceTo)
287
                    ) return false;
288
                }
289
            }
290

291
            // Apply move and update turn indicator.
292
            _start &= ~((0xF << (from << 2)) | (0xF << (to << 2)));
293
            _start |= pieceFrom << (to << 2);
294
            _start ^= TURN_MASK;
295

296
            // Update `pieces`.
297
            uint256 mask = 3 << (pieceTo << 1);
298
            pieceCounts =
299
                (pieceCounts & ~mask) |
300
                (((pieceCounts & mask) >> 1) & mask);
301
        }
302

303
        return pieceCounts == SOLVED_PIECE_COUNTS;
304
    }
305

306
    /// @notice A function to swap two pieces on the puzzle.
307
    /// @param _puzzle The board to swap pieces on.
308
    /// @param _a The index of the first piece to swap.
309
    /// @param _b The index of the second piece to swap.
310
    /// @return The board with the pieces swapped.
311
    function swap(
312
        uint256 _puzzle,
313
        uint256 _a,
314
        uint256 _b
315
    ) internal pure returns (uint256) {
316
        // Adjust board index to number of bits to shift by.
317
        _a <<= 2; // `<< 2` is equivalent to `* 4`.
318
        _b <<= 2; // `<< 2` is equivalent to `* 4`.
319

320
        // Get pieces at `_a` and `_b`.
321
        uint256 a = (_puzzle >> _a) & 0xF;
322
        uint256 b = (_puzzle >> _b) & 0xF;
323

324
        // Delete bits.
325
        _puzzle &= type(uint256).max ^ (0xF << _a);
326
        _puzzle &= type(uint256).max ^ (0xF << _b);
327

328
        // Insert pieces.
329
        _puzzle |= a << _b;
330
        _puzzle |= b << _a;
331

332
        return _puzzle;
333
    }
334
}
335