Grid puzzle solutionsIntroducing: Number Slope™HAISU (Room Count): An original grid-logic challengeA Six-Faced PuzzleMaking a grid deduction puzzleLogic 5x5 Letter Number Combination GridBullet Drop™ #1HAISU with a twistOriental HAISU - An unoriginal grid-deduction challengeModified Intersection PuzzleYou Sign Me Right Round
Does KNN have a loss function?
How do people drown while wearing a life jacket?
Why did the United States not resort to nuclear weapons in Vietnam?
If I buy and download a game through second Nintendo account do I own it on my main account too?
The grades of the students in a class
Reasons for using monsters as bioweapons
Could flaps be raised upward to serve as spoilers / lift dumpers?
Being told my "network" isn't PCI Complaint. I don't even have a server! Do I have to comply?
Applying for mortgage when living together but only one will be on the mortgage
How do I solve such questions on paramagnetism and ferromagnetism?
Can it be useful for a player block with a hanging piece in a back rank mate situation?
Traveling from New York city to Starkville Mississippi with public transport
Return last number in sub-sequences in a list of integers
Python π = 1 + (1/2) + (1/3) + (1/4) - (1/5) + (1/6) + (1/7) + (1/8) + (1/9) - (1/10) ...1748 Euler
Basic transistor circuit
Should 2FA be enabled on service accounts?
speaker impedence
Adding a (stair/baby) gate without facing walls
Were there any unmanned expeditions to the moon that returned to Earth prior to Apollo?
Can birds evolve without trees?
Why do player start with fighting for the corners in go?
What is the difference between "logical equivalence" and "material equivalence"?
Backpacking with incontinence
What is the most 'environmentally friendly' way to learn to fly?
Grid puzzle solutions
Introducing: Number Slope™HAISU (Room Count): An original grid-logic challengeA Six-Faced PuzzleMaking a grid deduction puzzleLogic 5x5 Letter Number Combination GridBullet Drop™ #1HAISU with a twistOriental HAISU - An unoriginal grid-deduction challengeModified Intersection PuzzleYou Sign Me Right Round
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
I have a simple grid puzzle:
Example:
| X | Y | X |
| Y | X | Y |
| Y | X | Y |
The move is defined as a row or a column move. So when you move one cell, whole column/row moves.
Example top row right 2 steps:
1 step
| X | X | Y |
| Y | X | Y |
| Y | X | Y |
2 step
| Y | X | X |
| Y | X | Y |
| Y | X | Y |
Now column move will look like this on the last row move up
1 step
| Y | X | Y |
| Y | X | Y |
| Y | X | X |
and so MoveRight - the most right cell will become the most left cell etc...
I am wondering if it is possible to go to every possible grid combination only with this moves. Let's assume that the grid will be 3x3 but it can be any size.
So, for example, I create random grid 3x3 with the same X count and Y count like this:
| Y | Y | Y |
| Y | Y | X |
| X | X | X |
Is it possible to check if there is a solution on how to make this grid the first grid with already specified moves? Or how to approach this problem?
Thanks, everyone.
grid-deduction
edited Jul 23 at 20:17
Nautilus
4,3206 silver badges26 bronze badges
asked Jul 23 at 19:46
Jakub GabčoJakub Gabčo
433 bronze badges
$endgroup$
add a comment |
$begingroup$
I have a simple grid puzzle:
Example:
| X | Y | X |
| Y | X | Y |
| Y | X | Y |
The move is defined as a row or a column move. So when you move one cell, whole column/row moves.
Example top row right 2 steps:
1 step
| X | X | Y |
| Y | X | Y |
| Y | X | Y |
2 step
| Y | X | X |
| Y | X | Y |
| Y | X | Y |
Now column move will look like this on the last row move up
1 step
| Y | X | Y |
| Y | X | Y |
| Y | X | X |
and so MoveRight - the most right cell will become the most left cell etc...
I am wondering if it is possible to go to every possible grid combination only with this moves. Let's assume that the grid will be 3x3 but it can be any size.
So, for example, I create random grid 3x3 with the same X count and Y count like this:
| Y | Y | Y |
| Y | Y | X |
| X | X | X |
Is it possible to check if there is a solution on how to make this grid the first grid with already specified moves? Or how to approach this problem?
Thanks, everyone.
grid-deduction
edited Jul 23 at 20:17
Nautilus
4,3206 silver badges26 bronze badges
asked Jul 23 at 19:46
Jakub GabčoJakub Gabčo
433 bronze badges
$endgroup$
$begingroup$
Are we guaranteed that it will be a 3x3 grid and only two values (X and Y)? With such a small grid, you can just brute force the solution by generating every possible configuration
$endgroup$
– Parseltongue
Jul 23 at 20:24
$begingroup$
@Parseltongue No, this is just an example. It can even have every cell other char and the size can be bigger. I am currently building a playable solution to try that, but I want to know more non-brute force method.
$endgroup$
– Jakub Gabčo
Jul 23 at 20:33
$begingroup$
Here's a 4x4 one from Simon Tatham's Portable Puzzle Collection, but you can change the size from the drop down. chiark.greenend.org.uk/~sgtatham/puzzles/js/sixteen.html
$endgroup$
– Ted
Jul 23 at 20:38
$begingroup$
I'm not sure of any solution that doesn't just use transposition tables
$endgroup$
– Parseltongue
Jul 23 at 20:58
$begingroup$
@Ted That is exactly the puzzle I mean. Thanks
$endgroup$
– Jakub Gabčo
Jul 23 at 21:10
add a comment |
$begingroup$
I have a simple grid puzzle:
Example:
| X | Y | X |
| Y | X | Y |
| Y | X | Y |
The move is defined as a row or a column move. So when you move one cell, whole column/row moves.
Example top row right 2 steps:
1 step
| X | X | Y |
| Y | X | Y |
| Y | X | Y |
2 step
| Y | X | X |
| Y | X | Y |
| Y | X | Y |
Now column move will look like this on the last row move up
1 step
| Y | X | Y |
| Y | X | Y |
| Y | X | X |
and so MoveRight - the most right cell will become the most left cell etc...
I am wondering if it is possible to go to every possible grid combination only with this moves. Let's assume that the grid will be 3x3 but it can be any size.
So, for example, I create random grid 3x3 with the same X count and Y count like this:
| Y | Y | Y |
| Y | Y | X |
| X | X | X |
Is it possible to check if there is a solution on how to make this grid the first grid with already specified moves? Or how to approach this problem?
Thanks, everyone.
grid-deduction
edited Jul 23 at 20:17
Nautilus
4,3206 silver badges26 bronze badges
asked Jul 23 at 19:46
Jakub GabčoJakub Gabčo
433 bronze badges
$endgroup$
I have a simple grid puzzle:
Example:
| X | Y | X |
| Y | X | Y |
| Y | X | Y |
The move is defined as a row or a column move. So when you move one cell, whole column/row moves.
Example top row right 2 steps:
1 step
| X | X | Y |
| Y | X | Y |
| Y | X | Y |
2 step
| Y | X | X |
| Y | X | Y |
| Y | X | Y |
Now column move will look like this on the last row move up
1 step
| Y | X | Y |
| Y | X | Y |
| Y | X | X |
and so MoveRight - the most right cell will become the most left cell etc...
I am wondering if it is possible to go to every possible grid combination only with this moves. Let's assume that the grid will be 3x3 but it can be any size.
So, for example, I create random grid 3x3 with the same X count and Y count like this:
| Y | Y | Y |
| Y | Y | X |
| X | X | X |
Is it possible to check if there is a solution on how to make this grid the first grid with already specified moves? Or how to approach this problem?
Thanks, everyone.
grid-deduction
grid-deduction
edited Jul 23 at 20:17
Nautilus
4,3206 silver badges26 bronze badges
asked Jul 23 at 19:46
Jakub GabčoJakub Gabčo
433 bronze badges
edited Jul 23 at 20:17
Nautilus
4,3206 silver badges26 bronze badges
asked Jul 23 at 19:46
Jakub GabčoJakub Gabčo
433 bronze badges
edited Jul 23 at 20:17
Nautilus
4,3206 silver badges26 bronze badges
edited Jul 23 at 20:17
Nautilus
4,3206 silver badges26 bronze badges
edited Jul 23 at 20:17
Nautilus
4,3206 silver badges26 bronze badges
4,3206 silver badges26 bronze badges
asked Jul 23 at 19:46
Jakub GabčoJakub Gabčo
433 bronze badges
asked Jul 23 at 19:46
Jakub GabčoJakub Gabčo
433 bronze badges
asked Jul 23 at 19:46
Jakub GabčoJakub Gabčo
433 bronze badges
433 bronze badges
$begingroup$
Are we guaranteed that it will be a 3x3 grid and only two values (X and Y)? With such a small grid, you can just brute force the solution by generating every possible configuration
$endgroup$
– Parseltongue
Jul 23 at 20:24
$begingroup$
@Parseltongue No, this is just an example. It can even have every cell other char and the size can be bigger. I am currently building a playable solution to try that, but I want to know more non-brute force method.
$endgroup$
– Jakub Gabčo
Jul 23 at 20:33
$begingroup$
Here's a 4x4 one from Simon Tatham's Portable Puzzle Collection, but you can change the size from the drop down. chiark.greenend.org.uk/~sgtatham/puzzles/js/sixteen.html
$endgroup$
– Ted
Jul 23 at 20:38
$begingroup$
I'm not sure of any solution that doesn't just use transposition tables
$endgroup$
– Parseltongue
Jul 23 at 20:58
$begingroup$
@Ted That is exactly the puzzle I mean. Thanks
$endgroup$
– Jakub Gabčo
Jul 23 at 21:10
add a comment |
$begingroup$
Are we guaranteed that it will be a 3x3 grid and only two values (X and Y)? With such a small grid, you can just brute force the solution by generating every possible configuration
$endgroup$
– Parseltongue
Jul 23 at 20:24
$begingroup$
@Parseltongue No, this is just an example. It can even have every cell other char and the size can be bigger. I am currently building a playable solution to try that, but I want to know more non-brute force method.
$endgroup$
– Jakub Gabčo
Jul 23 at 20:33
$begingroup$
Here's a 4x4 one from Simon Tatham's Portable Puzzle Collection, but you can change the size from the drop down. chiark.greenend.org.uk/~sgtatham/puzzles/js/sixteen.html
$endgroup$
– Ted
Jul 23 at 20:38
$begingroup$
I'm not sure of any solution that doesn't just use transposition tables
$endgroup$
– Parseltongue
Jul 23 at 20:58
$begingroup$
@Ted That is exactly the puzzle I mean. Thanks
$endgroup$
– Jakub Gabčo
Jul 23 at 21:10
$begingroup$
Are we guaranteed that it will be a 3x3 grid and only two values (X and Y)? With such a small grid, you can just brute force the solution by generating every possible configuration
$endgroup$
– Parseltongue
Jul 23 at 20:24
$begingroup$
Are we guaranteed that it will be a 3x3 grid and only two values (X and Y)? With such a small grid, you can just brute force the solution by generating every possible configuration
$endgroup$
– Parseltongue
Jul 23 at 20:24
$begingroup$
@Parseltongue No, this is just an example. It can even have every cell other char and the size can be bigger. I am currently building a playable solution to try that, but I want to know more non-brute force method.
$endgroup$
– Jakub Gabčo
Jul 23 at 20:33
$begingroup$
@Parseltongue No, this is just an example. It can even have every cell other char and the size can be bigger. I am currently building a playable solution to try that, but I want to know more non-brute force method.
$endgroup$
– Jakub Gabčo
Jul 23 at 20:33
$begingroup$
Here's a 4x4 one from Simon Tatham's Portable Puzzle Collection, but you can change the size from the drop down. chiark.greenend.org.uk/~sgtatham/puzzles/js/sixteen.html
$endgroup$
– Ted
Jul 23 at 20:38
$begingroup$
Here's a 4x4 one from Simon Tatham's Portable Puzzle Collection, but you can change the size from the drop down. chiark.greenend.org.uk/~sgtatham/puzzles/js/sixteen.html
$endgroup$
– Ted
Jul 23 at 20:38
$begingroup$
I'm not sure of any solution that doesn't just use transposition tables
$endgroup$
– Parseltongue
Jul 23 at 20:58
$begingroup$
I'm not sure of any solution that doesn't just use transposition tables
$endgroup$
– Parseltongue
Jul 23 at 20:58
$begingroup$
@Ted That is exactly the puzzle I mean. Thanks
$endgroup$
– Jakub Gabčo
Jul 23 at 21:10
$begingroup$
@Ted That is exactly the puzzle I mean. Thanks
$endgroup$
– Jakub Gabčo
Jul 23 at 21:10
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
In the general case (all symbols allowed), you cannot reach every position. The argument is a parity argument, similar to how half of the configurations of a Rubik's Cube cannot be achieved.
Every legal move in your game is equivalent to an even number of "swaps". Say you start with
ABC
DEF
GHI
and move the top row right:
CAB
DEF
GHI
This is equivalent to swapping BC, and then swapping the resulting AC:
ACB
DEF
GHI
CAB
DEF
GHI
Every move you can make is similarly equivalent to two swaps. This means that every position you can possibly ever arrive at is the equivalent of an even number of swaps.
The result of this is that you cannot ever arrive at a configuration that requires an odd number of swaps, like this one:
BAC
DEF
GHI
answered Jul 23 at 21:16
user61579user61579
1061 bronze badge
$endgroup$
$begingroup$
This answer is gold. Didn't realize that is like Rubick's cube. Thank you very much.
$endgroup$
– Jakub Gabčo
Jul 23 at 21:19
1
$begingroup$
For 4x4 this does not apply if I am right .. There are 3 swaps in 4x4 so only solutions are that has swipes count % 3 == 0. For 5x5 there are 4 swaps and so on..
$endgroup$
– Jakub Gabčo
Jul 23 at 21:22
$begingroup$
Yes - a move in 4x4 is equivalent to 3 swaps, meaning that you can arrive at both even and odd configurations. My response is for odd-sized square grids - I don't have a proof either way about even-sized square grids or rectangular grids with an even and an odd dimension. Ah, yes - I see your edit and that is the proof. Whatever the sizes, there will be configurations that aren't equal to 0 mod k for some relevant k.
$endgroup$
– user61579
Jul 23 at 21:26
$begingroup$
I'm confused as to how this constrains the search space, though? You still have to actually figure out if it's possible to get from position A to B in an even number of swaps (for 3x3), which still requires brute-forcing. The fact that you CAN get to a position in an odd number of swaps doesn't mean anything unless all your values are distinct. For example if you have[ACB] [BCA] [GHI]You can get["BAC"]in the top row in an even number of swaps, even though you can also get to it in an odd number of swaps.
$endgroup$
– Parseltongue
Jul 23 at 21:40
$begingroup$
This is also a variant of the sliding tile puzzle which has the same property - half the state space is unreachable. (See the proof description here: en.wikipedia.org/wiki/15_puzzle)
$endgroup$
– Nathan S.
Jul 24 at 5:08
|
show 2 more comments
Your Answer
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
);
);
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%2f86467%2fgrid-puzzle-solutions%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
$begingroup$
In the general case (all symbols allowed), you cannot reach every position. The argument is a parity argument, similar to how half of the configurations of a Rubik's Cube cannot be achieved.
Every legal move in your game is equivalent to an even number of "swaps". Say you start with
ABC
DEF
GHI
and move the top row right:
CAB
DEF
GHI
This is equivalent to swapping BC, and then swapping the resulting AC:
ACB
DEF
GHI
CAB
DEF
GHI
Every move you can make is similarly equivalent to two swaps. This means that every position you can possibly ever arrive at is the equivalent of an even number of swaps.
The result of this is that you cannot ever arrive at a configuration that requires an odd number of swaps, like this one:
BAC
DEF
GHI
answered Jul 23 at 21:16
user61579user61579
1061 bronze badge
$endgroup$
$begingroup$
This answer is gold. Didn't realize that is like Rubick's cube. Thank you very much.
$endgroup$
– Jakub Gabčo
Jul 23 at 21:19
1
$begingroup$
For 4x4 this does not apply if I am right .. There are 3 swaps in 4x4 so only solutions are that has swipes count % 3 == 0. For 5x5 there are 4 swaps and so on..
$endgroup$
– Jakub Gabčo
Jul 23 at 21:22
$begingroup$
Yes - a move in 4x4 is equivalent to 3 swaps, meaning that you can arrive at both even and odd configurations. My response is for odd-sized square grids - I don't have a proof either way about even-sized square grids or rectangular grids with an even and an odd dimension. Ah, yes - I see your edit and that is the proof. Whatever the sizes, there will be configurations that aren't equal to 0 mod k for some relevant k.
$endgroup$
– user61579
Jul 23 at 21:26
$begingroup$
I'm confused as to how this constrains the search space, though? You still have to actually figure out if it's possible to get from position A to B in an even number of swaps (for 3x3), which still requires brute-forcing. The fact that you CAN get to a position in an odd number of swaps doesn't mean anything unless all your values are distinct. For example if you have[ACB] [BCA] [GHI]You can get["BAC"]in the top row in an even number of swaps, even though you can also get to it in an odd number of swaps.
$endgroup$
– Parseltongue
Jul 23 at 21:40
$begingroup$
This is also a variant of the sliding tile puzzle which has the same property - half the state space is unreachable. (See the proof description here: en.wikipedia.org/wiki/15_puzzle)
$endgroup$
– Nathan S.
Jul 24 at 5:08
|
show 2 more comments
$begingroup$
In the general case (all symbols allowed), you cannot reach every position. The argument is a parity argument, similar to how half of the configurations of a Rubik's Cube cannot be achieved.
Every legal move in your game is equivalent to an even number of "swaps". Say you start with
ABC
DEF
GHI
and move the top row right:
CAB
DEF
GHI
This is equivalent to swapping BC, and then swapping the resulting AC:
ACB
DEF
GHI
CAB
DEF
GHI
Every move you can make is similarly equivalent to two swaps. This means that every position you can possibly ever arrive at is the equivalent of an even number of swaps.
The result of this is that you cannot ever arrive at a configuration that requires an odd number of swaps, like this one:
BAC
DEF
GHI
answered Jul 23 at 21:16
user61579user61579
1061 bronze badge
$endgroup$
$begingroup$
This answer is gold. Didn't realize that is like Rubick's cube. Thank you very much.
$endgroup$
– Jakub Gabčo
Jul 23 at 21:19
1
$begingroup$
For 4x4 this does not apply if I am right .. There are 3 swaps in 4x4 so only solutions are that has swipes count % 3 == 0. For 5x5 there are 4 swaps and so on..
$endgroup$
– Jakub Gabčo
Jul 23 at 21:22
$begingroup$
Yes - a move in 4x4 is equivalent to 3 swaps, meaning that you can arrive at both even and odd configurations. My response is for odd-sized square grids - I don't have a proof either way about even-sized square grids or rectangular grids with an even and an odd dimension. Ah, yes - I see your edit and that is the proof. Whatever the sizes, there will be configurations that aren't equal to 0 mod k for some relevant k.
$endgroup$
– user61579
Jul 23 at 21:26
$begingroup$
I'm confused as to how this constrains the search space, though? You still have to actually figure out if it's possible to get from position A to B in an even number of swaps (for 3x3), which still requires brute-forcing. The fact that you CAN get to a position in an odd number of swaps doesn't mean anything unless all your values are distinct. For example if you have[ACB] [BCA] [GHI]You can get["BAC"]in the top row in an even number of swaps, even though you can also get to it in an odd number of swaps.
$endgroup$
– Parseltongue
Jul 23 at 21:40
$begingroup$
This is also a variant of the sliding tile puzzle which has the same property - half the state space is unreachable. (See the proof description here: en.wikipedia.org/wiki/15_puzzle)
$endgroup$
– Nathan S.
Jul 24 at 5:08
|
show 2 more comments
$begingroup$
In the general case (all symbols allowed), you cannot reach every position. The argument is a parity argument, similar to how half of the configurations of a Rubik's Cube cannot be achieved.
Every legal move in your game is equivalent to an even number of "swaps". Say you start with
ABC
DEF
GHI
and move the top row right:
CAB
DEF
GHI
This is equivalent to swapping BC, and then swapping the resulting AC:
ACB
DEF
GHI
CAB
DEF
GHI
Every move you can make is similarly equivalent to two swaps. This means that every position you can possibly ever arrive at is the equivalent of an even number of swaps.
The result of this is that you cannot ever arrive at a configuration that requires an odd number of swaps, like this one:
BAC
DEF
GHI
answered Jul 23 at 21:16
user61579user61579
1061 bronze badge
$endgroup$
In the general case (all symbols allowed), you cannot reach every position. The argument is a parity argument, similar to how half of the configurations of a Rubik's Cube cannot be achieved.
Every legal move in your game is equivalent to an even number of "swaps". Say you start with
ABC
DEF
GHI
and move the top row right:
CAB
DEF
GHI
This is equivalent to swapping BC, and then swapping the resulting AC:
ACB
DEF
GHI
CAB
DEF
GHI
Every move you can make is similarly equivalent to two swaps. This means that every position you can possibly ever arrive at is the equivalent of an even number of swaps.
The result of this is that you cannot ever arrive at a configuration that requires an odd number of swaps, like this one:
BAC
DEF
GHI
answered Jul 23 at 21:16
user61579user61579
1061 bronze badge
answered Jul 23 at 21:16
user61579user61579
1061 bronze badge
answered Jul 23 at 21:16
user61579user61579
1061 bronze badge
answered Jul 23 at 21:16
user61579user61579
1061 bronze badge
1061 bronze badge
$begingroup$
This answer is gold. Didn't realize that is like Rubick's cube. Thank you very much.
$endgroup$
– Jakub Gabčo
Jul 23 at 21:19
1
$begingroup$
For 4x4 this does not apply if I am right .. There are 3 swaps in 4x4 so only solutions are that has swipes count % 3 == 0. For 5x5 there are 4 swaps and so on..
$endgroup$
– Jakub Gabčo
Jul 23 at 21:22
$begingroup$
Yes - a move in 4x4 is equivalent to 3 swaps, meaning that you can arrive at both even and odd configurations. My response is for odd-sized square grids - I don't have a proof either way about even-sized square grids or rectangular grids with an even and an odd dimension. Ah, yes - I see your edit and that is the proof. Whatever the sizes, there will be configurations that aren't equal to 0 mod k for some relevant k.
$endgroup$
– user61579
Jul 23 at 21:26
$begingroup$
I'm confused as to how this constrains the search space, though? You still have to actually figure out if it's possible to get from position A to B in an even number of swaps (for 3x3), which still requires brute-forcing. The fact that you CAN get to a position in an odd number of swaps doesn't mean anything unless all your values are distinct. For example if you have[ACB] [BCA] [GHI]You can get["BAC"]in the top row in an even number of swaps, even though you can also get to it in an odd number of swaps.
$endgroup$
– Parseltongue
Jul 23 at 21:40
$begingroup$
This is also a variant of the sliding tile puzzle which has the same property - half the state space is unreachable. (See the proof description here: en.wikipedia.org/wiki/15_puzzle)
$endgroup$
– Nathan S.
Jul 24 at 5:08
|
show 2 more comments
$begingroup$
This answer is gold. Didn't realize that is like Rubick's cube. Thank you very much.
$endgroup$
– Jakub Gabčo
Jul 23 at 21:19
1
$begingroup$
For 4x4 this does not apply if I am right .. There are 3 swaps in 4x4 so only solutions are that has swipes count % 3 == 0. For 5x5 there are 4 swaps and so on..
$endgroup$
– Jakub Gabčo
Jul 23 at 21:22
$begingroup$
Yes - a move in 4x4 is equivalent to 3 swaps, meaning that you can arrive at both even and odd configurations. My response is for odd-sized square grids - I don't have a proof either way about even-sized square grids or rectangular grids with an even and an odd dimension. Ah, yes - I see your edit and that is the proof. Whatever the sizes, there will be configurations that aren't equal to 0 mod k for some relevant k.
$endgroup$
– user61579
Jul 23 at 21:26
$begingroup$
I'm confused as to how this constrains the search space, though? You still have to actually figure out if it's possible to get from position A to B in an even number of swaps (for 3x3), which still requires brute-forcing. The fact that you CAN get to a position in an odd number of swaps doesn't mean anything unless all your values are distinct. For example if you have[ACB] [BCA] [GHI]You can get["BAC"]in the top row in an even number of swaps, even though you can also get to it in an odd number of swaps.
$endgroup$
– Parseltongue
Jul 23 at 21:40
$begingroup$
This is also a variant of the sliding tile puzzle which has the same property - half the state space is unreachable. (See the proof description here: en.wikipedia.org/wiki/15_puzzle)
$endgroup$
– Nathan S.
Jul 24 at 5:08
$begingroup$
This answer is gold. Didn't realize that is like Rubick's cube. Thank you very much.
$endgroup$
– Jakub Gabčo
Jul 23 at 21:19
$begingroup$
This answer is gold. Didn't realize that is like Rubick's cube. Thank you very much.
$endgroup$
– Jakub Gabčo
Jul 23 at 21:19
1
1
$begingroup$
For 4x4 this does not apply if I am right .. There are 3 swaps in 4x4 so only solutions are that has swipes count % 3 == 0. For 5x5 there are 4 swaps and so on..
$endgroup$
– Jakub Gabčo
Jul 23 at 21:22
$begingroup$
For 4x4 this does not apply if I am right .. There are 3 swaps in 4x4 so only solutions are that has swipes count % 3 == 0. For 5x5 there are 4 swaps and so on..
$endgroup$
– Jakub Gabčo
Jul 23 at 21:22
$begingroup$
Yes - a move in 4x4 is equivalent to 3 swaps, meaning that you can arrive at both even and odd configurations. My response is for odd-sized square grids - I don't have a proof either way about even-sized square grids or rectangular grids with an even and an odd dimension. Ah, yes - I see your edit and that is the proof. Whatever the sizes, there will be configurations that aren't equal to 0 mod k for some relevant k.
$endgroup$
– user61579
Jul 23 at 21:26
$begingroup$
Yes - a move in 4x4 is equivalent to 3 swaps, meaning that you can arrive at both even and odd configurations. My response is for odd-sized square grids - I don't have a proof either way about even-sized square grids or rectangular grids with an even and an odd dimension. Ah, yes - I see your edit and that is the proof. Whatever the sizes, there will be configurations that aren't equal to 0 mod k for some relevant k.
$endgroup$
– user61579
Jul 23 at 21:26
$begingroup$
I'm confused as to how this constrains the search space, though? You still have to actually figure out if it's possible to get from position A to B in an even number of swaps (for 3x3), which still requires brute-forcing. The fact that you CAN get to a position in an odd number of swaps doesn't mean anything unless all your values are distinct. For example if you have
[ACB] [BCA] [GHI] You can get ["BAC"] in the top row in an even number of swaps, even though you can also get to it in an odd number of swaps.$endgroup$
– Parseltongue
Jul 23 at 21:40
$begingroup$
I'm confused as to how this constrains the search space, though? You still have to actually figure out if it's possible to get from position A to B in an even number of swaps (for 3x3), which still requires brute-forcing. The fact that you CAN get to a position in an odd number of swaps doesn't mean anything unless all your values are distinct. For example if you have
[ACB] [BCA] [GHI] You can get ["BAC"] in the top row in an even number of swaps, even though you can also get to it in an odd number of swaps.$endgroup$
– Parseltongue
Jul 23 at 21:40
$begingroup$
This is also a variant of the sliding tile puzzle which has the same property - half the state space is unreachable. (See the proof description here: en.wikipedia.org/wiki/15_puzzle)
$endgroup$
– Nathan S.
Jul 24 at 5:08
$begingroup$
This is also a variant of the sliding tile puzzle which has the same property - half the state space is unreachable. (See the proof description here: en.wikipedia.org/wiki/15_puzzle)
$endgroup$
– Nathan S.
Jul 24 at 5:08
|
show 2 more comments
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.
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%2f86467%2fgrid-puzzle-solutions%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$
Are we guaranteed that it will be a 3x3 grid and only two values (X and Y)? With such a small grid, you can just brute force the solution by generating every possible configuration
$endgroup$
– Parseltongue
Jul 23 at 20:24
$begingroup$
@Parseltongue No, this is just an example. It can even have every cell other char and the size can be bigger. I am currently building a playable solution to try that, but I want to know more non-brute force method.
$endgroup$
– Jakub Gabčo
Jul 23 at 20:33
$begingroup$
Here's a 4x4 one from Simon Tatham's Portable Puzzle Collection, but you can change the size from the drop down. chiark.greenend.org.uk/~sgtatham/puzzles/js/sixteen.html
$endgroup$
– Ted
Jul 23 at 20:38
$begingroup$
I'm not sure of any solution that doesn't just use transposition tables
$endgroup$
– Parseltongue
Jul 23 at 20:58
$begingroup$
@Ted That is exactly the puzzle I mean. Thanks
$endgroup$
– Jakub Gabčo
Jul 23 at 21:10