11
\$\begingroup\$

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:

Example Tatamibari puzzle Example Tatamibari puzzle solution

Task

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
QQRRSSSTPP

Rules

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
5
\$\begingroup\$

Python 2, 417 374 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!

\$\endgroup\$
0
2
\$\begingroup\$

J, 193 bytes

Returns all possible solutions as grids with -1, -2 … indicating rooms. There is room for improvements, but the (((((( started to confuse me. :-)

[:(#~0=0(e.,)"2])'*+-|'([:,/(([(<./@,@:<:@[`]`[}{.<@:+"1,/@(#:i.)@{:)"2((((({(0,=/,</,>/)@$)~0({.*(1=#)*0<{.)@-.~,);.0~*[:*/0<1{])"2#]){.([,:-~)"1/>:))[(#~0<:,)~,/@(#:i.)@$)"2)^:(1#.*@,)@,:@i.]

Try it online! For the larger test cases I provided ff that has a filter [:(#~1*@#.|@,"2) for intermediate steps, where empty grids got added because of padding.

How it works

  • '*+-|' … i.] Map *+-| to 0 1 2 3.
  • ,/@(#:i.)@$ From all the tiles
  • [(#~0<:,)~ that aren't part of a room,
  • {.([,:-~)"1/>: starting from the most top-left tile, that isn't part of a room yet, try every possible rectangle spanning down-right.
  • …"2#] For that rectangle to be valid for the next step,
  • [:*/0<1{] 0.) it must have a positive size in each dimension
  • 0({.*(1=#)*0<{.)@-.~, 1.) no tile must be part of a room, 2.) exactly one symbol must be within the rectangle,
  • (({(0,=/,</,>/)@$)~ 3.) the dimension of the rectangle fulfill the constraint of the symbol.
  • (<./@,@:<:@[][}{.<@:+"1,/@(#:i.)@{:)"2 For every valid rectangle, copy the current grid and place the next room.
  • ^:(1#.*@,)@,: We need to do this n times, where n is the number of symbols.
  • [:(#~0=0(e.,)"2]) After this there might be grids that have n rooms, but still empty tiles; those must be filtered out.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.