Find a specific path on an n x n grid [duplicate]
$begingroup$
This question already has an answer here:
Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
1 answer
Can the rook pass every square just once?
1 answer
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 yesterday
JonMark Perry
18.5k63888
asked yesterday
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$
marked as duplicate by Rand al'Thor, Alconja, deep thought, Rupert Morrish, Glorfindel yesterday
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
1 answer
Can the rook pass every square just once?
1 answer
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 yesterday
JonMark Perry
18.5k63888
asked yesterday
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$
marked as duplicate by Rand al'Thor, Alconja, deep thought, Rupert Morrish, Glorfindel yesterday
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
yesterday
$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
yesterday
1
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
yesterday
add a comment |
$begingroup$
This question already has an answer here:
Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
1 answer
Can the rook pass every square just once?
1 answer
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 yesterday
JonMark Perry
18.5k63888
asked yesterday
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$
This question already has an answer here:
Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
1 answer
Can the rook pass every square just once?
1 answer
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?)
This question already has an answer here:
Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph
1 answer
Can the rook pass every square just once?
1 answer
mathematics combinatorics
mathematics combinatorics
edited yesterday
JonMark Perry
18.5k63888
asked yesterday
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 yesterday
JonMark Perry
18.5k63888
asked yesterday
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 yesterday
JonMark Perry
18.5k63888
edited yesterday
JonMark Perry
18.5k63888
edited yesterday
JonMark Perry
18.5k63888
18.5k63888
asked yesterday
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 yesterday
Danny YaroslavskiDanny Yaroslavski
1183
asked yesterday
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.
marked as duplicate by Rand al'Thor, Alconja, deep thought, Rupert Morrish, Glorfindel yesterday
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Rand al'Thor, Alconja, deep thought, Rupert Morrish, Glorfindel yesterday
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
yesterday
$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
yesterday
1
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
yesterday
add a comment |
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
yesterday
$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
yesterday
1
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
yesterday
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
yesterday
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
yesterday
$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
yesterday
$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
yesterday
1
1
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
yesterday
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
yesterday
add a comment |
1 Answer
1
active
oldest
votes
$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 yesterday
JonMark PerryJonMark Perry
18.5k63888
$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
yesterday
$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
yesterday
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
yesterday
$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
yesterday
$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
yesterday
|
show 2 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 yesterday
JonMark PerryJonMark Perry
18.5k63888
$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
yesterday
$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
yesterday
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
yesterday
$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
yesterday
$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
yesterday
|
show 2 more comments
$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 yesterday
JonMark PerryJonMark Perry
18.5k63888
$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
yesterday
$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
yesterday
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
yesterday
$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
yesterday
$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
yesterday
|
show 2 more comments
$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 yesterday
JonMark PerryJonMark Perry
18.5k63888
$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 yesterday
JonMark PerryJonMark Perry
18.5k63888
answered yesterday
JonMark PerryJonMark Perry
18.5k63888
answered yesterday
JonMark PerryJonMark Perry
18.5k63888
answered yesterday
JonMark PerryJonMark Perry
18.5k63888
18.5k63888
$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
yesterday
$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
yesterday
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
yesterday
$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
yesterday
$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
yesterday
|
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
yesterday
$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
yesterday
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
yesterday
$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
yesterday
$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
yesterday
$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
yesterday
$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
yesterday
$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
yesterday
$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
yesterday
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
yesterday
$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
yesterday
$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
yesterday
$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
yesterday
$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
yesterday
$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
yesterday
|
show 2 more comments
$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
yesterday
$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
yesterday
1
$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
yesterday