Pemecah tatamibari

10

Latar Belakang

Tatamibari adalah teka-teki logika yang dirancang oleh Nikoli.

Teka-teki Tatamibari dimainkan pada kotak persegi panjang dengan tiga jenis simbol yang berbeda di dalamnya: +, -. dan |. Pemecah harus mempartisi kisi-kisi menjadi daerah persegi panjang atau persegi sesuai dengan aturan berikut:

  • Setiap partisi harus mengandung tepat satu simbol di dalamnya.
  • Sebuah +simbol harus terkandung dalam persegi.
  • Sebuah |simbol harus terkandung dalam sebuah persegi panjang dengan tinggi lebih besar dari lebar.
  • Sebuah -simbol harus terkandung dalam sebuah persegi panjang dengan lebar lebih besar dari ketinggian.
  • Empat potong mungkin tidak pernah berbagi sudut yang sama. (Beginilah biasanya ubin tatami Jepang ditempatkan.)

Berikut ini adalah contoh puzzle, dengan solusinya:

Contoh puzzle Tatamibari Contoh solusi puzzle Tatamibari

Tugas

Pecahkan puzzle Tatamibari yang diberikan.

Input output

Inputnya adalah kisi 2D yang mewakili puzzle Tatamibari yang diberikan. Setiap sel berisi salah satu dari empat karakter: +, -, |, dan karakter pilihan Anda untuk mewakili sel non-petunjuk. Dalam kasus uji, tanda bintang *digunakan.

Anda dapat memilih format output yang sesuai yang dapat secara jelas menunjukkan solusi valid untuk puzzle Tatamibari. Ini termasuk, tetapi tidak terbatas pada: (jika ragu, tanyakan komentar.)

  • Daftar 4-tupel, di mana masing-masing tupel termasuk indeks atas, indeks kiri, lebar dan tinggi persegi panjang (atau representasi yang setara)
  • Kotak numerik dengan bentuk yang sama dengan input, di mana setiap angka mewakili persegi panjang
  • Daftar set koordinat, di mana setiap set menyertakan semua koordinat sel dalam persegi panjang

Jika sebuah teka-teki memiliki beberapa solusi, Anda dapat menampilkan nomor berapa saja (satu atau lebih) dari solusi yang valid. Input dijamin memiliki setidaknya satu solusi.

Uji kasus

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

Aturan

Aturan standar berlaku. Kode terpendek dalam byte menang.

Bubbler
sumber

Jawaban:

5

Python 2 , 417 374 366 byte

Input adalah daftar baris, ~untuk non-petunjuk. Menghasilkan satu solusi untuk stderr dalam 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)]

Cobalah online! Ini terlalu tidak efisien untuk kasus uji yang disarankan.


Tidak disatukan

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

Cobalah online!

ovs
sumber