Tatamibari求解器

Question

背景

塔塔米巴里是尼可利设计的一个逻辑难题。

Tatamibari拼图在一个矩形网格上进行，其中包含三种不同的符号：+、-。和|。求解者必须根据以下规则将网格划分为矩形或方形区域：

• 每个分区必须精确地包含一个符号。
• +符号必须包含在正方形中。
• |符号必须包含在高度大于宽度的矩形中。
• -符号必须包含在宽度大于高度的矩形中。
• 四块可能永远不会共用一个角落。(这就是日本的纹身砖通常被放置的方式。)

下面是一个示例谜题，并给出了解决方案：

任务

解开塔塔米巴里的谜题。

输入输出

输入是一个2D网格，表示给定的Tatamibari拼图。每个单元格包含四个字符中的一个：+、-、|和您选择的表示无线索单元格的字符。在测试用例中，使用星号*。

您可以选择任何合适的输出格式，这些格式可以明确地表示对Tatamibari难题的任何有效解决方案。这包括，但不限于：(如果有疑问，请发表评论)。

• 4元组的列表，其中每个元组包括矩形的顶部索引、左索引、宽度和高度(或任何等效的表示)。
• 与输入的形状相同的数字网格，其中每个数字表示一个矩形。
• 一个坐标集列表，其中每个集合包含矩形中单元格的所有坐标。

如果一个难题有多个解决方案，则可以输出其有效解决方案中的任意数目(一个或多个)。保证输入至少有一个解决方案。

测试用例

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

规则

适用标准的密码-高尔夫规则。以字节为单位的最短代码获胜。

Answer 1

J，193个字节

以-1，-2…作为网格返回所有可能的解决方案。指示室。还有改进的余地，但((((((开始让我感到困惑。:-)

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

对于更大的测试用例，我提供了在网上试试！，它为中间步骤提供了一个过滤器[:(#~1*@#.|@,"2)，在中间步骤中，由于填充而添加了空网格。

是如何工作的

• '*+-|' … i.]映射*+-|到0 1 2 3。
• 来自所有瓷砖的,/@(#:i.)@$
• [(#~0<:,)~不是房间的一部分，
• {.([,:-~)"1/>:从最左上角的瓷砖开始，这还不是房间的一部分，尝试每一个可能的矩形向下跨越-右。
• …"2#]使该矩形对下一步有效，
• [:*/0<1{] 0.)它必须在每个维度上都有一个正的大小。
• ( 0({.*(1=#)*0<{.)@-.~, 1.)任何瓷砖都不能是房间的一部分。一个符号必须在矩形内，
• ( (({(0,=/,/)@$)~ 3.)矩形的尺寸满足符号的约束。
• (<./@,@:<:@[[[}{.<@:+"1,/@(#:i.)@{:)"2]对于每个有效的矩形，复制当前网格并放置下一个房间。
• ^:(1#.*@,)@,:我们需要做这个n时间，其中n是符号的数量。
• 在此之后，[:(#~0=0(e.,)"2])可能会有带有n房间的网格，但仍然是空的；这些必须被过滤掉。