Sebuah kertas penyelidikan baharu telah menyelesaikan persoalan lama dalam sains komputer dengan membuktikan bahawa Tetris kekal sukar secara komputasi walaupun dimainkan pada papan permainan yang sangat kecil. Penemuan ini menjawab persoalan yang telah membingungkan penyelidik selama lebih 15 tahun mengenai kerumitan matematik permainan teka-teki yang digemari ini.
Misteri Kerumitan Menjadi Lebih Kecil
Pasukan penyelidik menunjukkan bahawa Tetris mengekalkan status NP-complete walaupun terhad kepada papan dengan hanya 8 lajur atau 4 baris. Ini luar biasa kerana ia menunjukkan kesukaran sedia ada permainan tidak datang daripada mempunyai medan permainan yang besar. Walaupun pada papan kecil ini, menentukan cara optimum untuk memainkan urutan kepingan yang diberikan kekal sesukar beberapa masalah paling mencabar dalam sains komputer.
Para penyelidik menggunakan teknik matematik yang dipanggil pengurangan daripada 3-PARTITION, yang melibatkan pembungkusan elemen secara bijak ke dalam bekas bersaiz sama. Mereka menambah baik kaedah terdahulu dengan mencari cara yang lebih baik untuk menyusun baldi matematik ini pada saiz papan yang terhad.
Nota: NP-complete merujuk kepada kelas masalah yang dipercayai memerlukan masa eksponen untuk diselesaikan, bermakna masa yang diperlukan meningkat dengan sangat cepat apabila saiz masalah bertambah.
Keputusan Kerumitan Tetris mengikut Saiz Papan:
- 8+ lajur: NP-lengkap (sukar dari segi pengiraan)
- 4+ baris: NP-lengkap (sukar dari segi pengiraan)
- 2 lajur atau kurang: Boleh diselesaikan dalam masa polinomial (mudah)
- 1 baris: Boleh diselesaikan dalam masa polinomial (mudah)
Apabila Tetris Menjadi Mudah
Sebaliknya, kajian mendapati bahawa versi Tetris yang sangat sempit sebenarnya boleh diselesaikan dengan cekap. Apabila papan permainan hanya mempunyai 2 lajur atau 1 baris, penyelidik membuktikan ia menjadi boleh diselesaikan dalam masa polinomial. Ini mewujudkan sempadan menarik di mana Tetris beralih daripada mudah kepada sukar berdasarkan dimensi papan.
Perbincangan komuniti mengenai penyelidikan ini telah menonjolkan beberapa implikasi praktikal. Sesetengah pemerhati menyatakan bahawa walaupun keputusan teori adalah menarik, pelaksanaan Tetris dunia sebenar sering menggunakan kaedah rawak yang berbeza yang mempengaruhi kesukaran permainan dalam cara yang melampaui kerumitan komputasi tulen.
Variasi Papan Tetris Standard:
- Tetris Klasik: 10 lajur × 20 baris
- Tetris Jr.: 8 lajur
- Tetris Wristwatch: 6 lajur
- Variasi ketinggian: 16-24 baris
- Variasi lebar: 6-20 lajur merentasi edisi yang berbeza
Kekeliruan Tarikh dan Proses Akademik
Perbincangan sampingan yang menghiburkan muncul mengenai butiran penerbitan kertas, dengan ahli komuniti menyedari percanggahan dalam footer hak cipta yang menunjukkan 1992 walaupun penyelidikan dijalankan sekitar 2019-2020. Ini mencetuskan perbualan mengenai proses penerbitan akademik dan bagaimana kertas yang dikemukakan berbeza daripada versi akhir yang diterbitkan, dengan nombor jilid dan butiran halaman yang hilang diisi kemudian semasa semakan rakan sebaya.
Penyelidikan ini melangkaui Tetris klasik untuk mengkaji kepingan teka-teki yang lebih besar dan konfigurasi papan yang berbeza, menyediakan kerangka matematik komprehensif untuk memahami permainan teka-teki blok jatuh. Kerja ini merapatkan jurang antara permainan rekreasi dan teori komputasi serius, menunjukkan bagaimana permainan yang kelihatan mudah pun boleh menyimpan kerumitan matematik yang mendalam.