14
$\begingroup$

While playing Simon Tatham's Galaxies, I found this particularly difficult one. I did eventually solve it, but I found the solve path and final answer to be quite satisfying, so I thought I'd share it here.

an image of the puzzle

A recap of the rules: Each dot is the center of a galaxy. A galaxy is a set of grid squares that contains one dot, and must be two-way rotationally symmetric around that dot. A galaxy should have no lines separating two of its own squares.

Here is a link to the puzzle, so you can play it with the site's tools. The site has a 'Solve Game' button, so an accepted answer will require working.

$\endgroup$

2 Answers 2

4
$\begingroup$

I think I have a clearer set of inferences. Here's my set of "obvious" starting moves:

starting inferences

Now R8C8 can only belong to one galaxy (R5C7 has an open cell symmetrically, but no path would connect them):

first little reach

and the symmetric cell being blocked from the C3 galaxy means that R4C3 has to belong to the C6.5 galaxy:

two more reaches

Now R8C4 can no longer be reached by R5C7, so must be R6C7. From there we finally get a better number of short conclusions, until finally R7C2 can no longer belong to the adjacent center:

The final long-distance inference

From here the rest is straightforward.

$\endgroup$
7
$\begingroup$

First, we can start with all galaxies in the border, and close all the lines opposing to the dots in the border, as they can't both be in the center of their galaxy and in the border Border

Then, we can also close all the frontiers between two galaxies frontiers

By doing so, we create a new border that touches dots, so we can repeat the process

repeat ??? profit

Then we can do some trial and error, for example, what if the red dot is three square high ? well, then his neighbors are affected, and we quickly see that there will be a problem on the right part of the board.

not working

As it can't be this solution, we can safely close this galaxy, and see how it affected his neighbors. For example, we can see that the top right galaxy has to be 3 square long horizontal, as it's the only galaxy that can fit the leftmost square. We can then try again, with another galaxy, ideally that have only two possible states, and if one does not work, go for the second one.

still nope

repeat again and again

and again and again and again

Once all the tiny galaxies are closed, you have only big ones, and you have to close borders, then you have to use the fact that galaxies are symmetrical, So a galaxy can't extend to a place without doing the same symmetrically. Use this to see that some squares can't belong to given galaxies, and close borders knowing this new information.

big galaxies

You can also use the fact that some square belonging to a galaxy have borders, and draw them symmetrically, to create new borders

lot of arrows

Finally, we are here

Solution

$\endgroup$
4
  • 1
    $\begingroup$ Good to see your step by step explanation. Not entirely convinced that "what if the red dot is three square high... we quickly see that there will be a problem on the right part of the board" is totally explained by the diagram that accompanies it though. Perhaps you could point out explicitly what the problem is there? Thanks :) $\endgroup$
    – Stiv
    Commented Nov 27 at 17:10
  • $\begingroup$ @Stiv The problem arises for example with the second row, right most field which can't belong to any galaxy if we assume the red dot is three squares high. $\endgroup$
    – quarague
    Commented Nov 27 at 18:18
  • $\begingroup$ @quarague gonna have to agree with Stiv - that field can belong to the galaxy centred on the 5th row/7th column. $\endgroup$ Commented Nov 27 at 21:42
  • $\begingroup$ There also appears to be a problem with "For example, we can see that the top right galaxy has to be 3 square long horizontal, as it's the only galaxy that can fit the leftmost square" - that square could belong to the galaxy centred on the 4th row/8th column at that stage of the solve. $\endgroup$ Commented Nov 27 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.