Lengkapi jalan yang mengisi kisi-kisi

18

Berliku kisi-kisi adalah jalur tertutup yang mengunjungi setiap sel dari kisi kisi sekurang-kurangnya satu kali, tidak pernah melintasi tepi antara sel yang berdekatan lebih dari satu kali dan tidak pernah melintasi dirinya sendiri. Sebagai contoh:N×N

Setelah diisi, setiap sel dari grid dapat diwakili oleh salah satu dari 8 ubin berikut:

Dengan penomoran seperti ini, ubin-ubin berliku di atas dapat diwakili oleh matriks ini:

5 6 5 6
4 8 3 2
5 7 6 2
4 3 4 3

Tugas Anda adalah untuk menyelesaikan jalan yang berliku-liku pada grid yang diberikan set ubin yang tidak lengkap. Misalnya, berliku-liku yang tidak lengkap:

... yang dapat direpresentasikan menggunakan 0s untuk ubin yang hilang:

5 0 0 0 6
0 0 7 0 0
0 0 0 0 3
2 4 0 0 0
0 0 3 0 0

... dapat diselesaikan seperti ini:

...yaitu:

5 6 5 1 6
4 8 7 6 2
5 7 7 7 3
2 4 8 8 6
4 1 3 4 3

Spesifikasi

  • Input akan selalu memiliki paling tidak dan paling banyak ubin (tidak kosong), di mana .1N22N7
  • Anda dapat menggunakan set nilai apa pun untuk mewakili ubin, selama itu ditentukan dalam jawaban Anda.
  • Input dan output Anda mungkin dalam format dan urutan apa pun, selama itu ditentukan dalam jawaban Anda.
  • Setidaknya satu solusi yang valid akan ada untuk semua input (yaitu Anda tidak perlu menangani input yang tidak valid).
  • Aturan I / O standar berlaku.
  • Celah standar dilarang.
  • Penjelasan, bahkan untuk bahasa "praktis", dianjurkan.

Uji kasus

Input ( Θ ):

0 6
0 0

Output ( Θ ):

5 6
4 3

Input ( Θ ):

5 6 5 6
4 0 3 2
5 7 6 2
4 3 4 3

Output ( Θ ):

5 6 5 6
4 8 3 2
5 7 6 2
4 3 4 3

Input ( Θ ):

5 0 0 0 6
0 0 7 0 0
0 0 0 0 3
2 4 0 0 0
0 0 3 0 0

Output ( Θ ):

5 6 5 1 6
4 8 7 6 2
5 7 7 7 3
2 4 8 8 6
4 1 3 4 3
Yordania
sumber
1
@Arnauld Anda benar; itu tidak valid. Jalan berliku adalah jalan tertutup tunggal.
Jordan
1
@Arnauld Terima kasih, saya telah melakukan perubahan itu. Saya tidak menyadari MathJax diaktifkan di situs ini!
Jordan

Jawaban:

11

JavaScript (ES7),  236 ... 193  185 byte

Output dengan memodifikasi matriks input.

m=>(g=(d,x,y,v,r=m[y],h=_=>++r[x]<9?g(d,x,y,v)||h():r[x]=0)=>r&&1/(n=r[x])?x|y|!v?n?g(d='21100--13203-32-21030321'[n*28+d*3+7&31],x+--d%2,y+--d%2,v+=n<7||.5):h():!m[v**.5|0]:0)(0,0,0,0)

Cobalah online!

(termasuk beberapa kode pasca pemrosesan untuk mencetak hasilnya baik sebagai matriks dan sebagai daftar datar yang kompatibel dengan alat visualisasi yang disediakan oleh OP)

Hasil

Bagaimana?

Variabel

gd(x,y)v

g

  • r

    r = m[y]
  • h18gg0

    h = _ => ++r[x] < 9 ? g(d, x, y, v) || h() : r[x] = 0

Pemeriksaan awal

n

r && 1 / (n = r[x]) ? ... ok ... : ... failed ...

(0,0)v>0

x | y | !v ? ... no ... : ... yes ...

Untuk sekarang, mari kita asumsikan bahwa kita tidak kembali ke titik awal.

Mencari jalan

n0h

n0

ndd

d = '21100--13203-32-21030321'[n * 28 + d * 3 + 7 & 31]

8 entri terakhir tidak valid dan dihilangkan. 4 entri yang tidak valid lainnya secara eksplisit ditandai dengan tanda hubung.

Untuk referensi, di bawah ini adalah tabel yang diterjemahkan, kompas dan ubin-set yang disediakan dalam tantangan:

   | 1 2 3 4 5 6 7 8
---+-----------------
 0 | 0 - - 1 3 - 3 1          1
 1 | - 1 - - 2 0 2 0        0 + 2
 2 | 2 - 1 - - 3 1 3          3
 3 | - 3 0 2 - - 0 2

g1/2v781

g(d, x + --d % 2, y + --d % 2, v += n < 7 || .5)

dxy

Memvalidasi jalur

(0,0)v>0

781/2v

v=N2v>N2v<N2kk=v

Karena itu kode JS:

!m[v ** .5 | 0]

Sumber yang diformat

m => (
  g = (
    d,
    x, y,
    v,
    r = m[y],
    h = _ => ++r[x] < 9 ? g(d, x, y, v) || h() : r[x] = 0
  ) =>
    r && 1 / (n = r[x]) ?
      x | y | !v ?
        n ?
          g(
            d = '21100--13203-32-21030321'[n * 28 + d * 3 + 7 & 31],
            x + --d % 2,
            y + --d % 2,
            v += n < 7 || .5
          )
        :
          h()
      :
        !m[v ** .5 | 0]
    :
      0
)(0, 0, 0, 0)
Arnauld
sumber
Kerja bagus. Saya ingin membaca penjelasan kode.
Jordan
@Arnauld apakah Anda memaksa atau menggunakan algoritma lain?
Jonah
1
@Jonah saya sedang menulis penjelasan. Pada dasarnya, ya, ini adalah pendekatan brute-force tetapi algoritma backtracks segera setelah beberapa inkonsistensi terdeteksi daripada mencoba setiap papan yang mungkin.
Arnauld