8
$\begingroup$

The rules of Masyu:

  1. Make a single loop with lines passing through the centers of cells, horizontally or vertically. The loop never crosses itself, branches off, or goes through the same cell twice.

  2. Lines must pass through all cells with black and white circles.

  3. Lines passing through white circles must pass straight through its cell, and make a right-angled turn on at least one side of the white circle cell (left or right).

  4. Lines passing through black circles must make a right-angled turn in its cell, then it must go straight through the next cell (till the middle of the second cell) on both sides.

A valid Masyu puzzle is a rectangular grid with some squares containing circles such that a unique loop can be drawn according to the above rules.

  1. What is the highest possible number of circles that can be placed on a chessboard to create a valid Masyu puzzle?

  2. What is the highest possible proportion of squares that contain circles in a valid Masyu puzzle on any large square grid?

$\endgroup$
  • $\begingroup$ Very interesting. Do you know the answer to either question? $\endgroup$ – hexomino Mar 27 at 22:15
  • 1
    $\begingroup$ @hexomino I have good answers for both but not necessarily the optimums. $\endgroup$ – noedne Mar 27 at 22:18
  • $\begingroup$ Thanks, I got it. In this version, is it necessary that the colour of each circle matches the colour of the square it lies in? $\endgroup$ – Arnaud Mortier Mar 27 at 22:33
  • $\begingroup$ @ArnaudMortier No, it is just an 8x8 board. $\endgroup$ – noedne Mar 27 at 22:35
5
$\begingroup$

Some grids for question 1:

44 circles

44 circles
Very easy masyu, the path only passes through circles

45 circles

45 circles
Slight modification to add another circle by using the empty 2x2 middle from the previous masyu.

45 circles

45 circles and every cell
Replacing some black circles with white circles to make the path go through every cell as well.

$\endgroup$
  • $\begingroup$ Nice job! Interestingly, my attempts followed the same progression as yours, finding these three boards in this order. (I also enjoy the symmetry of the first.) Thank you for sharing all three! $\endgroup$ – noedne Mar 28 at 13:43
  • $\begingroup$ @noedne Then there is probably a second thing I didn't understand from your settings :/ I've edited my answer. $\endgroup$ – Arnaud Mortier Mar 28 at 13:55
4
$\begingroup$

[EDITED to add:] Oops, this is not actually an answer to the question as posed because I failed to notice the requirement that there be a unique solution. I have now verified that my surely-non-optimal answer to Q1 is in fact a uniquely solvable puzzle. I haven't given any thought to that question in regard to Q2 yet. It might be rather hard.

A surely non-optimal answer to question 1:

enter image description here

This

has 40 circles and is easily verified to be uniquely solvable. (The yellow discs of course represent white circles; in the drawing program I'm using it's easier to make filled circles than empty ones.)

An answer to question 2 (provided I've understood correctly what's being asked for):

For large grids

"almost all" the squares can contain circles. (That is, the fraction tends to 1 as the size increases.)

That's because

we can make arbitrarily-long zigzag lines, each segment having length 3 (hence passing through four squares), with circles everywhere. (Each of those segments has a black circle at each end and two white circles in between.)

And

now we can just cover the entire plane with parallel zigzags in the obvious way, chop out an arbitrary-sized square region, and fix it up to make a loop while changing only the outermost few layers.

That is, start with this

enter image description here

then pick out this

enter image description here

and tweak it like this

![enter image description here

where

we reroute things around the edge in the green region, and skip portions we need to in the blue region, and leave everything else unaltered. These changes may invalidate some of the circles, but only ones near to the shaded regions: no further than 2 squares inward from them.

So

the total number of squares not occupied by circles is at most something like 7/2 times the perimeter of the square, and the fraction of uncircled squares tends to 0 as the size increases. (Of course this works for non-square rectangles too, so long as both sides' lengths increase without limit.)

$\endgroup$
  • $\begingroup$ Excellent work! But how do you know that this produces a board with a unique solution? $\endgroup$ – noedne Mar 27 at 22:30
  • $\begingroup$ Oh, yikes. I didn't notice that that was part of the question. I expect it does but have no expectation of being able to prove it. So my answer is entirely wrong (though something like it might be a useful beginning for one that isn't). Sorry about that. $\endgroup$ – Gareth McCaughan Mar 27 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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