Is this a valid Shakashaka solution?

Question

Background

Shakashaka is a puzzle on a grid, whose objective is to place some half-squares (right triangles) on the empty cells so that all the remaining contiguous regions form rectangles, either upright or 45 degrees rotated. Here is an example puzzle with a solution:

Ignore the number clues for this challenge.

Challenge

Given a grid with black squares and half-squares placed on some of the cells, determine if it is a valid solution to some Shakashaka puzzle, i.e. all the white regions form rectangles.

The input is a 2D grid (in any valid form) with each cell containing its encoded state. Each cell will be in one of the six states: white square (empty), black square, and four possible orientations of the half-square (NW, NE, SW, SE). You may encode them as six distinct numbers or (possibly multi-dimensional) arrays of numbers, and you can use characters instead of numbers (so strings or string arrays are also acceptable).

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Because it is pretty hard to reproduce a Shakashaka board with Unicode chars, I include a Python script to convert the input to any form of your choice. The default configuration renders them using Unicode geometric shapes, so you can roughly see how the actual grid will look like.

def gentest(tc,mapping,charjoin='',linejoin='\n',preamble='',postamble=''):
  return preamble+linejoin.join(charjoin.join(mapping[x] for x in line.split())for line in tc.strip().splitlines())+postamble

Try it online!

How to use it

tc - the testcase string, which will be supplied in the footer
mapping - the dict of 6 keys 'B', 'W', 'NE', 'NW', 'SE', 'SW' mapped to
          6 distinct strings
          'B' is filled (black) square, 'W' is white square,
          the rest four represent half-cell filled in that direction
charjoin - string to insert between each cell on a horizontal line
linejoin - string to insert between each line of cells
preamble - string to add in front of the entire grid
postamble - string to add at the end of the entire grid

---

Alternatively, you can use this Stack Snippet kindly written by @Arnauld to better visualize the test cases (it shows the 10 test cases by default):

function draw2() { let grids = document.getElementById("in").value.split('\n\n').map(g => g.split('\n').map(r => r.split(/ +/))), out = ""; grids.forEach(g => { out += '<div class="wrapper" style="width:' + g[0].length * 17 + 'px;height:' + g.length * 17 + 'px;">'; g.forEach(r => { r.forEach(s => { out += '<div class="cell"><div class="cell ' + s + '"></div></div>'; }); }); out += '</div>'; }); document.getElementById("out").innerHTML = out;}window.onload = () => { document.getElementById("in").value = [ "NW NE W W B W NW NE NW NE", "SW W NE NW NE B SW SE SW SE", "B SW SE SW SE W NW NE B W", "W NW NE NW NE W SW W NE W", "NW W SE SW SE B W SW SE B", "SW SE B B W W NW NE NW NE", "B NW NE W B NW W SE SW SE", "NW W W NE W SW SE B NW NE", "SW W W SE B NW NE NW W SE", "B SW SE W W SW SE SW SE B", "", "W W W", "W W W", "W W W", "", "NW NE W", "SW SE W", "W W B", "", "B B B", "B B B", "B B B", "", "SE", "", "W NW", "NW W", "", "NW W SE", "", "W NW NE W", "NW W W NE", "SW W B SE", "W SW SE W", "", "B W", "W W", "", "W NW NE B", "NW W W NE", "SW SE SW SE" ].join('\n'); draw2();};

textarea { width: 400px; } #wrapper, .wrapper { border-left: 1px solid #555; border-top: 1px solid #555; margin-top: 10px; } .cell { float: left; width: 16px; height: 16px; border-right: 1px solid #555; border-bottom: 1px solid #555; overflow: hidden; } .NW { width: 0; height: 0; border-right: 16px solid #fff; border-top: 16px solid #00b496; } .SW { width: 0; height: 0; border-right: 16px solid #fff; border-bottom: 16px solid #00b496; } .NE { width: 0; height: 0; border-left: 16px solid #fff; border-top: 16px solid #00b496; } .SE { width: 0; height: 0; border-left: 16px solid #fff; border-bottom: 16px solid #00b496; } .W { width: 16px; height: 16px; } .B { width: 16px; height: 16px; background-color: #000; }

<textarea id="in" oninput="draw2()"></textarea><div id="out"></div>

---

Truthy test cases

# The 10x10 puzzle solution above
NW NE W  W  B  W  NW NE NW NE
SW W  NE NW NE B  SW SE SW SE
B  SW SE SW SE W  NW NE B  W
W  NW NE NW NE W  SW W  NE W
NW W  SE SW SE B  W  SW SE B
SW SE B  B  W  W  NW NE NW NE
B  NW NE W  B  NW W  SE SW SE
NW W  W  NE W  SW SE B  NW NE
SW W  W  SE B  NW NE NW W  SE
B  SW SE W  W  SW SE SW SE B

# all white
W  W  W
W  W  W
W  W  W

# a diamond and some rectangles
NW NE W
SW SE W
W  W  B

# all black
B  B  B
B  B  B
B  B  B

Falsy test cases

# a triangle
SE

# a larger triangle, with a valid white square
W  NW
NW W

# a parallelogram
NW W SE

# a slanted square with a black hole in the middle
W  NW NE W
NW W  W  NE
SW W  B  SE
W  SW SE W

# a region that contains two rectangles but is not a rectangle by itself
B  W
W  W

# same as above, but 45 degrees rotated
W  NW NE B
NW W  W  NE
SW SE SW SE

Answer 1

Python 3.8 (pre-release), 179 bytes

lambda C:all({'','11','1'*4}>={*bin(65793*(a&3|c&12|d&48|b&192)).split("0")[2:-1]}for
i,j in p(C,[0]*len(C[0]))for(a,b),(c,d)in p([*zip(i,j)],(0,0)))
p=lambda l,d:zip([d]+l,l+[d])

Try it online!

mapping={'B': 0, 'W': 255, 'SE': 180, 'SW': 210, 'NW': 75, 'NE': 45}

Mapping visualization:

The numbers are the bit position (least significant bit position is 0). Black has value 0, white has value 1. With this bit order, some simple bitmasking will give the state of the 8 triangles around a corner.

Use the method that I posted in chat.

Other key ideas for golfing:

• 65793 = 0x10101.
• {'','11','1'*4}>={*bin(65793*X).split("0")[2:-1]} checks the condition with X a 8-bit number.

The function p returns the consecutive pairs in the list l, with the added first element (d, l[0]) and last element (l[-1], d).

Answer 2

Python 3, 667 554 526 461 bytes

-49 bytes thanks to @ovs and @pppery

C=eval(input())
N=next
E=enumerate
def F(x,y,f):
 try:1/-~x/-~y;c=C[y][x];(x,y)in v<Q;n[c]+=1;c&f<1<Q;C[y][x]=0;v[:0]=[(x,y)];[c>>i&1and F(x+i%2*(2-i),y+(i-1&~i),1<<(i^2))for i in(0,1,2,3)]
 except:1
while l:=[(x,y)for y,r in E(C)for x,e in E(r)if e]:
 a=0;v=[];n={k:0for k in range(16)};F(*l[0],15);a=len(v)+n[15];(len(v)!=n[15]or(N(M:=map(max,zip(*v)))-N(m:=map(min,zip(*v)))+1)*(N(M)-N(m)+1)!=a/2)and(a!=4*n[6]*n[12]or n[6]!=n[9]or n[3]!=n[12]or n[0]>0)and z

Try it online! (all testcases)

Throws NameError for false and doesn't throw for true.

Golf notes:

• or has a higher precedence than and

Commented, Ungolfed

# bit order of a cell:
# truthy bit if that side is white(opeN)
#   0
# 3   1
#   2

# black: 0
# white: 15
# SE: 9
# SW: 3
# NW: 6
# NE: 12

# helper function to flood fill starting at (x,y)
# passes x,y position
# passes down mutable values
  # visited: array of coordinates visited
  # num_visited: dict counting how many of each cell type have been visited
def flood_solve(case, x, y, coming_from):
    global touched0, white_area, visited, num_visited
    # if out-of-bounds in the positive direction, this will throw
    try: c = case[y][x]
    except: return
    if (x,y) in visited: return
    # maybe can include touched0 into num_visited dict, then del num_visited[0] later
    # Keep track if the white region touches a full-black cell (0)
    touched0 = touched0 or c == 0
    # Check if this new cell is white on the side of the previous cell
    if not c & coming_from: return
    # Turn all visited cells to 0 to avoid flood-filling the same region
    case[y][x] = 0
    # Keep track of which cells are visited
    visited += [(x,y)]
    # Keep track of the counts of NE,NW,SE,and SW cells (3,6,9,12)
    num_visited[c] += 1
    # Keep track of the area of cells visited (1 for full-white, 0.5 for all else)
    if c != 15:
        white_area += 0.5
    else:
        white_area += 1
    # Flood recurse in each direction
    # Call flood_solve on (x,y-1) if (x,y) is white on its top side
    # Whether (x,y-1) is white on its bottom side is determined using coming_from
    if c & 1 and y>0: flood_solve(case, x, y-1, 4)
    if c & 2: flood_solve(case, x+1, y, 8)
    if c & 4: flood_solve(case, x, y+1, 1)
    if c & 8 and x>0: flood_solve(case, x-1, y, 2)
    return(visited, num_visited)


def solve(case):
    global touched0, white_area, visited, num_visited
    touched0 = False
    white_area = 0
    visited = []
    num_visited = {3:0,6:0,9:0,12:0,15:0}
    # Pick a cell with white
    for y,row in enumerate(case):
        for x,e in enumerate(row):
            if e > 0:
                # Floodfill whites from it
                # Pass 15 (0b1111) as coming_from since (x,y) can always be reached
                # Pass case mutably
                visited, num_visited = flood_solve(case, x, y, 15); break
                # (Maybe rectangular checks can be moved here to avoid looping by re-calling solve)
        # flooding always visits at least one cell, so visited is equivalent to the proposition
        # "A cell containing some white has already been found"
        if visited: break
    # Base case: if no white remains, then return True
    if not visited:
        return True
    v = list(zip(*visited))
    # v = [list of x positions visited, list of y positions visited]
    top_left = list(map(min, v))
    bottom_right = list(map(max, v))
    # If only entered all-white cells and area of bounding box of cells entered == area of cells entered:
    if len(visited)==num_visited[15] and (bottom_right[1] - top_left[1] + 1) * (bottom_right[0] - top_left[0] + 1) == white_area:
        # looks like an infinite recursion, but visited cells are replaced with 0 in flood_solve
        return solve(case)
    # If touched an all-black cell, can't be an angled rectangle, since angled rectangles only have angled sides
    if touched0:
        return
    n = num_visited
    # Should have #(NW entered)=#(SE entered) and #(NE)=#(SW)
    # (is this check redundant with the next area check? Maybe the area check can be rearranged by using area<=2*(perimeter/2)^?)
    if not n[6] == n[9] or not n[3] == n[12]:
        return
    if 2*n[6]*n[12] == white_area:
        # Success! it's an angled rectangle
        return solve(case)

Pseudo-code algorithm

• Start
• Pick a cell with white; floodfill whites from it
  • (Base case: if no white remains, then return True)
  • While floodfilling:
    • Keep track of which cells are visited
    • Keep track of the counts of cells
    • Keep track if the white region touches a full-black cell (0)
    • Keep track of the area of cells visited (1 for full-white, 0.5 for all else)
    • Turn all visited cells to 0 to avoid flood-filling the same region
• If only entered all-white cells and area of bounding box of cells entered == area of cells entered:
  • Success! it's an upright rectangle.
  • GOTO Start; use the updated case (all visited cells turned black)
• If touched an all-black cell
  • Can't be an angled rectangle, since angled rectangles only have angled sides
  • return False
• Should have #(NW enetered)=#(SE entered) and #(NE)=#(SW) (is this check redundant with the next area check?)
• Each NW cell contributes sqrt(2) to the length of the NW side of the rectangle
• Each NE cell contributes sqrt(2) to the length of the NE side of the rectangle
• If area == 2*#(NW)*#(NE):
  • Success! it's an angled rectangle
  • GOTO Start; use the updated case (all visited cells turned black) White region filled can't be angled or upright rectangle anymore return False