Đề thi THPT Quốc gia môn Toán năm 2015, De thi thu THPT Quoc Gia nam 2015

You are here: Home »

Like VNMATH on FACEBOOK để ủng hộ VNMATH.

Thuật toán giúp giải mã trò Sudoku dễ dàng hơn

VNMATH.COM 15 tháng 10, 2012 , 0

Công nghệ kĩ thuật số cho phép chúng ta tiếp cận rất nhiều game hiện đại, tuy nhiên vẫn tồn tại các trò chơi giải trí tưởng như đơn giản nhưng lại đòi hỏi mức độ tập trung cao và hấp dẫn mọi người, mà giải ô số Sudoku là một ví dụ tiêu biểu. Phải thừa nhận rằng khi chọn mức độ chơi khó hoặc khó nhất của trò này, bên cạnh những suy luận mang tính logic người chơi phải kết hợp phán đoán hoặc thử ngược vài con số để đi đến đáp án cuối cùng. Thực sự nó rất tốn thời gian và làm nản chí những người không có đủ kiên nhẫn. Nhằm làm cho việc giải ô số trở nên dễ dàng hơn, một nhóm các nhà nghiên cứu tại Đại học Notre Dame (bang Indiana, Hoa Kỳ) đã phát minh ra một giải thuật toán học giúp người chơi không cần phải vận dụng tới các phép thử hoặc phán đoán nhàm chán. Hơn nữa bằng cách áp dụng giải thuật đó, họ có thể giải thích, định lượng độ khó của ô chữ Sudoku một cách chính xác và ứng dụng nó trong các lĩnh vực khác.

Trước khi đi vào tìm hiểu chi tiết hơn công trình của nhóm nghiên cứu tại Đại học Notre Dame, chúng ta hãy đi sơ qua về lịch sử của trò chơi Sudoku đầy thú vị.

Lược sử ra đời của Sudoku

Mặc dù được phổ biến bởi một công ty Nhật Bản có tên Nikoli vào năm 1984 và đến năm 2005 chính thức trở thành tên gọi quốc tế của trò chơi, Sudoku không phải có nguồn gốc từ nước mặt trời mọc. Dạng sơ khai của Soduku xuất hiện từ cuối thế kỷ 19 khi nó được đăng trên báo Le Siècle của Pháp. Ở thời điểm ấy trò chơi ô chữ cũng bao gồm một hình vuông to có kích thước 9x9 ô vuông nhỏ hơn, các ô nhỏ này cũng tạo thành các hình vuông trung bình 3x3 như chúng ta thấy ngày nay. Để giải ô chữ độc giả cũng phải điền các con số sao cho mỗi hàng dọc, hàng ngang, và các ô 3x3 sao cho chúng phải bao gồm cùng một bộ số. Tuy nhiên điểm khác biệt là các ô nhỏ khi đó có thể chứa một số có hai chữ số, do đó nó mang dáng dấp của một trò chơi số học hơn là logic như bây giờ. Có lẽ các bạn từng có điều kiện đọc nhiều tài liệu về số học ở cấp II sẽ dễ hình dung nó có vài nét tương đồng với các bài toán ma phương.


Trong ma trận 3x3 ở trên, các bộ {5,3-11} hay {-3,-1,3} tạo thành một tam giác với đường chéo phụ

Tới năm 1895, tờ báo cạnh tranh với Le Siècle là La France đã cách tân trò chơi và làm cho nó khá giống với Sudoku hiện đại. Họ đưa ra một số luật chơi mới bao gồm: giới hạn các số từ 1-9 ở mỗi hàng, mỗi cột, cũng như mỗi hình tam giác có cạnh đáy là một đường chéo phụ và đỉnh còn lại là vị trí ở góc của ma trận. Mặc dù kiểu ô chữ như vậy không có điều kiện áp đặt cho các ô 3x3, nhưng điều kiện về tam giác đường chéo phụ sẽ tự động dẫn tới hệ quả này.

Vì lý do lịch sử, trò giải ô số 9x9 bị lãng quên sau thế chiến thứ nhất, và phải tới năm 1979 trò này mới được Howard Garns (người Mỹ) giới thiệu trở lại với công chúng cùng luật chơi như hiện tại. Năm 1984 Nipoli đã phổ biến rộng rãi trò giải ô chữ của Garns với tên gọi Sudoku ở Nhật và nó phát triển trên toàn thế giới như chúng ta thấy hiện nay. Bản thân từ Sudoku trong tiếng Nhật có nghĩa là những con số có một chữ số.

Khó khăn khi chơi các Soduku phức tạp

Với các kiểu Sudoku đơn giản, nhiều ô trong bảng 9x9 đã được mở, người chơi chỉ cần dựa vào phán đoán logic để giải mã hoàn toàn những số cần điền. Tuy nhiên, với các bảng phức tạp hơn, tư duy logic chỉ làm việc với một số hữu hạn ô chữ, phần còn lại người chơi gần như phải sử dụng các phép thử một cách thủ công để đưa ra các phương án khả dĩ cho tới khi tìm ra lời giải đúng. Tất nhiên, nếu chúng ta có thời gian thì việc này cũng không có gì đáng kể, nhưng thực sự thay từng phương án như thế rất tốn công và thường làm mọi người nản chí.

Do tính chất cần sự phán đoán, việc lập trình giải mã trò chơi là không hề đơn giản. Chúng ta có thể thấy rằng với một bảng Sudoku, giải thuật thông thường chỉ có thể sử dụng để đưa ra một hệ phương trình tuyến tính cùng điều kiện hạn chế để các ẩn số là các số nguyên từ 1-9. Tuy nhiên, số phương trình cùng số điều kiện lại luôn luôn ít hơn số ẩn, do đó tất yếu là nghiệm của hệ sẽ trở nên suy biến. Nói cách khác chúng ta sẽ thu được không phải là một nghiệm duy nhất mà là một bộ nghiệm. Như vậy, cuối cùng mỗi nghiệm sẽ vẫn tương đương với các phương án khả dĩ của phán đoán ở trên và chúng ta vẫn phải thử lại.

Nghiên cứu giải thuật cho Sudoku tại Đại học Notre Dame

Mục tiêu của các nhà khoa học tại Đại học Notre Dame là tạo ra một phương pháp giải Sudoku không cần sử dụng các phán đoán để rút ngắn thời gian. Để đạt được mục tiêu đó thì họ phải vận dụng các thành tựu của lý thuyết tối ưu và lý thuyết độ phức tạp tính toán trong quá trình nghiên cứu. Kết quả là họ đã thiết lập được một thuật toán đặc biệt cho các bài đố Sudoku mà không cần các phép thử nhàm chán với lời giải chính xác trong thời gian ngắn.

Hơn nữa, họ cũng chỉ ra với giải thuật mới, độ khó của Sudoku tương đương với thời gian cần thiết để mở toàn bộ các ô số. Sự đánh giá này cũng khớp với độ khó được các nhà thiết kế Sudoku đưa ra. Để dễ dàng định lượng, thang độ phức tạp sẽ được chia ra từ 1 tới 4, tương ứng với các mức độ từ dễ, tới khó và cực khó. Theo tính toán, Sudoku cấp độ 2 đòi hỏi thời gian công phá gấp 10 lần cấp độ 1, trong khi Sudoku khó nhất bây giờ được đánh giá ở mức 3.6. Hiện chưa rõ khi nào người ta có thể thiết kế Sudoku khó hơn nữa.

Ứng dụng

Mặc dù thuật toán được đưa ra là để thỏa mãn việc giải những ô số Sudoku như một niềm đam mê, nhóm nghiên cứu cũng tin tưởng những bước phát triển và sự tối ưu trong phương pháp này có thể ứng dụng rộng rãi trong các bài toán công nghiệp, khoa học máy tính và sinh học tính toán. Không rõ là các tác giả có định đưa ra một phần mềm phổ biến trên cơ sở giải thuật của họ hay không. Tuy nhiên, sự thú vị của trò Sudoku lại nằm ở điểm nó tạo cảm giác thách thức trí tuệ của người chơi, do vậy nếu có một phần mềm hỗ trợ thì hi vọng các bạn chỉ sử dụng nó để tham khảo thôi nhé.

Nguồn: PhysOrg, Notre Dame University, Wikipedia

Về VNMATH.COM

VNMATH hoạt động từ năm 2008 với slogan Trao đổi để học hỏi, Sẻ chia để vươn lên. Hiện nay VNMATH.COM là trang web Toán học có lượt truy cập lớn nhất Việt Nam.

Chia sẻ bài viết này


Bài viết liên quan

Không có nhận xét nào :

Để lại Nhận xét