Hintergrund

Tatamibari ist ein logisches Puzzle, das von Nikoli entworfen wurde.

Ein Tatamibari-Puzzle wird auf einem rechteckigen Gitter mit drei verschiedenen Arten von Symbolen gespielt: +, -. und |. Der Löser muss das Raster gemäß den folgenden Regeln in rechteckige oder quadratische Bereiche unterteilen:

• Jede Partition muss genau ein Symbol enthalten.
• Ein +Symbol muss in einem Quadrat enthalten sein.
• Ein |Symbol muss in einem Rechteck mit einer größeren Höhe als Breite enthalten sein.
• Ein -Symbol muss in einem Rechteck mit einer größeren Breite als Höhe enthalten sein.
• Vier Teile dürfen niemals dieselbe Ecke teilen. (So ​​werden japanische Tatami-Kacheln normalerweise platziert.)

Das Folgende ist ein Beispielrätsel mit einer Lösung:

Aufgabe

Löse das gegebene Tatamibari-Rätsel.

Input-Output

Die Eingabe ist ein 2D-Raster, das das gegebene Tatamibari-Puzzle darstellt. Jede Zelle enthält eine der vier Zeichen: +, -, |, und ein Zeichen Ihrer Wahl eine nicht-clue Zelle darzustellen. In den Testfällen wird ein Sternchen *verwendet.

Sie können ein geeignetes Ausgabeformat auswählen, das eindeutig eine gültige Lösung für ein Tatamibari-Puzzle darstellt. Dies beinhaltet, ist aber nicht beschränkt auf: (Wenn Sie Zweifel haben, fragen Sie in Kommentaren.)

• Eine Liste von 4 Tupeln, wobei jedes Tupel den oberen Index, den linken Index, die Breite und Höhe eines Rechtecks ​​(oder eine gleichwertige Darstellung) enthält.
• Ein numerisches Raster mit der gleichen Form wie die Eingabe, wobei jede Zahl ein Rechteck darstellt
• Eine Liste von Koordinatensätzen, wobei jeder Satz alle Koordinaten der Zellen in einem Rechteck enthält

Wenn ein Puzzle mehrere Lösungen hat, können Sie eine beliebige Anzahl (eine oder mehrere) seiner gültigen Lösungen ausgeben. Die Eingabe hat garantiert mindestens eine Lösung.

Testfälle

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

Regeln

Es gelten die Standardregeln für Code-Golf . Der kürzeste Code in Bytes gewinnt.

Python 2 , 417 374 366 Bytes

Die Eingabe ist eine Liste von Zeilen, die ~keine Ahnung haben. Gibt eine einzelne Lösung für stderr im Format aus (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)]

Probieren Sie es online aus! Dies ist für die vorgeschlagenen Testfälle zu ineffizient.

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)]

Probieren Sie es online aus!