Tóm tắt: Tô màu đồ thị là một trong những bài toán cơ bản của Lý thuyết đồ thị, được ứng dụng nhiều trong tin học, nhằm giải quyết các vấn đề thực tiễn liên quan đến phân hoạch, phân nhóm, bản đồ… Sudoku là một trò chơi logic xuất xứ từ Nhật Bản được nhiều bạn trẻ yêu thích. Để giải quyết bài toán Sudoku trong tin học, chúng ta có thể sử dụng phương pháp đệ quy quay lui, nhưng trong bài báo này, mình xin được giới thiệu tới các bạn phương pháp sử dụng giải thuật tô màu đồ thị. Do việc lập trình bài toán tô màu đồ thị không khó (code trên mạng khá nhiều), nên mình chỉ dừng lại ở nội dung xây dựng được đồ thị cần tô màu, thì coi như chúng ta đã giải quyết được bài toán.
1. Bài toán tô màu đồ thị Tô màu (đỉnh) đồ thị là việc thực hiện gán màu cho mỗi đỉnh của đồ thị, sao cho hai đỉnh kề nhau không cùng một màu, và số màu được sử dụng là ít nhất. Số màu ít nhất có thể sử dụng để tô màu đồ thị được gọi là sắc số của đồ thị đó.
Thuật toán tô màu đồ thị được đề cập đến trong các tài liệu về Toán rời rạc hoặc Cấu trúc dữ liệu & Giải thuật. Chúng ta có thể trình bày các bước thuật toán dễ hiểu như sau:
Input: đồ thị G = (V, E).
Output: đồ thị G = (V, E) có các đỉnh đã được gán màu.
Các bước của thuật toán: Bước 1: Tính giá trị bậc của các đỉnh trong V. Lập danh sách V’:=[v1tv2, ...,vn] là các đỉnh của đồ thị được sắp xếp theo thứ tự bậc giảm dần: d(v1) > d(v2) > ... > d(vn). Ban đầu tất cả các đỉnh trong V (V’) đều chưa được tô màu.
Gán i := 1;
Bước 2: Tô màu i cho đỉnh đầu tiên trong danh sách V’. Duyệt lần lượt các đỉnh khác trong V’(nếu có) và chỉ tô màu i cho các đỉnh không kề đỉnh đã có màu i.
Bước 3: Kiểm tra nếu tất cả các đỉnh trong V đã được tô màu thì thuật toán kết thúc, đồ thị đã sử dụng i màu để tô. Ngược lại, nếu vẫn còn đỉnh chưa được tô thì chuyển sang bước 4.
Bước 4: Loại khỏi danh sách V’ các đỉnh đã tô màu. Sắp xếp lại các đỉnh trong V’ theo thứ tự bậc giảm dần. Gán i := i + 1 và quay lại bước 2.
Để dễ hiểu hơn, các bạn xem sự thể hiện các bước của thuật toán trong ví dụ sau: Cho đồ thị như hình vẽ, sử dụng thuật toán tô màu đồ thị ở trên, tô màu cho các đỉnh của đồ thị.
Bước 1: Ta có đồ thị có 5 đỉnh được đánh số 1, 2, 3, 4, 5 với các bậc tương ứng với từng đỉnh theo thứ tự là 3, 1, 2, 1, 3. Do đó V’ ban đầu có thứ tự là [1, 5, 3, 2, 4]. Gán i =1.
Bước 2: Tô màu 1 (red) cho đỉnh 1. Lần lượt duyệt các đỉnh còn lại trong V’:
Ta có: Đỉnh 5 kề đỉnh 1 (đỉnh 1 đã tô màu 1 - red) nên chưa tô màu cho đỉnh 5. Tương tự các đỉnh 3, 2 đều kề với đỉnh 1 nên đỉnh 3, 2 cũng chưa được tô màu.
Đỉnh 4 không kề với đỉnh 1, do đó thực hiện tô màu 1 cho đỉnh 4. Đỉnh 4 có màu 1 - red.
Bước 3: Kiểm tra thấy vẫn còn các đỉnh trong V chưa được tô màu nên chuyển sang bước 4.
Bước 4: Loại bỏ các đỉnh 1, 4 đã được tô màu ra khỏi V’, sắp xếp lại V’ theo thứ tự bậc giảm dần, ta thu được V’= [5, 3, 2]. Ta có i = 2. Thực hiện lặp lại bước 2:
Bước 2(1): Tô màu 2 (blue) cho đỉnh 5. Lần lượt duyệt các đỉnh còn lại trong V’. Ta có: Đỉnh 3 kề đỉnh 5 (đã tô màu 2 - blue) nên chưa tô màu cho đỉnh 3.
Đỉnh 2 không kề với đỉnh 5, do đó thực hiện tô màu 2 cho đỉnh 2. Đỉnh 2 có màu 2 - blue.
Bước 3(1): Kiểm tra thấy vẫn còn đỉnh 3 chưa được tô màu nên chuyển sang bước 4.
Bước 4(1): Loại bỏ các đỉnh 5, 2 đã được tô màu ra khỏi V’, V’=[3]. Ta có i = 3. Thực hiện lặp lại bước 2:
Bước 2(2): Tô màu 3 (Green) cho đỉnh 3.
Bước 3(2): Kiểm tra thấy tất cả các đỉnh trong V đã được tô màu, thuật toán dừng lại. Kết luận: Đỉnh 1 và 4 được tô màu 1-red, đỉnh 5 và đỉnh 2 được tô màu 2-blue, đỉnh 3 được tô màu 3-Green. Số màu cần thiết phải sử dụng là i =3 màu.
Bài toán tô màu đồ thị thường được ứng dụng để giải quyết vấn đề tô màu (các nước) trên bản đồ, sắp xếp lịch thi - phòng thi. Sau đây chúng ta xem xét ứng dụng của nó trong việc giải quyết bài toán Sudoku.
2. Bài toán Sudoku và cách giải quyết ứng dụng tô màu đồ thị Sudoku là một loại trò chơi logic, cách chơi là điền số từ 1 đến 9 vào những ô trống sao cho mỗi cột dọc, mỗi hàng ngang, mỗi phân vùng nhỏ (ô 3x3) có đủ các số từ 1 đến 9 mà không được lặp lại. Trò chơi có bảng câu đố hình vuông, mỗi chiều có 9 ô nhỏ, hợp thành 9 cột, 9 hàng và được chia thành 9 ô lớn 3x3. Một vài ô nhỏ được đánh số, đó là những manh mối duy nhất để bạn tìm lời giải. 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ư 16x16, 25x25 hay thậm chí 100x100, nhưng ở đây chúng ta xem xét cho trường hợp điển hình, bảng 9 x 9.
Trên quan điểm bảng câu đố này là một đồ thị, và mỗi ô vuông nhỏ (cell) là một đỉnh của đồ thị. Như vậy, đồ thị sẽ có 81 đỉnh. Những cặp đỉnh nào có ràng buộc sẽ có cạnh giữa chúng. Bài toán Sudoku dẫn ta về việc phải thực hiện tô màu cho đồ thị này, nếu việc sử dụng 9 màu có thể tô 81 đỉnh của đồ thị, và thỏa mãn tất cả các ràng buộc, thì bài toán được giải quyết thành công, và những ô tương ứng với các đỉnh cùng màu, thì được điền cùng một số. Bài toán Sudoku cũng có thể có 1, nhiều hơn 1 hoặc không có phương án điền số nào thỏa mãn tất cả các ràng buộc.
Vấn đề giờ là xây dựng được đồ thị cần tô màu, ứng với mỗi bài toán Sudoku cụ thể. Đồ thị này, như ta đã biết, có 81 đỉnh (9x9), việc quan trọng còn lại là xác định các cạnh của đồ thị, dựa trên các ràng buộc của bài toán. Trong một bài toán Sudoku, chúng ta có hai loại ràng buộc, đó là ràng buộc chung, là ràng buộc của mọi bài toán Sudoku: là số duy nhất trong hàng, trong cột và trong khối, ngoài ra còn có ràng buộc riêng, là ràng buộc về dữ liệu của bài toán cụ thể, ràng buộc giữa các đỉnh ứng với các ô đã điền được điền số, với các đỉnh ứng với các ô khác.
Ta đánh chỉ số các đỉnh từ 0 đến 80, theo thứ tự tương ứng với các ô từ trái qua phải, trên xuống dưới.
Cells[i] là ô tương ứng với đỉnh có chỉ số i, mỗi Cells[i] có 3 trường:
Cells[i].Row trả về giá trị hàng,
Cells[i].Column trả về giá trị cột của ô,
Cells[i].Value trả về giá trị số được điền trong ô. Giá trị của Cells[i].Row, Cells[i].Column, và Cells[i].Value đều trong khoảng [1,9]. Hàm
AddUndirectedEdge(cells[i], cells[idx]) là hàm thiết lập một cạnh nối đỉnh i và đỉnh idx, biểu trưng cho ràng buộc giữa ô
Cells[i] và ô
Cells[idx] nếu giữa chúng chưa thiết lập ràng buộc. Vì số lượng ràng buộc giữa các cặp định là rất nhiều, ta cần có thủ thuật lập trình để có thể xử lý trọn vẹn, thể hiện được tất cả các ràng buộc ứng với từng bài toán Sudoku cụ thể.
a. Lập trình xử lý ràng buộc chungVới mỗi ô Cells[i], i thuộc đoạn [0,80], Cells[idx] là ô có ràng buộc chung với Cells[i]. Trong ngôn ngữ C# chúng ta có thể lập trình như sau để vét hết các idx:
=========================================================================
private static void CreatePuzzleEdges(Graph graph)
{
//Mảng các đỉnh ứng với các ô chung hàng 1
var horizontalIndices = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8};
//Mảng các đỉnh ứng với các ô chung cột 1
var verticalIndices = new int[] {0, 9, 18, 27, 36, 45, 54, 63, 72};
//Mảng các đỉnh ứng với các ô chung khối 1 (3 x 3)
var diagonalIndices = new int[] {0, 1, 2, 9, 10, 11, 18, 19, 20};
//Biến idx lưu đỉnh có ràng buộc với đỉnh i
int idx=1, int r=1, int c=1;
//Lần lượt duyệt các đỉnh từ 0 đến 80
for (int i = 0; i < 81; i++)
{
//r là chỉ số của dòng, tính từ 0. Cells[i].Row = 1, i thuộc mảng horizontalIndices
r = cells[i].Row - 1;
//c là chỉ số của cột, tính từ 0. Cells[i].Column = 1, i thuộc mảng verticalIndices
c = cells[i].Column - 1;
for (int j = 0; j < 9; j++)
{
//idx la đinh ứng với ô Cells[idx] cùng hàng với ô Cells[i]
idx = horizontalIndices[j] + r*9;
if (idx != (r*9 + c)) //Nếu idx == i thì bỏ qua
//Thực hiện tạo cạnh nối hai đỉnh idx và i
AddUndirectedEdge(cells[i], cells[idx]);
//idx la đinh ứng với ô Cells[idx] cùng cột với ô Cells[i]
idx = verticalIndices[j] + c;
if (idx != (r*9 + c)) //Nếu idx == i thì bỏ qua
//Thực hiện tạo cạnh nối hai đỉnh idx và i
AddUndirectedEdge(cells[i], cells[idx]);
//idx la đinh ứng với ô Cells[idx] nằm cùng một khối 3x3 với ô Cells[i]
idx = diagonalIndices[j] + ((r/3)*3)*9 + (c/3)*3;
if (idx != (r*9 + c)) //Nếu idx == i thì bỏ qua
//Thực hiện tạo cạnh nối hai đỉnh idx và i
AddUndirectedEdge(cells[i], cells[idx]);
} }
}
=========================================================================
b. Lập trình xử lý các ràng buộc riêng
Cũng dựa trên ý tưởng xử lý ràng buộc chung, ta có thể xử lý trọn vẹn các ràng buộc về dữ liệu cụ thể của bài toán như sau:
- Với mỗi ô Cells[i] (ứng với đỉnh i) đã được điền số, tìm tất cả các đỉnh idx (ứng với ô Cells[idx]) cũng đã được điền số, thỏa mãn Cells[i].Value != Cells[idx].Value, khí đó, giữa hai đỉnh i và idx phải có ràng buộc.
- Với mỗi ô Cells[i] (ứng với đỉnh i) đã được điền số, tìm tất cả các đỉnh node (khác đỉnh i), ứng với ô Cells[node] (đã được điền số) thỏa mãn Cells[i].Value == Cells[node].Value (đỉnh i cùng màu với đỉnh node), khi đó đỉnh i cũng phải có ràng buộc với tất cả các đỉnh có ràng buộc với node. Tức là, nếu idx là một đỉnh đang có ràng buộc với đỉnh node, thì idx cũng phải có ràng buộc với đỉnh i. Tư tưởng đó được thể hiện trong đoạn lập trình sau:
=========================================================================
private static void CreateInstanceEdges(Graph
graph)
{
//Với mỗi ô sudokuCells thuộc danh sách cells
foreach (var sudokuCell in cells)
{
if (sudokuCell.Value.HasValue) //Nếu ô sudokuCells có dữ liệu
{
//Danh sách others gồm các ô có giá trị khác sudokuCells
var others = cells
.Where(c => c.Value.HasValue && c.Value.Value != sudokuCell.Value.Value);
//Với mỗi ô other thuộc danh sách others
foreach (var other in others)
{
//Thực hiện tạo cạnh nối hai đỉnh ứng với hai ô sudokuCells và other
AddUndirectedEdge(sudokuCell, other);
}
var horizontalIndices = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8};
var verticalIndices = new int[] {0, 9, 18, 27, 36, 45, 54, 63, 72};
var diagonalIndices = new int[] {0, 1, 2, 9, 10, 11, 18, 19, 20};
int idx=1, int r=1, int c=1;
//Danh sách equals chứa các ô có cùng giá trị Value với ô sudokuCells
var equals = cells
.Where(c => c.Value.HasValue && c.Value == sudokuCell.Value && c!= sudokuCell)
.ToList();
//Với mỗi ô node trong danh sách equals
foreach (var node in equals)
{
//Tìm đỉnh idx ứng với ô có ràng buộc với ô node
r = node.Row - 1;
c = node.Column - 1;
for (int j = 0; j < 9; j++)
{
//đỉnh idx ứng với ô có cùng hàng với ô node
idx = horizontalIndices[j] + r*9;
if (idx != (r*9 + c))
//Thiết lập ràng buộc giữa sudokuCells và Cells[idx]
AddUndirectedEdge(sudokuCell, cells[idx]);
//đỉnh idx ứng với ô có cùng cột với ô node
idx = verticalIndices[j] + c;
if (idx != (r*9 + c))
//Thiết lập ràng buộc giữa sudokuCells và Cells[idx]
AddUndirectedEdge(sudokuCell, cells[idx]);
//idx la đinh ứng với ô Cells[idx] nằm cùng một khối 3x3 với ô node
idx = diagonalIndices[j] + ((r/3)*3)*9 + (c/3)*3;
if (idx != (r*9 + c))
//Thiết lập ràng buộc giữa sudokuCells và Cells[idx]
AddUndirectedEdge(sudokuCell, cells[idx]);
} }
}
}
}
=========================================================================
c. Giải quyết bài toán Sudoku và thông báo kết quả
Như vậy là ta đã thiết lập xong đồ thị ứng với một bài toán Sudoku cụ thể. Ta sẽ tô màu đồ thị ấy. Nếu việc sử dụng 9 màu có thể tô 81 đỉnh của đồ thị, và thỏa mãn tất cả các ràng buộc, thì bài toán được giải quyết thành công, và những ô tương ứng với các đỉnh cùng màu, thì được điền cùng một số. Bài toán Sudoku có thể có 1, nhiều hơn 1 hoặc không có phương án nào được chấp nhận.
3. Kết luận và đánh giá
Như vậy bài báo đã trình bày về giải thuật tô màu đồ thị và ứng dụng của nó trong việc giải quyết bài toán Sudoku. So với việc sử dụng kỹ thuật đệ quy quay lui, tốc độ xử lý khi sử dụng tô màu đồ thị cao hơn nhiều. Tuy nhiên, một điều ta cần phải lưu ý rằng: Thuật toán tô màu đồ thị được nêu ở trên, dù được sử dụng rất rộng rãi, nhưng đã được chứng minh là không đúng trong mọi trường hợp. Thuật toán chỉ đảm bảo việc tô màu sẽ thỏa mãn các rảng buộc, nhưng tiêu chí số màu tô là tối thiểu thì có thể không đạt được. Vì thế các nhà khoa học hiện tại vẫn coi thuật toán này đúng một cách xấp xỉ (tuyệt đại đa số trường hợp). Cũng chính vì vậy, thay vì việc phải đi tìm chính xác sắc số của một đồ thị nào đó, người ta thường tiếp cận vấn đề theo hướng trả lời cho câu hỏi: Có thể dùng m màu để tô cho một đồ thị cụ thể có n đỉnh hay không? Trong trường hợp cụ thể của bài toán Sudoku là trả lời câu hỏi liệu có thể dùng 9 màu để tô cho đồ thị 81 đỉnh hay không? Thuật toán tô màu trên có thể được sử dụng để tô màu đồ thị phẳng và không phẳng. Đối với đồ thị phẳng thì đây là một bài toán kinh điển, và sắc số của một đồ thị phẳng đã được chứng minh là không quá 4 (định lý 4 màu), đối với đồ thị không phẳng, sắc số sẽ lớn hơn. Ta dễ dàng nhận thấy, đồ thị ứng với mỗi bài toán Sudoku là một đồ thị không phẳng.
Vấn đề liên quan đến tô màu đồ thị nói chung hiện vẫn chưa có được những thống nhất trọn vẹn, nhất là về tính đúng của sắc số trong mọi trường hợp hay độ phức tạp tính toán đa thức hay phi đa thức của thuật toán. Tuy không đảm bảo tính tối ưu, nhưng việc đảm bảo về ràng buộc, thuật toán tô màu đồ thị nói trên đã giúp chúng ta giải quyết rất nhiều bài toán quan trọng được đặt ra trong thực tiễn.
Tác giả bài báo mong muốn nhận được những trao đổi, góp ý chân thành của bạn đọc để có thể nâng cao chất lượng các bài viết. Xin trân trọng cảm ơn.Người viết bài: Nguyễn Tuấn Nghĩa