# Tatamibari solver

## Background

Tatamibari is a logic puzzle designed by Nikoli.

A Tatamibari puzzle is played on a rectangular grid with three different kinds of symbols in it: +, -. and |. The solver must partition the grid into rectangular or square regions according to the following rules:

• Every partition must contain exactly one symbol in it.
• A + symbol must be contained in a square.
• A | symbol must be contained in a rectangle with a greater height than width.
• A - symbol must be contained in a rectangle with a greater width than height.
• Four pieces may never share the same corner. (This is how Japanese tatami tiles are usually placed.)

The following is an example puzzle, with a solution:

Solve the given Tatamibari puzzle.

## Input & output

The input is a 2D grid that represents the given Tatamibari puzzle. Each cell contains one of the four characters: +, -, |, and a character of your choice to represent a non-clue cell. In the test cases, an asterisk * is used.

You can choose any suitable output format which can unambiguously represent any valid solution to a Tatamibari puzzle. This includes, but is not limited to: (if in doubt, ask in comments.)

• A list of 4-tuples, where each tuple includes the top index, left index, width and height of a rectangle (or any equivalent representation)
• A numeric grid of the same shape as the input, where each number represents a rectangle
• A list of coordinate sets, where each set includes all the coordinates of the cells in a rectangle

If a puzzle has multiple solutions, you can output any number (one or more) of its valid solutions. The input is guaranteed to have at least one solution.

## Test cases

Puzzle:
|-*
*+|
*-*
Solution:
122
134
554
=====
Puzzle:
+***
**|*
*+**
***-
Solution:
1122
1122
3322
3344
======
Puzzle:
|*+*+
*****
****-
***+|
+****
Solution:
12233
12233
44444
55667
55667
=======
Puzzle:
****-**
**-**|*
*|*****
****-**
*******
**+*|**
*****+*
One possible solution:
1122222
1133344
1155544
1155544
6667744
6667788
6667788
===========
Puzzle:
*-****|+**
+*-******|
****+*****
*-******||
**++|*****
+****-|***
-****-**+*
********-*
|*+*+|****
*-*--**+*+
Solution:
1111122334
5666622334
7777822994
7777A2299B
CCDEA2299B
CCFFFFGGHH
IIIIJJGGHH
KLLMMNGGOO
KLLMMNGGPP


## Rules

Standard rules apply. The shortest code in bytes wins.

# Python 2, 417374 366 bytes

Input is list of lines, ~ for non-clue. Outputs a single solution to stderr in the format (x_start, width, y_start, height).

R=range
k=input()
X,Y=len(k[0]),len(k)
W,H=R(X),R(Y)
Q=[[]]
for q in Q:C=[(x,y)for(a,b,c,d)in q for x in(a,a+b)for y in(c,c+d)];max(map(C.count,C+W))<4>0<all(sum(w>x-s>-1<y-t<h<[c for r in k[t:t+h]for c in r[s:s+w]if'~'>c]==['+|-'[cmp(h,w)]]for(s,w,t,h)in q)==1for x in W for y in H)>exit(q);Q+=[q+[(s,w+1,t,h+1)]for s in W for w in R(X-s)for t in H for h in R(Y-t)]


Try it online! This is too inefficient for the suggested test cases.

## Ungolfed

grid = input()
total_width = len(grid[0])
total_height = len(grid)

partitions = [[]]

for partition in partitions:
# list the corners of all rectangles in the current partition
corners = [(x, y)
for (start_x, width, start_y, height) in partition
for x in (start_x, start_x + width)
for y in (start_y, start_y + height)]
# if no corners appears more than three times ...
if corners != [] and max(map(corners.count, corners)) < 4:
# .. and all fields are covered by a single rectangle ...
if all(
sum(width > x - start_x > -1 < y - start_y < height
for (start_x, width, start_y, height) in partition) == 1
for x in range(total_width)
for y in range(total_height)):
# ... and all rectangles contain a single non-~
# symbol that matches their shape:
if all(
[char for row in grid[start_y: start_y + height]
for char in row[start_x:start_x + width] if '~' > char]
== ['+|-'[cmp(height, width)]]
for (start_x, width, start_y, height) in partition):
# output the current partition and stop the program
exit(partition)

# append each possible rectangle in the grid to the current partition,
# and add each new partition to the list of partitions.
partitions += [partition + [(start_x, width + 1, start_y, height + 1)]
for start_x in range(total_width)
for width in range(total_width - start_x)
for start_y in range(total_height)
for height in range(total_height - start_y)]



Try it online!