pasti aganwan/wati udah pada tau sama yg nama nya permainan Minesweeper kaya gini nih:
Spoiler for Minesweeper:
[
dan ini sejarah tentang permainan minesweeper,semoga no
Spoiler for Sejarah Minesweeper:
Minesweeper adalah permainan komputer untuk satu pemain. Tujuan permainan ini adalah untuk membersihkan lahan permainan tanpa mengenai ranjau. Permainan ini telah ditulis kembali untuk hampir semua platform. Versi yang paling terkenal adalah versi Minesweeper untuk Windows, yang disertakan dalam Windows 3.1 keatas.
Permainan
Permainan ini dilakukan dengan cara membuka kotak pada grid, umumnya dengan melakukan klik pada tetikus. Jika kotak yang terbuka berisi ranjau, pemain kalah. Kotak berisi angkan menandakan jumlah ranjau di sekelilingnya. Pemain dapat melakukan klik kanan untuk menandai kotak dengan ranjau.
Spoiler for Cara mainnya:
Pemecahan permainan minesweeper merupakan salah satu masalah yang termasuk ke dalam golongan masalah NP-complete. Bahkan Clay Mathematics Institute of Chambridge, Massachusetts (CMI) menggolongkannya ke dalam salah satu dari tujuh masalah millenium yang dikenal dengan nama Prize Problems.
NP-COMPLETE
Kebutuhan waktu algoritma yang mangkus bervariasi, mulai dari O(1), O(log log n), O(log n), O(n), O(n2
), dan O(n3). Semua algoritma tersebut dikenal sebagai solusi polinomial dikarenakan kebutuhan waktunya secara asimptotik dibatasi oleh fungsi polinomial. Misalnya log(n) < n untuk semua n ≥ 1. Sebaliknya, ada persoalan yang tidak terdapat solusi waktu polinomial untuk menyelesaikannya, misalnya TSP yang memiliki kompleksitas O(n!). Polynomial-time algorithm adalah algoritma yang
kempleksitas waktu kasus-terburuknya dibatasi oleh fungsi polinom dari ukuran masukannya. Di luar
algoritma tersebut, algoritmanya dikenal dengan nonpolynomial-time algorithm. P Problems adalah himpunan semua persoalan keputusan yang dapat dipecahkan oleh algoritma dengan
kebutuhan waktu polinom. NP Problems adalah himpunan persoalan keputusan yang dapat diselesaikan oleh algoritma non-deterministik dalam waktu polinom. Algoritma non-deterministik adalah algoritma yang
berhadapan dengan beberapa opsi pilihan, dan algoritma memiliki kemampuan untuk menerka opsi pilihan yang tepat. Semua persoalan P juga adalah NP, sebab tahap menerka tidak terdapat di dalam persoalan P. Karena itu, P adalah himpunan bagian dari NP. Namun, belum ada yang bisa membuktikan apakah masalah P = NP atau P tidaksamadengan NP. Pertanyaan ini penting sebab kebanyakan persoalan keputusan adalah NP. Karena itu, jika P = NP, maka akan ada banyak persoalan keputusan yang dapat dipecahkan secara mangkus dengan algoritma yang kebutuhan waktunya polinom. Namun kenyataannya, banyak ahli yang telah gagal menemukan algoritma waktu-polinom untuk persoalan NP. Karena itu, cukup aman kalau kita menduga-duga bahwa P tidaksamadengan NP. NP-Complete (NPC) adalah persoalan NP yang paling sulit. Sebuah persoalan X dikatakan NPC jika: 1. X termasuk ke dalam kelas NP 2. Setiap persoalan di dalam NP dapat direduksi dalam waktu polinom menjadi X Penjelasannya adalah sebagai berikut: untuk persoalan X di dalam NPC, pertama harus dipahami bahwa X adalah NP. Kemudian, kita seharusnya dapat mereduksi sembarang persoalan lain di dalam NP dengan transformasi sederhana menjadi instance persoalan X. Efeknya, jika transformasi ini dapat dilakukan, maka jika algoritma dalam waktu polinom ditemukan untuk X, maka semua persoalan di dalam NP dapat diselesaikan dengan mangkus. Dengan kata lain, jika X adalah NPC dan termasuk ke dalam P – yaitu algoritma yang mangkus (polinom, deterministik) untuk X ditemukan – maka P = NP. Hal ini karena transformasi tersebut sederhana (membutuhkan waktu polinom).
