Labirin pada kisi-kisi sel kotak N oleh N ditentukan dengan menentukan apakah setiap tepi adalah dinding atau bukan dinding. Semua tepi luar adalah dinding. Satu sel didefinisikan sebagai awal , dan satu sel didefinisikan sebagai pintu keluar , dan pintu keluar dapat dijangkau dari awal. Mulai dan keluar tidak pernah sel yang sama.
Perhatikan bahwa baik start maupun jalan keluar tidak perlu berada di perbatasan luar labirin, jadi ini adalah labirin yang valid:
String 'N', 'E', 'S' dan 'W' menunjukkan upaya untuk memindahkan Utara, Timur, Selatan dan Barat masing-masing. Langkah yang diblokir oleh dinding dilewati tanpa gerakan. Sebuah string keluar dari maze jika menerapkan string itu dari awal menghasilkan keluar yang dicapai (terlepas dari apakah string berlanjut setelah mencapai keluar).
Terinspirasi oleh pertanyaan yang membingungkan. SE yang xnor menyediakan metode penyelesaian yang dapat dibuktikan dengan string yang sangat panjang, tulis kode yang dapat menemukan string tunggal yang keluar dari labirin 3 dengan 3.
Tidak termasuk labirin yang tidak valid (mulai dan keluar pada sel yang sama, atau keluar tidak dapat dijangkau dari awal) ada 138.172 labirin yang valid dan string harus keluar masing-masing.
Keabsahan
String harus memenuhi yang berikut ini:
- Ini terdiri dari hanya karakter 'N', 'E', 'S' dan 'W'.
- Itu keluar dari setiap labirin itu diterapkan, jika dimulai pada awal.
Karena himpunan semua labirin yang mungkin termasuk setiap labirin mungkin dengan setiap kemungkinan titik awal yang valid, ini secara otomatis berarti bahwa string akan tutup semua labirin dari setiap titik awal yang valid. Yaitu, dari titik awal mana titik keluar dapat dicapai.
Kemenangan
Pemenangnya adalah jawaban yang memberikan string valid terpendek dan termasuk kode yang digunakan untuk memproduksinya. Jika lebih dari satu jawaban memberikan string dengan panjang terpendek ini, yang pertama memposting panjang string yang menang.
Contoh
Berikut adalah contoh string 500 karakter yang panjang, untuk memberi Anda sesuatu untuk dikalahkan:
SEENSSNESSWNNSNNNNWWNWENENNWEENSESSNENSESWENWWWWWENWNWWSESNSWENNWNWENWSSSNNNNNNESWNEWWWWWNNNSWESSEEWNENWENEENNEEESEENSSEENNWWWNWSWNSSENNNWESSESNWESWEENNWSNWWEEWWESNWEEEWWSSSESEEWWNSSEEEEESSENWWNNSWNENSESSNEESENEWSSNWNSEWEEEWEESWSNNNEWNNWNWSSWEESSSSNESESNENNWEESNWEWSWNSNWNNWENSNSWEWSWWNNWNSENESSNENEWNSSWNNEWSESWENEEENSWWSNNNNSSNENEWSNEEWNWENEEWEESEWEEWSSESSSWNWNNSWNWENWNENWNSWESNWSNSSENENNNWSSENSSSWWNENWWWEWSEWSNSSWNNSEWEWENSWENWSENEENSWEWSEWWSESSWWWNWSSEWSNWSNNWESNSNENNSNEWSNNESNNENWNWNNNEWWEWEE
Terima kasih orlp untuk menyumbang ini.
Papan peringkat
Skor yang sama tercantum dalam urutan posting skor itu. Ini belum tentu urutan jawaban yang diposting karena skor untuk jawaban yang diberikan dapat diperbarui dari waktu ke waktu.
Hakim
Berikut ini adalah validator Python 3 yang mengambil string NESW sebagai argumen baris perintah atau melalui STDIN.
Untuk string yang tidak valid, ini akan memberi Anda contoh visual dari labirin yang gagal untuknya.
sumber
Jawaban:
C ++,
979593918683828179 karakterStrategi saya cukup sederhana - sebuah algoritma evolusi yang dapat menumbuhkan, mengecilkan, menukar elemen, dan mengubah urutan yang valid. Logika evolusi saya sekarang hampir sama dengan @ Sp3000, karena itu adalah peningkatan dari saya.
Namun, implementasi saya pada labirin logika agak bagus. Ini memungkinkan saya untuk memeriksa apakah string valid pada kecepatan blistering. Cobalah untuk mencari tahu dengan melihat komentar,
do_move
danMaze
konstruktornya.sumber
do_move
sekarang sangat cepat.Python 3 + PyPy,
8280 karakterSaya ragu-ragu untuk memposting jawaban ini karena saya pada dasarnya telah mengambil pendekatan orlp dan menempatkan putaran saya sendiri di atasnya. String ini ditemukan dengan memulai dengan solusi pseudorandom panjang 500 - cukup banyak benih yang dicoba sebelum saya dapat memecahkan rekor saat ini.
Satu-satunya optimasi utama baru adalah bahwa saya hanya melihat sepertiga dari labirin. Dua kategori labirin dikecualikan dari pencarian:
<= 7
kotak dapat dijangkauIdenya adalah bahwa setiap string yang memecahkan sisa labirin juga harus menyelesaikan hal di atas secara otomatis. Saya yakin ini benar untuk tipe kedua, tetapi jelas tidak benar untuk tipe pertama, sehingga output akan mengandung beberapa false positive yang perlu diperiksa secara terpisah. Ini positif palsu biasanya hanya kehilangan sekitar 20 labirin, jadi saya pikir itu akan menjadi tradeoff yang baik antara kecepatan dan akurasi, dan itu juga akan memberi string sedikit lebih banyak ruang bernapas untuk bermutasi.
Awalnya saya membaca daftar panjang heuristik pencarian, tetapi secara mengerikan tidak ada satupun yang menghasilkan lebih dari 140 atau lebih.
sumber
0
untukn
sepanjang jalan dan kira bahwa stringS
membuat Anda dari0
ken
. KemudianS
juga membawa Anda dari sel perantarac
ken
. Misalkan sebaliknya. Membiarkana(i)
menjadi posisi setelahi
langkah-langkah mulai0
danb(i)
mulaic
. Kemudiana(0) = 0 < b(0)
, setiap langkah berubaha
danb
paling banyak 1, dana(|S|) = n > b(|S|)
. Ambil yang terkecilt
seperti itua(t) >= b(t)
. Jelasa(t) != b(t)
atau mereka akan sinkron, sehingga mereka harus bertukar tempat pada langkaht
dengan bergerak ke arah yang sama.C ++ dan perpustakaan dari lingeling
Dengan menggunakan pendekatan berbasis SAT , saya benar-benar bisa menyelesaikan masalah yang sama untuk labirin 4x4 dengan sel yang diblokir alih-alih dinding tipis dan tetap memulai dan keluar posisi di sudut yang berlawanan. Jadi saya berharap bisa menggunakan ide yang sama untuk masalah ini. Namun, meskipun untuk masalah lain saya hanya menggunakan 2.423 labirin (sementara itu telah mengamati bahwa 2083 sudah cukup) dan memiliki solusi panjang 29, pengkodean SAT menggunakan jutaan variabel dan menyelesaikannya butuh berhari-hari.
Jadi saya memutuskan untuk mengubah pendekatan dengan dua cara penting:
Saya juga melakukan beberapa optimasi untuk menggunakan lebih sedikit variabel dan klausa unit.
Program ini didasarkan pada @ orlp's. Perubahan penting adalah pemilihan labirin:
is_solution
memeriksa apakah semua posisi yang dapat dijangkau tercapai.Dengan cara ini, saya mendapatkan total 1.0772 labirin dengan posisi awal.
Inilah programnya:
Pertama
configure.sh
danmake
yanglingeling
solver, kemudian kompilasi program dengan sesuatu sepertig++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgl
, di mana...
merupakan jalan manalglib.h
resp.liblgl.a
adalah, jadi keduanya bisa jadi misalnya../lingeling-<version>
. Atau cukup taruh di direktori yang sama dan lakukan tanpa opsi-I
dan-L
.Program ini memakan waktu satu wajib argumen baris perintah, string yang terdiri dari
N
,E
,S
,W
(untuk arah tetap) atau*
. Jadi Anda bisa mencari solusi umum ukuran 78 dengan memberikan string 78*
detik (dalam tanda kutip), atau mencari solusi yang dimulai denganNEWS
menggunakanNEWS
diikuti oleh sebanyak yang*
Anda inginkan untuk langkah-langkah tambahan. Sebagai tes pertama, ambil solusi favorit Anda dan ganti beberapa huruf dengan*
. Ini menemukan solusi cepat untuk nilai "beberapa" yang sangat tinggi.Program ini akan memberi tahu labirin mana yang ditambahkan, dijelaskan oleh struktur dinding dan posisi awal, dan juga memberikan jumlah posisi dan dinding yang dapat dijangkau. Labirin diurutkan berdasarkan kriteria ini, dan yang pertama tidak terpecahkan ditambahkan. Karena itu, kebanyakan labirin yang ditambahkan memiliki
(9/4)
, tetapi terkadang labirin lain juga muncul.Saya mengambil solusi yang diketahui panjang 79, dan untuk setiap kelompok 26 huruf yang berdekatan, mencoba untuk menggantinya dengan 25 huruf. Saya juga mencoba menghapus 13 huruf dari awal dan dari akhir, dan menggantinya dengan 13 di awal dan 12 di akhir, dan sebaliknya. Sayangnya, semua itu tidak memuaskan. Jadi, dapatkah kita menganggap ini sebagai indikator bahwa panjang 79 optimal? Tidak, saya juga mencoba meningkatkan solusi panjang ke panjang 79, dan itu juga tidak berhasil.
Akhirnya, saya mencoba menggabungkan awal dari satu solusi dengan ujung yang lain, dan juga dengan satu solusi yang ditransformasikan oleh salah satu simetri. Sekarang saya kehabisan ide menarik, jadi saya memutuskan untuk menunjukkan kepada Anda apa yang saya miliki, meskipun itu tidak mengarah pada solusi baru.
sumber