Kuis tentang perjalanan ksatria | juliablogger.com – Beragampengetahuan

Oleh: Blog Bogumił Kamiński

Repost dari:

Sebelum saya mulai, saya ingin membuat pengumuman kecil. Jika Anda tertarik
dalam bahasa Julia, Anda dipersilakan untuk berpartisipasi dalam “Pengantar” selama 4 hari
to Julia for Data Science” yang akan diadakan di MIT 17-20 Januari 2023.
Semua orang diundang. Anda dapat menemukan PDF dengan jadwal di sini.

Sekarang kita bisa kembali ke bisnis blogging kita yang biasa.

Setelah posting saya baru-baru ini tentang kuis inklusi ksatria, saya ditanyai
konten pemecahan teka-teki lainnya. Jadi hari ini saya ingin memperkenalkan kepada Anda
bagaimana masalah perjalanan Ksatria dapat diselesaikan dengan menggunakan Julia.

Kode dalam posting ini telah diuji terhadap Julia 1.8.2 dan Plots.jl 1.35.0.

Pertimbangkan kisi persegi panjang. Kami menempatkan seorang ksatria catur di salah satu kotak di atas
jaringan ini. Satu bagian dapat memindahkan dua kotak secara vertikal dan satu kotak
secara horizontal, atau dua kotak secara horizontal dan satu kotak secara vertikal.

Kami ingin menemukan urutan gerakan seorang ksatria sehingga melewati masing-masing
persegi di grid tepat satu kali dan kembali ke posisi awal.

Saya akan menunjukkan kepada Anda bagaimana menemukan solusi untuk masalah ini (atau mengetahui bahwa tugas
tidak mungkin) untuk ukuran grid sewenang-wenang. Selanjutnya, kita akan melihat solusi untuk
Papan catur standar memiliki 8 baris dan 8 kolom.

Dalam penyelesaiannya objek utama yang akan kita lacak adalah a grid. Boleh jadi
adalah matriks yang menyimpan gerakan ksatria yang berurutan. Dalam matriks ini a 0
entri berarti alun-alun belum dikunjungi dan entri positif menunjukkan
Pindahkan nomor ketika alun-alun telah dikunjungi. Jadi nomor 1 adalah posisi awal dari
Ksatria.

Untuk melacak posisi ksatria di grid, kita akan menggunakan 2 set organisasi
posisi baris dan kolom ksatria saat ini. Itu disebut p dalam kode.

Pertama kita buat listoptions fungsi bantu. dibutuhkan grid dan p
sebagai argumen dan mengembalikan vektor dari kemungkinan gerakan ksatria p
ke kotak yang belum dikunjungi. Berikut implementasinya:

listoptions(grid, p) =
    [p .+ d for d in ((1, 2), (-1, 2), (1, -2), (-1, -2),
                      (2, 1), (-2, 1), (2, -1), (-2, -1))
     if get(grid, p .+ d, -1) == 0]

Perhatikan betapa uniknya get fungsi bekerja dalam kasus ini. Kami menggunakannya untuk mendapatkan
satu -1 nilai dalam kasus p .+ d tidak dalam batas-batas grid (jadi itu tidak valid
pindah dihapus).

Saatnya menghadirkan fungsi utama yang akan menangani transmisi
grid oleh ksatria:

function knight_jump!(grid=fill(0, 8, 8), p=(1, 1), i=1)
    grid[p...] = i
    if i == length(grid)
        p1 = Tuple(findfirst(==(1), grid))
        return extrema(abs, p .- p1) == (1, 2) ? grid : nothing
    end
    v = listoptions(grid, p)
    sort!(v, by=np -> length(listoptions(grid, np)))
    for np in v
        knight_jump!(grid, np, i + 1) !== nothing && return grid
    end
    grid[p...] = 0
    return nothing
end

Izinkan saya menjelaskan cara kerjanya. Itu grid dan p argumennya telah
diskusi. menambahkan i argumen menyimpan nomor langkah. Fungsi
laba grid dalam kasus itu menemukan solusi yang mungkin dan nothing jika tidak
Kemungkinan solusi ditemukan. Invarian ini sangat penting, karena kita akan menggunakannya
untuk melakukan pencarian mendalam pertama untuk tur ksatria yang valid.

Pertama kita atur grid di alamat ini p tiba i untuk merekam lokasi saat ini
dari ksatria.

selanjutnya i == length(grid) periksa kami memverifikasi bahwa kami telah mencapai slot gratis terakhir
pada kisi. Jika demikian, kami memeriksa lokasi saat ini p Menjadi
ksatria melompat keluar dari posisi awal ksatria (dilambangkan dengan p1 Di
kode). Jika ini masalahnya, kami kembali grid. Kalau tidak, tur tidak valid
dan kami kembali nothing.

Jika tur kami belum berakhir, kami akan menyimpannya v vektor kemungkinan gerakan
bisa kita lakukan selanjutnya. Sekarang bagian penting dari algoritma diterapkan. kami mengatur v
menggunakan aturanWarnsdorff, yaitu, kita menempatkan kuadrat dengan paling sedikit
seterusnya bergerak di depan vektor. Kami kemudian mengaksesnya secara rekursif
dan mencoba untuk memecahkan teka-teki. Jika kita berhasil, yaitu saat memanggil secara rekursif
tiba knight_jump! tidak ada pengembalian nothingkita selesai dan mengembalikan hasilnya.
Jika kita gagal untuk semua nilai di vIni berarti upaya untuk mengakses p menjadi
pilihan yang salah. Dalam hal ini kita perlu mengatur ulang grid sehingga dalam posisi
p memiliki 0 dan kembali nothing (untuk menandakan masalah).

Mari kita periksa bagaimana solusinya terlihat pada grid 8×8 (yang merupakan default di
kode kami):

julia> res = knight_jump!()
8×8 Matrix{Int64}:
  1  16  51  34   3  18  21  36
 50  33   2  17  52  35   4  19
 15  64  49  56  45  20  37  22
 32  55  44  63  48  53  42   5
 61  14  57  54  43  46  23  38
 28  31  62  47  58  41   6   9
 13  60  29  26  11   8  39  24
 30  27  12  59  40  25  10   7

Pertama, kita melihat bahwa solusi sebenarnya telah ditemukan (karena kita tidak mendapatkan nothing
dari panggilan). Kedua, inspeksi visual dari solusi menunjukkan bahwa memang
solusinya benar.

Mari kita visualisasikan lebih jauh untuk memudahkan analisis. Pertama kita mengkonversi
itu res matriks masukan moves vektor posisi ksatria berturut-turut disimpan
sebagai dataset. Selanjutnya kita tambahkan posisi pertama ke ujung vektor ini (seperti yang kita miliki
Sebuah siklus). Terakhir, kami menggambar papan catur dengan gerakan berurutan yang disajikan
per baris.

julia> using Plots

julia> moves = Tuple.(CartesianIndices(res)[sortperm(vec(res))])
64-element Vector{Tuple{Int64, Int64}}:
 (1, 1)
 (2, 3)
 (1, 5)
 ⋮
 (6, 3)
 (4, 4)
 (3, 2)

julia> push!(moves, first(moves))
65-element Vector{Tuple{Int64, Int64}}:
 (1, 1)
 (2, 3)
 (1, 5)
 ⋮
 (4, 4)
 (3, 2)
 (1, 1)

julia> plot(getindex.(moves, 1), getindex.(moves, 2);
            legend=false, size=(400, 400), color=:blue,
            marker=:o, markerstrokecolor=:blue,
            xlim=(0.5, 8.5), ylim=(0.5, 8.5),
            minorticks=2, minorgrid=true, grid=false,
            xticks=(0:9, [""; 'A':'H'; ""]), yticks=0:9,
            minorgridalpha=1.0, showaxis=false)

Plot yang dihasilkan terlihat seperti ini:

Karena saya memulai artikel dengan pengumuman kursus singkat, izinkan saya
Beralih ke mode kuliah sebentar. Untuk teka-teki ini, saya punya yang berikut ini
Latihan bagi Anda untuk melatih otot Julia:

• Periksa apakah kita perlu kembali ke algoritme karena mungkin kita sudah menyelesaikannya
  masalah pada percobaan pertama berkat aturan Warningsdorff?
• Ukur kinerja kode.
• Apakah Anda punya ide bagaimana meningkatkan kecepatannya (petunjuk: pikirkan bagaimana Anda bisa
  kurangi jumlah alokasi dan hindari penyortiran)
• Periksa apa yang terjadi jika kita tidak menggunakan aturanWarnsdorff. dua alam
  aturan kandidatnya adalah: kunjungi kotak secara acak dan kunjungi kotak secara berurutan
  Pesanan diproduksi oleh listoptions fungsi.
• Solusi yang diusulkan menggunakan rekursi. Karena Julia memiliki batas kedalaman rekursi
  kode tidak akan berfungsi seperti yang diharapkan untuk jaringan besar. Pertama, temukan batas ini.
  Kedua, pikirkan bagaimana Anda dapat menulis ulang program untuk menghindari penggunaan
  rekursif.

Saya harap Anda menikmati teka-teki dan solusi yang disajikan. Jika Anda mengalami kesulitan pada
bagian mana pun dari pekerjaan rumah yang dapat kita diskusikan pada Januari 2023 di MIT tepat waktu
kursus singkat atau hubungi saya di Julia Discourse atau
Julia Slack dan saya akan dengan senang hati menjawab pertanyaan Anda.

Terkait