Find a specific path on an n x n grid
3
$begingroup$
Given a puzzle of the following form:
Find a path between the top left corner to the bottom right corner, visiting each spot (.) exactly once. You can only move horizontally or vertically.
x . .
. . .
. . x
For a 3 x 3 grid, this yields two solutions:
x--.--.
|
.--.--.
|
.--.--x
x .--.
| | |
. . .
| | |
.--. x
There are mul olutions for a 5x5 grid, 7x7, and so on.
But for a 2x2, 4x4, 6x6, and higher n x n (where n is even), this does not seem to yield any solution.
How would you prove that this is the case? That there is no solution for n x n grids where n is even? (Is this even true?)
mathematics combinatorics
edited 3 mins ago
JonMark Perry
18.4k63888
asked 7 hours ago
Danny YaroslavskiDanny Yaroslavski
1183
New contributor
Danny Yaroslavski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
3
$begingroup$
Given a puzzle of the following form:
Find a path between the top left corner to the bottom right corner, visiting each spot (.) exactly once. You can only move horizontally or vertically.
x . .
. . .
. . x
For a 3 x 3 grid, this yields two solutions:
x--.--.
|
.--.--.
|
.--.--x
x .--.
| | |
. . .
| | |
.--. x
There are mul olutions for a 5x5 grid, 7x7, and so on.
But for a 2x2, 4x4, 6x6, and higher n x n (where n is even), this does not seem to yield any solution.
How would you prove that this is the case? That there is no solution for n x n grids where n is even? (Is this even true?)
mathematics combinatorics
edited 3 mins ago
JonMark Perry
18.4k63888
asked 7 hours ago
Danny YaroslavskiDanny Yaroslavski
1183
New contributor
Danny Yaroslavski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
7 hours ago
$begingroup$
Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
$endgroup$
– Danny Yaroslavski
7 hours ago
1
$begingroup$
Possible duplicate of Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
$endgroup$
– Rand al'Thor
6 hours ago
1
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
5 hours ago
add a comment |
3
3
3
$begingroup$
Given a puzzle of the following form:
Find a path between the top left corner to the bottom right corner, visiting each spot (.) exactly once. You can only move horizontally or vertically.
x . .
. . .
. . x
For a 3 x 3 grid, this yields two solutions:
x--.--.
|
.--.--.
|
.--.--x
x .--.
| | |
. . .
| | |
.--. x
There are mul olutions for a 5x5 grid, 7x7, and so on.
But for a 2x2, 4x4, 6x6, and higher n x n (where n is even), this does not seem to yield any solution.
How would you prove that this is the case? That there is no solution for n x n grids where n is even? (Is this even true?)
mathematics combinatorics
edited 3 mins ago
JonMark Perry
18.4k63888
asked 7 hours ago
Danny YaroslavskiDanny Yaroslavski
1183
New contributor
Danny Yaroslavski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Given a puzzle of the following form:
Find a path between the top left corner to the bottom right corner, visiting each spot (.) exactly once. You can only move horizontally or vertically.
x . .
. . .
. . x
For a 3 x 3 grid, this yields two solutions:
x--.--.
|
.--.--.
|
.--.--x
x .--.
| | |
. . .
| | |
.--. x
There are mul olutions for a 5x5 grid, 7x7, and so on.
But for a 2x2, 4x4, 6x6, and higher n x n (where n is even), this does not seem to yield any solution.
How would you prove that this is the case? That there is no solution for n x n grids where n is even? (Is this even true?)
mathematics combinatorics
mathematics combinatorics
edited 3 mins ago
JonMark Perry
18.4k63888
asked 7 hours ago
Danny YaroslavskiDanny Yaroslavski
1183
New contributor
Danny Yaroslavski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 3 mins ago
JonMark Perry
18.4k63888
asked 7 hours ago
Danny YaroslavskiDanny Yaroslavski
1183
New contributor
Danny Yaroslavski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 3 mins ago
JonMark Perry
18.4k63888
edited 3 mins ago
JonMark Perry
18.4k63888
edited 3 mins ago
JonMark Perry
18.4k63888
18.4k63888
asked 7 hours ago
Danny YaroslavskiDanny Yaroslavski
1183
New contributor
Danny Yaroslavski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 7 hours ago
Danny YaroslavskiDanny Yaroslavski
1183
asked 7 hours ago
Danny YaroslavskiDanny Yaroslavski
1183
1183
New contributor
Danny Yaroslavski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Danny Yaroslavski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Danny Yaroslavski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
7 hours ago
$begingroup$
Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
$endgroup$
– Danny Yaroslavski
7 hours ago
1
$begingroup$
Possible duplicate of Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
$endgroup$
– Rand al'Thor
6 hours ago
1
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
5 hours ago
add a comment |
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
7 hours ago
$begingroup$
Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
$endgroup$
– Danny Yaroslavski
7 hours ago
1
$begingroup$
Possible duplicate of Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
$endgroup$
– Rand al'Thor
6 hours ago
1
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
5 hours ago
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
7 hours ago
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
7 hours ago
$begingroup$
Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
$endgroup$
– Danny Yaroslavski
7 hours ago
1
1
$begingroup$
Possible duplicate of Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
$endgroup$
– Rand al'Thor
6 hours ago
$begingroup$
Possible duplicate of Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
$endgroup$
– Rand al'Thor
6 hours ago
1
1
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
5 hours ago
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
5 hours ago
add a comment |
1 Answer
1
active
oldest
votes
5
$begingroup$
Imagine the grid as a chessboard. Then for a $2ktimes2k$ board, the two corners are the same colour, say white. Any path must travel $WBWBdots WBW$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.
answered 7 hours ago
JonMark PerryJonMark Perry
18.4k63888
$endgroup$
$begingroup$
Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
7 hours ago
$begingroup$
Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
$endgroup$
– JonMark Perry
7 hours ago
|
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: "559"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
});
}
});
Danny Yaroslavski is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
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%2fpuzzling.stackexchange.com%2fquestions%2f78767%2ffind-a-specific-path-on-an-n-x-n-grid%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
5
$begingroup$
Imagine the grid as a chessboard. Then for a $2ktimes2k$ board, the two corners are the same colour, say white. Any path must travel $WBWBdots WBW$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.
answered 7 hours ago
JonMark PerryJonMark Perry
18.4k63888
$endgroup$
$begingroup$
Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
7 hours ago
$begingroup$
Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
$endgroup$
– JonMark Perry
7 hours ago
|
show 2 more comments
5
$begingroup$
Imagine the grid as a chessboard. Then for a $2ktimes2k$ board, the two corners are the same colour, say white. Any path must travel $WBWBdots WBW$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.
answered 7 hours ago
JonMark PerryJonMark Perry
18.4k63888
$endgroup$
$begingroup$
Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
7 hours ago
$begingroup$
Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
$endgroup$
– JonMark Perry
7 hours ago
|
show 2 more comments
5
5
5
$begingroup$
Imagine the grid as a chessboard. Then for a $2ktimes2k$ board, the two corners are the same colour, say white. Any path must travel $WBWBdots WBW$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.
answered 7 hours ago
JonMark PerryJonMark Perry
18.4k63888
$endgroup$
Imagine the grid as a chessboard. Then for a $2ktimes2k$ board, the two corners are the same colour, say white. Any path must travel $WBWBdots WBW$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.
answered 7 hours ago
JonMark PerryJonMark Perry
18.4k63888
answered 7 hours ago
JonMark PerryJonMark Perry
18.4k63888
answered 7 hours ago
JonMark PerryJonMark Perry
18.4k63888
answered 7 hours ago
JonMark PerryJonMark Perry
18.4k63888
18.4k63888
$begingroup$
Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
7 hours ago
$begingroup$
Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
$endgroup$
– JonMark Perry
7 hours ago
|
show 2 more comments
$begingroup$
Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
7 hours ago
$begingroup$
Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
$endgroup$
– JonMark Perry
7 hours ago
$begingroup$
Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
7 hours ago
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
7 hours ago
$begingroup$
Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
$endgroup$
– Danny Yaroslavski
7 hours ago
$begingroup$
I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
$endgroup$
– JonMark Perry
7 hours ago
$begingroup$
I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
$endgroup$
– JonMark Perry
7 hours ago
|
show 2 more comments
Danny Yaroslavski is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Danny Yaroslavski is a new contributor. Be nice, and check out our Code of Conduct.
Danny Yaroslavski is a new contributor. Be nice, and check out our Code of Conduct.
Danny Yaroslavski is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Puzzling 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.
draft saved
draft discarded
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%2fpuzzling.stackexchange.com%2fquestions%2f78767%2ffind-a-specific-path-on-an-n-x-n-grid%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
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
7 hours ago
$begingroup$
Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
$endgroup$
– Danny Yaroslavski
7 hours ago
1
$begingroup$
Possible duplicate of Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
$endgroup$
– Rand al'Thor
6 hours ago
1
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
5 hours ago