Masyu puzzles with many circles

Question

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?

Answer 1

Some grids for question 1:

44 circles

Very easy masyu, the path only passes through circles

45 circles

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

45 circles

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

Answer 2

[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:

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

then pick out this

and tweak it like this

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

Answer 3

I agree with @w l on part 1 of this question, we all seemed to get the exact same pattern.

Part 2 is still open, so here's my take:

I like using excel so all the circles are squares... hopefully everyone can grasp my idea anyway (I don't feel like drawing it correctly).



This is a 14x14 board. Stealing Gareth's basic idea, we can fill the center of the board with a zig-zag pattern. I had more luck with the smaller zig-zag size. This technique only fills 44 circles for the 8x8 board, so obviously there's a cutoff for where it is preferred.




This is a 15x15 board. Odd numbers have a little different approach. The trick to fill this board is to make the main diagonal zig-zag the bigger size, but then use the smaller zig-zag to fill the rest of the space. This adds a row and column to the pattern without losing too much filling power. We end up with an extra two holes in the top left, and that's basically why the odd-boards make for a solution with two less circles

So for even n x n boards we can fill n^2 - 4n + 12 circles

And for odd n x n boards we can fill n^2 - 4n + 10 circles

I don't have anything clever to say about if this creates a unique solution every time... it definitely does. The pattern doesn't become more complicated with size so the phrase "you solve one, you solve them all" seems to apply.

Also

I had a dream last night that I could eliminate that long "return line". It turns out I could. However, this fills in the exact same number of circles. Might be more pretty, though.