Mastermind

300000

Mastermind

Jumlah bilangan permainan: 445808

Nombor digit		0
Julat digit 1..		0
Bilangan maksimum satu digit mungkin ada		0
Bilangan maksimum untuk percubaan		0

Singkatan

Bagaimanakah seseorang boleh memecahkan keseluruhan soalan kepada sub-matlamat?

Apakah prinsip yang umum sekali untuk merumuskan tekaan seterusnya?

Alat yang berguna:

Untuk fasa pertama A) adalah berguna untuk membuat nota semua digit yang mungkin, mengapa?

Untuk fasa B) adalah berguna untuk mempunyai jadual penyingkiran, bagaimana dan mengapa?

A) Bagaimanakah seseorang boleh cuba mencari semua digit panas?

Selepas menghantar satu tekaan, hasil (balasan) yang manakah akan sangat berguna?
- Kita bernasib baik jika ternyata semua atau kebanyakan digit yang diteka panas, tetapi kita juga mendapat banyak maklumat jika kedua-dua nombor yang dikembalikan adalah kedua-duanya 0 kerana kemudian tiada satu pun digit yang diteka berlaku dalam penyelesaian, iaitu semua digit yang diteka adalah sejuk. Dalam kes itu, kita boleh memadam N digit daripada senarai kemungkinan digit atau baris N dalam jadual penyingkiran.

Jika kita tidak begitu bernasib baik, apakah strategi yang mungkin untuk mencari lebih banyak digit panas?
- Mari kita andaikan bahawa penyelesaian mempunyai 4 digit dan digit 1,…,9 mungkin muncul paling banyak sekali (jika tidak, ubah suai 3 ayat seterusnya). Dengan penyelesaian yang mengandungi 4 digit, kita akan meneka 1,2,3,4 dan kemudian 5,6,7,8 dan secara automatic akan mengetahui tentang 9 dengan mengira berapa digit 1,…,8 panas. Jika terdapat empat digit panas maka 9 adalah sejuk atau panas. Jika kita bernasib baik dan 1,2,3,4 sudah panas maka kita tidak akan mencuba digit lain kerana ia sejuk.

Mari kita andaikan kita membuat beberapa tekaan, katakan 7, selepas itu kita tahu untuk setiap digit sama ada ia panas atau sejuk.
Adakah penting sama ada 7 tekaan ini kebanyakannya mengandungi digit panas atau digit seuk?
- Nampaknya sama berguna untuk meneka dan mengetahui semua digit panas atau meneka semua digit sejuk kerana mengetahui satu set, seseorang tahu set yang lain juga. Tetapi itu tidak berlaku. Jika tekaan kita mengandungi banyak digit panas maka kita mengumpul maklumat tambahan di sebelahnya tentang kedudukan betul atau salah digit panas ini. Kita tidak akan mengumpul maklumat ini jika tekaan kita kebanyakannya mengandungi digit sejuk.
- Prinsip manakah yang kita ikuti apabila menghantar tekaan dengan banyak digit panas?
  - Prinsip 1) kerana di samping itu, kita mengumpul maklumat mengenai lokasi yang akan berguna nanti apabila kita tahu semua lokasi digit panas.
- Bolehkah anda memikirkan untuk merumuskan tekaan yang mengikut prinsip 2) ? Dalam kata lain, tekaan yang manakah memberikan balasan yang mudah digunakan?
  - Untuk mengikut prinsip 2) kita boleh mengambil satu tekaan dan mengubah suainya dengan mengeluarkan satu digit, katakan 5, dan masukkan satu digit, katakan 3. Jika tekaan baharu mempunyai lebih sedikit digit panas maka nombor 5 adalah panas dan nombor 3 adalah sejuk. Jika tekaan baru mempunyai lebih banyak digit panas maka nombor 5 adalah sejuk dan nombor 3 adalah panas. JIka tidak, nombor 5 dan 3 kedua-duanya panas atau kedua-duanya sejuk. Untuk menyelesaikan antara dua kes ini, seseorang boleh mempunyai kedua-duanya, nombor 5 dan 3 dalam tekaan seterusnya. Apabila memutuskan tekaan yang hendak diubah suai dengan satu digit, kita mengikut petunjuk terdahulu dan memilih tekan sebelumnya yang mempunyai digit paling panas untuk mengumpul juga maklumat tentang kedudukan dan mengikut prinsip 1).
Mari kita andaikan anda mengikuti petunjuk sebelum ini dan menghantarkan tekaan di mana anda hanya menukar satu digit, katakan 7 dengan 3, dan anda mengetahui daripada balasan bahawa digit 3 baharu adalah panas dan 7 adalah sejuk.
Itu sahaja yang anda pelajari daripada tekaan ini?
- Tidak. Anda kini boleh kembali kepada tekaan awal dan gunakan pengetahuan bahawa 3 panas dan 7 sejuk untuk membuat kesimpulan lebih banyak maklumat daripada tekaan sebelumnya. Sebagai contoh, tekaan sebelum ini termasuk 3 dan hanya mempunyai satu digit panas kemudian digit lain dalam tekaan itu sejuk. Fakta bahawa mereka sejuk mungkin memberi anda petunjuk yang mana digit-digit lain adalah panas daripada tekaan lain dan sebagainya.

Jika anda memutuskan digit mana yang sepatutnya ada dalam tekaan seterusnya, adakah ia peting dalam susunan yang mana untuk meletakkannya?
- Jika anda memutuskan digit mana yang sepatutnya ada dalam tekaan seterusnya, adakah ia peting dalam susunan yang mana untuk meletakkannya?
Sebaik sahaja kita mengetahui semua digit panas, kita juga tahu semua digit sejuk dan boleh memadam barisnya dalam jadual penyingkiran.

B) Bagaimanakah kita boleh mencari lokasi setiap digit panas?

Sekarang, setelah kita mengetahui semua digit panas, balasan apakah yang akan menjadi sangat berguna?
- Jika semua digit yang diteka berada pada lokasi yang betul maka, sudah tentu, kita bertuah dan menyelesaikan masalah itu. Satu lagi keputusan bertuah ialah apabila tiada satu pun daripada angka yang diteka berada pada kedudukan yang betul. Kemudian kita belajar banyak dan boleh memadam N kawasan dalam jadual penyingkiran.

Ingat balik, bagaimana kita boleh menggunakan jadual penyingkiran dalam peringkat akhir penyelesaian ini?
- Jika semua baris digit dipadamkan dan jika terdapat baris atau lajur dengan hanya satu kawasan yang tidak dipadamkan maka ini memberitahu kita digit mana yang mempunyai lokasi ini dalam penyelesaian dan kawasan kosong yang tinggal dalam lajur ini boleh dipadam. Jika setiap digit boleh berlaku sekali sahaja maka semua kawasan dalam baris ini juga boleh dipadamkan.

Berapakah bilangan nombor yang boleh dibentuk daripada digit panas?
- Setiap jujukan digit tersebut dipanggil pilih atur. Jadi persoalannya ialah: Berapa banyak pilih atur yang ada untuk N objek , di sini N digit?
  Jika semua digit berbeza maka untuk digit pertama terdapat N pilihan. Bagi setiap satu daripada N ini terdapat pilihan N-1 untuk digit kedua. Bagu setiap kombinasi N x (N-1)ini terdapat pilihan N-2 untuk digit ke-3 dan seterusnya, dalam jumlah N x (N-1) x … x 2 x 1 = N! (dipanggil N faktorial) banyak.
  Jika tidak semua digit adalah berbeza maka kita boleh mempunyai, sebagai contoh, N=4 dan 4 digit panas ialah 2,2,2,5. Kemudian produk N! = 4! Kena bahagi 3! Kerana susunan antara tiga 2 itu tidak penting. Kita akan mendapat 4!/3! = 24/6 = 4 (atau lebih elegan 4!/3! = 4x3! / 3! = 4)
- Berapakah bilang itu untuk N=3 atau N=4?
  - Jika setiap digit muncul hanya sekali, kita mendapat 3! = 3x2x1=6 dan 4!=4x3! =24 pilih atur (jujukan). Ini tidak banyak.
- Apakah maksudnya untuk mencari penyelesaian?
  - Seseorang boleh menulis semua nombor (permutasi N digit panas) dan menyemaknya satu demi satu berkenaan dengan semua tekaan awal. Biasanya hanya satu atau dua daripada nombor ini kekal mungkin yang mana satu boleh cuba sebagai tekaan seterusnya.

Sila ambil perhatian: Selepas meneka, kita mungkin tahu apakah penyelesaiannya tetapi kitamasih perlu menghantarkan penyelesaian itu untuk membuktikan computer yang kita temui.

Berapa kerap seseorang perlu meneka secara purata jika petunjuk di atas diikuti?