10
$\begingroup$

Warning: extreme difficulty

Does there exist a 6x6 masyu puzzle with one black pearl in each row/column (without any white pearls) which is uniquely solvable? What about for 7x7 grids? In fact, what is the smallest N such that there exists a uniquely solvable NxN grid?

Hint helpfulness level 0

I have no idea what the answer is.

Hint helpfulness level 1

I conjectured the answer was 7 but I have not been able to find a grid that works

Hint helpfulness level 2

You may need a computer for this

Hint helpfulness level 3

You might as well give up if you need this many hints

$\endgroup$
0

2 Answers 2

9
$\begingroup$

There are two solutions for 7x7 grids

(not counting reflections and rotations)

7-1 enter image description here

I found these by brute force. Each grid can be abstracted as a permutation of 1234567, where each digit represents the column a black pearl is placed on the row correlating to the digit's position. I used this javascript page to generate a list of all 5040 permutations in a space delimited block of text. I used only the permutations that began with 1-4, because 5-7 would all be reflections of a previous permutation (in retrospect, I could have cut it off at 1-3).

As my coding skill is only slightly past the stone age, it took an embarrassingly long time to hack together code snippets from stack exchange answers to make a batch script that would write a text file for every permutation that would be properly formatted to be evaluated by Naoyuki Tamura's Masyu solver. I had to convert the space delimiters in my permutations list (permutations.txt) to newlines, which was easy enough with Notepad++.

Here is the laughable code for the batch script I used to write the puzzle files:

echo off
setlocal enableextensions enabledelayedexpansion
set /a countraw=0
for /F "tokens=*" %%a in (permutations.txt) do (
set /a countraw+=1
set count=000!countraw!
set count=!count:~-4!
set tstring=%%a
echo !count!: !tstring!
echo 7 > mgrid!count!.txt
echo 7 >> mgrid!count!.txt
set q=!tstring:~0,1!
if !q! EQU 1 echo b - - - - - - >> mgrid!count!.txt
if !q! EQU 2 echo - b - - - - - >> mgrid!count!.txt
if !q! EQU 3 echo - - b - - - - >> mgrid!count!.txt
if !q! EQU 4 echo - - - b - - - >> mgrid!count!.txt
if !q! EQU 5 echo - - - - b - - >> mgrid!count!.txt
if !q! EQU 6 echo - - - - - b - >> mgrid!count!.txt
if !q! EQU 7 echo - - - - - - b >> mgrid!count!.txt
set q=!tstring:~1,1!
if !q! EQU 1 echo b - - - - - - >> mgrid!count!.txt
if !q! EQU 2 echo - b - - - - - >> mgrid!count!.txt
if !q! EQU 3 echo - - b - - - - >> mgrid!count!.txt
if !q! EQU 4 echo - - - b - - - >> mgrid!count!.txt
if !q! EQU 5 echo - - - - b - - >> mgrid!count!.txt
if !q! EQU 6 echo - - - - - b - >> mgrid!count!.txt
if !q! EQU 7 echo - - - - - - b >> mgrid!count!.txt
set q=!tstring:~2,1!
if !q! EQU 1 echo b - - - - - - >> mgrid!count!.txt
if !q! EQU 2 echo - b - - - - - >> mgrid!count!.txt
if !q! EQU 3 echo - - b - - - - >> mgrid!count!.txt
if !q! EQU 4 echo - - - b - - - >> mgrid!count!.txt
if !q! EQU 5 echo - - - - b - - >> mgrid!count!.txt
if !q! EQU 6 echo - - - - - b - >> mgrid!count!.txt
if !q! EQU 7 echo - - - - - - b >> mgrid!count!.txt
set q=!tstring:~3,1!
if !q! EQU 1 echo b - - - - - - >> mgrid!count!.txt
if !q! EQU 2 echo - b - - - - - >> mgrid!count!.txt
if !q! EQU 3 echo - - b - - - - >> mgrid!count!.txt
if !q! EQU 4 echo - - - b - - - >> mgrid!count!.txt
if !q! EQU 5 echo - - - - b - - >> mgrid!count!.txt
if !q! EQU 6 echo - - - - - b - >> mgrid!count!.txt
if !q! EQU 7 echo - - - - - - b >> mgrid!count!.txt
set q=!tstring:~4,1!
if !q! EQU 1 echo b - - - - - - >> mgrid!count!.txt
if !q! EQU 2 echo - b - - - - - >> mgrid!count!.txt
if !q! EQU 3 echo - - b - - - - >> mgrid!count!.txt
if !q! EQU 4 echo - - - b - - - >> mgrid!count!.txt
if !q! EQU 5 echo - - - - b - - >> mgrid!count!.txt
if !q! EQU 6 echo - - - - - b - >> mgrid!count!.txt
if !q! EQU 7 echo - - - - - - b >> mgrid!count!.txt
set q=!tstring:~5,1!
if !q! EQU 1 echo b - - - - - - >> mgrid!count!.txt
if !q! EQU 2 echo - b - - - - - >> mgrid!count!.txt
if !q! EQU 3 echo - - b - - - - >> mgrid!count!.txt
if !q! EQU 4 echo - - - b - - - >> mgrid!count!.txt
if !q! EQU 5 echo - - - - b - - >> mgrid!count!.txt
if !q! EQU 6 echo - - - - - b - >> mgrid!count!.txt
if !q! EQU 7 echo - - - - - - b >> mgrid!count!.txt
set q=!tstring:~6,1!
if !q! EQU 1 echo b - - - - - - >> mgrid!count!.txt
if !q! EQU 2 echo - b - - - - - >> mgrid!count!.txt
if !q! EQU 3 echo - - b - - - - >> mgrid!count!.txt
if !q! EQU 4 echo - - - b - - - >> mgrid!count!.txt
if !q! EQU 5 echo - - - - b - - >> mgrid!count!.txt
if !q! EQU 6 echo - - - - - b - >> mgrid!count!.txt
if !q! EQU 7 echo - - - - - - b >> mgrid!count!.txt
)

Obviously, it would have been ideal to structure it as nested for's, but batch is weird about variables in for loops and I could never get any variable references to work. Perhaps someone who knows more about batch scripting can come up with a better solution, or suggest what coding environment I should have used.

In any case, I then put all the text files into a folder with the solver and another batch script, whose code follows:

echo off
echo BEGIN REPORT>report.txt
for %%a in (mgrid*.txt) do (
echo %%a
echo %%a >> report.txt
scala -cp copris-masyu-v1-1.jar masyu.Solver -o multi %%a >> report.txt
echo. >>report.txt
)

I then searched the report for the string "NumOfSolutions = 1" and rendered all of the results that weren't reflections and rotations of previous results, of which there were the two above.

By modifying the code and testing, I was able to determine that

There are no solutions for 6x6, 5x5, or 4x4 grids. N=7

EDIT:

I decided to try white pearls as well. For them, N=4, as there is one solution, not counting its reflection:

enter image description here

I tried 5x5, but found there were no grids that would produce a unique solution, which leads me to believe that 4x4 is the only grid size that could produce a unique solution with white pearls.

I'm curious about the upper limit of the grid size for black pearls. This would certainly require that I figure out some way to pare out all reflections and rotations from the permutation list, which would then leave me with 45360 permutations for a 9x9 grid (as 8x8 has already been proven). The solver usually finishes smaller grids in about 1 second. If this is true for 9x9 grids, it would take at least 12 hours to go through all unique 9x9, but I estimate it could easily take double that.

$\endgroup$
7
$\begingroup$

8x8 has been solved

Nazi puzzle

Give it a go!

Yes, I know what shape that makes >:)

$\endgroup$

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.