Bài toán hóc búa trong trò xếp hình Tetris

Mọi người đều nghĩ rằng trò xếp hình quen thuộc hoàn toàn có thể chơi được dễ dàng. Nhưng giờ đây, các nhà khoa học đã phát hiện ra rằng việc hoàn thành trò chơi này khó hơn bạn tưởng rất nhiều.

Trò Tetris do nhà sáng tạo người Nga, Alexey Pajitnov, tạo ra vào năm 1985 và từ đó đến nay, nó đã trở thành game được chơi rộng rãi nhất mọi thời đại. Bất cứ ai chơi game máy tính trong 15 năm trở lại đây hẳn đã phải sờ tay đến Tetris dưới nhiều hình thức khác nhau. Ban đầu trò chơi này thường được chơi với bộ điều khiển Gameboy của Nintendo.

Tetris giao cho người chơi nhiệm vụ tạo ra những dãy liền khít gồm các viên gạch có hình thù khác nhau từ từ rơi xuống một khung gạch sẵn có. Những miếng gạch này có thể xoay chuyển để vừa khít với nhau tạo ra những dãy liền mạch. Tốc độ game sẽ càng tăng khi chuyển lên những mức độ cao hơn, khiến cho người chơi gặp khó khăn trong việc xoay chuyển các viên gạch.

Erik Demaine, Susan Hohenberger và David Liben-Nowell tại phòng thí nghiệm của Viện công nghệ Massachusetts đã phân tích để tìm ra sự phức tạp của trò chơi này. 3 nhà khoa học đã phát hiện Tetris có nhiều điểm tương đồng với những câu hỏi toán học hóc búa nan giải nhất như kiểu Travelling Salesman Problem - bao gồm việc tìm ra đường đi hiệu quả nhất cho một nhà buôn, khi ông ta phải đi qua rất nhiều địa điểm khác nhau.

Các nhà khoa học cho biết, những bài toán như vậy (còn được gọi là NP-Hard problem) là rất khó giải bởi không có một thuật toán tắt nào để giải quyết chúng một cách nhanh gọn. Thay vào đó, mọi phương án có thể đều phải thử nghiệm để tìm ra biện pháp hiệu quả nhất.

Tetris chính là một NP-Hard problem và không có cách nào để đạt được được điểm tối đa của trò chơi, cho dù thứ tự của các viên gạch đã được biết trước. 

Minh Thi (theo BBC)