Xjyuk

Why can't a country print its own money to spend it only abroad?

Can you find Airpod Case using Find my iPhone?

What kind of anatomy does a centaur have?

Why is there an extra "t" in Lemmatization?

Is it OK to accept a job opportunity while planning on not taking it?

Adding gears to my grandson's 12" bike

Has Peter Parker ever eaten bugs?

Strange LED behavior: Why is there a voltage over the LED with only one wire connected to it?

Is an easily guessed plot twist a good plot twist?

Killing a star safely

What is the best word describing the nature of expiring in a short amount of time, connoting "losing public attention"?

Would using carbon dioxide as fuel work to reduce the greenhouse effect?

How can I indicate that what I'm saying is not sarcastic online?

Import data from a current web session?

Impact of throwing away fruit waste on a peak > 3200 m above a glacier

What kind of world would drive brains to evolve high-throughput sensory?

I have a domain, static IP address and many devices I'd like to access outside my house. How do I route them?

Can't understand how static works exactly

Can I pay with HKD in Macau or Shenzhen?

Can an infinite group have a finite number of elements with order k?

Are there any English words pronounced with sounds/syllables that aren't part of the spelling?

Grid puzzle solutions

Can GPL and BSD licensed applications be used for government work?

What is "ass door"?

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;

5

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

share|improve this question

edited 8 hours ago

Nautilus

4,32066 silver badges2626 bronze badges

asked 8 hours ago

Jakub GabčoJakub Gabčo

2833 bronze badges

New contributor

Jakub Gabčo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$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
  8 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  8 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  8 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm not sure of any solution that doesn't just use transposition tables
  $endgroup$
  – Parseltongue
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Ted That is exactly the puzzle I mean. Thanks
  $endgroup$
  – Jakub Gabčo
  7 hours ago
  

  
  
  
  

add a comment | 

5

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

share|improve this question

edited 8 hours ago

Nautilus

4,32066 silver badges2626 bronze badges

asked 8 hours ago

Jakub GabčoJakub Gabčo

2833 bronze badges

New contributor

Jakub Gabčo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$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
  8 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  8 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  8 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm not sure of any solution that doesn't just use transposition tables
  $endgroup$
  – Parseltongue
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Ted That is exactly the puzzle I mean. Thanks
  $endgroup$
  – Jakub Gabčo
  7 hours ago
  

  
  
  
  

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

share|improve this question

edited 8 hours ago

Nautilus

4,32066 silver badges2626 bronze badges

asked 8 hours ago

Jakub GabčoJakub Gabčo

2833 bronze badges

New contributor

Jakub Gabčo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

| X | Y | X | 
| Y | X | Y | 
| Y | X | Y | 

1 step
| X | X | Y | 
| Y | X | Y | 
| Y | X | Y | 

2 step
| Y | X | X | 
| Y | X | Y | 
| Y | X | Y |

1 step
| Y | X | Y | 
| Y | X | Y | 
| Y | X | X |

| Y | Y | Y | 
| Y | Y | X | 
| X | X | X | 

share|improve this question

edited 8 hours ago

Nautilus

4,32066 silver badges2626 bronze badges

asked 8 hours ago

Jakub GabčoJakub Gabčo

2833 bronze badges

New contributor

Jakub Gabčo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this question

edited 8 hours ago

Nautilus

4,32066 silver badges2626 bronze badges

asked 8 hours ago

Jakub GabčoJakub Gabčo

2833 bronze badges

New contributor

Jakub Gabčo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited 8 hours ago

Nautilus

4,32066 silver badges2626 bronze badges

edited 8 hours ago

Nautilus

4,32066 silver badges2626 bronze badges

asked 8 hours ago

Jakub GabčoJakub Gabčo

2833 bronze badges

New contributor

Jakub Gabčo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 8 hours ago

Jakub GabčoJakub Gabčo

2833 bronze badges

1 Answer
1

active

oldest

votes

5

$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

share|improve this answer

answered 7 hours ago

user61579user61579

6611 bronze badge

New contributor

user61579 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 answer is gold. Didn't realize that is like Rubick's cube. Thank you very much.
  $endgroup$
  – Jakub Gabčo
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  
  

  
  
  
  

add a comment | 

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
);



);

Jakub Gabčo 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

Name

Email

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

Name

Email

Required, but never shown

5

$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

share|improve this answer

answered 7 hours ago

user61579user61579

6611 bronze badge

New contributor

user61579 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 answer is gold. Didn't realize that is like Rubick's cube. Thank you very much.
  $endgroup$
  – Jakub Gabčo
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  
  

  
  
  
  

add a comment | 

5

$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

share|improve this answer

answered 7 hours ago

user61579user61579

6611 bronze badge

New contributor

user61579 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 answer is gold. Didn't realize that is like Rubick's cube. Thank you very much.
  $endgroup$
  – Jakub Gabčo
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  
  

  
  
  
  

add a comment | 

$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

share|improve this answer

answered 7 hours ago

user61579user61579

6611 bronze badge

New contributor

user61579 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

ABC
DEF
GHI

CAB
DEF
GHI

ACB
DEF
GHI

CAB
DEF
GHI

BAC
DEF
GHI

share|improve this answer

answered 7 hours ago

user61579user61579

6611 bronze badge

New contributor

user61579 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 7 hours ago

user61579user61579

6611 bronze badge

New contributor

user61579 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 7 hours ago

user61579user61579

6611 bronze badge