Saya sangat suka menggeser puzzle ubin, tetapi baru-baru ini, saya belum punya waktu untuk itu. Oleh karena itu, saya memerlukan program untuk memberi saya perbaikan teka-teki geser ubin, khususnya teka-teki Klotski.
Masukan Anda akan dalam format berikut:
#######
#001gg#
##.222#
.######
di mana #
mewakili dinding, .
mewakili area terbuka, g
mewakili tujuan, dan angka yang berdekatan mewakili blok yang berbeda. Anda dapat mengasumsikan bahwa:
- Tidak akan lebih dari 10 blok
- Tidak akan ada dua blok dengan nomor yang sama
- Semua blok akan ditutup oleh dinding
- Grid berbentuk persegi panjang
- The
0
blok cukup besar untuk menutup semua kotak gawang. - Ada solusi yang valid
Anda harus mengembalikan urutan gerakan yang akan menempatkan 0
blok sehingga mencakup semua kotak sasaran. Blok tidak bisa melewati dinding atau blok lainnya. Untuk teka-teki di atas, urutan yang tepat adalah
2L,1R,1R,1D,0R,0R,0R
sementara mewakili memindahkan 2
blok 1 persegi kiri, 1
blok 2 kotak kanan (di atas gawang) kemudian 1 persegi bawah, dan kemudian 0
blok 3 kotak kanan.
Sebenarnya ada beberapa urutan yang akan bekerja untuk masalah di atas, dan menghasilkan salah satu dari mereka dapat diterima. Solusi Anda harus optimal, artinya harus menghasilkan urutan yang memecahkan teka-teki sesedikit mungkin langkah.
Urutan harus dicetak seperti di atas, tetapi dapat berupa koma, baris baru, atau spasi terpisah. Saya tidak peduli jika ada tanda koma atau spasi. Anda harus menghasilkan output dalam waktu yang wajar (maksimum 120 detik pada teka-teki di bawah).
Teka-teki 1:
..####..
..#00#..
###00###
#......#
#.1122.#
##3124##
.#3344#.
.##55##.
..#gg#..
..####..
Teka-teki 2:
######
#1002#
#1002#
#3445#
#3675#
#8gg9#
######
Teka-teki 3:
.####.
##1g##
#22g3#
#4255#
#4.56#
#.006#
#7008#
######
Teka-teki 4:
.####.
##00##
#.00g#
#.0.1#
#..g2#
######
Ini adalah kode-golf, jadi solusi terpendek (dalam byte) menang!
sumber
Jawaban:
Python, 1761
Agak lelah dengan pertanyaan ini, jadi saya tidak bisa bermain golf. Apa pun itu, sekarang ini satu-satunya solusi yang menyelesaikan semuanya dalam batas waktu (terpanjang, # 3, membutuhkan waktu 27 detik).
sumber
JavaScript (ES6), 446
388Breadth First Search, jadi solusi pertama yang ditemukan adalah yang terpendek.
Meskipun saya masih berpikir itu solusi yang baik, itu tidak cukup baik. Bahkan setelah memeriksa jutaan posisi (runtime beberapa menit), saya tidak dapat menemukan solusi misalnya 2 dan 3.
Edit versi modifikasi ES6 untuk mengatasi batas waktu eksekusi javascript. Puzzle 3 diselesaikan dalam 7 menit, 145 langkah. Puzzle 2 dipecahkan dalam 10 menit, 116 langkah
Edit 2 speedup besar, menggunakan ide @ orlp untuk mempertimbangkan sama dengan dua blok dengan bentuk yang sama (tidak termasuk blok '0' yang khusus). Ini mengurangi ruang posisi yang dikunjungi selama BSF. Misalnya, untuk puzzle 2, posisi apa pun dengan blok 1,2,3 atau 5 yang ditukar benar-benar sama.
Pengaturan waktu: yang terpanjang adalah puzzle 3, ~ 20 detik di laptop saya.
Gunakan Firefox untuk bermain dengan JsFiddle baru untuk menguji.
Ketinggalan jaman
EcmaScript 6 (FireFox) JSFiddleEcmaScript 5 (Chrome) JSFiddleContoh
Teka-teki 1
Teka-teki 2
Teka-teki 3
Teka-teki 4
sumber