3 Một số bài toán ứng dụng
3.5 Bài toán Sudoku
Vào thế kỷ thứ XVIII nhà toán học Leonhard Euler đã sáng tạo ra trò chơi hình vuông Latinh, với luật chơi là sự sắp xếp các con số sao cho chúng không trùng lặp theo chiều ngang lẫn chiều dọc. Sau đó trò chơi này du nhập vào Nhật và được nhà xuất bản Nikoli đổi tên thành Sudoku. Bài toán đặt ra cho người chơi như sau
Điền số từ 1 đến9 vào những ô trống của bảng hình vuông (9x9) sao cho mỗi cột dọc, mỗi hàng ngang, mỗi khối vuông nhỏ (ô 3x3) có đủ các số từ 1 đến 9
mà không được lặp lại. Trong bảng có một vài ô nhỏ được đánh số tuỳ theo mức độ nhiều hay ít của các manh mối, các câu đố được xếp loại dễ, trung bình, khó hay cực khó. Ngoài ra, còn những bảng như 4x4, 16x16, 25x25hay thậm chí
100x100.
Đã có nhiều nhà toán học sử dụng các phương pháp khác nhau để giải các câu đố về Sudoku. Năm2007, hai nhà toán học Herzberg và Murty đã phát triển một phương pháp để tính số cách mà người ta có thể tô màu các đỉnh của một đồ thị, được tô màu một phần sao cho không có hai đỉnh liền kề nào có cùng màu. Bằng phương pháp này, ta có thể tìm ra bao nhiêu lời giải cho một câu đố Sudoku nhất định.
Sau đây là lời giải cho bài toán Sudoku ở trên. Trước hết, chúng ta chuyển bảng Sudoku với 9Ö9 ô Sudoku thành một đồ thị. Đồ thị sẽ có 81 đỉnh với mỗi đỉnh tương ứng với một ô trong bảng. Hai đỉnh khác biệt sẽ kề nhau nếu và chỉ nếu các ô tương ứng trong bảng nằm trong cùng một hàng, hoặc cùng một cột, hoặc cùng một bảng con (3x3). Bảng Sudoku giải xong khi đồ thị được tôk màu thích hợp.
đỉnh có nhãn (i, j) với 1 ≤ i, j ≤ n2. Ta nói rằng (i, j) và (i0, j0) là liền kề nếu
i=i0 hoặc j =j0 hoặc [i/n] = [i0/n] và [j/n] = [j0/n] (kí hiệu [.] chỉ phần nguyên của một số). Kí hiệu đồ thị này là Xn và gọi nó là đồ thị Sudoku hạng n. Đồ thị
được gọi là đều nếu tung độ của mọi đỉnh là như nhau. Ta tính được bậc của đồ thị đều Xn là 3n2−2n−1 = (3n+ 1)(n−1). Trường hợp n = 3 thì mỗi đỉnh
của X3 có bậc 20 và số cạnh |H|= 20x81/2 = 810.
Thuật toán tô màu đồ thị Sudoku gồm các bước sau
Bước 1: Đỉnh đã được tô màu được chọn và liên kết bằng các cạnh cùng màu với tất cả các đỉnh khác của tập hợp mà đỉnh nằm trong đó. Các đỉnh này không còn có thể được tô cùng màu. Điều này được lặp lại cho tất cả các đỉnh mà các gợi ý được đưa ra.
Bước 2: Các đỉnh mà số lượng các cạnh màu lớn nhất hội tụ được tìm thấy (rất có thể chỉ có một ứng cử viên).
Bước 3: Nếu có các đỉnh trong số chúng chỉ có thể được tô màu bằng một màu, thì chúng được tô màu với nó và quy trình tiếp tục từ bước đầu tiên (không cần vẽ các cạnh đó vào đồ thị dẫn đến một đỉnh đã có cạnh khác cùng màu). Nếu không có đỉnh nào như vậy, quy trình tiếp tục với Bước 4.
Bước 4: Từ tập hợp các đỉnh đã chọn đó, đỉnh liền kề với số lượng lớn nhất của các đỉnh không được tô màu sẽ được chọn và tô màu thành màu có giá trị thấp nhất không được sử dụng cho các đỉnh lân cận của nó. Nếu có nhiều đỉnh như vậy, một trong số chúng được chọn ngẫu nhiên. Trong bước tiếp theo, thuật toán tiếp tục từ bước đầu tiên.
Chuyển sang đồ thị Sudoku có 16 đỉnh và 56 cạnh như dưới đây
Đồ thị sau khi thực hiện Bước 2.
Ta có ma trận biểu diễn
Ví dụ 3.5.2. Cho bài toán Sudoku có kích thước 9x9 như sau
Kết luận
Trong luận văn này chúng tôi đã thực hiện được các công việc sau đây. 1. Trình bày một số vấn đề về tô màu đồ thị, và sắc số của đồ thị (Mệnh đề 1.2.2, Mệnh đề 1.2.3). Tính toán chi tiết và tường minh sắc số của đồ thị (Mệnh đề 1.2.7, Mệnh đề 1.2.8, Mệnh đề 1.2.9, Mệnh đề 1.2.10). Trình bày thuật toán tô màu đỉnh đồ thị (Mục 1.3, Ví dụ 1.3.1).
2. Trình bày một số vấn đề về đa thức màu của đồ thị (Mệnh đề 2.1.4, Mệnh đề 2.1.5, Mệnh đề 2.1.6, Mệnh đề 2.1.7). Tính toán chi tiết và tường minh đa thức màu của một số họ đồ thị đặc biệt có bậc 1≤n≤4 (Ví dụ 2.2.10).
3. Sưu tầm và trình bày chi tiết lời giải một số bài toán có nội dung thực tế liên quan đến tô màu đỉnh của đồ thị: Bài toán điều khiển đèn tín hiệu giao thông (Mục 3.1), bài toán lập lịch thi (Mục 3.2), bài toán lập thời khóa biểu (Mục 3.3), bài toán phân chia tần số (Mục 3.4), bài toán Sudoku (Mục 3.5).
Danh mục tài liệu tham khảo
[1] Vũ Đình Hòa (2003), Định lý và vấn đề về đồ thị hữu hạn, Nhà xuất bản Giáo dục, Hà Nội.
[2] Berge C. (1971) Lý thuyết đồ thị và ứng dụng, Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội.
[3] J. Bondy, U. Murty (1967), Graph theory with applications, American Else- vier Pub, New York.
[4] G. Chartrand, L. Lesniak (2005), Graphs and Digraphs, Chapman and Hall/CRC, London.
[5] R. Diestel (2006), Graph Theory, Springer-Verlag New York, New York. [6] Graph Theory Part 2. http://web.math-alive/5/Notes2.pdf.
[7] The University of Sydney Math (2009), Graph Theory, Tutorial 8 Solutions (2004).
[8] Sudoku Squares and Chromatic Polynomials, Agnes M.Heberg and M.Ram Murty. https://www.ams.org/notices/200706/tx070600708p.pdf