Kita semua pernah mendengar tentang teka-teki Tur Ksatria : temukan rute untuk seorang ksatria yang melewati semua kotak di papan catur. Tapi jujur ​​saja, ini sedikit membosankan. Jadi, mari kita berikan ksatria sedikit tantangan.

Tugas

Tulis sebuah program yang membawa ksatria melalui semua kotak pada papan catur berukuran sewenang-wenang. Ini harus mengambil papan catur sebagai input dan output set gerakan dan posisi awal. Dalam hal papan tidak mungkin, itu harus menampilkan set bergerak dan posisi awal untuk tur dengan panjang terpanjang yang mungkin. Catatan: ksatria tidak perlu melakukan perjalanan pulang-pergi; berasumsi bahwa dia memiliki cara lain untuk pulang.

Potongan catur berukuran kecil, jadi kode Anda harus cukup kecil untuk dibawa oleh ksatria.

Memasukkan

Input akan berupa representasi berbasis-string atau berbasis-array dari papan catur, di mana nilai non-kosong / jujur ​​adalah kuadrat, dan nilai kosong / salah adalah ruang kosong. Demi kesederhanaan, saya akan menggunakan #dan diatur dalam kotak untuk contoh.

Keluaran

Output akan berupa dua bilangan bulat besar, diikuti oleh serangkaian bilangan bulat 4-bit, atau setara dengan bahasa Anda. Dua bilangan bulat besar akan mewakili koordinat awal, dan angka-angka berikut akan mewakili langkah seperti:

 7 0
6   1
  K
5   2
 4 3

di mana Kposisi sebelum pindah, dan nomor adalah posisi setelah pindah.

Contohnya

Karena ada banyak solusi yang memungkinkan untuk teka-teki Tur Knight, saya hanya akan memberikan contoh hasil. Mungkin ada lebih banyak output.

###
# #
###
0 0 3 0 5 2 7 4 1

^{Tantangan baru: Munculkan lebih banyak contoh}

Mathematica, 151 byte

Needs@"Combinatorica`"
{Reverse@#[[1]]-1,3-Floor[1.2Arg[Complex@@@Differences@#]]}&[#[[HamiltonianPath@MakeGraph[#,Norm[#-#2]^2==5&]]]&@Position[#,1]]&

Jelas, HamiltonianPath@MakeGraph[#,Norm[#-#2]^2==5&]melakukan semua pekerjaan.

Input adalah 2D (0,1) -matrix like {{0,0,1},{1,1,1},{1,0,1},{1,1,1}}.

Output terlihat seperti ini: {{2, 0}, {5, 3, 0, 5, 2, 7, 4, 1}}

Saya tidak tahu banyak tentang golf Mathematica, jadi silakan tunjukkan perbaikannya. Apakah ada cara yang lebih baik untuk menyimpan hasil individual daripada menggunakan satu miliar fungsi murni?

Disimpan satu byte; terima kasih, CatsAreFluffy.