Saya yakin bahwa banyak pembaca kadang-kadang terlibat dalam omong kosong yang tidak berguna di kelas alih-alih mendengarkan guru. Saya melakukan hal itu, dan satu cara untuk menghabiskan waktu adalah bermain di atas kertas. Game pratinjau (yang namanya masih belum saya kenal) terasa sangat menarik bagi saya, tetapi ada dua alasan: tidak memerlukan orang kedua dan bisa diselesaikan! Benar, sangat jarang melakukan ini. Untuk waktu yang lama saya bertanya-tanya seberapa sederhana solusinya, dan sekarang, setelah bertahun-tahun, tidak akan sulit untuk menemukannya secara terprogram.
Aturannya
Pertama, perlu dijelaskan aturannya. Permainan dimulai dengan bidang berikut:
123456789
111213141
516171819
Di sini, semua angka dari 1 hingga 19 dicatat karakter demi karakter, dengan pengecualian 10. Angka-angka tersebut terletak dari kiri ke kanan, baris demi baris. Aturannya cukup sederhana - pada setiap langkah Anda perlu mencoret 2 angka yang sesuai dengan kriteria berikut:
- angkanya harus sama atau total memberi 10 (1 dan 1, 3 dan 7, 8 dan 2, dll.);
- mereka harus berdiri di atas satu sama lain atau diatur secara seri. Dalam hal ini, nomor yang sudah dicoret diabaikan.
Salah satu opsi untuk beberapa langkah pertama ditunjukkan di bawah ini:
1 23456789
1 11213141
5161718 19
#2345678 9
# 1 1213141
5161718##
#2345678#
##1213141
5161718##
Pada saat tidak ada lagi gerakan, semua angka yang tidak ditandai ditambahkan ke bagian akhir. Permainan berakhir saat seluruh bidang dicoret.
#2345678#
##1213141
51 6 171 8 ##
23 4 567 8 12
131415161
718
#2345678#
##1213 1 41
5 1 # 1 71###
23#567#12
131415 1 61
718
#2345678#
##1213#41
5###71###
2 3 #567#12
1 3 1415#61
718
...
Jumlah gerakan yang tersedia meningkat pesat, permainan mulai bercabang dengan kuat. Seringkali meja menjadi sangat panjang sehingga meluap ke halaman berikutnya dalam buku catatan. Lebih mudah untuk memulai batch baru. Terkadang saya terus keluar dari ketekunan, tetapi pada akhirnya saya menyerah.
Ini menimbulkan pertanyaan yang masuk akal - seberapa cepat Anda bisa menyelesaikan game ini? Di masa kanak-kanak, itu mungkin untuk menemukan solusi dalam satu kolom pada lembar notebook - ini adalah sekitar 40 baris atau 360 karakter.
Saya tidak tahu cara dijamin untuk menyelesaikan game. Sama sekali tidak jelas bagaimana memilih strategi. Anda dapat mencoba memainkannya sendiri jika tidak.
Solusi
Bagaimana solusi untuk masalah seperti itu dicari? Saya tidak tahu pasti, tetapi saya memilih payudara yang biasa.
Kami membutuhkan antrian, pertama hanya terdiri dari satu konfigurasi awal. Pada setiap langkah, kami mengambil konfigurasi berikut dari antrian, melihat semua gerakan yang tersedia, dan menambahkan semuanya ke akhir antrian atau menyatakan diri sebagai pemenang jika tidak ada gerakan seperti itu.
123456789 #23456789 12345678# 123456789 123456789 123456789 123456789 ...
111213141 #11213141 #11213141 ##1213141 1##213141 11#213141 11121314# ...
516171819 516171819 516171819 516171819 516171819 516#71819 51617181# ...
Jika Anda tidak memikirkan solusi yang tersedia pertama, maka algoritma ini akan menghasilkan semua solusi yang mungkin (di hadapan jumlah RAM yang tak terbatas).
Dalam praktiknya, pendekatan naif semacam itu tidak akan membantu sama sekali, setidaknya karena duplikat yang terus muncul dalam antrian. Oleh karena itu, beberapa optimasi akan diperlukan, yang sekarang akan saya jelaskan:
- Secara alami, konfigurasi perlu di-cache agar tidak perlu antri lagi. Ini akan sangat meningkatkan penggunaan memori, tetapi tetap tidak akan membantu untuk mendapatkan solusi dalam jumlah waktu yang wajar. Selain itu, pertanyaan membandingkan konfigurasi muncul dengan tajam. Karena dua konfigurasi pemenang dengan ukuran yang sama akan selalu hanya terdiri dari angka yang dicoret, diperlukan cara tambahan untuk membedakannya, jika tidak, tidak semua solusi akan ditemukan;
- untuk membuat pencarian bermakna dan cepat, lebih baik menggunakan antrian prioritas. Semakin sedikit angka di lapangan (termasuk dicoret), konfigurasi yang lebih awal harus dipertimbangkan;
- jika Anda membutuhkan lebih dari satu solusi, tetapi banyak, lebih baik untuk membatasi jumlah angka maksimum di lapangan, pencarian akan mengeluarkan solusi lebih awal.
Jawabannya
Jika semuanya benar, ternyata solusi minimum hanya terdiri dari 68 karakter atau 8 baris!
Saya akan membawanya dalam bentuk animasi gif. Beberapa gerakan terpaku menjadi satu untuk mengurangi jumlah frame:
Saya jujur, saya terkejut dengan betapa pendeknya keputusan ini. Tapi mungkin keberuntungan ini dan keputusan lain tidak akan segera dipenuhi dan akan sangat lama?
Tidak, keputusan tidak jarang sama sekali. Jawaban cepat ditemukan dalam panjang 72, 74 dan 76. Dan 4 solusi yang berbeda secara fundamental dengan panjang 80. Secara umum, saya berhasil menemukan 30 solusi hingga 90 panjang (inklusif), dan jika saya meningkatkan perbatasan ke 100, maka akan ada 170 solusi. tetapi mencari mereka menjadi lebih mahal.
Di bawah spoiler, solusi optimal dijelaskan secara rinci:
Teks tersembunyi 123456789 111213141 516171819 123456789 111213141 5161718## 123456789 1##213141 5161718## 12345678# 1##21314# 5161718## #2345678# ###21314# 5161718## #234567## ####1314# 5161718## #234567## ####1314# 5161718## 234567131 45161718 #234567## ####1314# 51#1718## 23#567131 45161718 #234567## ####1314# 51#171### #3#567131 45161718 #234567## ####1314# 51#171### #3#567#31 451617#8 #234567## ####1314# 51#171### #3#56###1 451617#8 #234567## ####1314# 5###71### #3#56###1 451617#8 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 571356145 16178 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 57#356145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 5###56145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 #####6145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 34567131# ######145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 3456713## #######45 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 3#56713## #######45 1##78 #234567## ####1314# 5###71### #3#56###1 451617### 3#56713## #######45 1##78 #234567## ####1314# 5###71### #3#56###1 45161#### ##56713## #######45 1##78 #234567## ####1314# 5###7#### #3#56###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# 5######## ###56###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##56##### #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##5###### ########5 1##78 #234567## ####1314# ######### ####6###1 45161#### ######### ######### 1##78 #234567## ####131## ######### ########1 45161#### ######### ######### 1##78 #234567## ####13### ######### ######### 45161#### ######### ######### 1##78 #234567## #####3### ######### ######### 4516##### ######### ######### 1##78 #23456### ######### ######### ######### 4516##### ######### ######### 1##78 #2345#### ######### ######### ######### #516##### ######### ######### 1##78 #234##### ######### ######### ######### ##16##### ######### ######### 1##78 #23###### ######### ######### ######### ##1###### ######### ######### 1##78 #23###### ######### ######### ######### ######### ######### ######### ###78 #2####### ######### ######### ######### ######### ######### ######### ####8 ######### ######### ######### ######### ######### ######### ######### #####
Kode solusi Java saya dapat dilihat di tautan ini , tetapi saya memperingatkan Anda bahwa itu mengerikan, karena awalnya ditulis bukan untuk publikasi. Dalam bentuk saat ini, ia menemukan semua solusi hingga 70 karakter (yaitu, hanya satu solusi). Ini mudah diperbaiki dengan bermain-main dengan kondisi dalam kode.
Terima kasih atas perhatian anda!