Skip to content

Instantly share code, notes, and snippets.

@peter-dolkens
Last active April 4, 2020 03:36
Show Gist options
  • Save peter-dolkens/1369f21bce29c18c048711c61e413295 to your computer and use it in GitHub Desktop.
Save peter-dolkens/1369f21bce29c18c048711c61e413295 to your computer and use it in GitHub Desktop.
Mathematical solution to https://cdn.cs50.net/2020/x/events/puzzles/puzzles.pdf -> Putting it all together

Mathematical solution to https://cdn.cs50.net/2020/x/events/puzzles/puzzles.pdf -> Putting it all together

First, we encode tiles into binary in low-byte order, assuming an 8-bit row-size.

For example:

 J
UN
H

would be encoded as 00000001 00000011 00000010 => 66306

To solve the puzzle then, we would expect to see all (8) rows and all (8) columns filled.

This would mean 64 bits would be filled, which can be represented as 2^64.

We can move a tile around the puzzle by "shifting" it in the binary space.

If we label the position of each tile a-r, then we can represent the "shift" action of tile a as 2^a.

All solutions to this puzzle satisfy this equation:

2^64 =
66306 * 2^a +
66305 * 2^b +
769 * 2^c +
771 * 2^d +
65795 * 2^e +
1796 * 2^f +
1794 * 2^g +
1539 * 2^h +
515 * 2^i +
66305 * 2^j +
770 * 2^k +
65793 * 2^l +
770 * 2^m +
65793 * 2^n +
131587 * 2^o +
196865 * 2^p +
259 * 2^q +
770 * 2^r

All solutions to this puzzle are also integers, and must fit within the board, thus we can constrain a-r as such:

a-z ∈ ℤ {0, 63}

We will then still have some solutions which are not possible, as a piece may be positioned on a row-boundary.

To solve this, we will encode just the width of each tile in similar fashion to the tile encoding.

For example:

 J
UN
H

would be encoded as 00000011 => 3

We can then add the constraints (TODO - these are wrong - fix)

0 = (2^8 - 1) AND (3 x 2^a % 2^8) - (3 x 2^a) +
    (2^8 - 1) AND (3 x 2^b % 2^8) - (3 x 2^b) +
    (2^8 - 1) AND (3 x 2^c % 2^8) - (3 x 2^c) +
    (2^8 - 1) AND (3 x 2^d % 2^8) - (3 x 2^d) +
    (2^8 - 1) AND (7 x 2^e / 2^8) - (7 x 2^e) +
    (2^8 - 1) AND (7 x 2^f / 2^8) - (7 x 2^f) +
    (2^8 - 1) AND (7 x 2^g / 2^8) - (7 x 2^g) +
    (2^8 - 1) AND (3 x 2^h / 2^8) - (3 x 2^h) +
    (2^8 - 1) AND (3 x 2^i / 2^8) - (3 x 2^i) +
    (2^8 - 1) AND (3 x 2^j / 2^8) - (3 x 2^j) +
    (2^8 - 1) AND (3 x 2^k / 2^8) - (3 x 2^k) +
    (2^8 - 1) AND (1 x 2^l / 2^8) - (1 x 2^l) +
    (2^8 - 1) AND (3 x 2^m / 2^8) - (3 x 2^m) +
    (2^8 - 1) AND (1 x 2^n / 2^8) - (1 x 2^n) +
    (2^8 - 1) AND (3 x 2^o / 2^8) - (3 x 2^o) +
    (2^8 - 1) AND (3 x 2^p / 2^8) - (3 x 2^p) +
    (2^8 - 1) AND (3 x 2^q / 2^8) - (3 x 2^q) +
    (2^8 - 1) AND (3 x 2^r / 2^8) - (3 x 2^r)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment