Sotithieutrongtrochoisudoku

Đối với các nhà toán học, đột nhiên được giải quyết một vấn đề lâu dài luôn là một khoảnh khắc hạnh phúc. Năm 2012 bắt đầu với thời điểm như vậy, khi một nhà toán học Ireland tên là Gary McGuire đã công bố một giải pháp cho vấn đề số đầu mối tối thiểu trong trò chơi Sudoku. Bạn đã thấy trò chơi Sudoku? không nghi ngờ gì nữa, vì ngày nay, nó phổ biến trên các báo và tạp chí. Trông nó như thế này:
 


 
 
Nhiệm vụ của bạn là điền vào trong các ô bỏ trống với những chữ số từ 1-9 theo cách như vậy mỗi hàng, cột và khối 3x3 chứa mỗi con số chính xác một lần. Trong một trò chơi thích hợp, các đầu mối bắt đầu như vậy để đảm bảo có 1 và chỉ một cách để hoàn thành hình vuông. Trò chơi này đặc biệt chỉ có 17 đầu mối bắt đầu. Nó đã từ lâu được tin rằng 17 là số lượng tối thiểu cho bất kỳ 1 trò chơi thích hợp. Nhà toán học Gordon Royle duy trì một cơ sở dữ liệu trực tuyến hiện có gần 50.000 câu đố với 17 đầu mối bắt đầu (trong thực tế, các câu đố trên được chuyển thể từ một trong những câu đố trong danh sách đó). Tuy nhiên, mặc dù tìm kiếm bằng máy tính, người ta vẫn không tìm thấy ví dụ cho 1 trò chơi với 16 hoặc ít hơn những đầu mối. Vấn đề là tìm kiếm máy tính đầy đủ dường như không thể. Đơn giản bởi có quá nhiều khả năng để xem xét. Ngay cả bằng cách sử dụng các phần cứng hiện đại nhất, và sử dụng các kỹ thuật tìm kiếm hiệu quả nhất được biết đến, hàng trăm hàng ngàn năm mới được yêu cầu. Tương tự, Toán học thuần túy cũng hỗ trợ được rất ít. Nó rất dễ dàng để thấy rằng bảy đầu mối là không đủ. Với bảy đầu mối bắt đầu sẽ có ít nhất hai chữ số mà không được xuất hiện khi bắt đầu trò chơi. Để cụ thể, chúng ta hãy nói rằng đã có không có số 1 hoặc 2 trong bảng bắt đầu. Khi đó, trong bất kỳ cách hoàn thành nào, chỉ cần thay các ô 1 bởi 2 và các ô 2 bởi 1, ta sẽ tạo ra một lời giải thứ hai hợp lệ để câu đố. Tuy nhiên, sau khi quan sát này, ta đã không biết làm thế nào để tiếp tục. Ngay cả một lập luận đơn giản là chứng minh sự bất cập của tám đầu mối đã được khẳng định là rất khó Giải pháp của McGuire đòi hỏi một sự kết hợp của toán học và khoa học máy tính. Để giảm thời gian cần thiết cho một tìm kiếm đầy đủ, ông đưa ra ý tưởng về một  "tập hợp không thể tránh khỏi" (Hãy xét các ô được tô đậm)


 
Bây giờ tưởng tượng ra một câu đố bắt đầu có hình vuông này cho một giải pháp. Bạn có thể thấy lý do tại sao chúng ta sẽ cần phải có ít nhất một đầu mối bắt đầu từ một trong những “tế bào” được tô đậm? Lý do là nếu không như vậy, sau đó ta sẽ có thể chuyển đổi các chữ số trong các ô để tạo ra một giải pháp thứ hai cho cùng một câu đố. Trong thực tế, đặc biệt Sudoku vuông, có rất nhiều bộ tương tự như "bộ không thể tránh khỏi", nói chung một số hình vuông sẽ có nhiều hơn những cái khác, và các loại khác nhau. Một phần của giải pháp McGuire liên quan đến việc tìm kiếm một bộ sưu tập lớn của một số "các bộ không thể tránh khỏi" trong mỗi hình vuông Sudoku được xem xét. Tìm kiếm các "bộ không thể tránh khỏi" cho phép giảm đáng kể kích thước của không gian phải được tìm kiếm. Thay vì tìm kiếm thông qua tất cả các tập hợp con 16 đầu mối của một Sudoku vuông, sự tìm kiếm tuyệt vọng thực sự cho một câu đố thích hợp, chúng tôi chỉ cần xem xét tập hợp của 16 đầu mối bắt đầu có chứa ít nhất một “tế bào” từ mỗi “bộ không thể tránh khỏi” được biết đến. Tìm kiếm những bộ cụ thể của các đầu mối bắt đầu là 1 ví dụ cụ thể của 1 vấn đề tổng quát hơn, đó là thuật toán để giải quyết các vấn đề tập hợp đánh một lượng hợp lý "vấn đề tập hợp đánh." số lần. Giải quyết vấn đề tối thiểu đầu mối cho Sudoku là một ứng dụng của thuật toán mới này. Tất nhiên, thận trọng là cần thiết cho đến khi các nhà nghiên cứu có thời gian để kiểm tra kỹ các lập luận của McGuire. Nó là một trong những sự “tàn bạo” của toán học nhằm cẩn thận tránh những lỗi tinh tế của các nghiên cứu viên. Chúng ta chắc chắn có thể nói, mặc dù, rằng các kỹ thuật đang được sử