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.
$\begingroup$
$\endgroup$
3
3 Answers
$\begingroup$
$\endgroup$
2
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
-
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 OehmCommented Aug 31, 2018 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 OehmCommented Aug 31, 2018 at 8:24
$\begingroup$
$\endgroup$
7
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
-
-
$\begingroup$ @JonMarkPerry Sorry that was just me messing up the formatting on stackexchange $\endgroup$ Commented Aug 31, 2018 at 16:25
-
$\begingroup$ okay, but you should have found 120 solutions like this $\endgroup$– JMPCommented Aug 31, 2018 at 16:32
-
1$\begingroup$ your 2 solutions are permutations of each other by row, and there are 5!=5.4.3.2.1=120 of these. $\endgroup$– JMPCommented Aug 31, 2018 at 16:59
-
2$\begingroup$ I think what you've done is find the first perm, which is straight from 'pieces', then GO BACK one, and your loop now thinks you are at the end and so terminates. Because the order you slot the pieces together doesn't matter, so the two solutions you have are the same. $\endgroup$– JMPCommented Aug 31, 2018 at 17:50
$\begingroup$
$\endgroup$
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.
Oby., it would make reading easier. $\endgroup$