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:
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 code-golf rules apply. The shortest code in bytes wins.