14
$\begingroup$

Can you piece these jigsaw pieces back together again?

X...X......X....X..X  
X.X.....X.....X....X  
XX.X...X...X  
X.....X.X...X.....X  
X.X.X.X..X..

The solution consists of 25 X's in a row. Where two pieces overlap, X's replace the .'s.

$\endgroup$
  • $\begingroup$ Nice puzzle. How did you set about looking for a set of pieces which would make a non-trivial puzzle? $\endgroup$ – Rosie F Aug 31 '18 at 10:28
  • 2
    $\begingroup$ my current ad hoc solution is based around another of my puzzles - Keys. Scrambling this proved very difficult, and I resorted to generating a random puzzle and obscuring the answer by trial and error, all using computers. This has left me with a healthy sense of how to make a solution unique, but as I said, is by no means guaranteed to work. You just reject the rejects I guess. $\endgroup$ – JMP Aug 31 '18 at 10:38
  • 1
    $\begingroup$ If I may, would you mind replacing the O by ., it would make reading easier. $\endgroup$ – Matthieu M. Aug 31 '18 at 11:30
13
$\begingroup$

The solution is:

                   X . . . X . . . . . . X . . . . X . . X       1
                 X . X . . . . . X . . . . . X . . . . X         2
         X X . X . . . X . . . X                                 3
             X . . . . . X . X . . . X . . . . . X               4
                                   X . X . X . X . . X . .       5

         3 3 4 3 2 1 2 3 4 1 4 3 2 5 4 5 1 5 2 5 4 1 5 2 1

$\endgroup$
  • 2
    $\begingroup$ There isn't that much to explain, really: I just pushed the pieces around in a fixed-width text editor until they aligned. $\endgroup$ – M Oehm Aug 31 '18 at 8:20
  • 1
    $\begingroup$ (I liked the puzzle and I also like the idea of text editors as low-key front end.) $\endgroup$ – M Oehm Aug 31 '18 at 8:24
2
$\begingroup$

Here is a Python script which bruteforces the solution. To summarize, it assumes one of the pieces is the right-most, then shifts each remaining piece to the left and checks if it solves the puzzle.

The check is done by treating the strings as binary numbers, performing bit shifts (i.e. multiplying by powers of 2), then check if their sum is equal to $2^{25} - 1$ i.e. the 25-bit number with all 1s.

Note that in the case where the solution consists of multiple pieces aligned at the right-most, the script will think there are multiple solutions, but these can be easily screened out manually.

On my computer this runs for ~0.5s. I imagine this can be optimized if necessary for larger inputs.

def f(x):
    return int(x.replace('X', '1').replace('.', '0'), base=2)

def finv(x):
    return "{0:b}".format(x).replace('1', 'X').replace('0', '.')

pieces = [
    f('X...X......X....X..X'),
    f('X.X.....X.....X....X'),
    f('XX.X...X...X'),
    f('X.....X.X...X.....X'),
    f('X.X.X.X..X..')
]

finallen = 25

def piece_len(piece):
    from math import log2, ceil
    return ceil(log2(piece))
    # Alternatively, return len(finv(piece))

for piece in pieces:
    remainingpieces = pieces[:]
    remainingpieces.remove(piece)

    # Assume the current piece is the right-most.
    # The position of each remaining piece is then at most
    # (25 - length of piece) to the left.

    positionstoshift = [0] * len(remainingpieces)
    stoploop = False
    while not stoploop:
        shiftedremainingpieces = []

        for i in range(len(remainingpieces)):
            shiftedremainingpieces.append(
                remainingpieces[i] << positionstoshift[i]
            )

        arithsum = sum(shiftedremainingpieces) + piece

        if arithsum == 2 ** finallen - 1:
            print("Solution found:")
            # Print all pieces with appropriate space padding
            print(" " * (finallen - piece_len(piece)) + finv(piece))
            for i in range(len(remainingpieces)):
                print(" " * (
                    finallen -
                    piece_len(remainingpieces[i]) -
                    positionstoshift[i]
                ) + finv(remainingpieces[i]))
            print("")
            # Terminate the program here if only one solution is needed

        # Increment positionstoshift
        positionstoshift[-1] += 1
        # Loop from the right, carry over as necessary
        for i in range(-1, -len(positionstoshift) - 1, -1):
            if positionstoshift[i] > finallen - piece_len(remainingpieces[i]):
                positionstoshift[i] = 0
                try:
                    positionstoshift[i - 1] += 1
                except IndexError:
                    # Can't carry over, hence reached the end
                    stoploop = True
                    break

Output:

Solution found:
     X...X......X....X..X
    X.X.....X.....X....X
XX.X...X...X
  X.....X.X...X.....X
             X.X.X.X..X..

Solution found:
             X.X.X.X..X..
     X...X......X....X..X
    X.X.....X.....X....X
XX.X...X...X
  X.....X.X...X.....X

$\endgroup$
  • $\begingroup$ your first 'solution' isn't $\endgroup$ – JMP Aug 31 '18 at 16:23
  • $\begingroup$ @JonMarkPerry Sorry that was just me messing up the formatting on stackexchange $\endgroup$ – user12205 Aug 31 '18 at 16:25
  • $\begingroup$ okay, but you should have found 120 solutions like this $\endgroup$ – JMP Aug 31 '18 at 16:32
  • $\begingroup$ @JonMarkPerry How did you arrive at the number 120? I'm struggling to see how my algorithm skipped 118 cases. $\endgroup$ – user12205 Aug 31 '18 at 16:38
  • $\begingroup$ your 2 solutions are permutations of each other by row, and there are 5!=5.4.3.2.1=120 of these. $\endgroup$ – JMP Aug 31 '18 at 16:59
0
$\begingroup$

A start:

Number the 25 positions $1\dots 25$.

I note that your 2nd piece occupies 4 positions of one parity and 1 of the other. So do your 3rd and 5th pieces. And your 4th occupies 5 positions all of the same parity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.