Puzzle #10
Last One Standing
Author
1// SPDX-License-Identifier: Unlicense2pragma solidity ^0.8.17;3
4import {IPuzzle} from "../interfaces/IPuzzle.sol";5
6/// @title Last One Standing7/// @custom:subtitle 4 × 4 Chess Puzzle.8/// @author fiveoutofnine9/// @notice The goal of the puzzle is to make a series of moves such that only10/// 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 king12/// can not be captured by any black piece. The starting position must have13/// all the pieces a standard game of chess has, except for the pawns.14contract Chess is IPuzzle {15 // -------------------------------------------------------------------------16 // Pieces17 // -------------------------------------------------------------------------18 // Let `pieceType` be `piece & 7` (i.e. the last 3 bits). Then, the19 // 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 the23 // other direction. The square of these is 5 (`2**2 + 1**2`), and24 // there are no other pair of numbers whose squares sum to 5. This25 // gives rise to a very nice way to validate knight moves:26 // `xDiff * xDiff + yDiff * yDiff == pieceType` is valid if and only27 // if the move is made by a knight.28 // * Unlike knights, kings have multiple "sum of squares" values: (1) a29 // king may move 0 in 1 direction and 0 in another30 // (`0**2 + 1**2 = 1`), or (2) a king may move 1 in both directions31 // (`1**2 + 1**2 = 2`). If we wrap32 // `xDiff * xDiff + yDiff * yDiff - pieceType` in an `unchecked`33 // block, we can check for both of these conditions at once if we34 // denote 1 as king: the expression will evaluate to 0 or 1 if the35 // move is valid (note: we make use of the fact that underflows result36 // in a number larger than 1). Since 6 (1 more than the value assigned37 // for knights (5)) also has no other pair of numbers whose squares38 // sum to it, we can extend this logic to knights! Conclusion: as39 // long as we check the condition in a block where we know the piece40 // 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 // Moves77 // -------------------------------------------------------------------------78 // The following are masks to extract pieces relevant to some ray a sliding79 // piece traverses. If a piece is a sliding piece, the bits we retrieve by80 // masking the board shifted to the smaller index of the move and the81 // 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 into91 // a single `uint256`, which will serve as a look-up table for ray check92 // 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 may101 // require. Let `board` be the position of the board, `minIndex` be the102 // 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, and104 // `minPiece` be the piece at the smaller of the 2 indices. Then, the105 // 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 State121 // -------------------------------------------------------------------------122
123 /// @notice The position of the board, before it is shuffled. There are the124 /// same number of pieces as in a regular game of chess, except for the125 /// 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 to146 /// play: if it is `0`, a black piece must play next; if it is `1`, a white147 /// 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 type152 /// 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 00155 /// ------+------------------------------------------156 /// Bits | 10_01_10_10_01_00_00_00_10_01_10_10_01_00157 uint256 private constant STARTING_PIECE_COUNTS = 0x9A409A4;158
159 /// @notice By the end of the sequence of moves, the piece counts must be160 /// equivalent to this.161 /// @dev The expression below evaluates to `0x40000`: there must only be 1162 /// 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 IPuzzle166 function name() external pure returns (string memory) {167 return "Last One Standing";168 }169
170 /// @inheritdoc IPuzzle171 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 may176 // 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 to179 // 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 IPuzzle195 function verify(196 uint256 _start,197 uint256 _solution198 ) 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 _b315 ) 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
Time Left
Solve locally (WIP)
- Clone GitHub repo + install deps
git clone https://github.com/waterfall-mkt/curta-puzzles.git && cd curta-puzzles && forge install
- Set
RPC_URL_MAINNET
in.env
.env
RPC_URL_MAINNET=""
- Write solution + run script
forge script <PATH_TO_PUZZLE> -f mainnet -vvv
This is still WIP.