Proving a jigsaw is possible
$begingroup$
This is an offshoot of this question.
Suppose we have jigsaw puzzle pieces which are basically squares but where each side can be either straight, concave or convex. An example of three such pieces is shown below:
It is clear that there can be $3^4=81$ different types of pieces. I was wondering, given one of each type (and with no rotations or flips allowed), whether it was possible to create a standard jigsaw puzzle, using just those $81$ pieces. By "standard jigsaw puzzle" I mean one of dimensions $m times n$ where all perimeter sides are straight.
A $1times 81$ puzzle is clearly not possible as it would require all $81$ pieces to be straight on both the left and the right side. A similar argument holds for a $81times 1$ puzzle.
A $3times 27$ puzzle would require $27$ pieces with a left straight side and $27$ pieces with a right straight edge, and while it is true that such two sets exist, they have an overlap of $9$ pieces. This is therefore not possible. As before, a similar argument holds for a $27times 3$ puzzle.
This leaves the $9times 9$ possibility. A priori, I can see no reason this shouldn't be possible. And I think I have a proof that it is possible, which is what I would like your opinion on.
Given a $9times 9$ puzzle, we have the situation below:
Each black side of a piece is fixed, but each green side of a piece represents a possible connection type. A connection type could be a "straight - straight", "concave - convex" or "convex - concave" type. It seems to me that if we run through every possible connection type for each piece, one of those scenarios must give a puzzle where each of the $81$ piece types is used exactly once.
Am I right?
combinatorics recreational-mathematics puzzle
asked Jun 11 '17 at 18:54
JensJens
3,7152930
$endgroup$
|
show 4 more comments
$begingroup$
This is an offshoot of this question.
Suppose we have jigsaw puzzle pieces which are basically squares but where each side can be either straight, concave or convex. An example of three such pieces is shown below:
It is clear that there can be $3^4=81$ different types of pieces. I was wondering, given one of each type (and with no rotations or flips allowed), whether it was possible to create a standard jigsaw puzzle, using just those $81$ pieces. By "standard jigsaw puzzle" I mean one of dimensions $m times n$ where all perimeter sides are straight.
A $1times 81$ puzzle is clearly not possible as it would require all $81$ pieces to be straight on both the left and the right side. A similar argument holds for a $81times 1$ puzzle.
A $3times 27$ puzzle would require $27$ pieces with a left straight side and $27$ pieces with a right straight edge, and while it is true that such two sets exist, they have an overlap of $9$ pieces. This is therefore not possible. As before, a similar argument holds for a $27times 3$ puzzle.
This leaves the $9times 9$ possibility. A priori, I can see no reason this shouldn't be possible. And I think I have a proof that it is possible, which is what I would like your opinion on.
Given a $9times 9$ puzzle, we have the situation below:
Each black side of a piece is fixed, but each green side of a piece represents a possible connection type. A connection type could be a "straight - straight", "concave - convex" or "convex - concave" type. It seems to me that if we run through every possible connection type for each piece, one of those scenarios must give a puzzle where each of the $81$ piece types is used exactly once.
Am I right?
combinatorics recreational-mathematics puzzle
asked Jun 11 '17 at 18:54
JensJens
3,7152930
$endgroup$
3
$begingroup$
"if we run through every possible connection type for each piece" - I'm not sure I understand what you mean. What about the piece with all straight sides, the one with all concave sides, and the one with all convex sides? Could you clarify your statement?
$endgroup$
– Michael Lee
Jun 11 '17 at 19:31
8
$begingroup$
What you're describing sounds like a brute-force method of generating a solution if one exists, but definitely not a proof of existence.
$endgroup$
– Michael Lee
Jun 11 '17 at 19:34
5
$begingroup$
If there is such a solution, you'll find it. If there isn't, you won't. I see no reason to rule out either possibility.
$endgroup$
– Robert Israel
Jun 11 '17 at 19:49
6
$begingroup$
It won't if there isn't a solution.
$endgroup$
– Robert Israel
Jun 11 '17 at 20:11
5
$begingroup$
@Jens; Robert Israel is saying that while the approach you're suggesting is a valid strategy to find out if there is a solution or not, it is not in itself a proof either way. You could end up trying every single combination and find that none of them actually make a valid grid (though in this particular case, as Bram28 answered, it is in fact possible and therefore brute-force will indeed find a solution when applied). As a silly example of the negative, I could claim a boolean "a" exists such that "a = not a", with the "proof" that if I try every possible value of a, one of them must work.
$endgroup$
– Dave
Jun 11 '17 at 22:29
|
show 4 more comments
$begingroup$
This is an offshoot of this question.
Suppose we have jigsaw puzzle pieces which are basically squares but where each side can be either straight, concave or convex. An example of three such pieces is shown below:
It is clear that there can be $3^4=81$ different types of pieces. I was wondering, given one of each type (and with no rotations or flips allowed), whether it was possible to create a standard jigsaw puzzle, using just those $81$ pieces. By "standard jigsaw puzzle" I mean one of dimensions $m times n$ where all perimeter sides are straight.
A $1times 81$ puzzle is clearly not possible as it would require all $81$ pieces to be straight on both the left and the right side. A similar argument holds for a $81times 1$ puzzle.
A $3times 27$ puzzle would require $27$ pieces with a left straight side and $27$ pieces with a right straight edge, and while it is true that such two sets exist, they have an overlap of $9$ pieces. This is therefore not possible. As before, a similar argument holds for a $27times 3$ puzzle.
This leaves the $9times 9$ possibility. A priori, I can see no reason this shouldn't be possible. And I think I have a proof that it is possible, which is what I would like your opinion on.
Given a $9times 9$ puzzle, we have the situation below:
Each black side of a piece is fixed, but each green side of a piece represents a possible connection type. A connection type could be a "straight - straight", "concave - convex" or "convex - concave" type. It seems to me that if we run through every possible connection type for each piece, one of those scenarios must give a puzzle where each of the $81$ piece types is used exactly once.
Am I right?
combinatorics recreational-mathematics puzzle
asked Jun 11 '17 at 18:54
JensJens
3,7152930
$endgroup$
This is an offshoot of this question.
Suppose we have jigsaw puzzle pieces which are basically squares but where each side can be either straight, concave or convex. An example of three such pieces is shown below:
It is clear that there can be $3^4=81$ different types of pieces. I was wondering, given one of each type (and with no rotations or flips allowed), whether it was possible to create a standard jigsaw puzzle, using just those $81$ pieces. By "standard jigsaw puzzle" I mean one of dimensions $m times n$ where all perimeter sides are straight.
A $1times 81$ puzzle is clearly not possible as it would require all $81$ pieces to be straight on both the left and the right side. A similar argument holds for a $81times 1$ puzzle.
A $3times 27$ puzzle would require $27$ pieces with a left straight side and $27$ pieces with a right straight edge, and while it is true that such two sets exist, they have an overlap of $9$ pieces. This is therefore not possible. As before, a similar argument holds for a $27times 3$ puzzle.
This leaves the $9times 9$ possibility. A priori, I can see no reason this shouldn't be possible. And I think I have a proof that it is possible, which is what I would like your opinion on.
Given a $9times 9$ puzzle, we have the situation below:
Each black side of a piece is fixed, but each green side of a piece represents a possible connection type. A connection type could be a "straight - straight", "concave - convex" or "convex - concave" type. It seems to me that if we run through every possible connection type for each piece, one of those scenarios must give a puzzle where each of the $81$ piece types is used exactly once.
Am I right?
combinatorics recreational-mathematics puzzle
combinatorics recreational-mathematics puzzle
asked Jun 11 '17 at 18:54
JensJens
3,7152930
asked Jun 11 '17 at 18:54
JensJens
3,7152930
asked Jun 11 '17 at 18:54
JensJens
3,7152930
asked Jun 11 '17 at 18:54
JensJens
3,7152930
asked Jun 11 '17 at 18:54
JensJens
3,7152930
3,7152930
3
$begingroup$
"if we run through every possible connection type for each piece" - I'm not sure I understand what you mean. What about the piece with all straight sides, the one with all concave sides, and the one with all convex sides? Could you clarify your statement?
$endgroup$
– Michael Lee
Jun 11 '17 at 19:31
8
$begingroup$
What you're describing sounds like a brute-force method of generating a solution if one exists, but definitely not a proof of existence.
$endgroup$
– Michael Lee
Jun 11 '17 at 19:34
5
$begingroup$
If there is such a solution, you'll find it. If there isn't, you won't. I see no reason to rule out either possibility.
$endgroup$
– Robert Israel
Jun 11 '17 at 19:49
6
$begingroup$
It won't if there isn't a solution.
$endgroup$
– Robert Israel
Jun 11 '17 at 20:11
5
$begingroup$
@Jens; Robert Israel is saying that while the approach you're suggesting is a valid strategy to find out if there is a solution or not, it is not in itself a proof either way. You could end up trying every single combination and find that none of them actually make a valid grid (though in this particular case, as Bram28 answered, it is in fact possible and therefore brute-force will indeed find a solution when applied). As a silly example of the negative, I could claim a boolean "a" exists such that "a = not a", with the "proof" that if I try every possible value of a, one of them must work.
$endgroup$
– Dave
Jun 11 '17 at 22:29
|
show 4 more comments
3
$begingroup$
"if we run through every possible connection type for each piece" - I'm not sure I understand what you mean. What about the piece with all straight sides, the one with all concave sides, and the one with all convex sides? Could you clarify your statement?
$endgroup$
– Michael Lee
Jun 11 '17 at 19:31
8
$begingroup$
What you're describing sounds like a brute-force method of generating a solution if one exists, but definitely not a proof of existence.
$endgroup$
– Michael Lee
Jun 11 '17 at 19:34
5
$begingroup$
If there is such a solution, you'll find it. If there isn't, you won't. I see no reason to rule out either possibility.
$endgroup$
– Robert Israel
Jun 11 '17 at 19:49
6
$begingroup$
It won't if there isn't a solution.
$endgroup$
– Robert Israel
Jun 11 '17 at 20:11
5
$begingroup$
@Jens; Robert Israel is saying that while the approach you're suggesting is a valid strategy to find out if there is a solution or not, it is not in itself a proof either way. You could end up trying every single combination and find that none of them actually make a valid grid (though in this particular case, as Bram28 answered, it is in fact possible and therefore brute-force will indeed find a solution when applied). As a silly example of the negative, I could claim a boolean "a" exists such that "a = not a", with the "proof" that if I try every possible value of a, one of them must work.
$endgroup$
– Dave
Jun 11 '17 at 22:29
3
3
$begingroup$
"if we run through every possible connection type for each piece" - I'm not sure I understand what you mean. What about the piece with all straight sides, the one with all concave sides, and the one with all convex sides? Could you clarify your statement?
$endgroup$
– Michael Lee
Jun 11 '17 at 19:31
$begingroup$
"if we run through every possible connection type for each piece" - I'm not sure I understand what you mean. What about the piece with all straight sides, the one with all concave sides, and the one with all convex sides? Could you clarify your statement?
$endgroup$
– Michael Lee
Jun 11 '17 at 19:31
8
8
$begingroup$
What you're describing sounds like a brute-force method of generating a solution if one exists, but definitely not a proof of existence.
$endgroup$
– Michael Lee
Jun 11 '17 at 19:34
$begingroup$
What you're describing sounds like a brute-force method of generating a solution if one exists, but definitely not a proof of existence.
$endgroup$
– Michael Lee
Jun 11 '17 at 19:34
5
5
$begingroup$
If there is such a solution, you'll find it. If there isn't, you won't. I see no reason to rule out either possibility.
$endgroup$
– Robert Israel
Jun 11 '17 at 19:49
$begingroup$
If there is such a solution, you'll find it. If there isn't, you won't. I see no reason to rule out either possibility.
$endgroup$
– Robert Israel
Jun 11 '17 at 19:49
6
6
$begingroup$
It won't if there isn't a solution.
$endgroup$
– Robert Israel
Jun 11 '17 at 20:11
$begingroup$
It won't if there isn't a solution.
$endgroup$
– Robert Israel
Jun 11 '17 at 20:11
5
5
$begingroup$
@Jens; Robert Israel is saying that while the approach you're suggesting is a valid strategy to find out if there is a solution or not, it is not in itself a proof either way. You could end up trying every single combination and find that none of them actually make a valid grid (though in this particular case, as Bram28 answered, it is in fact possible and therefore brute-force will indeed find a solution when applied). As a silly example of the negative, I could claim a boolean "a" exists such that "a = not a", with the "proof" that if I try every possible value of a, one of them must work.
$endgroup$
– Dave
Jun 11 '17 at 22:29
$begingroup$
@Jens; Robert Israel is saying that while the approach you're suggesting is a valid strategy to find out if there is a solution or not, it is not in itself a proof either way. You could end up trying every single combination and find that none of them actually make a valid grid (though in this particular case, as Bram28 answered, it is in fact possible and therefore brute-force will indeed find a solution when applied). As a silly example of the negative, I could claim a boolean "a" exists such that "a = not a", with the "proof" that if I try every possible value of a, one of them must work.
$endgroup$
– Dave
Jun 11 '17 at 22:29
|
show 4 more comments
2 Answers
2
active
oldest
votes
$begingroup$
I wouldn't call what you say a proof ... It is not immediately clear from what you say that you will indeed get all possible pieces in there.
However, your hunch is correct: this puzzle is indeed solvable. Here is a proof:
Let's call the straight edge $1$, the concave edge $2$, and the convex edge $3$. Now, label the $10$ vertical edges in each row of your $9 times 9$ board with $1,1,2,3,1,3,3,2,2,1$ in that order. Note that if you look at two sucessive edges (so these would be the left and right edges of a piece), you get all possible pairings: $11,12,23,31,13,33,32,22,21$. Hence, pieces in the same column will have the same left and right edge, but pieces in different columns will have differen left/right pairings.
Ok, do the same with the horizontal edges from top to bottom. This will give you all possible pairings for top and bottom edges. So, since different rows have different top/bottom pairings, and since different columns will have different left/right pairings, you do indeed get all $81$ possible combinations, and thus all the $81$ different pieces in there.
Here is the resulting solved puzzle (thanks @Frxstrem !)
answered Jun 11 '17 at 21:03
Bram28Bram28
60.5k44590
$endgroup$
1
$begingroup$
I'm convinced. Thank you.
$endgroup$
– Jens
Jun 11 '17 at 21:13
3
$begingroup$
@Jens You're welcome! :) I was playing with those 1,2,3's for a while, and initally had a hard time (which is why it wasn't at all clear to me there had to be a solution) ... But then I found the right way to think about it, and just had to find a sequence with all possible pairings
$endgroup$
– Bram28
Jun 11 '17 at 21:16
8
$begingroup$
By the way, this is a de Bruijn sequence of order 2 on an alphabet of size 3.
$endgroup$
– Rahul
Jun 11 '17 at 23:01
9
$begingroup$
@Bram28 Here's an illustration of your solution, if you want to add it to your answer: imgur.com/a/H78uk
$endgroup$
– Frxstrem
Jun 12 '17 at 0:23
1
$begingroup$
Is this answer unique (up to reflections/rotations) or are there several options for coding each axis?
$endgroup$
– Neil_UK
Jun 12 '17 at 8:33
|
show 10 more comments
$begingroup$
This answer, complementing the excellent answer of @Bram28, explains the idea with line coloring. It is possible (see figure 1) to place 10 horizontal and 10 vertical lines using (R,G,B) colors in such a way that the $3^4=81$ different squares are present (for example, there is a unique square with North, West, South, East colored (G,B,R,R) resp.: this square is found in the South East corner). Check that the $3^4=81$ different squares are there (without duplicates).
Associate now colors to each side according to its aspect :
- R$to$"flat side",
- G$to$"convex side",
- B$to$"concave side".
This gives figure 2.
Remarks:
1) The color sequencing of lines and the color sequencing of columns have been deliberately chosen different. In fact there are 24 different color sequencements. Why that ? Identify the East and West side ; similarly, identify the North and South sides. In other words, consider our puzzle as drawn on a torus, so $9 times 9$ is the number of pieces and as well the number of lines. This number $9$ is, I would say by chance, a power $9=3^2$. We fall thus into the framework of de Bruijn sequences here of type $B(3,2)$. Such a sequence is made of $3^2$ "letters" (imagined arranged in a ring) such that, by sliding a window of width 2 on the sequence, one gets all the words on an alphabet of 3 items : R,G,B. An example : RRGGBBRBG where the window sliding will provide RR,RG,GG,GB,BB,BR,RB,BG and GR, all the words with 2 letters on an alphabet of 3 (please note that the last word, GR, has been obtained by wrapping the sequence). For more, see (https://en.wikipedia.org/wiki/De_Bruijn_sequence) where you will find a formula explaining showing that there are $6^3/3^2=24$ of them.
2) Out of a solution, one can generally build a big amount of other solutions. For example, in the case of the given figure, consider the two identical $1 times 4$ (or $1 times 5$, or $3 times 3$... !) rectangles in the South West and North East corners of the puzzle : another solution is provided by switching them.
Edit : (Feb 8 '18)
Related :
http://erikdemaine.org/papers/Jigsaw_GC/paper.pdf
What is known about this jigsaw combinatorics problem?
Somewhat related :
https://puzzling.stackexchange.com/a/48864
I found an old reference mentionning an analogous type of pieces (around page 69) in an old-fashioned delicious booklet entitled "New Mathematical Pastimes" by Major McMahon, Cambridge, 1921
(https://archive.org/details/newmathematicalp00macmuoft).
answered Jun 12 '17 at 0:32
Jean MarieJean Marie
28.9k41949
$endgroup$
1
$begingroup$
Cool, thanks!! Yes, that's a nice illustration :)
$endgroup$
– Bram28
Jun 12 '17 at 1:08
$begingroup$
Based on the OP's 1x81 and 3x27 proofs, I think that the intention is for all outside edges of the 9x9 puzzle to be straight. Your solution would fit that criteria if the top three rows were removed from the top to the bottom of the puzzle.
$endgroup$
– James
Jun 12 '17 at 17:03
$begingroup$
@James You are right. I am going to modify my example.
$endgroup$
– Jean Marie
Jun 12 '17 at 18:14
$begingroup$
While it's not triggering the flickering dots of the classic B&W version (halfway down), your colored grid of lines is throwing me for a mental loop. My subconscious is insisting that something should be going on there even though nothing's making its way up to my conscious sight.
$endgroup$
– Dan Neely
Jun 12 '17 at 18:21
$begingroup$
@Dan Neely I have modified my figures, but the effect should still be present. On the "subconscient" side, this set of 81 pieces could take place on a cylinder (by gluing the two vertical sides) or even a torus (by gluing as well the two horizontal sides).
$endgroup$
– Jean Marie
Jun 12 '17 at 18:37
|
show 2 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2318847%2fproving-a-jigsaw-is-possible%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I wouldn't call what you say a proof ... It is not immediately clear from what you say that you will indeed get all possible pieces in there.
However, your hunch is correct: this puzzle is indeed solvable. Here is a proof:
Let's call the straight edge $1$, the concave edge $2$, and the convex edge $3$. Now, label the $10$ vertical edges in each row of your $9 times 9$ board with $1,1,2,3,1,3,3,2,2,1$ in that order. Note that if you look at two sucessive edges (so these would be the left and right edges of a piece), you get all possible pairings: $11,12,23,31,13,33,32,22,21$. Hence, pieces in the same column will have the same left and right edge, but pieces in different columns will have differen left/right pairings.
Ok, do the same with the horizontal edges from top to bottom. This will give you all possible pairings for top and bottom edges. So, since different rows have different top/bottom pairings, and since different columns will have different left/right pairings, you do indeed get all $81$ possible combinations, and thus all the $81$ different pieces in there.
Here is the resulting solved puzzle (thanks @Frxstrem !)
answered Jun 11 '17 at 21:03
Bram28Bram28
60.5k44590
$endgroup$
1
$begingroup$
I'm convinced. Thank you.
$endgroup$
– Jens
Jun 11 '17 at 21:13
3
$begingroup$
@Jens You're welcome! :) I was playing with those 1,2,3's for a while, and initally had a hard time (which is why it wasn't at all clear to me there had to be a solution) ... But then I found the right way to think about it, and just had to find a sequence with all possible pairings
$endgroup$
– Bram28
Jun 11 '17 at 21:16
8
$begingroup$
By the way, this is a de Bruijn sequence of order 2 on an alphabet of size 3.
$endgroup$
– Rahul
Jun 11 '17 at 23:01
9
$begingroup$
@Bram28 Here's an illustration of your solution, if you want to add it to your answer: imgur.com/a/H78uk
$endgroup$
– Frxstrem
Jun 12 '17 at 0:23
1
$begingroup$
Is this answer unique (up to reflections/rotations) or are there several options for coding each axis?
$endgroup$
– Neil_UK
Jun 12 '17 at 8:33
|
show 10 more comments
$begingroup$
I wouldn't call what you say a proof ... It is not immediately clear from what you say that you will indeed get all possible pieces in there.
However, your hunch is correct: this puzzle is indeed solvable. Here is a proof:
Let's call the straight edge $1$, the concave edge $2$, and the convex edge $3$. Now, label the $10$ vertical edges in each row of your $9 times 9$ board with $1,1,2,3,1,3,3,2,2,1$ in that order. Note that if you look at two sucessive edges (so these would be the left and right edges of a piece), you get all possible pairings: $11,12,23,31,13,33,32,22,21$. Hence, pieces in the same column will have the same left and right edge, but pieces in different columns will have differen left/right pairings.
Ok, do the same with the horizontal edges from top to bottom. This will give you all possible pairings for top and bottom edges. So, since different rows have different top/bottom pairings, and since different columns will have different left/right pairings, you do indeed get all $81$ possible combinations, and thus all the $81$ different pieces in there.
Here is the resulting solved puzzle (thanks @Frxstrem !)
answered Jun 11 '17 at 21:03
Bram28Bram28
60.5k44590
$endgroup$
1
$begingroup$
I'm convinced. Thank you.
$endgroup$
– Jens
Jun 11 '17 at 21:13
3
$begingroup$
@Jens You're welcome! :) I was playing with those 1,2,3's for a while, and initally had a hard time (which is why it wasn't at all clear to me there had to be a solution) ... But then I found the right way to think about it, and just had to find a sequence with all possible pairings
$endgroup$
– Bram28
Jun 11 '17 at 21:16
8
$begingroup$
By the way, this is a de Bruijn sequence of order 2 on an alphabet of size 3.
$endgroup$
– Rahul
Jun 11 '17 at 23:01
9
$begingroup$
@Bram28 Here's an illustration of your solution, if you want to add it to your answer: imgur.com/a/H78uk
$endgroup$
– Frxstrem
Jun 12 '17 at 0:23
1
$begingroup$
Is this answer unique (up to reflections/rotations) or are there several options for coding each axis?
$endgroup$
– Neil_UK
Jun 12 '17 at 8:33
|
show 10 more comments
$begingroup$
I wouldn't call what you say a proof ... It is not immediately clear from what you say that you will indeed get all possible pieces in there.
However, your hunch is correct: this puzzle is indeed solvable. Here is a proof:
Let's call the straight edge $1$, the concave edge $2$, and the convex edge $3$. Now, label the $10$ vertical edges in each row of your $9 times 9$ board with $1,1,2,3,1,3,3,2,2,1$ in that order. Note that if you look at two sucessive edges (so these would be the left and right edges of a piece), you get all possible pairings: $11,12,23,31,13,33,32,22,21$. Hence, pieces in the same column will have the same left and right edge, but pieces in different columns will have differen left/right pairings.
Ok, do the same with the horizontal edges from top to bottom. This will give you all possible pairings for top and bottom edges. So, since different rows have different top/bottom pairings, and since different columns will have different left/right pairings, you do indeed get all $81$ possible combinations, and thus all the $81$ different pieces in there.
Here is the resulting solved puzzle (thanks @Frxstrem !)
answered Jun 11 '17 at 21:03
Bram28Bram28
60.5k44590
$endgroup$
I wouldn't call what you say a proof ... It is not immediately clear from what you say that you will indeed get all possible pieces in there.
However, your hunch is correct: this puzzle is indeed solvable. Here is a proof:
Let's call the straight edge $1$, the concave edge $2$, and the convex edge $3$. Now, label the $10$ vertical edges in each row of your $9 times 9$ board with $1,1,2,3,1,3,3,2,2,1$ in that order. Note that if you look at two sucessive edges (so these would be the left and right edges of a piece), you get all possible pairings: $11,12,23,31,13,33,32,22,21$. Hence, pieces in the same column will have the same left and right edge, but pieces in different columns will have differen left/right pairings.
Ok, do the same with the horizontal edges from top to bottom. This will give you all possible pairings for top and bottom edges. So, since different rows have different top/bottom pairings, and since different columns will have different left/right pairings, you do indeed get all $81$ possible combinations, and thus all the $81$ different pieces in there.
Here is the resulting solved puzzle (thanks @Frxstrem !)
answered Jun 11 '17 at 21:03
Bram28Bram28
60.5k44590
edited Jun 12 '17 at 16:35
answered Jun 11 '17 at 21:03
Bram28Bram28
60.5k44590
answered Jun 11 '17 at 21:03
Bram28Bram28
60.5k44590
answered Jun 11 '17 at 21:03
Bram28Bram28
60.5k44590
60.5k44590
1
$begingroup$
I'm convinced. Thank you.
$endgroup$
– Jens
Jun 11 '17 at 21:13
3
$begingroup$
@Jens You're welcome! :) I was playing with those 1,2,3's for a while, and initally had a hard time (which is why it wasn't at all clear to me there had to be a solution) ... But then I found the right way to think about it, and just had to find a sequence with all possible pairings
$endgroup$
– Bram28
Jun 11 '17 at 21:16
8
$begingroup$
By the way, this is a de Bruijn sequence of order 2 on an alphabet of size 3.
$endgroup$
– Rahul
Jun 11 '17 at 23:01
9
$begingroup$
@Bram28 Here's an illustration of your solution, if you want to add it to your answer: imgur.com/a/H78uk
$endgroup$
– Frxstrem
Jun 12 '17 at 0:23
1
$begingroup$
Is this answer unique (up to reflections/rotations) or are there several options for coding each axis?
$endgroup$
– Neil_UK
Jun 12 '17 at 8:33
|
show 10 more comments
1
$begingroup$
I'm convinced. Thank you.
$endgroup$
– Jens
Jun 11 '17 at 21:13
3
$begingroup$
@Jens You're welcome! :) I was playing with those 1,2,3's for a while, and initally had a hard time (which is why it wasn't at all clear to me there had to be a solution) ... But then I found the right way to think about it, and just had to find a sequence with all possible pairings
$endgroup$
– Bram28
Jun 11 '17 at 21:16
8
$begingroup$
By the way, this is a de Bruijn sequence of order 2 on an alphabet of size 3.
$endgroup$
– Rahul
Jun 11 '17 at 23:01
9
$begingroup$
@Bram28 Here's an illustration of your solution, if you want to add it to your answer: imgur.com/a/H78uk
$endgroup$
– Frxstrem
Jun 12 '17 at 0:23
1
$begingroup$
Is this answer unique (up to reflections/rotations) or are there several options for coding each axis?
$endgroup$
– Neil_UK
Jun 12 '17 at 8:33
1
1
$begingroup$
I'm convinced. Thank you.
$endgroup$
– Jens
Jun 11 '17 at 21:13
$begingroup$
I'm convinced. Thank you.
$endgroup$
– Jens
Jun 11 '17 at 21:13
3
3
$begingroup$
@Jens You're welcome! :) I was playing with those 1,2,3's for a while, and initally had a hard time (which is why it wasn't at all clear to me there had to be a solution) ... But then I found the right way to think about it, and just had to find a sequence with all possible pairings
$endgroup$
– Bram28
Jun 11 '17 at 21:16
$begingroup$
@Jens You're welcome! :) I was playing with those 1,2,3's for a while, and initally had a hard time (which is why it wasn't at all clear to me there had to be a solution) ... But then I found the right way to think about it, and just had to find a sequence with all possible pairings
$endgroup$
– Bram28
Jun 11 '17 at 21:16
8
8
$begingroup$
By the way, this is a de Bruijn sequence of order 2 on an alphabet of size 3.
$endgroup$
– Rahul
Jun 11 '17 at 23:01
$begingroup$
By the way, this is a de Bruijn sequence of order 2 on an alphabet of size 3.
$endgroup$
– Rahul
Jun 11 '17 at 23:01
9
9
$begingroup$
@Bram28 Here's an illustration of your solution, if you want to add it to your answer: imgur.com/a/H78uk
$endgroup$
– Frxstrem
Jun 12 '17 at 0:23
$begingroup$
@Bram28 Here's an illustration of your solution, if you want to add it to your answer: imgur.com/a/H78uk
$endgroup$
– Frxstrem
Jun 12 '17 at 0:23
1
1
$begingroup$
Is this answer unique (up to reflections/rotations) or are there several options for coding each axis?
$endgroup$
– Neil_UK
Jun 12 '17 at 8:33
$begingroup$
Is this answer unique (up to reflections/rotations) or are there several options for coding each axis?
$endgroup$
– Neil_UK
Jun 12 '17 at 8:33
|
show 10 more comments
$begingroup$
This answer, complementing the excellent answer of @Bram28, explains the idea with line coloring. It is possible (see figure 1) to place 10 horizontal and 10 vertical lines using (R,G,B) colors in such a way that the $3^4=81$ different squares are present (for example, there is a unique square with North, West, South, East colored (G,B,R,R) resp.: this square is found in the South East corner). Check that the $3^4=81$ different squares are there (without duplicates).
Associate now colors to each side according to its aspect :
- R$to$"flat side",
- G$to$"convex side",
- B$to$"concave side".
This gives figure 2.
Remarks:
1) The color sequencing of lines and the color sequencing of columns have been deliberately chosen different. In fact there are 24 different color sequencements. Why that ? Identify the East and West side ; similarly, identify the North and South sides. In other words, consider our puzzle as drawn on a torus, so $9 times 9$ is the number of pieces and as well the number of lines. This number $9$ is, I would say by chance, a power $9=3^2$. We fall thus into the framework of de Bruijn sequences here of type $B(3,2)$. Such a sequence is made of $3^2$ "letters" (imagined arranged in a ring) such that, by sliding a window of width 2 on the sequence, one gets all the words on an alphabet of 3 items : R,G,B. An example : RRGGBBRBG where the window sliding will provide RR,RG,GG,GB,BB,BR,RB,BG and GR, all the words with 2 letters on an alphabet of 3 (please note that the last word, GR, has been obtained by wrapping the sequence). For more, see (https://en.wikipedia.org/wiki/De_Bruijn_sequence) where you will find a formula explaining showing that there are $6^3/3^2=24$ of them.
2) Out of a solution, one can generally build a big amount of other solutions. For example, in the case of the given figure, consider the two identical $1 times 4$ (or $1 times 5$, or $3 times 3$... !) rectangles in the South West and North East corners of the puzzle : another solution is provided by switching them.
Edit : (Feb 8 '18)
Related :
http://erikdemaine.org/papers/Jigsaw_GC/paper.pdf
What is known about this jigsaw combinatorics problem?
Somewhat related :
https://puzzling.stackexchange.com/a/48864
I found an old reference mentionning an analogous type of pieces (around page 69) in an old-fashioned delicious booklet entitled "New Mathematical Pastimes" by Major McMahon, Cambridge, 1921
(https://archive.org/details/newmathematicalp00macmuoft).
answered Jun 12 '17 at 0:32
Jean MarieJean Marie
28.9k41949
$endgroup$
1
$begingroup$
Cool, thanks!! Yes, that's a nice illustration :)
$endgroup$
– Bram28
Jun 12 '17 at 1:08
$begingroup$
Based on the OP's 1x81 and 3x27 proofs, I think that the intention is for all outside edges of the 9x9 puzzle to be straight. Your solution would fit that criteria if the top three rows were removed from the top to the bottom of the puzzle.
$endgroup$
– James
Jun 12 '17 at 17:03
$begingroup$
@James You are right. I am going to modify my example.
$endgroup$
– Jean Marie
Jun 12 '17 at 18:14
$begingroup$
While it's not triggering the flickering dots of the classic B&W version (halfway down), your colored grid of lines is throwing me for a mental loop. My subconscious is insisting that something should be going on there even though nothing's making its way up to my conscious sight.
$endgroup$
– Dan Neely
Jun 12 '17 at 18:21
$begingroup$
@Dan Neely I have modified my figures, but the effect should still be present. On the "subconscient" side, this set of 81 pieces could take place on a cylinder (by gluing the two vertical sides) or even a torus (by gluing as well the two horizontal sides).
$endgroup$
– Jean Marie
Jun 12 '17 at 18:37
|
show 2 more comments
$begingroup$
This answer, complementing the excellent answer of @Bram28, explains the idea with line coloring. It is possible (see figure 1) to place 10 horizontal and 10 vertical lines using (R,G,B) colors in such a way that the $3^4=81$ different squares are present (for example, there is a unique square with North, West, South, East colored (G,B,R,R) resp.: this square is found in the South East corner). Check that the $3^4=81$ different squares are there (without duplicates).
Associate now colors to each side according to its aspect :
- R$to$"flat side",
- G$to$"convex side",
- B$to$"concave side".
This gives figure 2.
Remarks:
1) The color sequencing of lines and the color sequencing of columns have been deliberately chosen different. In fact there are 24 different color sequencements. Why that ? Identify the East and West side ; similarly, identify the North and South sides. In other words, consider our puzzle as drawn on a torus, so $9 times 9$ is the number of pieces and as well the number of lines. This number $9$ is, I would say by chance, a power $9=3^2$. We fall thus into the framework of de Bruijn sequences here of type $B(3,2)$. Such a sequence is made of $3^2$ "letters" (imagined arranged in a ring) such that, by sliding a window of width 2 on the sequence, one gets all the words on an alphabet of 3 items : R,G,B. An example : RRGGBBRBG where the window sliding will provide RR,RG,GG,GB,BB,BR,RB,BG and GR, all the words with 2 letters on an alphabet of 3 (please note that the last word, GR, has been obtained by wrapping the sequence). For more, see (https://en.wikipedia.org/wiki/De_Bruijn_sequence) where you will find a formula explaining showing that there are $6^3/3^2=24$ of them.
2) Out of a solution, one can generally build a big amount of other solutions. For example, in the case of the given figure, consider the two identical $1 times 4$ (or $1 times 5$, or $3 times 3$... !) rectangles in the South West and North East corners of the puzzle : another solution is provided by switching them.
Edit : (Feb 8 '18)
Related :
http://erikdemaine.org/papers/Jigsaw_GC/paper.pdf
What is known about this jigsaw combinatorics problem?
Somewhat related :
https://puzzling.stackexchange.com/a/48864
I found an old reference mentionning an analogous type of pieces (around page 69) in an old-fashioned delicious booklet entitled "New Mathematical Pastimes" by Major McMahon, Cambridge, 1921
(https://archive.org/details/newmathematicalp00macmuoft).
answered Jun 12 '17 at 0:32
Jean MarieJean Marie
28.9k41949
$endgroup$
1
$begingroup$
Cool, thanks!! Yes, that's a nice illustration :)
$endgroup$
– Bram28
Jun 12 '17 at 1:08
$begingroup$
Based on the OP's 1x81 and 3x27 proofs, I think that the intention is for all outside edges of the 9x9 puzzle to be straight. Your solution would fit that criteria if the top three rows were removed from the top to the bottom of the puzzle.
$endgroup$
– James
Jun 12 '17 at 17:03
$begingroup$
@James You are right. I am going to modify my example.
$endgroup$
– Jean Marie
Jun 12 '17 at 18:14
$begingroup$
While it's not triggering the flickering dots of the classic B&W version (halfway down), your colored grid of lines is throwing me for a mental loop. My subconscious is insisting that something should be going on there even though nothing's making its way up to my conscious sight.
$endgroup$
– Dan Neely
Jun 12 '17 at 18:21
$begingroup$
@Dan Neely I have modified my figures, but the effect should still be present. On the "subconscient" side, this set of 81 pieces could take place on a cylinder (by gluing the two vertical sides) or even a torus (by gluing as well the two horizontal sides).
$endgroup$
– Jean Marie
Jun 12 '17 at 18:37
|
show 2 more comments
$begingroup$
This answer, complementing the excellent answer of @Bram28, explains the idea with line coloring. It is possible (see figure 1) to place 10 horizontal and 10 vertical lines using (R,G,B) colors in such a way that the $3^4=81$ different squares are present (for example, there is a unique square with North, West, South, East colored (G,B,R,R) resp.: this square is found in the South East corner). Check that the $3^4=81$ different squares are there (without duplicates).
Associate now colors to each side according to its aspect :
- R$to$"flat side",
- G$to$"convex side",
- B$to$"concave side".
This gives figure 2.
Remarks:
1) The color sequencing of lines and the color sequencing of columns have been deliberately chosen different. In fact there are 24 different color sequencements. Why that ? Identify the East and West side ; similarly, identify the North and South sides. In other words, consider our puzzle as drawn on a torus, so $9 times 9$ is the number of pieces and as well the number of lines. This number $9$ is, I would say by chance, a power $9=3^2$. We fall thus into the framework of de Bruijn sequences here of type $B(3,2)$. Such a sequence is made of $3^2$ "letters" (imagined arranged in a ring) such that, by sliding a window of width 2 on the sequence, one gets all the words on an alphabet of 3 items : R,G,B. An example : RRGGBBRBG where the window sliding will provide RR,RG,GG,GB,BB,BR,RB,BG and GR, all the words with 2 letters on an alphabet of 3 (please note that the last word, GR, has been obtained by wrapping the sequence). For more, see (https://en.wikipedia.org/wiki/De_Bruijn_sequence) where you will find a formula explaining showing that there are $6^3/3^2=24$ of them.
2) Out of a solution, one can generally build a big amount of other solutions. For example, in the case of the given figure, consider the two identical $1 times 4$ (or $1 times 5$, or $3 times 3$... !) rectangles in the South West and North East corners of the puzzle : another solution is provided by switching them.
Edit : (Feb 8 '18)
Related :
http://erikdemaine.org/papers/Jigsaw_GC/paper.pdf
What is known about this jigsaw combinatorics problem?
Somewhat related :
https://puzzling.stackexchange.com/a/48864
I found an old reference mentionning an analogous type of pieces (around page 69) in an old-fashioned delicious booklet entitled "New Mathematical Pastimes" by Major McMahon, Cambridge, 1921
(https://archive.org/details/newmathematicalp00macmuoft).
answered Jun 12 '17 at 0:32
Jean MarieJean Marie
28.9k41949
$endgroup$
This answer, complementing the excellent answer of @Bram28, explains the idea with line coloring. It is possible (see figure 1) to place 10 horizontal and 10 vertical lines using (R,G,B) colors in such a way that the $3^4=81$ different squares are present (for example, there is a unique square with North, West, South, East colored (G,B,R,R) resp.: this square is found in the South East corner). Check that the $3^4=81$ different squares are there (without duplicates).
Associate now colors to each side according to its aspect :
- R$to$"flat side",
- G$to$"convex side",
- B$to$"concave side".
This gives figure 2.
Remarks:
1) The color sequencing of lines and the color sequencing of columns have been deliberately chosen different. In fact there are 24 different color sequencements. Why that ? Identify the East and West side ; similarly, identify the North and South sides. In other words, consider our puzzle as drawn on a torus, so $9 times 9$ is the number of pieces and as well the number of lines. This number $9$ is, I would say by chance, a power $9=3^2$. We fall thus into the framework of de Bruijn sequences here of type $B(3,2)$. Such a sequence is made of $3^2$ "letters" (imagined arranged in a ring) such that, by sliding a window of width 2 on the sequence, one gets all the words on an alphabet of 3 items : R,G,B. An example : RRGGBBRBG where the window sliding will provide RR,RG,GG,GB,BB,BR,RB,BG and GR, all the words with 2 letters on an alphabet of 3 (please note that the last word, GR, has been obtained by wrapping the sequence). For more, see (https://en.wikipedia.org/wiki/De_Bruijn_sequence) where you will find a formula explaining showing that there are $6^3/3^2=24$ of them.
2) Out of a solution, one can generally build a big amount of other solutions. For example, in the case of the given figure, consider the two identical $1 times 4$ (or $1 times 5$, or $3 times 3$... !) rectangles in the South West and North East corners of the puzzle : another solution is provided by switching them.
Edit : (Feb 8 '18)
Related :
http://erikdemaine.org/papers/Jigsaw_GC/paper.pdf
What is known about this jigsaw combinatorics problem?
Somewhat related :
https://puzzling.stackexchange.com/a/48864
I found an old reference mentionning an analogous type of pieces (around page 69) in an old-fashioned delicious booklet entitled "New Mathematical Pastimes" by Major McMahon, Cambridge, 1921
(https://archive.org/details/newmathematicalp00macmuoft).
answered Jun 12 '17 at 0:32
Jean MarieJean Marie
28.9k41949
edited Dec 13 '18 at 20:44
answered Jun 12 '17 at 0:32
Jean MarieJean Marie
28.9k41949
answered Jun 12 '17 at 0:32
Jean MarieJean Marie
28.9k41949
answered Jun 12 '17 at 0:32
Jean MarieJean Marie
28.9k41949
28.9k41949
1
$begingroup$
Cool, thanks!! Yes, that's a nice illustration :)
$endgroup$
– Bram28
Jun 12 '17 at 1:08
$begingroup$
Based on the OP's 1x81 and 3x27 proofs, I think that the intention is for all outside edges of the 9x9 puzzle to be straight. Your solution would fit that criteria if the top three rows were removed from the top to the bottom of the puzzle.
$endgroup$
– James
Jun 12 '17 at 17:03
$begingroup$
@James You are right. I am going to modify my example.
$endgroup$
– Jean Marie
Jun 12 '17 at 18:14
$begingroup$
While it's not triggering the flickering dots of the classic B&W version (halfway down), your colored grid of lines is throwing me for a mental loop. My subconscious is insisting that something should be going on there even though nothing's making its way up to my conscious sight.
$endgroup$
– Dan Neely
Jun 12 '17 at 18:21
$begingroup$
@Dan Neely I have modified my figures, but the effect should still be present. On the "subconscient" side, this set of 81 pieces could take place on a cylinder (by gluing the two vertical sides) or even a torus (by gluing as well the two horizontal sides).
$endgroup$
– Jean Marie
Jun 12 '17 at 18:37
|
show 2 more comments
1
$begingroup$
Cool, thanks!! Yes, that's a nice illustration :)
$endgroup$
– Bram28
Jun 12 '17 at 1:08
$begingroup$
Based on the OP's 1x81 and 3x27 proofs, I think that the intention is for all outside edges of the 9x9 puzzle to be straight. Your solution would fit that criteria if the top three rows were removed from the top to the bottom of the puzzle.
$endgroup$
– James
Jun 12 '17 at 17:03
$begingroup$
@James You are right. I am going to modify my example.
$endgroup$
– Jean Marie
Jun 12 '17 at 18:14
$begingroup$
While it's not triggering the flickering dots of the classic B&W version (halfway down), your colored grid of lines is throwing me for a mental loop. My subconscious is insisting that something should be going on there even though nothing's making its way up to my conscious sight.
$endgroup$
– Dan Neely
Jun 12 '17 at 18:21
$begingroup$
@Dan Neely I have modified my figures, but the effect should still be present. On the "subconscient" side, this set of 81 pieces could take place on a cylinder (by gluing the two vertical sides) or even a torus (by gluing as well the two horizontal sides).
$endgroup$
– Jean Marie
Jun 12 '17 at 18:37
1
1
$begingroup$
Cool, thanks!! Yes, that's a nice illustration :)
$endgroup$
– Bram28
Jun 12 '17 at 1:08
$begingroup$
Cool, thanks!! Yes, that's a nice illustration :)
$endgroup$
– Bram28
Jun 12 '17 at 1:08
$begingroup$
Based on the OP's 1x81 and 3x27 proofs, I think that the intention is for all outside edges of the 9x9 puzzle to be straight. Your solution would fit that criteria if the top three rows were removed from the top to the bottom of the puzzle.
$endgroup$
– James
Jun 12 '17 at 17:03
$begingroup$
Based on the OP's 1x81 and 3x27 proofs, I think that the intention is for all outside edges of the 9x9 puzzle to be straight. Your solution would fit that criteria if the top three rows were removed from the top to the bottom of the puzzle.
$endgroup$
– James
Jun 12 '17 at 17:03
$begingroup$
@James You are right. I am going to modify my example.
$endgroup$
– Jean Marie
Jun 12 '17 at 18:14
$begingroup$
@James You are right. I am going to modify my example.
$endgroup$
– Jean Marie
Jun 12 '17 at 18:14
$begingroup$
While it's not triggering the flickering dots of the classic B&W version (halfway down), your colored grid of lines is throwing me for a mental loop. My subconscious is insisting that something should be going on there even though nothing's making its way up to my conscious sight.
$endgroup$
– Dan Neely
Jun 12 '17 at 18:21
$begingroup$
While it's not triggering the flickering dots of the classic B&W version (halfway down), your colored grid of lines is throwing me for a mental loop. My subconscious is insisting that something should be going on there even though nothing's making its way up to my conscious sight.
$endgroup$
– Dan Neely
Jun 12 '17 at 18:21
$begingroup$
@Dan Neely I have modified my figures, but the effect should still be present. On the "subconscient" side, this set of 81 pieces could take place on a cylinder (by gluing the two vertical sides) or even a torus (by gluing as well the two horizontal sides).
$endgroup$
– Jean Marie
Jun 12 '17 at 18:37
$begingroup$
@Dan Neely I have modified my figures, but the effect should still be present. On the "subconscient" side, this set of 81 pieces could take place on a cylinder (by gluing the two vertical sides) or even a torus (by gluing as well the two horizontal sides).
$endgroup$
– Jean Marie
Jun 12 '17 at 18:37
|
show 2 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2318847%2fproving-a-jigsaw-is-possible%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
"if we run through every possible connection type for each piece" - I'm not sure I understand what you mean. What about the piece with all straight sides, the one with all concave sides, and the one with all convex sides? Could you clarify your statement?
$endgroup$
– Michael Lee
Jun 11 '17 at 19:31
8
$begingroup$
What you're describing sounds like a brute-force method of generating a solution if one exists, but definitely not a proof of existence.
$endgroup$
– Michael Lee
Jun 11 '17 at 19:34
5
$begingroup$
If there is such a solution, you'll find it. If there isn't, you won't. I see no reason to rule out either possibility.
$endgroup$
– Robert Israel
Jun 11 '17 at 19:49
6
$begingroup$
It won't if there isn't a solution.
$endgroup$
– Robert Israel
Jun 11 '17 at 20:11
5
$begingroup$
@Jens; Robert Israel is saying that while the approach you're suggesting is a valid strategy to find out if there is a solution or not, it is not in itself a proof either way. You could end up trying every single combination and find that none of them actually make a valid grid (though in this particular case, as Bram28 answered, it is in fact possible and therefore brute-force will indeed find a solution when applied). As a silly example of the negative, I could claim a boolean "a" exists such that "a = not a", with the "proof" that if I try every possible value of a, one of them must work.
$endgroup$
– Dave
Jun 11 '17 at 22:29