Solve Tango Puzzle

Question

Tango is a puzzle that consists of a 6x6 grid partially filled with moons (M) and suns (S) and two lists of coordinate pairs, which we will call = and ×ばつ . The goal is to fill the rest of the grid following these rules:

• Each cell must contain either M or S
• There cannot be more than 2 M or S next to each other, either vertically or horizontally
• Each row and column must contain the same number of M and S
• Cells corresponding to a pair of coordinates in = must be of the same type
• Cells corresponding to a pair of coordinates in ×ばつ must be of the opposite type

Input

• Partially filled 6x6 grid
• List of coordinate pairs (=) indicating the two cells must be equal
• List of coordinate pairs (×ばつ) indicating the two cells must be different

You may receive the grid and pairs in any reasonable format.

Output: Solved puzzle

You may assume that each input has exactly one answer and that it can be solved via deduction, i.e. you should never have to make a guess.

Test cases

Notes:

• The coordinates are 0-indexed
• The leftmost top cell has coordinates (row, col) = (0,0)
• . denotes an empty cell
• Pairs are provided as follows:

(a,b), (c,d), (e,f), (g,h), ...
pair 1: (a,b) and (c,d)
pair 2: (e,f) and (g,h)
...

Test 1

Input

= (1,1), (2,1), (3,1), (3,2)×ばつ (1,2), (2,2), (1,3), (1,4), (2,3), (2,4), (3,3), (4,3), (3,4), (4,4), (4,1), (4,2) 
.MSSM.
M....M
S....M
S....S
M....S
.SMMS.

Output

MMSSMS
MSSMSM
SSMSMM
SMMSMS
MMSMSS
SSMMSM

Test 2

Input

= (2,2), (2,3), (2,3), (3,3)×ばつ (3,2), (3,3), (2,2), (3,2)
MS....
M...SM
SM..M.
.S..MS
SM...M
....MS

Output

MSMMSS
MSSMSM
SMSSMM
MSMSMS
SMSMSM
SMMSMS

Test 3

Input

= (0,1), (1,1), (1,0), (2,0), (2,5), (3,5), (3,0), (4,0), (4,0), (4,1)×ばつ (0,1), (0,2), (0,3), (0,4), (0,4), (1,4), (1,0), (1,1), (1,4), (1,5), (1,5), (2,5), (2,0), (3,0), (3,5), (4,5), (4,4), (4,5), (4,4), (5,4), (5,3), (5,4), (5,1), (5,2), (4,1), (5,1)
......
......
..S.S.
.M.S..
......
......

Output

SSMSMM
MSSMSM
MMSMSS
SMMSMS
SSMMSM
MMSSMS

Test 4

Input

= (1,2), (2,2), (2,1), (3,1), (3,2), (3,3), (4,0), (5,0), (5,1), (5,2), (5,3), (5,4), (4,5), (5,5)×ばつ (1,3), (2,3), (2,4), (3,4), (4,1), (4,2), (4,3), (4,4)
..SS..
......
......
......
......
......

Output

SMSSMM
MSMMSS
SMMSSM
SMSSMM
MSMMSS
MSSMMS

• z..: related
• Jonah: Unless you intend the 2^36 brute force solution to be legal, consider adding a runtime constraint to the rules.
• Kjetil S: @Jonah - or if we are allowed to assume at least 16 pre-filled cells, like in the examples, then 2^20 (a million) would be a more feasible brute force.
• z..: @Lucenaposition that simply means that given the current grid state and constraints, there's always at least one move that is guaranteed to be correct without having to guess. See an example here for today's puzzle.
• z..: @Arnauld yes you can take the input in whatever format you want.

Answer 1

JavaScript (ES6), 176 bytes

Expects (m)(A), where m is a matrix of characters and A is a list of 5-tuples [i,y,x,Y,X] with i=0 for equal and i=1 for different.

Updates the input matrix in-place.

m=>g=A=>m.some((r,y)=>r.some((c,x)=>c<g?g(A,r[x]="M")&&g(A,r[x]="S")?r[x]=c:0:!A.every(([i,V,H,Y,X])=>Y-y|X-x|m[V][H]==c^i)|/(\w)((\D*1円){3}|,1,円1円)/.test(r+0+m.map(r=>r[x]))))

Try it online!

Method and performance

This simply makes a guess on each empty cell but aborts as soon as an inconsistent state is detected, even on incomplete columns or rows (e.g. MM..MM is recognized as invalid). So it's still pretty fast -- a few milliseconds for the test cases.

It's worth noting that there are only 11,222 valid grids⁽¹⁾. Without any clue given in the input, a slightly modified version of this code can generate all of them in ~15 seconds on TIO.

_{(1) as confirmed here}

Commented

m => // outer function taking m[]
g = A => // inner recursive function taking A[]
m.some((r, y) => // for each row r[] at index y in m[]:
 r.some((c, x) => // for each character c at index x in r[]:
 c < g ? // if this cell is still empty (c is "."):
 g(A, r[x] = "M") && // recursive call with a moon inserted
 g(A, r[x] = "S") // recursive call with a sun inserted
 ? // if both calls failed:
 r[x] = c // restore r[x] to "."
 : // else:
 0 // do nothing
 : // else (c is "M" or "S"):
 !A.every( // for each 5-tuple ...
 ([i, V, H, Y, X]) => // ... [i, V, H, Y, X] in A[]:
 Y - y | X - x | // tests whether (X, Y) matches (x, y)
 m[V][H] == c // and m[V][H] either does or doesn't
 ^ i // match c, according to i
 ) | // end of every()
 /(\w)((\D*1円){3}|,1,円1円)/ // look for 4 identical symbols anywhere
 .test( // or 3 consecutive identical symbols in:
 r + // either the current row
 0 + // (use 0 as a separator)
 m.map(r => r[x]) // or the current column
 ) // end of test()
 ) // end of inner some()
) // end of outer some()

Answer 2

Julia, 264 bytes

f(G,E,X)=while true
A=map(g->g∈"MS" ? g : rand(['M','S']),G)
(M,N)=map(Z->all(map(p->A[p[1]...]==A[p[2]...],zip(Z[1:2:end],Z[2:2:end]))),(E, X))
(P,Q)=map(D->all((A.!=circshift(A,D[1])).||(A.!=circshift(A,D[2]))),[(1,2),((0,1),(0,2))])
M&&!N&&P&&Q&&(return A)end

Attempt This Online!

I checked the list of standard loopholes and this wasn't in there, so I hope it's ok. This function randomly fills the blanks of the grid with Ms and Ses, checking each time to see if the rules are satisfied, and returning if so.

M is true if all of the = rules are satisfied; N is false if x is satisfied, P is true if no vertical triples exist, and Q is true if no horizontal triples exist.

The grid is input as a Matrix{Char} and the rules = and x are just a list of tuples. If I could "pre-zip" them into 2-tuples of 2-tuples, it would save a large number of bytes (25), but in the spirit of the question I'm taking them as a flat list.

Because of the slow execution time (exponential with the number of blanks in the grid), the link above demonstrates a 3x3 example with only 3 blanks.

• Neil: My understanding is that the program merely needs to have a 100% chance of completing and you're good to go.

Answer 3

Python3, 599 bytes

C=lambda x:[]if[]==x else[x[:2]]+C(x[2:])
E=enumerate
def f(a,b,c):
 A,B=dict(C(a)+[(k,j)for j,k in C(a)]),dict(C(b)+[(k,j)for j,k in C(b)])
 q,S=[(c,[(x,y)for x,r in E(c)for y,v in E(r)if'.'==v])],[]
 for c,l in q:
 if[]==l:return c
 (x,y),*l=l
 for t in'SM':
 e=eval(str(c));e[x][y]=t
 if all(all(m*3 not in''.join(k)for k in e+[*zip(*e)])for m in'SM')and all('.'in j or j.count('M')==j.count('S')for j in e+[*zip(*e)])and e not in S:
 F=0
 if(x,y)in A:X,Y=A[(x,y)];F=e[X][Y]in['.',t]
 elif(x,y)in B:X,Y=B[(x,y)];F=e[X][Y]=='.' or e[X][Y]!=t
 else:F=1
 if F:q+=[(e,l)];S+=[e]

Try it online!

• Rhaixer: 2 bytes can be shaved by removing the spaces between m*3 and not, and between =='.' and or e[x]
• ceilingcat: 586 bytes

Answer 4

Uiua (SBCS), 80 bytes

Uses experimental Uiua-0.17 features.

⋅⊙⋅⋅⋅◌⍢(◡(×ばつ∩(×ばつ♭∨∩⌞≠⊸⬚0⊃↻1↻2)×ばつ▽⤙=×ばつ⊂⧋⊓/=/≠∩⌞ ̃⊡⊙◌]+1↯6_6⋯36)+1◌◌)¬0∞0

Pad

Input is a flat list of 1s and 2s (1 is moon, 2 is sun), then a list of equal and not equal pairs (shape \$n\times2\times2\$).

Since this is a brute force solution, it takes up to 2 weeks to run for \$n=6\$, so an example for \$n=4\$ is given in the pad, which solves considerably faster.

Explanation

Iterates over all possible 6x6 grids, finding the first (lexicographically) to satisfy the puzzle constraints. Unfortunately, the normal method of constructing permutations using uiua's ⧅ doesn't work at this scale of \2ドル^{36}\$ (due to a hard limit and also the impossibility of storing this in RAM), so I increment a counter and interpret its bits as a permutation to check.

Expanded:

(
 0 ∞ 0 # initial stack data (condition fail, junk, i=0)
 ⍢( # repeat...
 +1◌◌ # cleanup and inc i
 ◡(+1 ↯ 6_6⋯36 # convert i's bits to 6*6 permutation
 ×ばつ:⟜⊃[ # test if ALL of the conditions hold:
 # keep those without XXX
 ⟜⍉ # copy + transpose grid
 ×ばつ∩( # for both directions,
 ⊸⬚0⊃↻1↻2 # copy+shift grid twice
 ×ばつ♭∨∩⌞≠ # at least one non equal
 )
 | ×ばつ▽⤙=♭ # permutation matches input (where nonzero)
 | # equal, diff coords match (or don't)
 ∩⌞ ̃⊡⊙◌ # pick indices mentioned as coords
 ⧋⊓/=/≠ # check equality or inequality
 ×ばつ⊂ # reduce by and
 ])
 )¬ # if condition fails, continue
 ⋅⊙⋅⋅⋅◌ # clean up stack garbage to output grid
)

Answer 5

Charcoal, 99 bytes

≔E2E⪪S4E⪪λ2⍘ν6θ⊞υ⭆6SFυFEMS⭆ι⎇=×ばつ3ν›Noλν3¿Noκ.⊞υκ⪪κ6

Try it online! Link is to verbose version of code. Takes the = and ×ばつ lists as a concatenated string of digits e.g. (1,1), (2,1), (3,1), (3,2) becomes 11213132 and outputs all found solutions. Explanation:

≔E2E⪪S4E⪪λ2⍘ν6θ

Input the = and ×ばつ lists, split them into fours, split each four into pairs, then interpret each pair in base 6.

⊞υ⭆6SFυ

Start a breadth-first search with the flattened input grid.

FEMS⭆ι⎇=ν⌕ι.κμ

Try replacing the first . in the grid with M and S in turn.

¿¬∨⊙θ⊙λNo⪪§⪪⍘156MS4μ2⭆ν§κπ

If neither the = and ×ばつ lists are violated, ... (156 in base 2 is 10011100 or SMMSSSMM; SM and MS must not appear in the = list and SS and MM must not appear in the ×ばつ list)

×ばつ3ν›Noλν3

... and none of the rows or columns contain 4 of each letter or a tripled letter, then:

¿Noκ.⊞υκ⪪κ6

If there is still a . to process then push the result to the search list otherwise output the result as a grid.

Answer 6

05AB1E, 53 bytes

UþSDg„MSSsãδ.;.ΔS¶¡Ðø«εü3€ËàyD¢Ë«}s ̃X6δδβèε2ô€ËNÊ} ̃«P

First input \$[=×ばつ]\$ as a pair of lists of pairs of 0-based integers; second input grid as a multi-line string with 0s for empty cells.

Brute-force approach.

(Don't) try it online. (Will time-out.)

Explanation:

Step 1: Get all possible output-grids by replacing the 0s with "M" or "S":

U # Pop and store the first (implicit) input-pair in variable `X`
þ # Keep the digits (the 0s) of the second (implicit) input-string
 S # Convert it to a list of 0s
 D # Duplicate this list
 g # Pop and push the length of the copy
 „MS # Push string "MS"
 S # Convert it to a pair of characters: ["M","S"]
 s # Swap so the length is at the top again
 ã # Cartesian product
 δ # Map over each list of M/S using the remaining list of 0s as argument:
 .; # Replace every first 0 one-by-one with the M/S in the second (implicit) input

Try just step 1 online.

Step 2: Keep the first valid result:

.Δ # Find the first value that's truthy for:
 S # Convert the string to a list of characters
 ¶¡ # Split it on newlines to a 6x6 matrix
 Ð # Triplicate this matrix
 ø # Zip/transpose the top copy; swapping rows/columns
 « # Merge the top two lists together
 ε # Map over this list of rows+columns:
 ü3 # Get all overlapping triplets of each
 € # Inner map over each inner triplet
 Ë # Check that all characters are the same
 y # Push the current row/column again
 D # Duplicate it
 ¢ # Pop both and count how many times each character occurs
 Ë # Check that all those counts are the same as well
 « # Append the two checks to one-another
 # (only 1 is truthy in 05AB1E, so we're expecting "01" here)
 } # Close the map
 s # Swap to get the matrix again
 ̃ # Flatten it to a list
 X # Push the first input from variable `X`
 δδ # Apply triple-vectorized to the inner-most pairs,
 6 β # Convert these pairs from a base-6 list to a base-10 integer
 è # Use those values to index into the list
 ε # Map over the pair of lists of M/S:
 2ô # Split the current list into pairs
 € # Inner map over each inner pair:
 Ë # Check whether both items are the same
 NÊ # Check for each that it's NOT equal to the 0-based map-index
 } ̃ # After the map: flatten the pair of bits
 « # Merge the two lists together
 P # Check that everything is truthy
 # (after which the found result is output implicitly)

Verify the validator with a single given (valid) grid.

Answer 7

Jelly, 62 bytes

^{Probably beatable by a lot with a more brute-force approach.}

Wœi".ŒṬ1¡aⱮ)MSƲo€$€Ẏ;Zċþ)MSƲ<ȦɗƇ4QƲÐLœị@E€€¬0¦FẠƊɗƇ;ZKƊṡ3EƇƊÐḟ

A dyadic Link that accepts a list of six lists, each of six characters from .MS, on the left and a list of two lists of pairs of pairs - equal followed by unequal coordinate pairs (1-indexed) - and yields a list of all solutions, each in the same format as the first input (a singleton list given the input is guaranteed to have a unique solution).

Try it online! Footer increments the coordinates and pretty-prints. (Too slow on TIO for the last test, but completes in ~4 min locally.)