Đề tài Các bài toán SUDOKU

120 trang yendo 5900

Download

Bạn đang xem 20 trang mẫu của tài liệu "Đề tài Các bài toán SUDOKU", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

de_tai_cac_bai_toan_sudoku.pdf

Nội dung text: Đề tài Các bài toán SUDOKU

Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU NHẬN XÉT CỦA GIÁO VIÊN HƢỚNG DẨN TpHCM, ngày tháng năm Giáo viên hƣớng dẫn [Ký tên và ghi rõ họ tên] Trang 3
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN TpHCM, ngày tháng năm . Giáo viên phản biện [Ký tên và ghi rõ họ tên] Trang 4
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU LỜI CẢM ƠN Chúng em xin gửi lời cảm ơn chân thành đến tất cả các Thầy Cô đã giảng dạy chúng em trong suốt thời gian qua. Cảm ơn Thầy Trần Quảng Hồng - ngƣời đã hƣớng dẫn chúng em thực hiện đồ án này. Nhân đây, chúng con cũng xin bày tỏ lòng biết ơn sâu sắc đến Ba Mẹ và gia đình đã nuôi dạy chúng con nên ngƣời, và luôn là chỗ dựa tinh thần vững chắc, giúp cho chúng con vƣợt qua mọi khó khăn, thử thách trong cuộc sống. Bên cạnh đó, để hoàn thành đồ án này, chúng em cũng đã nhận đƣợc rất nhiều sự giúp đỡ, những lời động viên quý báu của các bạn bè, các anh chị thân hữu, chúng em xin hết lòng ghi ơn. Tuy nhiên, do kiến thức còn hạn hẹp, mặc dù đã nỗ lực hết sức mình, nhƣng chắc rằng đồ án khó tránh khỏi thiếu sót. Chúng em rất mong nhận đƣợc sự thông cảm và chỉ bảo tận tình của quý Thầy cô và các bạn. Xin chân thành cảm ơn. Tp.HCM, 7/2009 Nhóm sinh viên thực hiện Lê Quang Tâm Lƣu Văn Viết Trang 5
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU ĐỀ CƢƠNG CHI TIẾT Tên Đề Tài: Các Bài Toán Về Sudoku Giáo viên hƣớng dẫn: Trần Quản Hồng Thời gian thực hiện: Từ ngày 9/3 đến ngày 26/7. Sinh viên thực hiện: Lƣu Văn Viết MSSV: 206205371 Lê Quang Tâm MSSV: 206205348 Loại đề tài: Tìm hiểu các bài toán Sudoku Nội Dung Đề Tài: Các bài Toán về Soduku Mô tả: Tìm hiểu thuật toán và xây dựng ứng dụng để giải quyết 1 số bài toán soduku Yêu cầu: Sử dụng bộ công cụ Visual Studio 2005, ngôn ngữ sử dụng là Csharp Phƣơng pháp thực hiện: Làm việc theo nhóm và tìm hiểu qua Internet Kết quả đạt đƣợc: Hiểu đƣợc các bài toán về Sudoku và 1 ứng dụng Kế Hoạch Thực Hiện Tuần 1(14-21/03/2009): Tìm hiểu tổng quan về bài toán Soduku và thu thập tài liệu Tuần 2(22-29/03/2009):Xác định rõ bài toán và thu thập thêm tài liệu Tuần 3(30-06/04/2009):Tìm hiểu về các thuật toán để giải quyết. Tuần 4(07-14/04/2009):Xác định và lựa chọn thuật toán cho việc lập trình Tuần 5(15-22/04/2009):Thiết kế giao diện và thực hiện việc viết code giải thuật Tuần 6(25-02/05/2009):Lập trình Tuần 7(03-10/05/2009):Lập trình Tuần 8(11-18/05/2009):Lập trình Tuần 9(19-26/05/2009):Lập trình Tuần 10(27-03/06/2009):Lập trình Tuần 11(04-11/06/2009):Lập trình Trang 6
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Tuần 12(12-19/06/2009):Lập trình và sửa lỗi Tuần 13(20-27/06/2009): Sửa lỗi và viết báo cáo Tuần 14(28-05/07/2009):Sữa lỗi và hoàn thiện báo cáo Tuần 15(06-13/07/2009):Nộp báo cáo và chƣơng trình Xác nhận của GVHD Ngày 13 tháng 03 năm 2009 SV Thực hiện Lƣu Văn Viết Lê Quang Tâm Trang 7
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU MỤC LỤC NHẬN XÉT CỦA GIÁO VIÊN HƢỚNG DẨN 3 NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN 4 LỜI CẢM ƠN 5 ĐỀ CƢƠNG CHI TIẾT 6 MỤC LỤC 8 TÓM TẮT KHÓA LUẬN 13 1. Vấn đề nghiên cứu. 13 2.Phát biểu bài toán 13 2.1 Chức năng chính 13 2.2 Cách chơi 13 3.Phƣơng pháp tiếp cận giải quyết vấn đề. 14 4. Kết quả đạt đƣợc. 14 LỜI MỞ ĐẦU 15 NỘI DUNG BÁO CÁO 16 CHƢƠNG 1. LỊCH SỬ SUDOKU 17 1.1 Sudoku có lịch sử xa xƣa từ hàng ngàn năm. 17 CHƢƠNG 2. CÁC BIẾN THỂ PHỔ BIẾN CỦA SUDOKU 19 2.1. Dạng chuẩn: 19 2.2. Một số biến thể phổ biến nhƣ: 19 2.3. Biến thể với kích thƣớc lớn cũng khá phổ biến: 20 CHƢƠNG 3. LUẬT CHƠI SUDOKU 23 CHƢƠNG 4: MÔ HÌNH USECASE CHO SUDOKU 25 4.1 Sơ đồ UseCase 25 4.2 Danh Sách các Actor 25 4.3 Danh Sách các UseCase 26 Trang 8
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 4.4 Đặc tả UseCase 27 4.4.1 Đặc tả Use-case “New Game”: 27 4.4.2 Đặc tả Use-case “OpenGame” 28 4.4.3 Đặc tả Use-case “SolveGame” 28 4.4.4 Đặc tả Use-case “SaveGame ” 29 4.4.5 Đặc tả Use-case “Exit” 30 4.4.6 Đặc tả Use-case “Undo” 31 4.4.7 Đặc tả Use-case “Redo” 31 4.4.8 Đặc tả Use-case “Help” 32 4.4.9 Đặc tả Use-case “ChooseLevel” 33 5.1. Bƣớc 1: Áp dụng một vài suy luận cơ bản và thông thƣờng để xác định chắc chắn một vài ô số cần tìm. 34 5.2. Bƣớc 2: Liệt kê những số có khả năng xuất hiện tại mỗi ô trong các miền con. 38 5.3. Bƣớc 3: Các suy luận và Phép loại bỏ để giải ô số SUDOKU. 40 5.3.1 Suy luận 1: Số duy nhất xuất hiện trong hàng, trong cột và trong một miền con. 40 5.3.2 Suy luận 2: Số nằm trên một hàng và một miền. 43 5.3.3 Suy luận 3: Số nằm trên một cột và một miền con. 44 5.3.4 Suy luận 4: 2 ô số trong một cột chỉ chứa 2 số giống nhau. 45 5.3.5 Suy luận 5: 2 ô số trong một hàng chỉ chứa 2 số giống nhau. 46 5.3.6 Suy luận 6: 2 ô số trong một miền con chỉ chứa 2 số giống nhau. 47 5.3.7 Suy luận 7: 3 ô số chứa một cặp số nằm trên một hàng 48 5.3.8 Suy luận 8: 3 ô số chứa một cặp số nằm trên một hàng thuộc một miền con 51 5.3.9 Suy luận 9: 3 ô số chứa một cặp số nằm trên một cột 53 5.3.10 Suy luận 10: 3 ô số chứa một cặp số nằm trên một cột thuộc một miền con 56 4.3.11 Suy luận 11: 3 ô số chứa một cặp số nằm trên một miền con 58 Trang 9
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 5.3.12 Suy luận 12: Phép thử 60 CHƢƠNG 6. THUẬT GIẢI SUDOKU 66 6.1 Giới thiệu về thuật giải 66 6.1.1 Backtracking – Quay lui 66 6.1.2 Backtracking- Ý tƣởng 68 6.1.3 Backtracking- Nhận xét 68 6.1.4 Backtracking- Giải thuật tổng quát 68 6.1.5 Giải thuật tổng quát 69 6.1.6 Giải thuật tổng quát 69 CHƢƠNG 7. GIẢI THUẬT TRONG CHƢƠNG TRÌNH SUDOKU 71 7.1 Kỹ thuật cơ bản để giải Sudoku 71 7.1.1 Kỹ thuật khử (Elimination Technology) 71 7.1.2 Kịch bản Biệt Lệ 78 Invalid Puzze 78 Invalid Move 79 7.1.3 Triển khai giải thuật CRME bẳng chƣơng trình. 80 7.1.3.1 Triển khai thuật toán SetCell 80 7.1.3.1.1 Giới thiệu 80 7.1.3.1.2 Mã nguổn chƣơng trình Csharp 81 7.1.3.2 Thuật toán CalculatePossibleValues – Tính các giá trị có thể có cho các cell 82 7.1.3.2.1 Giới thiệu 82 7.1.3.2.2 Mã nguồn bằng Csharp 84 7.1.3.3 Giải thuật CheckColumnsAndRows – Kiểm tra hàng và Cột 85 7.1.3.3.1 Giới thiệu 85 7.1.3.3.2 Mã nguồn bằng Csharp 86 7.1.3.4 Giải thuật SolvePuzze 86 7.1.3.4.1 Giới thiệu 86 7.1.3.4.2 Mã nguồn cho giải thuật 87 Trang 10
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 7.2 Kỹ thuật nâng cao trong việc giải bài toán Sudoku 88 7.2.1 Lone Rangers 88 7.2.1.1 Lone Rangers trong Minigrid 88 7.2.1.1.1 Triển khai giải thuật LookForLoneRangerinMinigrids 90 7.2.1.1.1.1 Thuật Giải LookForLoneRangerinMinigrids 90 7.2.1.1.1.2 Phần mã nguồn của giải thuật 92 7.2.1.2 Lone Ranges trong Row 93 7.2.1.2.1 Triển khai giải thuật LookForLoneRangerinRows 94 7.2.1.2.1.1 Giải thuật LookForLoneRangerinRows 94 7.2.1.2.1.2 Giải thuật 95 7.2.1.3 Lone Rangers trong Columns 96 7.2.1.3.1 Triển khai giải thuật LookForLoneRangerinColumns 96 7.2.1.3.1.1 Giải thuật LookForLoneRangerinColumns 96 7.2.1.3.1.2 Phần mã nguồn của giải thuật LookForLoneRangerinColumns 97 7.2.1.4 Tinh chỉnh lại Function SolvePuzze 98 7.2.1.4.1 Triển khai giải thuật- Tinh chỉnh thêm phần giải thuật SolvePuzze 99 7.2.1.4.1.1 Giải thuật SolvePuzze 99 7.3 Các kỹ thuật nâng cao trong việc giải bài toán Sudoku 100 7.3.2 Kỹ thuật tìm kiếm cặp đôi -Look For Twins 100 7.3.2.1 Triển khai giải thuật để tìm kiếm cặp đôi trong Minigrids 104 7.3.2.1.1 Giải thuật LookForTwinsinMinigrids(Tìm cặp sinh đôi trong Minigrids) 105 7.3.2.1.2 Triển khai giải thuật tìm kiếm cặp đôi trong Rows 107 7.3.2.1 Giải thuật tìm cặp đôi trong Hàng. 107 7.3.2.1.3 Triển khai giải thuật tìm kiếm cặp đôi trong Cột 108 7.3.3 Kỹ thuật tìm kiếm cặp ba – Look For Triplets 110 7.3.3.1 Các biến thể của Triplets 111 7.3.3.2 Triển khai giải thuật tìm cặp 3 trong Minigrids 114 7.3.4 Tinh chỉnh lại phƣơng thức SolvePuzzle (đã giới thiệu ở phần mục lục 7.1.3.4) 116 7.3.5 Sử dụng Burte - Force Elimination 117 Trang 11
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Kết luận: 122 Hƣớng phát triển: 122 Danh mục tài liệu tham khảo 122 Trang 12
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU TÓM TẮT KHÓA LUẬN 1. Vấn đề nghiên cứu. Xuất hiện ở Việt Nam khoảng giữa năm 2005, Sudoku không ồn ào, cuồng nhiệt nhƣ hip hop, breakdance mà vẫn hút khách bởi nó không chỉ đơn thuần là một trò chơi, mà còn là cách thức giải trí giúp rèn luyện trí não, tƣ duy lôgic và tính kiên trì. Ngoài sự hấp dẫn của những con số, kích thích tƣ duy, suy nghĩ logic, Sudoku còn hấp dẫn giới trẻ vì một lý do nữa là có thể chơi đƣợc mọi lúc mọi nơi, trên xe buýt, trong giờ ra chơi, thậm chí khi đi dã ngoại, du lịch. Trong khi giới học sinh thƣờng giải Sudoku theo cách truyền thống, tức là trên báo hoặc sách thì các sinh viên và những cƣ dân mạng lại lên Internet để chơi. Một số diễn đàn của học sinh cũng xuất hiện Sudoku. Không chỉ học sinh mà thầy cô cũng "kết" game này. 2.Phát biểu bài toán 2.1 Chức năng chính Newgame: Tạo một game sudoku mới , cho phép ngƣời chơi có thể chọn lựa cấp độ để chơi game, có 4 cấp độ là: Easy, Medium, Difficult, Extremely Difficult. OpenGame: Cho phép ngƣời chơi mở 1 file game(file text) đã tồn tại để tiếp tục chơi hoặc giải. SaveGame: Cho phép ngƣời chơi lƣu lại game đang chơi dở dang và sẽ đƣợc chơi tiếp bất cứ khi nào ngƣời chơi muốn. Undo: Cho phép ngƣời chơi quay trở lại ô sudoku vừa mới đi. Redo : Quay trở lại ô vừa mới Undo. SolveGame: Cho phép ngƣời chơi giải một game hiện hành. Pause: Chức năng cho phép tạm ngƣng game đang chơi. Help: Chức năng trợ giúp ngƣời chơi về cách chơi Sudoku. ChooseLevel: Cho phép ngƣời chơi có thể chọn một cấp độ game để chơi. 2.2 Cách chơi Luật chơi Sudoku thì không có gì là khó hiểu cả nhƣng để giải đƣợc những ô số sudoku khó thì đó là cả một vấn đề mà chúng ta, những ngƣời đam mê trò chơi này rất Trang 13
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU quan tâm. Luật chơi của nó đƣợc diễn giải nhƣ sau: Sudoku bắt nguồn từ từ xứ sở hoa anh đào đầy thơ mộng, chữ Su có nghĩa trong tiếng Nhật là Con Số, doku trong tiếng Nhật là độc nhất, đúng vậy Sudoku chính là con số độc nhất và nó cũng nói lên đƣợc phần nào luật chơi. Sudoku là một loại trò chơi logic và cách chơi là điền các con 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ỏ (ô 3*3) Có đủ các số từ 1 đến 9 mà không đƣợc lặp lại. 3.Phƣơng pháp tiếp cận giải quyết vấn đề. Bài toán đƣợc giải quyết theo phƣơng pháp thiết kế lập trình hƣớng đối tƣợng bao gồm các bƣớc sau: - Xác định rõ bài toán. - Tìm hiểu về các thuật toán để giải quyết. - Xác định và lựa chọn thuật toán cho việc lập trình. - Thiết kế giao diện và thực hiện việc viết code giải thuật. - Giải trình các thuật giải. 4. Kết quả đạt đƣợc. - Quyển báo cáo. - Chƣơng trình giải các bài toán SUDOKU, với các thuật giải đƣợc tìm hiểu. Trang 14
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU LỜI MỞ ĐẦU Trong mấy năm gần đây, một trò chơi về ô số gọi là Sudoku đã đƣợc phổ biến mọi nơi. Ngƣời ta cho rằng đó là một puzzle đặc sắc của thế kỷ 21, vì thích hợp với mọi lứa tuổi, từ các trẻ em đến các vị bô lão. Đủ loại trò giải trí liên hệ đƣợc bầy bán trong các tiệm đồ chơi. Nhiều loại ô số cũng đƣợc đăng tải trên các báo hàng ngày, kể cả tuần san, nguyệt san. Nếu đến một hiệu sách, nhƣ Barnes & Noble tại Mỹ, chúng ta thấy có cả một khu đầy sách nói về Sudoku. Trên lý thuyết, có nhiều loại Sudoku để mà lựa chọn, nên những sách này đều mô tả luật sắp xếp các con số và cách giải đáp. Thƣờng là sách về Sudoku 9x9 dùng 9 con số đặt trong 81 ô vuông, có kèm theo từ mấy trăm đến cả ngàn bài toán đố về ô số và lời giải. Thí dụ 1001 Sudoku, một sƣu tập của Thunder's Mouth Press, in bởi Avalon Publishing Group, New York, NY10011. Tuy nhiên, sách này in không lấy gì làm đẹp, bảng mục lục kém rõ ràng mà sách lại không có đánh số trang. Do là một sinh viên viết phần mềm nên khó tránh khỏi những sai sót rất mong sự góp ý của các Thầy cô và các bạn. Nhóm sinh viên thực hiện. Lê Quang Tâm Lƣu Văn Viết Trang 15
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU NỘI DUNG BÁO CÁO 1. Lịch sử ra đời của Sudoku 2. Các biến thể phổ biến của Sudoku 3. Luật chơi Sudoku. 4. Mô hình usecase cho chƣơng trình. 5. Một số thuật toán giải quyết Sudoku. 6. Thuật giải Sudoku. 7. Thiết kế ứng dụng cho bài toán Sudoku. Trang 16
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU CHƢƠNG 1. LỊCH SỬ SUDOKU 1.1 Sudoku có lịch sử xa xƣa từ hàng ngàn năm. Sudoku có lịch sử xa xƣa từ hàng ngàn năm.Trong một tài liệu của Ả rập vào thế kỷ thứ 9, Sudoku có lẽ đƣợc bắt nguồn từ Trung Hoa và đƣợc các học giả ngƣời Ả Rập gọi là wafq. Còn trong tiếng Nhật, Sudoku đƣợc tạm dịch là con số độc nhất (Su là số, Doku là đơn độc). Sudoku từng đi qua các nền văn hóa cổ. Những ô số vuông vắn ấy đƣợc dùng làm bùa để giúp phụ nữ dễ sinh đẻ. Nó đƣợc gọi tên là ô vuông buduh. Món bùa này trở nên phổ biến đến mức các nhà văn Hồi giáo bắt đầu lập ra các tổ hợp số phức tạp hơn sao cho không có con số nào lặp lại. Abraham Ben ibn Ezra - một nhà triết học kiêm chiêm tinh học ngƣời Hispanic (Tây Ban Nha - Bồ Đào Nha) gốc Do Thái đã đi khắp Tây Ban Nha, Ý và các nƣớc khác ở châu Âu để giới thiệu với công chúng về “những ô số kỳ ảo”. Vào năm 1225, Ahmed al-Buni đã có ý tƣởng tạo nên những ranh giới cho các khối vuông nhằm biến nó thành trò chơi, mặc dù phƣơng pháp này đƣợc tin là có xuất xứ từ Ba Tƣ. Trong nhiều năm, chỉ có giới toán học biết đến Hình vuông Latinh. Đến thập kỷ 1970, nhà xuất bản Dell của Mỹ đã đƣa vào những tập sách đố, và đặt tên cho nó là Vị trí con số (Number Place). Đến năm 1776 nhà toán học kiêm vật lý học ngƣời Thuỵ Sĩ tên Leonhard Euler bắt đầu nghiên cứu và phát triển các luật chơi mà ngày nay ta gọi là luật chơi Sudoku. Hình 1. 1 Leonhard Euler Năm 1901, một nhà toán học ngƣời Pháp tiếp tục công trình này và năm 1959, hai ngƣời Mỹ tên là Bose và Shrikhande nối gót theo ông ta. Mãi cho đến năm 1986, Trang 17
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU trong một chuyến đi Mỹ, một nhà xuất bản Nhật Bản, Nikoli, đã khám phá ra các ô số. Họ đặt tên cho nó là SuDoku và làm cho nó nhanh chóng trở thành một trò chơi phổ biến ở Nhật Bản. Tại đây, tất cả các câu đố Sudoku đều đƣợc viết tay. Vào thời đó, ai mà có câu đố đƣợc đăng trên một trong các tạp chí của Nikoli coi đó nhƣ một vinh dự lớn. Hơn 20 năm sau một thẩm phán ngƣời Hồng Kông gốc New Zealand tên là Wayne Gould tình cờ phát hiện một cuốn sudoku trong một hiệu sách Nhật Bản. Ông đâm nghiền trò chơi số cổ xƣa này. Năm 2004, nhân một chuyến thăm ngẫu nhiên báo The Times, Gould đã thuyết phục tổng biên tập của báo này cho đăng Sudoku bên cạnh các ô chữ. Độc giả lập tức bị cuốn hút và yêu cầu đăng thêm nữa. Chỉ trong vài tuần lễ cuộc chạy đua bắt đầu. Tờ Mail tung ra bản Sudoku của riêng mình, và chả bao lâu sau tất cả các nhật báo phát hành trên toàn nƣớc Anh đã kịp ăn theo, ngoại trừ tờ chuyên về tài chính Financial Times. Ai nấy đều khẳng định câu đố của họ mới là hay nhất. Chẳng hạn, tờ Guardian có lần chạy một câu đố Sudoku trên mỗi trang của phần phụ san và tuyên bố họ là tờ báo duy nhất có các câu đố đƣợc viết tay trên núi Phú Sĩ. Những ngày này, thử vào bất kỳ toa tàu điện ngầm ở London hay lên trên các xe buýt hai tầng vào giờ cao điểm, bạn sẽ bắt gặp ít nhất một ngƣời đang chơi Sukodu. Từ đó, Sudoku bắt đầu lan rộng sang Mỹ, Canada, Úc, Pháp, Nam Phi và nhiều quốc gia khác. Hình 1. 2 Wayne Gould Trang 18
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU CHƢƠNG 2. CÁC BIẾN THỂ PHỔ BIẾN CỦA SUDOKU 2.1. Dạng chuẩn: - Khuôn dạng chuẩn có kích thƣớc 9x9 ô, chia làm 3x3 vùng Hình 2. 1 Ô Sudoku 9x9 dạng chuẩn 2.2. Một số biến thể phổ biến nhƣ: - Kích thƣớc 4x4 ô chia làm 2x2 vùng Hình 2. 2 Sudoku 4x4 - Kích thƣớc 6x6 ô chia làm 2x3 vùng Hình 2. 3 Sudoku 6x6 Trang 19
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU - Kích thƣớc 5x5 ô chia vùng theo pentomino Hình 2. 4 Sudoku 5x5 2.3. Biến thể với kích thƣớc lớn cũng khá phổ biến: - Kích thƣớc 16x16 ô (Monster SuDoku) Hình 2. 5 Sudoku 16x16 - Kích thƣớc 12x12 ô chia làm 4x3 vùng (Dodeka Sudoku) Hình 2. 6 Sudoku 12x12 Trang 20
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU - Kích thƣớc 25x25 ô (Giant Sudoku) Hình 2. 7 Sudoku 25x25 Trang 21
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Một ngƣời Việt Nam là Phạm Văn Hải đã phát triển các biến thể 8x8 ô chia vùng theo qui tắc (4x2)x(4x2). Đây là cách chia thành 4 vùng chính, mỗi vùng 16 ô. Trong mỗi vùng chính lại chia thành 2 vùng 8x8 dựa vào màu nền của từng ô. Tùy theo cách bố trí các ô khác màu này, sẽ phát sinh thêm một biến thể khác. Cách bố trí đơn giản nhất là các ô khác màu nằm xen kẽ nhau – trông rất giống bàn cờ quốc tế. Ba biến thể phát triển theo nguyên tắc này: Hinh 2. 8.phiên bản của biến thể 8x8 Trang 22
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU CHƢƠNG 3. LUẬT CHƠI SUDOKU Luật chơi Sudoku cực kỳ đơn giản, nhƣng đáp án đôi khi lại cực kỳ khó giải. Do không cần dùng đến kiến thức số học hay tính toán, Sudoku thích ứng cho mọi ngƣời. Vì vậy trẻ em cũng có cơ hội giải đƣợc Sudoku thành công nhƣ ngƣời lớn. Trên thực tế, ở một số nƣớc châu Âu, các em nhỏ đã chiến thắng ngƣời lớn trong các cuộc thi đấu Sudoku. Ví dụ: Hình 3. 1 Quy định đánh giá trị hàng cột Điền vào ô trống những số ( từ 1 – 9 ), sao cho : - Các ô ở mỗi hàng ( ngang ) phải có đủ các số từ 1 – 9 ( không cần theo thứ tự). - Các ô ở mỗi cột ( dọc ) phải có đủ các số từ 1 – 9 ( không cần theo thứ tự ). - Mỗi miền con ( 3x3 ) đƣợc viền đậm, phải có đủ các số từ 1 – 9. Một số quy ƣớc để diễn giải trong phƣơng pháp giải SUDOKU Trang 23
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 3. 2 Quy ƣớc diễn dải ô số Sudoku Ô số SUDOKU cổ điển 9x9 Một ô số SUDOKU cổ điển 9x9, đƣợc quy ƣớc có 9 miền con A, B, C, D, E, F, G, H và I. Chia thành 9 hàng và 9 cột ( có thứ tự từ 1 – 9. Bảng 1 ).Trong đó: A ( 3x3): gọi là miền con 3x3 tên A. Hình 3. 3 Quy ƣớc diễn dải ô số Sudoku Trang 24
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU CHƢƠNG 4: MÔ HÌNH USECASE CHO SUDOKU 4.1 Sơ đồ UseCase Hình 4. 1 Sơ đồ UseCase 4.2 Danh Sách các Actor STT Tên Actor Ý nghĩa/Ghi chú 1 User Ngƣời chơi Sudoku Trang 25
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 4.3 Danh Sách các UseCase STT Tên UseCase Ý nghĩa/Ghi chú 1 New Game Tạo mới 1 Game 2 OpenGame Mở 1 file đã tồn tại để tiếp tục chơi hoặc giải. 3 SolveGame Giải Game 4 Save Lƣu một Game đang chơi vào 1 file 5 Exit Thoát game đang chơi 6 Pause Tạm ngƣng ván cờ đang chơi 7 Undo Quay trở lại ô vừa điền 8 Redo Quay trở lại ô game vừa Undo 9 Help Trợ giúp về cách chơi sudoku 11 ChooseLevel Chọn cấp độ chơi game Trang 26
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 4.4 Đặc tả UseCase 4.4.1 Đặc tả Use-case “New Game”:  Tóm tắt: Use-case này cho phép ngƣời chơi tạo 1 game mới.  Dòng sự kiện Dòng sự kiện chính:Use-case bắt đầu khi actor muốn tạo một game mới, actor ngƣời chơi sẽ vào menu New Game. Hệ thống sẽ khởi tạo 1 game mới với cấp độ mà actor đã chọn. Các dòng sự kiện khác :Không có  Các yêu cầu đặc biệt:Không có.  Trạng thái hệ thống khi bắt đầu thực hiện Use-case: Không có.  Trạng thái hệ thống sau khi thực hiện Use-case: Hệ thống tạo mới một game cho action chơi ở trạng thái bắt đầu.  Điểm mở rộng Hệ thống sẽ cho phép action tuỳ chọn vào Use-case: Exit để thoát khỏi phần mền, nếu ngƣời chơi không thích chơi nữa. Nếu kết quả sau khi use-case Create New đƣợc thực hiện thành công, thì use-case Save Game sẽ đƣợc thực hiện khi action muốn lƣu lại ván cờ đang chơi. Trang 27
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 4.4.2 Đặc tả Use-case “OpenGame”  Tóm tắt :Use-case này cho phép ngƣời chơi load 1 Game đã lƣu trƣớc đó và chơi tiếp.  Dòng sự kiện Dòng sự kiện chính:Use-case này bắt đầu khi actor muốn load 1 ván chơi đã lƣu trƣớc đó và chơi tiếp, actor sẽ click vào menu OpenGame. Các dòng sự kiện khác: Không có.  Các yêu cầu đặc biệt: Không có  Trạng thái hệ thống khi bắt đầu thực hiện Use-case: Không có.  Trạng thái hệ thống sau khi thực hiện Use-case Hệ thống thực hiện chức năng OpenGame.  Điểm mở rộng Nếu ngƣời chơi đang ở trạng thái nào đó của trò chơi thì hệ thống sẽ cho ngƣời chơi chọn lựa có lƣu lại trạng thái hiện tại của trò chơi hay không. Nếu ngƣời chơi đồng ý lƣu lại thì các luồng phụ (Save Game ,Exit,Undo,Redo, Help) sẽ đƣợc thực hiện. Nếu kết quả sau khi use-case OpenGame đƣợc thực hiện thành công thì use-case Save Game sẽ đƣợc thực hiện. 4.4.3 Đặc tả Use-case “SolveGame”  Tóm tắt Use-case này cho phép ngƣời chơi Giải Game  Dòng sự kiện Dòng sự kiện chính Use-case này bắt đầu khi action ghi usecase OpenGame hay NewGame đƣợc thực hiện. Trang 28
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Các dòng sự kiện khác :Không có.  Các yêu cầu đặc biệt : Không có  Trạng thái hệ thống khi bắt đầu thực hiện Use-case Không có.  Trạng thái hệ thống sau khi thực hiện Use-case Load Game , sắp xếp các ô số theo đúng định dạng trong 1 file ở trạng thái ban đầu.  Điểm mở rộng Nếu ngƣời chơi đang ở trạng thái nào đó của trò chơi thì hệ thống sẽ cho ngƣời chơi chọn lựa có lƣu lại trạng thái hiện tại của trò chơi hay không. Nếu ngƣời chơi đồng ý lƣu lại thì các luồng phụ (Save As, Save) sẽ đƣợc thực hiện. Nếu đây là kết quả sau khi use-case SolveGame đƣợc thực hiện thành công, thì use-case SaveGame sẽ đƣợc thực hiện. 4.4.4 Đặc tả Use-case “SaveGame ”  Tóm tắt Use-case này cho phép ngƣời chơi lƣu lại trạng thái hiện tại của game, lần chơi sau nếu ngƣời chơi chọn tiếp tục chơi tiếp ở trạng thái này thì chƣơng trình sẽ load lại trạng thái của game để ngƣời chơi chơi tiếp  Dòng sự kiện Dòng sự kiện chính Use-case này bắt đầu khi actor muốn lƣu lại trạng thái của game, actor sẽ Click vào menu Save Game . Hệ thống xuất hiện hộp thoại yêu cầu: 1. Hệ thống yêu cầu actor nhập tên cho trạng thái game. 2. Actor nhập tên của trạng thái game. 3. Hệ thống lƣu trạng thái của game vào 1 file text. Trang 29
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU  Các dòng sự kiện khác Nếu ngƣời chơi quyết định không lƣu trạng thái hiện tại của game, thì thao tác lƣu bị hủy và Dòng sự kiện chính bắt đầu lại từ đầu.  Các yêu cầu đặc biệt Không có  Trạng thái hệ thống khi bắt đầu thực hiện Use-case Ngƣời chơi phải chơi ở một trạng thái nào đó của game,nhƣng không phải là trạng thái kết thúc khi use-case này bắt đầu.  Trạng thái hệ thống sau khi thực hiện Use-case Nếu use-case này thành công thì trạng thái hiện tại của game đƣợc lƣu vào 1 file text. Ngƣợc lại trạng thái của hệ thống không thay đổi.  Điểm mở rộng Không có 4.4.5 Đặc tả Use-case “Exit”  Tóm tắt Use-case này cho phép ngƣời chơi thoát khỏi chƣơng trình.  Dòng sự kiện Dòng sự kiện chính Use-case này bắt đầu khi actor muốn thoát khỏi chƣơng trình, actor sẽ click vào menu Exit, hệ thống sẽ đóng các cửa sổ của chƣơng trình và kết thúc chƣơng trình. Các dòng sự kiện khác Không có.  Các yêu cầu đặc biệt Không có  Trạng thái hệ thống khi bắt đầu thực hiện Use-case Không có.  Trạng thái hệ thống sau khi thực hiện Use-case Thoát khỏi chƣơng trình. Trang 30
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU  Điểm mở rộng Không có. 4.4.6 Đặc tả Use-case “Undo”  Tóm tắt Use-case này cho phép ngƣời chơi quay trở lại ô sudoku vừa điền.  Dòng sự kiện chính Use-case này bắt đầu khi actor muốn quay trở lại lại ô sudoku vừa điền, actor sẽ click vào menu Undo để thực hiện chức năng.  Các dòng sự kiện khác Không có  Các yêu cầu đặc biệt Không có  Trạng thái hệ thống khi bắt đầu thực hiện Use-case Ngƣời chơi đang chơi một game sudoku.  Trạng thái hệ thống sau khi thực hiện Use-case Nếu use-case này thành công thì trạng thái của game đƣợc quay ngƣợc lại trạng thái trƣớc đó .  Điểm mở rộng Không có 4.4.7 Đặc tả Use-case “Redo”  Tóm tắt Use-case này cho phép ngƣời chơi quay trở lại ô sudoku vừa Undo.  Dòng sự kiện chính Use-case này bắt đầu khi actor muốn quay trở lại ô sudoku Undo(sau khi thực hiện chức năng Undo), actor sẽ click vào menu Redo để thực hiện chức năng. Trang 31
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU  Các dòng sự kiện khác Không có  Các yêu cầu đặc biệt Sao khi gọi thực hiện Use-case: Undo  Trạng thái hệ thống khi bắt đầu thực hiện Use-case Ngƣời chơi đang chơi một game sudoku, đã thực hiện Use-case Undo  Trạng thái hệ thống sau khi thực hiện Use-case Nếu use-case này thành công thì trạng thái của game đƣợc quay ngƣợc lại trạng thái Undo  Điểm mở rộng Không có 4.4.8 Đặc tả Use-case “Help”  Tóm tắt Use-case này cho trợ giúp ngƣời chơi trong quá trình chơi cờ.  Dòng sự kiện chính Use-case này bắt đầu khi actor không biết cách chơi cờ và thực hiện các chức năng nhƣ thế nào. Action click vào menu Help,hệ thống sẽ xuất hiện thông tin mà action đang cần trợ giúp.  Các dòng sự kiện khác Không có  Các yêu cầu đặc biệt  Trạng thái hệ thống khi bắt đầu thực hiện Use-case Không có  Trạng thái hệ thống sau khi thực hiện Use-case Nếu use-case này thành công thì hệ thống sẽ xuất hiện một cửa sổ khác, có những thông tin cần thiết mà action đang cần trợ giúp.  Điểm mở rộng Không có Trang 32
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 4.4.9 Đặc tả Use-case “ChooseLevel”  Tóm tắt Use-case này cho phép ngƣời chơi chọn chức năng theo cấp độ chơi khác nhau, có 3 cấp độ: Easy, Medium, Difficult, Extremely Difficult.  Dòng sự kiện Dòng sự kiện chính Use-case này bắt đầu khi actor muốn chọn cấp độ game để chơi Các dòng sự kiện khác Nếu ngƣời chơi không chọn thì mặc định cấp độ chơi của game là Easy.  Các yêu cầu đặc biệt Không có  Trạng thái hệ thống khi bắt đầu thực hiện Use-case Không có Trang 33
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU CHƢƠNG 5: PHƢƠNG PHÁP GIẢI SUDOKU Để giải một ô số SUDOKU, chúng ta cần tiến hành 3 bƣớc : 5.1. Bƣớc 1: Áp dụng một vài suy luận cơ bản và thông thƣờng để xác định chắc chắn một vài ô số cần tìm. Ví dụ 1 : Hình 5. 1 Ví dụ ô số Sudoku - Ô h2c6: chắc chắn phải là số 6. - Ô h5c4: chắc chắn phải là số 2. - Ô h5c9: chắc chắn phải là số 5. - Ô h8c3: chắc chắn phải là số 4. - Ô h9c7: chắc chắn phải là số 9. Ví dụ 2 : Hình 5. 2 Ví dụ ô số Sudoku Trang 34
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU - Ô h8c2: chắc chắn phải là số 8. - Ô h5c9: chắc chắn phải là số 2. - Ô h5c6: chắc chắn phải là số 8. - Ô h4c3: chắc chắn phải là số 6. - Ô h3c3: chắc chắn phải là số 8. - Ô h3c5: chắc chắn phải là số 3. - Xét miền I. Ta thấy số 5 chỉ xuất hiện ở cột c7 gồm 2 ô: ô h7c7 và ô h9c7. Do đó cột c7 ở miền con C gồm 2 ô: ô h1c7 và ô h3c7 sẽ không xuất hiện số 5. Cột c9 miền con F đã có số 5, hàng h2 ( tại ô h2c5 là số 5 ) đã có số 5. Nên tại miền con C sô 5 chỉ xuất hiện tại ô h1c8. Vậy ô h1c8 chắc chắn là số 5. - Xét miền H. Ta thấy số 5 chỉ xuất hiện ở hàng h7 gồm 2 ô: ô h7c4 và ô h7c6. Do đó hàng h7 ở miền con I gồm 2 ô: ô h7c7 và ô h7c9 sẽ không xuất hiện số 5. Cột c9 đã có số 5 nên ô h9c9 sẽ không có số 5. Hàng h8 đã có số 5 ( tại ô h8c3 ) nên ô h8c8 sẽ không có số 5. Nên trong miền con I số 5 chỉ xuất hiện tại ô h9c7. Vậy ô h9c7 chắc chắn là số 5. - Ô h3c2: chắc chắn phải là số 5. - Xét cột c2: Ta thấy ô h1c2 thuộc hàng h1 đã có số 1 tại ô h1c6, nên ô h1c2 không thể chứa số 1. Ô h4c2 và ô h6c2 thuộc miền con D đã có số 1 tại ô h6c3, nên 2 ô này không thể chứa số 1. Ô h9c2 thuộc hàng h9 đã có số 1 tại ô h9c4, nên ô h9c4 không thể chứa số 1. Do đó trong cột c2 chỉ có ô duy nhất chứa số 1 là ô h2c2. Vậy ô h2c2 chắc chắn là số 1. Với vài suy luận cơ bản và thông thƣờng nhƣ trên ta đã biến Sudoku ban đầu thành Sudoku đơn giản hơn, khi đó ta có bảng sau : Hình 5. 3 Ví dụ ô số Sudoku Trang 35
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Ví dụ 3 : Hình 5. 4 Ví dụ ô số Sudoku Trang 36
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU - Ô h9c1: chắc chắn phải là số 5. - Ô h7c5: chắc chắn phải là số 3. - Xét miền H: Ta thấy ô h8c6 và ô h9c6 là 2 ô có thể chứa số 9. Tại miền I ta thấy ô h8c8 và ô h9c8 là 2 ô có thể chứa số 9. Do đó sẽ một số 9 thuộc hàng h8 và h9. Nên hàng h7 sẽ có một số 9 tại ô h7c2. Vậy ô h7c2 chắc chắn là số 9. Với vài suy luận cơ bản và thông thƣờng nhƣ trên ta đã biến Sudoku ban đầu thành Sudoku đơn giản hơn, khi đó ta có bảng sau : Hình 5. 5 Ví dụ ô số Sudoku Với một vài cách suy luận cơ bản và thông thƣờng nhƣ trên ta đã xác định đƣợc chắc chắn vài số cần tìm trong ô số SUDOKU 9x9. Trang 37
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 5.2. Bƣớc 2: Liệt kê những số có khả năng xuất hiện tại mỗi ô trong các miền con. Ví dụ: Tìm các số trong SUDOKU 9x9 dƣới đây, tuy nhiên có thêm: Mỗi 2 vùng ( có tô màu ) cũng đồng thời bao gồm các số từ 1 – 9. Hình 5. 6 Ví dụ ô số Sudoku Dựa vào các suy luận cơ bản và thông thƣờng nhƣ ở Bƣớc 1 ta có thể xác định đƣợc một số ô có các số chắc chắn : - Ô h7c7: chắc chắn phải là số 7. - Ô h9c7: chắc chắn phải là số 8. - Ô h7c1: chắc chắn phải là số 1. - Ô h3c3: chắc chắn phải là số 8. - Ô h9c8: chắc chắn phải là số 3. - Ô h1c3: chắc chắn phải là số 2. - Ô h1c2: chắc chắn phải là số 3. - Ô h2c8: chắc chắn phải là số 1. - Ô h1c9: chắc chắn phải là số 1. - Ô h7c2: chắc chắn phải là số 4. - Ô h6c2: chắc chắn phải là số 6. - Ô h5c2: chắc chắn phải là số 5. - Ô h8c2: chắc chắn phải là số 8. Trang 38
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Sau khi xác định chắc chắn các ô số trên ta có bảng sau : Hình 5. 7 Ví dụ ô số Sudoku Đến đây, ta dùng Bƣớc 2: Liệt kê tất cả các số có thể xuất hiện trong mỗi ô nhỏ tại các miền con. - Xét ô h1c4 ta thấy sẽ tồn tại các số: 1, 4,6,9. - Xét ô h1c5 ta thấy sẽ tồn tại các số: 1,4,6,9. - Xét ô h1c6 ta thấy sẽ tồn tại các số: 1,4,6,9. - Xét ô h1c7 ta thấy sẽ tồn tại các số: 4,6,9. - Xét ô h2c1 ta thấy sẽ tồn tại các số: 6,7. - Xét ô h2c4 ta thấy sẽ tồn tại các số: 2,5,6,7,8. - Xét ô h2c5 ta thấy sẽ tồn tại các số: 2,5,6,7,8. - Xét ô h2c6 ta thấy sẽ tồn tại các số: 2,5,6,7,8. - Xét ô h2c7 ta thấy sẽ tồn tại các số: 2,6. Trang 39
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Tƣơng tự nhƣ trên ta liệt kê cho các ô nhỏ còn lại và ta có bảng sau : Hình 5. 8 Ví dụ ô số Sudoku Cách liệt kê nhƣ bảng trên gọi là Bƣớc 2 để giải ô số SUDOKU, là Bƣớc rất cần thiết để giải bất kỳ một loại SUDOKU, dù ở dạng nào ( Clasic Sudoku, Digital Sodoku, Samurai Sudoku, Sum Sudoku ). 5.3. Bƣớc 3: Các suy luận và Phép loại bỏ để giải ô số SUDOKU. 5.3.1 Suy luận 1: Số duy nhất xuất hiện trong hàng, trong cột và trong một miền con. Xem ví dụ 1 : Hình 5. 9 Ví dụ ô số Sudoku Trang 40
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Nhìn vào hàng 4 ta thấy ô h4c4 là ô duy nhất xuất hiện số 9. Do đó ô h4c4 phải là số 9. Kết hợp với phép loại bỏ: bỏ tất cả các số 9 trong cột, bỏ tất cả các số 9 trong miền con có chứa ô h4c4. Khi đó ta có bảng sau : Hình 5. 10 Ví dụ ô số Sudoku * Số duy nhất xuất hiện trong hàng chắc chắn là số đó tại vị trí ô chứa số duy nhất. Xem ví dụ 2 : Hình 5. 11 Ví dụ ô số Sudoku Trang 41
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Nhìn vào cột 8 ta thấy ô h3c8 là ô duy nhất trong cột 8 xuất hiện số 9. Do đó ô h3c8 phải là số 9. Kết hợp với phép loại bỏ: bỏ tất cả các số 9 trong hàng, bỏ tất cả các số 9 trong miền con có chứa ô h3c8. Khi đó ta có bảng sau : Hình 5. 12 Ví dụ ô số Sudoku * Số duy nhất xuất hiện trong cột chắc chắn là số đó tại vị trí ô chứa số duy nhất Xem ví dụ 3 : Hình 5. 13 Ví dụ ô số Sudoku Nhìn vào miền con 3x3, ta thấy ô h1c7 là ô duy nhất trong miền con chứa số 4. Do đó ô h1c7 phải là số 4. Kết hợp với phép loại bỏ: bỏ tất cả các số 4 trong hàng và tất cả các số 4 trong cột có chứa ô h1c7. Khi đó ta có bảng sau : Trang 42
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 14 Ví dụ ô số Sudoku * Số duy nhất xuất hiện trong miền con chắc chắn là số đó tại vị trí ô chứa số duy nhất. 5.3.2 Suy luận 2: Số nằm trên một hàng và một miền. Xem ví dụ dƣới đây : Hình 5. 15 Ví dụ ô số Sudoku Nhìn vào hàng 3 ta thấy các ô: ô h3c4 và ô h3c6 là 2 ô duy nhất trong hàng 3 chứa số 7. Do đó trên hàng 3 số 7 chỉ xuất hiện tại 2 ô này. Kết hợp với phép loại bỏ: ô h3c4 và ô h3c6 thuộc miền con ( 3x3 ) nên ta bỏ tất cả các số 7 còn lại trong miền con này. Khi đó ta có bảng sau : Trang 43
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 16 Ví dụ ô số Sudoku Chú ý: Ví dụ trên là 2 số xuất hiện trong hàng, tuy nhiên nếu xuất hiện 3 số trong hàng ta cũng suy luận và đƣợc phép loại bỏ nhƣ trên. 5.3.3 Suy luận 3: Số nằm trên một cột và một miền con. Xem ví dụ dƣới đây : Hình 5. 17 Ví dụ ô số Sudoku Nhìn vào cột 8 ta thấy các ô h4c8 và ô h6c8 là 2 ô số duy nhất trong cột 8 chứa số 5. Do đó trên cột 8 số 5 chỉ xuất hiện tại 2 ô này. Kết hợp với phép loại bỏ: ô h4c8 và ô h6c8 thuộc miền con ( 3x3 ) nên ta bỏ tất cả các số 5 còn lại trong miền con này. Khi đó ta có bảng sau : Trang 44
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 18 Ví dụ ô số Sudoku Chú ý: Ví dụ trên là 2 số xuất hiện trong cột, tuy nhiên nếu xuất hiện 3 số trong cột ta cũng suy luận và đƣợc phép loại bỏ nhƣ trên. 5.3.4 Suy luận 4: 2 ô số trong một cột chỉ chứa 2 số giống nhau. Xem ví dụ dƣới đây : Hình 5. 19 Ví dụ ô số Sudoku Nhìn vào cột 3 ta thấy các ô h4c3 và ô h4c7 là 2 ô số chỉ chứa số 2 và số 5. Do đó sô 2 số 5 chỉ xuất hiện tại 1 trong 2 ô này. Kết hợp với phép loại bỏ: bỏ tất cả các số 2 và số 5 còn lại trong cột này. Khi đó ta có bảng sau : Trang 45
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 20 Ví dụ ô số Sudoku 5.3.5 Suy luận 5: 2 ô số trong một hàng chỉ chứa 2 số giống nhau. Xem ví dụ dƣới đây : Hình 5. 21 Ví dụ ô số Sudoku Nhìn vào hàng 5 ta thấy các ô h5c3 và ô h5c8 là 2 ô số chỉ chứa số 3 và số 7. Do đó số 3 và số 7 chỉ xuất hiện tại 1 trong 2 ô này. Kết hợp với phép loại bỏ: bỏ tất cả các số 3 và số 7 còn lại trong hàng này. Khi đó ta có bảng sau : Trang 46
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 22 Ví dụ ô số Sudoku 5.3.6 Suy luận 6: 2 ô số trong một miền con chỉ chứa 2 số giống nhau. Xem ví dụ dƣới đây : Hình 5. 23 Ví dụ ô số Sudoku Nhìn vào miền con 3x3, ta thấy các ô h8c5 và ô h9c4 là 2 ô số chỉ chứa số 6 và số 8. Do đó số 6 và số 8 chỉ xuất hiện 1 trong 2 ô này. Kết hợp với phép loại bỏ: bỏ tất cả các số 6 và số 8 còn lại trong miền con này. Khi đó ta có bảng sau : Trang 47
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 24 Ví dụ ô số Sudoku 5.3.7 Suy luận 7: 3 ô số chứa một cặp số nằm trên một hàng Xem ví dụ dƣới đây : Hình 5. 25 Ví dụ ô số Sudoku Nhìn vào hàng h4, ta thấy các ô số ô h4c2, ô h4c5, ô h4c7 là 3 ô số chỉ chứa các số 2, 6, 8 theo từng cặp một. Do đó ta có thể khẳng định các số 2, 6 và 8 chỉ xuất hiện tại các ô h4c2, ô h4c5 và ô h4c7. Kết hợp với phép loại bỏ: bỏ tất cả các số 2, 6 và số 8 còn lại trong hàng h4. Khi đó ta có bảng sau Trang 48
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 26 Ví dụ ô số Sudoku Ghi chú: Ví dụ trên là 3 ô số chứa một cặp số ( theo từng cặp một ), tuy nhiên nếu xuất hiện 3 hoặc 4 ô số chứa 3 hoặc 4 số (theo từng nhóm 3 hoặc 4 số giống nhau) nằm trên một hàng ta vẫn đƣợc phép loại bỏ các số đó tại các ô còn lại trong hàng. Chẳng hạn: Nhóm 3 số giống nhau nằm trên một hàng Hình 5. 27 Ví dụ ô số Sudoku Nhìn vào hàng h4, ta thấy các ô số ô h4c2, ô h4c5, ô h4c7 là 3 ô số chỉ chứa các số 2, 6, 8. Do đó ta có thể khẳng định các số 2, 6 và 8 chỉ xuất hiện tại các ô h4c2, ô h4c5 và ô h4c7. Kết hợp với phép loại bỏ: bỏ tất cả các số 2, 6 và số 8 còn lại trong hàng h4. Khi đó ta có bảng sau : Trang 49
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 28 Ví dụ ô số Sudoku Chẳng hạn: Nhóm 4 số giống nhau nằm trên một hàng Hình 5. 29 Ví dụ ô số Sudoku Nhìn vào hàng h4, ta thấy các ô số ô h4c2, ô h4c5, ô h4c6 và ô h4c7 là4 ô số chỉ chứa các số 1, 2, 6, 8. Do đó ta có thể khẳng định các số 1, 2, 6 và 8 chỉ xuất hiện tại các ô h4c2, ô h4c5, ô h4c6 và ô h4c7. Kết hợp với phép loại bỏ: bỏ tất cả các số 1, 2, 6 và số 8 còn lại trong hàng h4. Khi đó ta có bảng sau : Trang 50
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 30 Ví dụ ô số Sudoku 5.3.8 Suy luận 8: 3 ô số chứa một cặp số nằm trên một hàng thuộc một miền con Xem ví dụ dƣới đây : Hình 5. 31 Ví dụ ô số Sudoku Nhìn vào miền con 3x3, ta thấy các ô số ô h3c4, ô h3c5, ô h3c6 là 3 ô số chỉ chứa các số 2, 6, 8 theo từng cặp một. Do đó ta có thể khẳng định các số 2, 6 và 8 chỉ xuất hiện tại các ô h3c4, ô h3c5 và ô h3c6. Kết hợp với phép loại bỏ: bỏ tất cả các số 2, 6 và số 8 còn lại trong miền con này, đồng thời bỏ luôn các số 2, 6 và 8 tại các ô còn lại trong hàng h3. Khi đó ta có bảng sau : Trang 51
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 32 Ví dụ ô số Sudoku Ghi chú: Ví dụ trên là 3 ô số chứa một cặp số ( theo từng cặp một ), tuy nhiên nếu xuất hiện 3 ô số chứa 3 số (theo từng nhóm 3 số giống nhau) nằm trên một hàng và thuộc một miền con, ta vẫn đƣợc phép loại bỏ các số đó tại các ô còn lại trong hàng và trong miền con đó. Chẳng hạn: Nhóm 3 số giống nhau nằm trên một hàng và thuộc một niềm con. Hình 5. 33 Ví dụ ô số Sudoku Nhìn vào miền con 3x3, ta thấy các ô số ô h3c4, ô h3c5, ô h3c6 là 3 ô số chỉ chứa các số 2, 6, 8. Do đó ta có thể khẳng định các số 2, 6 và 8 chỉ xuất hiện tại các ô h3c4, ô h3c5 và ô h3c6. Kết hợp với phép loại bỏ: bỏ tất cả các số 2, 6 và số 8 còn lại trong miền con này, đồng thời bỏ luôn các số 2, 6 và 8 tại các ô còn lại trong hàng h3. Khi đó ta có bảng sau : Trang 52
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 34 Ví dụ ô số Sudoku 5.3.9 Suy luận 9: 3 ô số chứa một cặp số nằm trên một cột Xem ví dụ dƣới đây : Hình 5. 35 Ví dụ ô số Sudoku Nhìn vào cột c4, ta thấy các ô số ô h2c4, ô h5c4, ô h9c4 là 3 ô số chỉ chứa các số 3, 5, 7 theo từng cặp một. Do đó ta có thể khẳng định các số 3, 5 và 7 chỉ xuất hiện tại các ô h2c4, ô h5c4 và ô h9c4. Kết hợp với phép loại bỏ: bỏ tất cả các số 3, 5 và số 7 còn lại trong cột c4. Khi đó ta có bảng sau : Trang 53
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 36 Ví dụ ô số Sudoku Ghi chú: Ví dụ trên là 3 ô số chứa một cặp số ( theo từng cặp một ), tuy nhiên nếu xuất hiện 3 hoặc 4 ô số chứa 3 hoặc 4 số (theo từng nhóm 3 hoặc 4 số giống nhau) nằm trên một cột ta vẫn đƣợc phép loại bỏ các số đó tại các ô còn lại trong cột. Chẳng hạn: Nhóm 3 số giống nhau nằm trên một cột. Hình 5. 37 Ví dụ ô số Sudoku Nhìn vào cột c4, ta thấy các ô số ô h2c4, ô h5c4, ô h9c4 là 3 ô số chỉ chứa các số 3, 5, 7. Do đó ta có thể khẳng định các số 3, 5 và 7 chỉ xuất hiện tại các ô h2c4, ô h5c4 và ô h9c4. Kết hợp với phép loại bỏ: bỏ tất cả các số 3, 5 và số 7 còn lại trong cột c4. Khi đó ta có bảng sau : Trang 54
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 38 Ví dụ ô số Sudoku Chẳng hạn: Nhóm 4 số giống nhau nằm trên một cột. Hình 5. 39 Ví dụ ô số Sudoku Nhìn vào cột c4, ta thấy các ô số ô h2c4, ô h4c4, ô h5c4, ô h9c4 là 4 ô số chỉ chứa các số 1, 3, 5, 7. Do đó ta có thể khẳng định các số 1, 3, 5 và 7 chỉ xuất hiện tại các ô h2c4, ô h4c4, ô h5c4 và ô h9c4. Kết hợp với phép loại bỏ: bỏ tất cả các số 1, 3, 5 và số 7 còn lại trong cột c4. Khi đó ta có bảng sau : Trang 55
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 40 Ví dụ ô số Sudoku 5.3.10 Suy luận 10: 3 ô số chứa một cặp số nằm trên một cột thuộc một miền con Xem ví dụ dƣới đây : Hình 5. 41 Ví dụ ô số Sudoku Nhìn vào miền con 3x3, ta thấy các ô số ô h4c4, ô h5c4, ô h6c4 là 3 ô số chỉ chứa các số 3, 5, 7 theo từng cặp một. Do đó ta có thể khẳng định các số 3, 5 và 7 chỉ xuất hiện tại các ô h4c4, ô h5c4 và ô h6c4. Kết hợp với phép loại bỏ: bỏ tất cả các số 3, 5 và số 7 còn lại trong miền con này, đồng thời bỏ luôn các số 3, 5 và 7 tại các ô còn lại trong cột c4. Khi đó ta có bảng sau : Trang 56
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 42 Ví dụ ô số Sudoku Ghi chú: Ví dụ trên là 3 ô số chứa một cặp số ( theo từng cặp một ), tuy nhiên nếu xuất hiện 3 ô số chứa 3 số (theo từng nhóm 3 số giống nhau) nằm trên một cột và thuộc một miền con, ta vẫn đƣợc phép loại bỏ các số đó tại các ô còn lại trong cột và trong miền con đó. Chẳng hạn: Nhóm 3 số giống nhau nằm trên một cột và thuộc một niềm con. Hình 5. 43 Ví dụ ô số Sudoku Nhìn vào miền con 3x3, ta thấy các ô số ô h4c4, ô h5c4, ô h6c4 là 3 ô số chỉ chứa các số 3, 5, 7. Do đó ta có thể khẳng định các số 3, 5 và 7 chỉ xuất hiện tại các ô h4c4, ô h5c4 và ô h6c4. Kết hợp với phép loại bỏ: bỏ tất cả các số 3, 5 và số 7 còn lại trong miền con này, đồng thời bỏ luôn các số 3, 5 và 7 tại các ô còn lại trong cột c4. Khi đó ta có bảng sau : Trang 57
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 44 Ví dụ ô số Sudoku 5.3.11 Suy luận 11: 3 ô số chứa một cặp số nằm trên một miền con Xem ví dụ dƣới đây : Hình 5. 45 Ví dụ ô số Sudoku Nhìn vào miền con 3x3, ta thấy các ô số ô h4c6, ô h5c6, ô h6c4 là 3 ô số chỉ chứa các số 1, 4, 9 theo từng cặp một. Do đó ta có thể khẳng định các số 1, 4 và 9 chỉ xuất hiện tại các ô h4c6, ô h5c6 và ô h6c4. Kết hợp với phép loại bỏ: bỏ tất cả các số 1, 4 và số 9 còn lại trong miền con này. Khi đó ta có bảng sau : Trang 58
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 46 Ví dụ ô số Sudoku Ghi chú: Ví dụ trên là 3 ô số chứa một cặp số ( theo từng cặp một ), tuy nhiên nếu xuất hiện 3 hoặc 4 ô số chứa 3 hoặc 4 số (theo từng nhóm 3 hoặc 4 số giống nhau) nằm trên một miền con, ta vẫn đƣợc phép loại bỏ các số đó tại các ô còn lại trong miền con đó. Chẳng hạn: Nhóm 3 số giống nhau thuộc một niềm con. Hình 5. 47 Ví dụ ô số Sudoku Nhìn vào miền con 3x3, ta thấy các ô số ô h4c6, ô h5c6, ô h6c4 là 3 ô số chỉ chứa các số 1, 4, 9. Do đó ta có thể khẳng định các số 1, 4 và 9 chỉ xuất hiện tại các ô h4c6, ô h5c6 và ô h6c4. Kết hợp với phép loại bỏ: bỏ tất cả các số 1, 4 và số 9 còn lại trong miền con này. Khi đó ta có bảng sau Trang 59
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 48 Ví dụ ô số Sudoku 5.3.12 Suy luận 12: Phép thử Sau khi dùng các bƣớc, các suy luận kết hợp với phép loại bỏ. Ta có thể biến một Sudoku phức tạp ( có nhiều ô trống cần tìm ) thành một Sudoku đơn giản ( ít ô trống cần tìm ). Trong một vài trƣờng hợp, sau khi đã dùng phƣơng pháp suy luận và loại bỏ ta biến một Sudoku phức tạp thành một Sudoku đơn giản, nhƣng vẫn còn vài ô cần tìm mà không thể dùng các suy luận và loại bỏ đƣợc nữa, chúng ta bắt buộc dùng phép thử. Để phép thử có kết quả nhanh chóng, ta chọn ô số chứa ít số cần tìm nhất ( tuy nhiên lại liên quan nhiều nhất đến các ô số còn lại cần tìm ) để thử. Phép thử là một phƣơng pháp cơ bản nhƣng lại không khoa học và là điều không thể không dùng đến trong một vài trƣờng hợp. Xem ví dụ dƣới đây: Hình 5. 49 Ví dụ ô số Sudoku Trang 60
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Sau khi áp dụng một vài suy luận cơ bản và thông thƣờng, liệt kê kết hợp với phép loại bỏ. Ta biến đổi Sudoku phức tạp thành Sudoku đơn giản, dƣới đây : Hình 5. 50 Ví dụ ô số Sudoku Đến đây chúng ta không thể áp dụng một số suy luận và phép loại bỏ để hoàn tất việc giải Sudoku trên, do đó chúng ta phải dùng phép thử. Nhìn vào bảng trên ta thấy ô h1c9 chỉ bao gồm 2 số là 4 và 9. Nhƣng các ô h1c1 và ô h5c9, ô h2c8 chỉ chứa 2 số và đều có số 9. Do đó ta chọn ô h1c9 để thử. Giả sử ô h1c9 là ô chứa số 9. Dùng các phép suy luận kết hợp với phép loại bỏ, ta giải đƣợc ô số Sudoku trên. Khi chúng ta đã nhuần nhuyễn các bƣớc liệt kê, suy luận và phép loại bỏ nhƣ đã giới thiệu ở trên. Việc giải một ô số Sudoku (bất kỳ dạng Sudoku nào) đối với chúng ta là không còn khó nữa. Xin giới thiệu đến các bạn ô số Sudoku có tên Al Escargot ( Ốc sên ) đƣợc mệnh danh là khó nhất hiện nay ( theo tin AFP, ngày 05/11/2006 ). Do Tiến sĩ toán học Arto Lnkala giới thiệu và “ Ông đã phải điên đầu trong 3 tháng và xem xét đến 1 tỷ khả năng phối hợp khác nhau “ Trang 61
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 51 Ví dụ ô số Sudoku Chúng ta thử giải theo phƣơng pháp đã giới thiệu trên : Bƣớc 1: Xác định một vài ô số chắc chắn. Nhìn vào ô số Sudoku Ốc sên, ta có thể xác định ngay ô h8c3 chắc chắn là số 1, ta có bảng sau : Hình 5. 52 Ví dụ ô số Sudoku Bƣớc 2: Liệt kê các số có khả năng xuất hiện. Liệt kê các số có khả năng xuất hiện tại các ô số còn lại trong Sudoku Ốc sên, ta có bảng sau : Trang 62
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 53 Ví dụ ô số Sudoku Bƣớc 3: Giải ô số Sudoku Ốc sên -. Ô số Sudoku Ốc sên quả là khó, qua xem xét bảng liệt kê trên, ta chƣa thể áp dụng đƣợc các suy luận. Trong trƣờng hợp này, chúng ta phải dùng suy luận 12 (phép thử). Để xác xuất thử cao nhất, ta xét các ô số. Ta thấy cột 3, có chứa 2 ô số ô h2c3 và ô h5c3 là 2 ô số chứa ít số nhất, có liên kết với nhau (cùng chứa số 4). Ta quyết định chọn số 4 tại ô h2c3. Khi đã chọn số 4 tại ô h2c3, dùng các suy luận và phép loại bỏ, khi đó ta có bảng sau : Hình 5. 54 Ví dụ ô số Sudoku Trang 63
Trƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU -. Nhìn vào bảng trên ta thấy ô h2c8 là ô số chứa 2 số 6 và 7. Nhƣng xét thấy số 7 có liên quan đến những ô số khác nhiều hơn số 6, ta chọn ô h2c8 là số 7. Sau khi chọn ô h2 c8 là số 7, dùng các suy luận và phép loại bỏ ta có bảng sau : Hình 5. 55 Ví dụ ô số Sudoku -. Nhìn vào bảng trên ta thấy ô h3c6 là ô số chứa 2 số 3 và 8. Nhƣng xét thấy số 3 có liên quan đến những ô số khác nhiều hơn số 8, ta chọn ô h3c6 là số 3. Sau khi chọn ô h3 c6 là số 3, dùng các suy luận và phép loại bỏ ta có bảng sau : Hình 5. 56 Ví dụ ô số Sudoku - Nhìn vào bảng trên ta thấy ô h5c1 là ô số chứa 2 số 4 và 9. Nhƣng xét thấy số 9 có liên quan đến những ô số khác nhiều hơn số 4, ta chọn ô h5c1 là số 9. Sau khi chọn ô h5c1 là số 9, dùng các suy luận và phép loại bỏ, ta đã giải đƣợc ô số Sudoku Ốc sên, kết quả nhƣ sau : Trang 64
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 5. 57 Ví dụ ô số Sudoku Trang 65
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU CHƢƠNG 6. THUẬT GIẢI SUDOKU 6.1 Giới thiệu về thuật giải 6.1.1 Backtracking – Quay lui Quay lui (tiếng Anh: backtracking) là một chiến lược tìm kiếm lời giải cho các bài toán thỏa mãn ràng buộc. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950. Các bài toán thỏa mãn ràng buộc là các bài toán có một lời giải đầy đủ, trong đó thứ tự của các phần tử không quan trọng. Các bài toán này bao gồm một tập các biến mà mỗi biến cần được gán một giá trị tùy theo các ràng buộc cụ thể của bài toán. Việc quay lui là để thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều tổ hợp chưa hoàn chỉnh, và nhờ đó giảm thời gian chạy. Phương pháp quay lui có quan hệ chặt chẽ với tìm kiếm tổ hợp Về bản chất, tư tưởng của phương pháp là thử từng khả năng cho đến khi tìm thấy lời giải đúng. Đó là một quá trình tìm kiếm theo độ sâu trong một tập hợp các lời giải. Trong quá trình tìm kiếm, nếu ta gặp một hướng lựa chọn không thỏa mãn, ta quay lui về điểm lựa chọn nơi có các hướng khác và thử hướng lựa chọn tiếp theo. Khi đã thử hết các lựa chọn xuất phát từ điểm lựa chọn đó, ta quay lại điểm lựa chọn trước đó và thử hướng lựa chọn tiếp theo tại đó. Quá trình tìm kiếm thất bại khi không còn điểm lựa chọn nào nữa. Quy trình đó thường được cài đặt bằng một hàm đệ quy mà trong đó mỗi thể hiện của hàm lấy thêm một biến và lần lượt gán tất cả các giá trị có thể cho biến đó, với mỗi lần gán trị lại gọi chuỗi đệ quy tiếp theo để thử các biến tiếp theo. Chiến lược quay lui tương tự với tìm kiếm theo độ sâu nhưng sử dụng ít không gian bộ nhớ hơn, nó chỉ lưu giữ trạng thái của một lời giải hiện tại và cập nhật nó. Để tăng tốc quá trình tìm kiếm, khi một giá trị được chọn, trước khi thực hiện lời gọi đệ quy, thuật toán thường xóa bỏ giá trị đó khỏi miền xác định của các biến có mâu thuẫn chưa được gán (kiểm tra tiến - forward checking) và kiểm tra tất cả các hằng số để tìm các giá trị khác đã bị loại trừ bởi giá trị vừa được gán (lan truyền ràng buộc - Trang 66
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU constraint propagation). Người ta thường sử dụng một số phương pháp để tăng tốc cho quá trình quay lui. Do các biến có thể được xử lý theo thứ tự bất kỳ, việc thử các biến bị ràng buộc chặt nhất (nghĩa là các biến có ít lựa chọn về giá trị nhất) thường có hiệu quả do nó tỉa cây tìm kiếm từ sớm (cực đại hóa ảnh hưởng của lựa chọn sớm hiện hành). Các cài đặt quay lui phức tạp thường sử dụng một hàm biên, hàm này kiểm tra xem từ lời giản chưa đầy đủ hiện tại có thể thu được một lời giải hay không, nghĩa là nếu đi tiếp theo hướng hiện tại thì liệu có ích hay không. Nhờ đó, một kiểm tra biên phát hiện ra các lời giải dở dang chắc chắn thất bại có thể nâng cao hiệu quả của tìm kiếm. Do hàm này hay được chạy, có thể tại mỗi bước, nên chi phí tính toán các biên cần tối hiểu, nếu không, hiệu quả toàn cục của thuật toán sẽ không được cải tiến. Các hàm kiểm tra biên được tạo theo kiểu gần như các hàm heuristic khác: nới lỏng một số điều kiện của bài toán. Trang 67
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 6.1.2 Backtracking- Ý tƣởng Tập biến x1 x2 x3 xn có thứ tự. Mỗi biến có thể có 1 miền trị riêng. Tại mỗi thời điểm, biến xi đƣợc tìm trị phù hợp. Nếu tìm đƣợc trị phù hợp thì tiếp tục sang biến xi+1 Ngƣợc lại, tìm trị khác cho biến xi-1 6.1.3 Backtracking- Nhận xét Phải ghi nhớ các bƣớc đã đi qua để có thể lùi về trạng thái trƣớc đó Cơ chế stack Kỹ thuật đệ quy rất phù hợp. Nếu lƣu trữ đƣợc các khả năng (trị của miền trị) đã đƣợc thử thì sẽ tránh đƣợc những việc lặp không cần thiết. 6.1.4 Backtracking- Giải thuật tổng quát Tập biến X= (x1 x2 x3 xn), số biến n Tập miền trị D =(D1 D2 D3 Dn) void Try ( int i, X , n) { ∀j ∈ Di { if ( acceptable(xi, j)) { xi = j; if (i==n) Process (CấuHìnhCủa X) else Try (i+1, X, n) } } } Trang 68
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 6.1.5 Giải thuật tổng quát Hình 6. 1 Sơ đồ giải thuật 6.1.6 Giải thuật tổng quát Hình 6. 22 Sơ đồ giải thuật Trang 69
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Trang 70
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU CHƢƠNG 7. GIẢI THUẬT TRONG CHƢƠNG TRÌNH SUDOKU 7.1 Kỹ thuật cơ bản để giải Sudoku Trong phần này sẽ trình bày những kỹ thuật khác nhau để giải bài toán sudoku. Trƣớc tiên là mô tả những giải thuật cơ bản để giải quyết đƣợc đa số các sudoku cực kì đơn giản. 7.1.1 Kỹ thuật khử (Elimination Technology)  Hầu hết các sudoku đều có thể giải quyết đƣợc bằng kỹ thuật khử(Elimination).Ví dụ nếu 1 hàng mà có 8 ô đƣợc điền thì ô còn lại chính là con số còn lại từ 1 đến 9 chƣa xuất hiện trong hàng này. Trong hình dƣới giá trị còn lại của ô (5,1) sẽ phải là 5 vì giá trị từ 1 đến 4 và từ 6 đến 9 đã đƣợc điền vào trong hàng này. Hình 7. 1 Xác định ô số còn lại dựa trên kỹ thuật khử cơ bản.  Khi chúng ta đặt 1 con số nào đó vào trong 1 ô và chỉ kiểm tra trên hàng đó thì chƣa đủ, có thể nó sẽ không phù hợp với các hàng hay cột khác, vì thế chúng ta phải quét Cột, nếu vẫn chƣa đủ thì chúng ta có thể phải quét thêm Minigrid(vùng 3x3). Chúng ta có thể gọi kỹ thuật này là kỹ thuật khử Cột(Coloumn), Hàng(Row), Minigrid Elimination(CRME).  Thuật toán của CRME – Thuật toán Khử Hàng, Cột và Minigrid Quét các ô từ trong Grid từ trái qua phải, từ trên xuống dƣới For Each Cell: (Với mỗi ô) Thiết lập các giá trị có thể có cho mỗi ô từ 1 9 Quét cột và khử các giá trị đã tồn tại trong cột Quét hàng và khử các giá trị đã tồn tại trong hàng Quét Minigrid và khử các giá trị đã tồn tại trong Minigrid If( Nếu chỉ có 1 giá trị có thể có cho ô ) Trang 71
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Thiết lập giá trị cho ô hiện hành. Lặp cho đến khi các ô đƣợc đặt giá trị  Để thấy đƣợc cách làm việc của kỹ thuật CRME thì chúng ta xét một ví dụ đơn giản sau. Hình 7. 2 Một phần của Sudoku Puzze đã điền các con số. Theo nhƣ hình trên, chúng ta áp dụng kỹ thuật CRME bằng cách quét từ trái qua phải, từ trên xuống dƣới, ô trống đầu tiên ta gặp là (2,1) (Tức là cột thứ 2 hàng thứ nhất). Khi đó ta kiểm tra cột thì ta thấy rằng các giá trị có thể cho ô này là 2,3,4,6,7,8,9 nhƣ Hinh 3. Hình 7. 3 Quét cột Tuy nhiên khi quét hàng ngang thì các giá trị có thể có đƣợc giảm đi một giá trị đó là 9, bởi vì các giá trị khác đã tồn tại và đƣợc sử dụng , chúng ta xem hình 4. Trang 72
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 4 Quét hàng Bây giờ chúng ta có thể chắc chắn rằng ô (2,1) phải điền vào giá trị là 9. Hình 7. 5 Giá trị 9 đƣợc điền vào ô(2,1) Chúng ta tiếp tục quét đến ô trống kế tiếp là ô (2,2), bằng việc quét hàng và cột, giá trị có thể có cho ô này là 3,4,6,7,8( Hình 6) Hình 7. 6 Quét hàng và cột Bằng việc quét Minigrid , ta thấy rằng các giá trị 1,2,3,4,9 đã tồn tại, vì thế các giá Trang 73
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU trị có thể có cho ô này sẽ là 6,7,8. Bởi vì ô (2,2) có nhiều hơn một giá trị có thể có cho 1 ô sau khi đã thực hiện kỹ thuật CRME. Tới đây thì giá trị tại ô (2,2) không đƣợc xác định và câu trả lời là chƣa biết, nhƣng chúng ta cũng biết rằng giá trị có thể có cho ô (2,2) này là 6,7,8. Chú ý: Biết đƣợc các giá trị có thể có cho 1 ô là rất quan trọng trong quá trình giải Sudoku. Trong khi một ô có nhiểu hơn một giá trị có thể có thì giải thuật CRME không thể giải, ta sẽ sử dụng một giải thuật khác. Bây giờ chúng ta lại tiếp tục quét tới ô kế tiếp, ô (1,4) nhƣ hình 7. Hình 7. 7 Kiểm tra ô (1,4) Bằng cách quét hàng ta thấy rằng ô (1,4) có các giá trị có thể có là 3,8. Nhƣng khi thực hiện quét hàng thì chỉ có giá trị 3 đƣợc điền. Trang 74
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 8 Điền vào ô (1,4) giá trị 3. Tiếp tục quét, xét ô kế tiếp là (2,6). Tới đây chúng ta thực hiện quét hàng và cột thì không xác định đƣợc giá trị có thể có cho ô (2,6), nhƣng thực hiện quét Minigrid thì xác định đƣợc giá trị cho ô (2,6) là 2 (Hình 9) Hình 7. 9 Xác nhận giá trị 2 bằng CRME Giờ ta chỉ còn một ô cuối cùng cho ô (1,7) và giá trị còn lại cho ô (1,7) chỉ là số 8. Bây giờ ta xem xét danh sách các giá trị có thể có cho mỗi ô sau khi thực hiện thuật toán CRME (Hình 10). Trang 75
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 10 Danh sách các giá trị có thể cho mỗi ô trong Grid. Tuy thuật toán CRME khi chạy không giải đƣợc toàn bộ bài toán Sudoku nhƣng trong tình huống thực tế thì sẽ có nhiều cơ hôi lạc quan là chúng ta sẽ giải đƣợc. Sau khi dùng kĩ thuật CRME cho các ô Sudoku , chúng ta cũng có thể dùng kĩ thuật này để xác định giá trị cho nhiều ô khác nữa. Vì thế chúng ta phải lặp lại quá trình quét này cho đến bất cứ khi nào một ô đƣợc xác nhận. Để hiểu tại sao nó lại quan trọng , chúng ta xét một ví dụ tiếp theo sau đây.Trong ví dụ trƣớc giá trị của ô (1,4) đƣợc xác nhận và sau đó nó đƣợc sử dụng để trợ giúp cho việc xác nhận giá trị cho ô (2,6). Trong trƣờng hợp này ô (1,4) và ô (2,6) chỉ xác nhận một lần bằng cách quét hàng, cột, Minigrid. Tuy nhiên trong vài trƣờng hợp khác thì chúng ta có thể sẽ không đƣợc may mắn nhƣ vậy. Chúng ta xét tiếp một Grid sau (Hinh 11) Trang 76
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 11 Một sudoku Trong trƣờng hợp này nếu chúng ta dùng kỹ thuật CRME thì ô đầu tiên đƣợc xác nhận là (2,6) và giá trị là 2 (Hình 12). Hình 7. 12 Xác nhận chỉ một lần cho ô (2,6) Nhƣng chỉ bằng cách đặt giá trị 2 vào ô (2,6) ta có thể xác định giá trị đƣợc cho ô (1,4). Tuy nhiên khi chúng ta quét từ trái qua phải, từ trên xuống dƣới, bằng lần xác nhận ô (2,6) chúng ta cũng passed đƣợc ô (1,4). Vì thế để lấy đƣợc giá trị của ô (1,4) chúng ta cần quét Grid một hoặc nhiều lần,lần này ô (1,4) đƣợc xác nhận giá trị là 3 (Hình 13). Trang 77
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 13 Xác nhận giá trị cho ô (1,4) trong 2 lần. Một câu hỏi đặt ra là khi chúng ta ngừng quét Grid thì điều gì sẽ xảy ra ? Câu trả lời hiển nhiên là – Nếu ta không thể xác nhận giá trị bất kì ô nào trong khi quét (quét 81 ô, từ ô (1,1) đến ô (9,9)). Khi điều này xảy ra , chúng ta có thể chắc rằng kỹ thuật CRME là hữu ích( Nếu chúng ta không giải đƣợc Grid sau này). 7.1.2 Kịch bản Biệt Lệ Trong trƣờng hợp tổng quát, khi chúng ta dùng kỹ thuật CRME để giải Sudoku, chúng ta có thể chắc chắn một điều là bất cứ khi nào giá trị có thể có cho 1 ô sudoku là hạn chế - số đƣợc điền. Tuy nhiên có 2 trƣờng hợp có thể dẫn đến việc mất hiệu lực của quy luật. Sudoku không hợp lệ (Invalid Puzze) Ngƣời sử dụng đặt một con số vào một ô mà không thể có lời giải (Invalid Move) Invalid Puzze Chúng ta xét một Sudoku dƣờng nhƣ có vẻ không có gì là không giải đƣợc sau đây(Hình 14). Hình 7. 14 Một phần của một Sudoku không có lời giải. Sử dụng kỹ thuật CRME, ô đầu tiêu chúng ta confirmed là (1,3) (Hình 15). Trang 78
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 15 Điền giá trị cho ô (1,3) Ta quét từ ô (8,3) , chúng ta thấy rõ ngay là không có một giá trị nào có thể có cho ô này.Trong trƣờng hợp này thì hệ thống phải hiển thị một cảnh báo cho biết là đã có lỗi với Sudoku này. Invalid Move Ngƣợc lại, chúng ta đã dùng kỹ thuật CRME để giải một Sudoku không thể giải ở trên , bây giờ chúng ta chúng ta bắt đẩu với 1 Sudoku có thể giải đƣợc (Hình 16) Hình 7. 16 Một phần của Sudoku có thể có lời giải. Áp dụng kỹ thuật CRME cho Sudoku trên sẽ có kết quả nhƣ hình 17 Hình 7. 17 Điền giá trị vào cho vài ô Sudoku. Tuy nhiên nếu User bắt đầu với Sudoku với một lỗi di chuyển, giống nhƣ đặt giá trị 8 vào ô (8,1) nhƣ Hình 18, nguyên nhân này làm cho Sudoku không thể giải. Trang 79
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 18 Đặt vào Grid một giá trị dẫn đến không thể giải Ta quét ô (8,3) thì phát hiện rằng không có giá trị có thể nào (Hình 19) Hình 7. 19 Quét ô (8,3) không có giá trị có thể có Cũng giống nhƣ trƣờng hợp trƣớc, đối với trƣờng hợp này chƣơng trình sẽ hiển thị một message cho User biết là đã có một lỗi cho Sudoku này. 7.1.3 Triển khai giải thuật CRME bẳng chƣơng trình. 7.1.3.1 Triển khai thuật toán SetCell 7.1.3.1.1 Giới thiệu Để hiểu một cách tốt nhất giải thuật CRME, chúng ta sẽ thực thi giải thuật này bằng chƣơng trình.Chúng ta sử dụng 2 biến sau cho thủ tục SetCell() Private String[,] possible =new String[9,9] : Lƣu các giá trị có thể có cho 1 Cell. Private Bool HintMode : Sử dụng để chỉ ra rằng User có muốn giải Sudoku bằng từng bƣớc hay không ? Thủ tục này có nhiệm vụ gán các giá trị cho Grid, thiết lập lại các giá trị có Trang 80
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU thể có khi chúng ta xóa một Cell nào đó thì một chuổi rỗng sẽ đƣợc gán cho ô đó. Một phần thủ tục có nhiệm vụ Reset lại các giá trị có thể có cho 1 Cell. Procedure SetCell (col:số nguyên,row:số nguyên,value:số nguyên, erasable số nguyên ) //Bắt đầu thuật giải. If(value=0) r:=1 While(r<=9) c:=1 While(c<=9) if(actual[c,r]==0) then possible[c,r]=” ” c:=c+1 r:=r+1; else possible[c,r]:=value //Kết thúc thuật giải. 7.1.3.1.2 Mã nguổn chƣơng trình Csharp public void SetCell(int col, int row, int value, short earsable) { Control[] lbl = this.Controls.Find(col.ToString() + row.ToString(), true); Label cellLabel = (Label)lbl[0]; //Luu gia tri vao trong mang actual[col, row] = value; //Neu xoa 1 cell, thiet lap lai cac gia tri co the co cho tất cả các cell khác. if (value == 0) { for (int r = 1; r <= 9; r++) { for (int c = 1; c <= 9; c++) { if (actual[c, r] == 0) possible[c, r] = string.Empty; } } } else { possible[col, row] = value.ToString(); } // Thiet lap lai su xuat hien cho Label control Trang 81
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU if (value == 0) { // Xoa cell cellLabel.Text = string.Empty; cellLabel.Tag = earsable; cellLabel.BackColor = Default_BackColor; } else { if (earsable == 0) { // Mau mac dinh cho cell cellLabel.BackColor = Fixed_BackColor; cellLabel.ForeColor = Fixed_ForceColor; } else { // Mau mac dinh neu nguoi dung thiet lap cho cell cellLabel.BackColor = User_BackColor; cellLabel.ForeColor = User_ForceColor; } cellLabel.Text = value.ToString(); cellLabel.Tag = earsable; } } 7.1.3.2 Thuật toán CalculatePossibleValues – Tính các giá trị có thể có cho các cell 7.1.3.2.1 Giới thiệu Để tính toán các giá trị có thể có cho các cell, chúng ta bắt đầu quét cột,sau đó là quét hàng và sau là Minigrid. Sau khi quét giá trị có thể là một chuỗi rỗng thì ứng dụng sẽ xây dựng 1 Exeption để chỉ ra rằng có một lỗi . Tất cả các bƣớc đƣợc làm bởi thuật toán CalculatePossibleValues, giá trị trả về là một chuỗi có chứa danh sách các giá trị có thể có cho một ô xác định. Thuật toán đƣợc trình bày nhƣ sau. Procedure CalculatePossibleValues(col: số nguyên, row: số nguyên) //bắt đầu thuật giải. c:=0,r:=0 //Bƣớc 1: Check Column r:=1 while(r<=9) if(actual[col,r] ≠ 0) then str=actual[col,r] r:=r+ 1 Trang 82
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU //Bƣớc 2: Check Row c:=1 while(c<=9) if(actual[c,row] ≠ 0 ) then str=actual[c,row] c:=c+1; //Check bên trong minigrid startC=col-((col-1)%3) startR=row-((row-1)%3) rr:=startR, cc=startC while(rr<=startR+2) while(cc<=startC+2) if(actual[cc,rr] ≠ 0) then str=actual[cc,rr] cc:=cc+1 rr:=rr+1 Trang 83
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 7.1.3.2.2 Mã nguồn bằng Csharp public string CalculatePossibleValues(int col, int row) { // lấy giá trị có thể có của ô hiên hành string str; if (possible[col, row] == string.Empty) { str = "123456789"; } else { str = possible[col, row]; } // Bƣớc 1:Check Column int r; int c; for (r = 1; r Ném ra 1 erro if (str == string.Empty) { throw new Exception("Invalid Move"); } return str; } Trang 84
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 7.1.3.3 Giải thuật CheckColumnsAndRows – Kiểm tra hàng và Cột 7.1.3.3.1 Giới thiệu Hàm này có chức năng là quét từng ô riêng lẻ trong Grid từ trái qua phải và từ trên xuống dƣới.Hàm này sẽ gọi hàm CalculatePossibleValues() sau đó nó gán các giá trị có thể có cho mỗi Control Label . Nếu giá trị có thể có trả về là 1 giá trị đơn, sau đó giá trị này sẽ confirmed cho ô đó và Grid sẽ cập nhật lại ô đó. Thuật toán đƣợc trình bày nhƣ sau. Procedure CheckColumnsAndRows () :bool change:=false row:=1,col:=1 while(row<=9) while(col<=9) if(actual[col,row]=0) then possible[col,row]=CalculatePossiblevalues(col,row) //Hiển thị giá trị vào toolTip button setTooltip(col,row,possible(col,row)) if(possible[col,row].Length=1) Then SetCell(col,row,possible[col,row],1)//goi hàm Setcell actual[col,row]=possible[col,row] // xác nhận giá trị Push(col +row+possible[col,row]) // luu các di chuyển vào bên trong Stack col:=col+1 row:=row+1 //Kết thúc thuật giải Trang 85
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 7.1.3.3.2 Mã nguồn bằng Csharp private bool CheckColumnsAndRows() { bool changes = false; // Kiểm tra tất cả các Cell for (int row = 1; row <=9; row++) { for (int col = 1; col <=9; col++) { if (actual[col, row] == 0) { try { possible[col, row] = CalculatePossibleValues(col, row); } catch (Exception ex) { DisplayActivity("đặt giá trị ko hop lệ, vui lòng Undo !",false); throw ex; } if (possible[col, row].Length == 1) { SetCell(col,row,Convert.ToInt32(possible[col,row]),1); // number is confirmed actual[col, row] = Convert.ToInt32(possible[col,row].ToString()); DisplayActivity("Khử CRME",false); DisplayActivity("===", false); DisplayActivity("Inserted " + actual[col, row] +"in"+(+col+","+row), false); changes = true; if (HintMode) return true; } } } } return changes; } 7.1.3.4 Giải thuật SolvePuzze 7.1.3.4.1 Giới thiệu Giải thuật này đƣợc sử dụng khi User Click vào sự kiện Click của Button SolveGame hay HintButton. Thuật giải Procedure SolvePuzze():Boolean change:=false exitLoop=false do { Trang 86
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU //Khử bằng kỹ thuật CRME Change=CheckColumnsAndRows() if(HintMode && change)||IsPuzzeSolved()) Then exitLoop=true break; //Thoát khỏi vòng lặp }while(change); If(IsPuzzeSolved()) then return true else return false //Ket thuc Fuction 7.1.3.4.2 Mã nguồn cho giải thuật public bool SolvePuzzle() { bool changes = false; bool ExitLoop = false; try { do { //Khử CRME changes = CheckColumnsAndRows(); if ((HintMode && changes) || IsPuzzleSolved()) { ExitLoop = true; break; //Thoát khỏi vòng lặp } } while (!(!changes)); } catch (Exception ex) { throw ex; } if (IsPuzzleSolved()) { timer1.Enabled = false; Console.Beep(); Statuslabel1.Text = " Giải Hoàn Thành "; MessageBox.Show("Giải Hoàn Thành ~(`_`_`)"); return true; } else { return false; } } Trang 87
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 7.2 Kỹ thuật nâng cao trong việc giải bài toán Sudoku Trong phần kỹ thuật cơ bản để giải Sudoku chúng ta đã nhắc tới một kỹ thuật tuy không giải đƣợc hầu hết các Sudoku nhƣng nó là cơ sở để cho chúng ta xác định đƣợc các giá trị có thể có cho 1 Cell, kỹ thuật đó sẽ làm bƣớc đệm và là cơ sở để chúng ta nghiên cứu phần nâng cao này. 7.2.1 Lone Rangers Lone Rangers là một thuật ngữ trong vấn đề giải thuật sudoku. Nó là thuật ngữ đề cập đến một con số mà có nhiều giá trị có thể có cho ô sudoku nhƣng nó chỉ xuất hiện duy nhất trong 1 row, coloumn, minigrid.Để thấy rõ đƣợc ta xét một ví dụ trong hình 20. Trong hàng này 6 con số đã đƣợc điền, ta có thể thấy đƣợc các giá trị có thể có cho các ô đƣợc bôi đậm –các giá trị xác định đƣợc là do chúng ta sử dụng kỹ thuật CRME. Chúng ta chú ý rằng tại ô thứ 2 chì có một giá trị có thể là 8, và bây giờ ta có thề xác định đƣợc rằng ô số này sẽ chỉ có 1 số duy nhất đƣợc điền chính là số 8.Trong trƣờng hợp này ta biết số 8 nhƣ là một số Lone Rangers. Hình 7. 20 Xác định con số Lone Ranger trong 1 hàng. Con số Lone Rangers vô cùng hữu ích trong việc giúp cho ta biết con số nào sẽ đƣợc confirmed vào 1 Cell và nó hữu ích hơn trong việc giải các bài toán Sudoku khó. Con số Lone Rangers này có thể xuất hiện trong hàng, cột hay Minigrid. 7.2.1.1 Lone Rangers trong Minigrid Bây giờ ta xét một phần của Grid sau (Hình 21) Hình 7. 21Một phần của một Sudoku Puzze Chúng ta sẽ sử dụng kỹ thuật CRME để xác giá trị cho 3 ô đƣợc hiển thị Trang 88
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU trong hình 22 Hình 7. 22 Xác nhận 3 số cho 3 ô trong Grid Tiếp theo ta sử dụng kỹ thuật CRME để xác định các giá trị có thể có cho các ô trong Grid nhƣ trong hình 23. Hình 7. 23 Các giá trị có thể có đƣợc xác định bằng CRME Giờ ta chỉ quan tâm đến Grid thứ 3 để xét Hình 24 Hình 7. 24Xét Grid thứ 3 Ta quan sát ô thứ (7,2) thì thấy ngay rằng con số 1 sẽ đƣợc điền vào ô này, giá trị 1 này chính là con số Lone Ranger.Và con số 1 chỉ xuất hiện trong ô (7,2) và nó không xuất hiện ở bất kì ô nào khác trong Grid này. Theo logic, chúng ta có thể kết luận rằng “Khi có 1 con số chỉ xuất hiện một lần bên trong Minigrid (nó Trang 89
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU nhƣ là một giá trị có thể có ), thì con số đó có thể confirmed cho ô mà nó chứa”. Điều này là hợp logic bởi vì các ô (7,1) ,(8,1),(9,1) không thể chứa giá trị 1. Và bây giờ con số 1 đƣợc confirmed cho ô (7,2). Theo lý luận này ta có thể đặt giá trị 1 vào ô (7,2) nhƣ hình 25. Hình 7. 25 Confirmed giá trị 1 cho ô (7,2) 7.2.1.1.1 Triển khai giải thuật LookForLoneRangerinMinigrids 7.2.1.1.1.1 Thuật Giải LookForLoneRangerinMinigrids Nhiệm vụ của Function này là tìm kiếm trên 9 minigrids và quét để tìm các con số Lone Ranges( từ 1 đến 9).Nếu có 1 số Lone Ranger đƣợc tìm thấy thì Function này phải Insert giá trị đó cho ô chứa nó. Function này trả về giá trị True nếu có 1 con số Lone Ranger đƣợc tìm thấy trong các Minigrids, ngƣợc lại nó sẽ trả về giá trị False. Hình 26 hiển thị các bƣớc thực hiện Function LookForLoneRangerinMinigrids(). Hình 7. 26 Biểu thị hình ảnh quét các Minigrids Trang 90
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Bƣớc 1: Quét các từ đỉnh bên trái các ô cho mỗi Minigrid. Bƣớc 2: Với mỗi Minigrid đƣợc quét từ trái qua phải, từ trên xuống dƣới. Bƣớc 3: Xử lý lặp lại cho các số từ 1 đến 9. Phần giải thuật chính của LookForLoneRangerinMinigrids() Procedure LookForLoneRangerinMinigrids():Boolean //Begin change=false nextminigrid=false occurrence=0,cpos=0,rpos=0 n=1,r=1,c=1,rr=0,cc=0 while(n 1) then nextminigrid=true Break; cc:=cc+2 rr:=rr+2 c:=c+3 r:=r+3 n:=n+1 Trang 91
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU //End Function 7.2.1.1.1.2 Phần mã nguồn của giải thuật private bool LookForLoneRangersinMinigrids() { bool changes = false; bool NextMiniGrid = false; int occurrence = 0; int cPos = 0; int rPos = 0; // check for each number from 1 to 9 for (int n = 1; n 1) { NextMiniGrid = true; break;//Thoát khỏi vòng lặp } } } if (NextMiniGrid) break; } if ((!NextMiniGrid) && occurrence == 1) { SetCell(cPos, rPos, n, 1); SetToolTip(cPos, rPos, n.ToString()); Moves.Push(cPos+rPos+n.ToString()); DisplayActivity("Lone Ranger tìm thấy", false); DisplayActivity("===", false); DisplayActivity("Insert giá trị" + n.ToString()+"vào"+(+cPos+","+rPos),false); Application.DoEvents(); actual[cPos, rPos] = n; changes = true; } } } } return changes; } Trang 92
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 7.2.1.2 Lone Ranges trong Row Lone Rangers không chỉ xuất hiện bên trong Minigrid mà đôi khi nó còn xuất hiện trong các hàng. Chúng ta xét trƣờng hợp sau tron hình Hình 7. 27 Tìm kiếm 1 Lone Ranger trong các hàng Vẫn áp dụng kỹ thuật CRME để xác định các giá trị có thể có cho các Cell (Hình 28) Hình 7. 28: Áp dụng CRME để tìm kiếm số Lone Ranger trong các hàng. Trang 93
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Ta quét các Minigrids để tìm các con số Lone Ranger nhƣng không phát hiện có con số nào, nhƣng lại thấy nó xuất hiện trong hàng thứ 5 và tại ô thứ (6,5). Hình 7. 29 Số Lone Ranger đƣợc phát hiện tại dòng số 5. 7.2.1.2.1 Triển khai giải thuật LookForLoneRangerinRows 7.2.1.2.1.1 Giải thuật LookForLoneRangerinRows Ta viết Function LookForLoneRangerinRows ().Hàm này có chức năng quét tìm số Lone Ranger trong 9 row của Sudoku.Ta quét từ hàng đầu tiên của Grid cho đến hàng cuối cùng. Hàm này ít phức tạp hơn hàm quét Minigrids vì hàm trƣớc quét bên trong Minigrid và thêm vào là cấu trúc lặp. Hình 7. 30 hiển thị các bƣớc quét của Function LookForLoneRangerinRows() Bƣớc 1: Quét bắt đầu từ hàng đầu tiên phía trên cùng của Grid Bƣớc 2: Mỗi hàng ta quét từ trái qua phải, tìm Lone Ranger. Trang 94
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Bƣớc 3: Lặp lại bƣớc 2 cho 9 số từ 1 đến 9 Bƣớc 4: Tiếp tục quét hàng kế tiếp cho đến hàng cuối cùng trong Grid 7.2.1.2.1.2 Giải thuật Procedure LookForLoneRangersinRows():Boolean //Bắt đầu giải thuật change=false occurrence=0,cpos=0,rpos=0 n=1,r=1,c=1 while(n 1) then Break cpos=c rpos=r c:=c+1 r:=r+1 n:=n+1 return changes //End Fucntion Trang 95
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 7.2.1.3 Lone Rangers trong Columns Hàm này thực thi quét các cột trong Grid để tìm đƣợc số Lone Rangers Hình 7. 31 Tìm kiếm số Lone Rangers trong các Columns Bƣớc 1: Thực hiện quét từ cột đầu tiên trong Grid Bƣớc 2: Tại mỗi column quét từ trên xuống dƣới, tìm Lone Ranger Bƣớc 3: Lặp lại bƣớc 2 cho mỗi số từ 1 đến 9 Bƣớc 4: Tiếp tục quét từ cột đầu tiên cho đến cột cuối cùng của Grid. 7.2.1.3.1 Triển khai giải thuật LookForLoneRangerinColumns 7.2.1.3.1.1 Giải thuật LookForLoneRangerinColumns Procedure LookForLoneRangersinRows():Boolean //Bắt đầu giải thuật change=false occurrence=0,cpos=0,rpos=0 n=1,r=1,c=1 while(c<=9) while(n<=9) while(r<=9) if(actual[c,r]=0 && possible[c,r).Contains(n) then Trang 96
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU occurrence:= occurrence+1 if(occurrence>1) then Break // exit vòng lặp cpos=c rpos=r r:=r+1 n:=n+1 c:=c+1 return changes //End Fucntion 7.2.1.3.1.2 Phần mã nguồn của giải thuật LookForLoneRangerinColumns public bool LookForLoneRangersinColumns() { bool changes = false; int occurrence = 0; int cPos = 0; int rPos = 0; // Kiểm tra column for (int c = 1; c 1) break; Exit For cPos = c; rPos = r; } } if (occurrence == 1) { SetCell(cPos, rPos, n, 1); SetToolTip(cPos, rPos, n.ToString()); Moves.Push(cPos + rPos + n.ToString()); DisplayActivity("Look for Lone Rangers in Columns", false); DisplayActivity("===", false); DisplayActivity("Inserted value" + n.ToString() + "in" + (+cPos + "," + rPos), false); Application.DoEvents(); // Số đƣợc confirmed actual[cPos, rPos] = n; changes = true; } } } Trang 97 return changes; }
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 7.2.1.4 Tinh chỉnh lại Function SolvePuzze Để giải Sudoku chúng ta sử dụng kỹ thuật Lone Ranger .Đầu tiên chúng ta áp dụng kỹ thuật CRME.Nếu không có sự thay đổi nào,khi đó ta tìm các số Lone Rangers trong các Minigrids.Nếu có ít nhất một Cell đƣợc confirmed trong các Minigrids, chúng ta áp dụng kỹ thuật CRME lại lần nữa.Chúng ta sẽ quét các số Lone Rangers trong các Rows chỉ khi lần thứ 2 không có sự thay đổi nào trong Grids.Sau cùng ta cũng thực hiện việc quét các Columns sau khi không có sự thay đổi nào trong Grids. Hình 7. 32 Lƣợc đồ biểu diễn các kỹ thuật khác nhau để áp dụng giải Sudoku Trang 98
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU 7.2.1.4.1 Triển khai giải thuật- Tinh chỉnh thêm phần giải thuật SolvePuzze 7.2.1.4.1.1 Giải thuật SolvePuzze Procedure SolvePuzze():Boolean //Begin Function changes:=false exitLoop:=false Do{ Do{ Do{ Do{ Do{ change=CheckColumnAndRows if((hintMode && changes)||IsSolvePuzze()) then exitLoop=true break //End if }while(change); If(exitLoop)then Break change=LookForLoneRangerinMinigrids() if((hintMode && change)||IsSolvedPuzze()) exitLoop=true break }while(change); if(exitLoop) then break change=LookForLoneRangerinRows() if((hintMode && change)||IsSolvedPuzze()) Trang 99
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU exitLoop=true break }while(change); if(exitLoop) then break change=LookForLoneRangerinColumns() if((hintMode && change)||IsSolvedPuzze()) exitLoop=true break }while(change); } //End Fucntion 7.3 Các kỹ thuật nâng cao trong việc giải bài toán Sudoku Phần này trình bày về một số kỹ thuật khác trong việc giải sudoku, nhƣ trong các phần trƣớc chúng ta đã xét các kỹ thuật nhƣ: CRME( kỹ thuật khử cột, hàng, minigrids) và kỹ thuật Lone Rangers. Để giải đƣợc các Sudoku loại khó thì việc chúng ta xét các nhiều trƣờng hợp là rất cần thiết, nên trong phần này chúng em trình bày về các kỹ thuật nâng cao khác nhƣ: Look For Twins(Tìm cặp đôi) và Look For Triplets(Tìm cặp 3), Brute Force Elimination. 7.3.1 Kỹ thuật tìm kiếm cặp đôi -Look For Twins Để hiểu đƣợc sự hữu ích của kỹ thuật tìm kiếm cặp đôi chúng ta xem xét hình sau, nó gồm một danh sách các giá trị có thể có cho các ô Sudoku chƣa đƣợc giải. Trang 100
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 33 Một phần của Sudoku với các giá trị có thể có. Chúng ta hãy quan sát ô (5,2) và (6,2). Chúng có chứa các giá trị có thể có là 2,3 .Trong trƣờng hợp này nếu ô (5,2) lấy giá trị 2 thì khi đó ô (6,2) phải lấy giá trị là 3, ngƣợc lại nếu ô (5,2) lấy giá trị 3 thì ô (6,2) lấy giá trị 2. Nếu giá trị đƣợc điền cho ô (5,2) và (6,2) thì các ô bên ngoài hàng thứ 2 sẽ không thể chứa 2 giá trị 2 hoặc 3. Vì 2 ô (5,2) và (6,2) là các giá trị cho Grids và nó cùng nằm trên 1 hàng , chúng đƣợc biết nhƣ là Twins(cặp đôi). Hình 7. 34 Xác định Twins Thực hiện quét hàng, cột chúng ta khử đƣợc các giá trị 2 và 3 cho các ô khác. Khi đó Grid của ta sẽ có hình sau. Trang 101
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 35 Khử giá trị 2 và 3 cho các Cell khác. Tƣơng tự , bởi vì Twins đƣợc xuất hiện trong cùng một Minigrid, tất cả các ô khác trong Minigrids sẽ không thể chứa giá trị 2 và 3. Vì thế ta có thể khử đƣợc giá trị của các ô (4,1) và (5,1). Hình 7. 36 Khử các giá trị 2 và 3 trong Minigrids Bây giờ chúng ta để ý , có 3 cặp đôi trong Grids (Xem hình 37). Trong đó có 2 cặp đôi trong hai hàng đầu và cặp thứ 3 trong cột thứ 5. Trang 102
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 37 Các cặp đôi xuất hiện khi thực hiện Scanning lần thứ nhất. Đối với cặp đôi “23”, chúng ta có thể thực hiện quét theo cột để xóa bỏ các giá trị gây ra lỗi đối với hai con số 2 và 3. Ví dụ, nếu chúng ta kiểm tra các giá trị có thể có cho cột thứ 5, chúng ta có thể thấy rằng các giá trị 2 và 3 đƣợc khử từ nhiều ô trong cột này (Hình 38). Hình 7. 38 Quét cột cho cặp đôi Trang 103
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Đối với cặp đôi “45”, chúng ta thực hiện quét trong các Minigrids cho phép ta loại bỏ các giá trị 4 và 5 trong ô (2,1). Khi đó ô (2,1) sẽ đƣợc confirmed giá trị 2 và ô (2,4) sẽ confirmed giá trị 4. Hình 7. 39 Xác nhận ô (2,1), tiếp theo là ô (2,4) Đối với cặp đôi “89” không có nhiều, chúng ta có thể xem các hàng, cột mà cặp đôi này xuất hiện. Ta coi hình 40, nhƣ chúng ta có thể thấy, thực hiện quét cặp đôi trong Column, Row và Minigrids sẽ cho kết quả tốt hơn trƣớc rất nhiều, trong hình này giá trị của 2 ô đã đƣợc Confirmed. Hình 7. 40 Grid sau khi quét Rows, Columns và Minigrids 7.3.1.1 Triển khai giải thuật để tìm kiếm cặp đôi trong Minigrids Trang 104
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Chúng ta sẽ hiện thực thuật toán để tìm kiếm cặp đôi tên là LookForTwinsinMinigrids(). Function này có chức năng là tìm kiếm cặp đôi cho 9 Minigrid. Nó thực hiện quét tất cả các ô trong Grid và tìm kiếm các ô với 2 giá trị có thể có cho ô.Mỗi lần nó tìm một ô với 2 giá trị có thể có cho ô, nó tìm các cặp đôi trong Minigrid mà nó chứa. Nếu quả thật có một cặp đôi giống nhau trong cùng minigrid, các ô trong Minigrid sẽ hiển thị các giá trị có thể có đã đƣợc Modified và xóa các giá trị cặp đôi.Sau khi xử lý , nếu các ô bên trái với một giá trị có thề, khi đó giá trị này sẽ đƣợc confirmed cho ô đó. Hàm này sẽ trả giá trị là True nếu có bất kì sự thay đổi trong danh sách các giá trị có thể có cho bất kì ô nào trong Grid, ngƣợc lại nếu hàm trả về giá trị là False nếu không có bất kì giá trị có thể nào cho ô. 7.3.1.1.1 Giải thuật LookForTwinsinMinigrids(Tìm cặp sinh đôi trong Minigrids) Bƣớc 1: Changes=false. Bƣớc 2:Duyệt qua các row trong Grid Bƣớc 2.1: Duyệt qua các Column trong Grid Bƣớc 2.2: Kiểm tra giá trị thực tế trên ô và giá trị có thể có cho ô(Kiểm tra Twins) Bƣớc 2.2.1: o StartC=c - ((c-1)%3) //xác định vị trí ô bắt đầu quét trong Minigrids o StartR=r-((r-1)%3) //xác định vị trí hàng bắt đầu quét trong Minigrids. Bƣớc 2.2.2: Duyệt qua các hàng và cột trong minigrid (cc: vị trí cột bắt đầu trong minigrid và rr: vị trí hàng bắt đầu trong minigrid) Bƣớc 2.2.2.1 : Kiểm tra cc=c and rr=r and possible[cc,rr]=possible[c,r] //Twins đƣợc tìm thấy, ngƣợc lại lặp lại bƣớc 2.2.1 Bƣớc 2.2.2.2 : Xóa các Twins từ tất cả các giá trị có thể có trong Minigrid. Bƣớc 2.2.2.2.1 : Kiểm tra Cell có rỗng không ? Trang 105
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Bƣớc 2.2.2.2.2 : Lƣu một bản copy các giá trị có thể có. Bƣớc 2.2.2.2.3: Xóa cặp đôi đầu tiên từ các giá trị có thể có. Bƣớc 2.2.2.2.4: Xóa cặp đôi thứ 2 từ các giá trị có thề có. Bƣớc 2.2.2.2.5: Khi giá trị có thể có đƣợc Modified thì thiết lập biến change=True.Ngƣợc lại quay về bƣớc 2.2.2.2. Bƣớc 2.2.2.2.6: Nếu các giá trị có thể có cho 1 ô là một chuỗi rỗng, sau khi User đã di chuyển giá trị cho ô mà kết quả không thể giải đƣợc , Ngƣợc lại quay về bƣớc 2.2.2.2. Bƣớc 2.2.2.2.7: Nếu vị trí bên trái của một ô có một giá trị có thể có cho ô đó thì giá trị này đƣợc Confirmed cho ô đó.Ngƣợc lại quay lại bƣớc 2.2.2.2. Bƣớc 3: Return change Function này sẽ quét từng ô riêng biệt trong Grid.Nếu một ô có 2 giá trị có thể có cho ô này, khi đó sẽ quét các cặp sinh đôi trong Minigrid mà nó chứa cặp đôi này. Khi quét trong Minigrid sẽ quét từ phía trên bên trái Minigrid và sẽ tiếp tục cho đến ô cuối cùng của Minigrid. Hình 7. 41 Quét cặp sinh đôi trong Minigrids Trang 106
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Ví dụ , nếu ô (5,5) có 2 giá trị có thể có cho ô này, khi đó quét bắt đầu từ ô đầu tiên trong Minigrid, tọa độ của ô này đƣợc xác định từ công thức StartC=c-((c-1)%3) StartR=r-((r-1)%3) Vì c=5 và r=5, nên ta có thể sử dụng công thức trên, khi đó ta có thể lấy StartC=5-(5-1)%3) có giá trị là 4 và StartR cũng có giá trị là 4.Công thức này đƣợc áp dụng cho bất kì ô nào trong Grid và chúng ta sẽ lấy đƣợc tọa độ của ô bắt đầu trong Minigrid. 7.3.1.1.2 Triển khai giải thuật tìm kiếm cặp đôi trong Rows Chức năng của giải thuật tìm kiếm cặp đôi trong Row cũng giống nhƣ trong Minigrids, tức là giải thuật này muốn tìm kiếm cặp đôi trong các hàng của Grid.Nó kiểm tra trong mỗi hàng và quét từ trái sang phải , ngay khi nó phát hiện đƣợc một ô với 2 giá trị có thể có , nó quét bắt đầu từ ô kế tiếp cho đến ô cuối cùng. Nếu quả thực có một cặp sinh đôi trong row, phần còn lại của các ô trong hàng sẽ có một danh sách các giá trị có thể đƣợc chỉnh sửa lại để loại các giá trị của Twins. Hàm LookForTwinsinRows() sẽ thực thi giải thuật tìm kiếm cặp đôi trong các hàng của Grid, hàm này sẽ trả về giá trị True nếu có bất kì sự thay đổi nào trong danh sách các giá trị có thể có của bất kì ô nào trong Grid.Ngƣợc lại hàm trả về False nếu nếu không có giá trị có thể có của ô bị ảnh hƣởng. Hình 7. 42 Quét các cặp sinh đôi trong hàng. 7.3.1.1 Giải thuật tìm cặp đôi trong Hàng. Trang 107
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Bƣớc 1: Change=false Bƣớc 2: Duyệt qua các hàng của Grid Bƣớc 2.1: Duyệt qua các cột của Grid Bƣớc 2.2: Kiểm tra xem có cặp đôi trong Grid hay không. Bƣớc 2.2.1: Duyệt qua các cột trong hàng, nếu possible[cc,r]=possible[c,r] qua bƣớc 2.2.2 - tức cặp đôi đƣợc tìm thấy trong hàng, ngƣợc lại trở về bƣớc 2.2. Bƣớc 2.2.2: Xóa bỏ các giá trị có thể khác có trong Column Bƣớc 2.2.2.1: Xóa cặp đôi đầu tiên Bƣớc 2.2.2.2: Xóa cặp đôi thứ hai Bƣớc 2.2.2.3: Nếu các giá trị có thể có đƣợc Modified, khi đó thiết lập lại biến change thành True để chỉ ra rằng các giá trị có thể có của ô đã đƣợc thay đổi.Ngƣợc lại trở về bƣớc 2.2 Bƣớc 2.2.2.4: Nếu bên trái có một giá trị có thể có cho ô hiện hành thì Confirmed giá trị cho ô này. Bƣớc 2.2.2.5: Lƣu các giá trị đƣợc di chuyển vào Stack. Bƣớc 3: Return Change 7.3.1.1.3 Triển khai giải thuật tìm kiếm cặp đôi trong Cột Giải thuật sẽ quét và tìm kiếm cặp đôi trong 9 cột của Grid. Nó kiểm tra trên mỗi cột và thực hiện quét từ trên xuống dƣới cho, ngay khi nó phát hiện đƣợc một ô với 2 giá trị có thể có , nó quét bắt đầu từ ô kế tiếp cho đến ô cuối cùng. Nếu quả thực có một cặp sinh đôi trong Column, phần còn lại của các ô trong cột sẽ có một danh sách các giá trị có thể đƣợc chỉnh sửa lại để loại các giá trị của Twins. Bƣớc 1: Change=false Bƣớc 2: Duyệt qua các cột của Grid Trang 108
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Bƣớc 2.1: Duyệt qua các hàng của Grid Bƣớc 2.2: Kiểm tra xem có cặp đôi trong Grid hay không. Bƣớc 2.2.1: Duyệt qua các hàng trong cột này, nếu possible[cc,r]=possible[c,r] qua bƣớc 2.2.2 - tức cặp đôi đƣợc tìm thấy trong cột, ngƣợc lại trở về bƣớc 2.2. Bƣớc 2.2.2: Xóa bỏ các giá trị có thể khác có trong Column Bƣớc 2.2.2.1: Xóa cặp đôi đầu tiên Bƣớc 2.2.2.2: Xóa cặp đôi thứ hai Bƣớc 2.2.2.3: Nếu các giá trị có thể có đƣợc Modified, khi đó thiết lập lại biến change thành True để chỉ ra rằng các giá trị có thể có của ô đã đƣợc thay đổi.Ngƣợc lại trở về bƣớc 2.2 Bƣớc 2.2.2.4: Nếu bên trái có một giá trị có thể có cho ô hiện hành thì Confirmed giá trị cho ô này. Bƣớc 2.2.2.5: Lƣu các giá trị đƣợc di chuyển vào Stack. Bƣớc 3: Return Change Hàm LookForTwinsinColumns() sẽ thực thi giải thuật tìm kiếm cặp đôi trong các cột của Grid, hàm này sẽ trả về giá trị True nếu có bất kì sự thay đổi nào trong danh sách các giá trị có thể có của bất kì ô nào trong Grid.Ngƣợc lại hàm trả về False nếu nếu không có giá trị có thể có của ô bị ảnh hƣởng. Trang 109
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 43 Quét cặp đôi trong hàng 7.3.3 Kỹ thuật tìm kiếm cặp ba – Look For Triplets Trong khi tìm kiếm cặp đôi là hữu ích trong việc giải bài toán Sudoku, nhƣng thỉnh thoảng ta cũng gặp một số trƣờng hợp là cặp 3, chúng ta hãy xem xét một phần của Grid sau. Hình 7. 44 Một phần của Sudoku Hình trên chúng ta thấy không có cặp đôi nào nhƣng nó có 3 ô với các giá trị giống nhau. Chúng ta gọi chúng ta các Triplets. Cũng giống nhƣ cặp đôi chúng rất hữu ích để trợ giúp cho việc khử các giá trị có thể có cho các ô khác, trong Puzze đƣợc hiển thị ở trên, các số 2,4,6 phải đƣợc xác định đặt vào một trong 3 ô có chứa các giá trị có thể có là 2,4,6. Khi điều kiện đã đƣợc thiết lập, chúng ta có thể loại trừ giá trị 2,4,6 từ các ô khác trong Minigrids. Trang 110
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7. 45 Modify lại giá trị trong Minigrid nơi mà Triplets đƣợc tìm thấy. Thông qua hình trên chúng ta thấy rằng việc tìm kiếm Triplets sẽ không ô nào đƣợc Confirmed giá trị, nhƣng kỹ thuật này rất hữu ích trong việc làm giảm các giá trị có thể có cho các ô, khi đó chúng ta sẽ sử dụng lại các kỹ thuật nhƣ CRME và Lone Ranger để confirmed giá trị cho ô. Chú ý: Cũng giống nhƣ Twins, Triplets cũng có thể xuất hiện trong rows, columns, minigrids. 7.3.3.1 Các biến thể của Triplets Nhƣ phần trên chúng ta đã biết Triplets đƣợc hình thành từ 3 ô, với mỗi ô có chứa các giá trị có thể có cho các ô.Tuy nhiên định nghĩa này không hoàn toàn chính xác. Có 3 trƣờng hợp khác nhau mà có thể phân loại đƣợc coi nhƣ là các Triplets:  Trƣờng hợp 1: 3 ô với 3 giá trị có thể có giống nhau  Trƣờng hợp 2: 2 ô với 3 giá trị có thể có và 1 ô có chứa 2 giá trị có thể có mà nó chính là tập con của 3 giá trị có thể có kia.  Trƣờng hợp 3: 1 ô với 3 giá trị có thể có và 2 ô có chứa 2 giá trị có thể có mà nó chính là tập con của 3 giá trị có thể có kia. Điều này là quan trọng để định danh 3 trƣờng hợp bởi vì chúng ta phải viết code cho cả 3 trƣờng hợp trên, để hiều đƣợc 3 trƣờng hợp trên chúng ta xem xét ví dụ sau. Trang 111
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Trƣờng hợp 1: Đây là trƣờng hợp thƣờng thấy nhất, miễn là có 3 ô đƣợc thiết lập các giá trị có thể có, một Triplet đƣợc hiển thị nhƣ hình sau. Hình 7. 46 Một bộ của Triplet Trang 112
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Trƣờng hợp 2: Trong trƣờng hợp này thì ít phổ biến hơn, có 2 ô với 3 giá trị có thể có và 1 ô có chứa 2 giá trị có thể có mà nó là tập con của 3 giá trị có thể có. Có 3 hình thể hiện trong trƣờng hợp này. Hình 7. 47 Các ví dụ của Triplet – 2 ô với Để làm rõ vấn đề là tại sao trong ví dụ trên đƣợc phân loại nhƣ là một Triplets. Bây giờ chúng ta xem xét từng ví dụ. Bắt đầu với ô đầu tiên bên trái trong hình 47, chúng ta thừa nhận rằng ô thứ 3 sẽ lấy giá trị là 2, nguyên nhân là do 2 ô đầu là Twins, với các giá trị có thể có là 1 và 3 (Hình 48). Dựa vào kỹ thuật Twins, 2 ô đầu tiên phải xác định một trong các giá trị các trong các giá trị có thể có. Hình 7. 48 Kiểm tra một ví dụ của Triplets. Thực vậy, chúng ta chắc rằng trong 3 ô phải có chứa một trong 3 giá trị có thể có là 1,2 hoặc 3. Tất cả các ô khác mà có chứa các giá trị có thể có là 1,2 hoặc 3 giờ đƣợc giới hạn trong danh sách các giá trị có thể có. Trang 113
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Trƣờng hợp 3: Trƣờng hợp này rất ít khi xuất hiện so với 2 trƣờng hợp trƣớc. Hình sau là một ví dụ cho trƣờng hợp này. Hình 7. 49 Hai thể hiện của Triplet – một ô với 3 giá trị có thể có và 2 ô với 2 giá trị có thể có cho ô. Sử dụng ví dụ đầu bên trái để minh họa, giả sử ô thứ 2 lấy giá trị là 1 (Hình 51), nguyên nhân là do ô thứ 3 có giá trị 3, lần lƣợt ô đầu tiên có giá trị là 3. Do đó 3 ô phải có chứa một trong 3 giá trị có thể có là 1,2 hoặc 3. Hình 7. 50: Thử với ví dụ đầu. 7.3.3.2 Triển khai giải thuật tìm cặp 3 trong Minigrids Chúng ta sẽ triển khai giải thuật với cái tên : LookForTripletsinMinigrids(), chức năng chính của Function này là quét tất cả các ô trong Grid và tìm các ô với 3 giá trị có thể(triplets). Mỗi lần tìm kiếm một ô với các giá trị có thể có và nó tìm kiếm 2 ô triplets khác trong minigrids. Nếu quả thực có một Triplets trong Minigrids. Thuật giải quét để tìm cặp 3(triplets) cũng tƣơng tự nhƣ thuật giải tìm cặp Trang 114
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU đôi. Tuy nhiên, nó có phần phức tạp hơn bởi vì ứng dụng bây giờ phải lƣu tọa độ của 3 ô (Triplets) thay vì 2 ô (Twins). Cặp 3 đƣợc lƣu giữa là một chuỗi các kí tự. Ví dụ Triplets là 3 ô (1,1) ,(4,1) và (7,1) thì nó sẽ đƣợc lƣu dƣới dạng “114171”. Thuật Giải LookForTripletsinMinigrids Bƣớc 1: Change=false Bƣớc 2: Duyệt qua các hàng trong Grid Bƣớc 2.1: Duyệt qua các cột trong Grid Bƣớc 2.2: Kiểm tra xem có triplets nào đƣợc tìm thấy không actual[c,r]=0 && possible[c.r].Lenght=3 Bƣớc 2.2.1: Quét trong các Minigrids StartC=c – ((c-1)%3) StartR=r – ((r-1)%3) Bƣớc 2.2.1.1: Duyệt các hàng trong Minigrids Bƣớc 2.2.1.1.1: Duyệt các cột trong Minigrids Bƣớc 2.1.1.1.1: Kiểm tra cc=c && rr=r &&possible[cc,rr]=possible[c,r] hoặc : possible[cc,rr].Lenght=2 && possible[c,r] chứa possible[cc,rr][0] && possible[cc,rr][1] (với cc: là vị trí cột bắt đầu trong Minigrid, c: là vị trí cột trong Grid, rr: vị trí hàng bắt đầu trong Minigrid, r: vị trí hàng trong Grid)  Lƣu lại tọa độ của Triplet Trang 115
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Bƣớc 2.2.2 : Kiểm tra xem Triplet đã tìm thấy chƣa, nếu tìm thấy bỏ các giá trị này từ các ô khác.Ngƣợc lại quay về bƣớc 2.2. Ngoài ra còn các giải thuật Tìm Triplets trong các hàng và các cột, cũng tƣơng tự nhƣ giải thuật tìm trong Minigrids. Đối với giải thuật tìm cặp 3 trong Hàng thì thực hiện quét từ trái qua phải. Còn tìm cặp 3 trong Cột thì quét từ trên xuống dƣới. 7.3.4 Tinh chỉnh lại phƣơng thức SolvePuzzle (đã giới thiệu ở phần mục lục 7.1.3.4) Phần này mục đích là kết hợp các kỹ thuật khác nhau để giải sudoku, chúng ta sẽ phải chỉnh sửa lại Function SolvePuzzle() nhƣ đã trình bày ở phần trƣớc. Thuật giải SolvePuzzle Bƣớc 1: change=false exitLoop=false Bƣớc 2 : Tìm cặp 3 trong các hàng Bƣớc 3: Tìm cặp 3 trong các cột Bƣớc 4: Tìm cặp 3 trong Minigrids Bƣớc 5: Tìm cặp đôi trong các hàng Bƣớc 6:Tìm cặp đôi trong các cột Bƣớc 7: Tìm cặp đôi trong các Minigrids Bƣớc 8: Tìm con số Lone Ranger trong các cột Bƣớc 9: Tìm con số Lone Ranger trong các hàng Bƣớc 10: Tìm con số Lone Ranger trong các Minigrids Bƣớc 11: Trả về giá trị True hoặc False cho ô sudoku này (True là giải đƣợc, False không có lời giải) Trang 116
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Nhƣ chúng ta trƣớc tiên sẽ sử dụng kỹ thuật CRME, sau đó là đến các kỹ thuật nhƣ: Lone Ranger(cho hàng, cột, minigrids), Twins(cho hàng, cột, minigrids), Triplets( cho hàng, cột, minigrids) . 7.3.5 Sử dụng Burte - Force Elimination Khi chúng ta sử dụng các kỹ thuật để giải một sudoku nhƣng vẫn chƣa thể giải đƣợc, để giải quyết tình huống này chúng ta sẽ triển khai thêm một Function nữa đó là thuật giải Brute-Force Elimination (Sự khử dùng Brute-force). Chúng ta giờ đây phải sử dụng một vài kỹ thuật khác trong lập trình đó là dùng Stack, Stack sẽ giúp ta lƣu đƣợc các giá trị có thể có cho các ô trong Grid và sẽ quay lui lại mỗi bƣớc đi nhằm cho việc phục hổi lại trạng thái cũ của Grid, khi mà một đƣờng đi nào đó không đúng sẽ dẩn đến Sudoku không giải đƣợc. Chúng ta xem xét hình sau: Hình 7.51: Một ô sudoku Khi đó danh sách các giá trị có thể cho ô Sudoku này là: Trang 117
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7.52: Danh sách các giá trị có thể cho mỗi ô Chúng ta sẽ lựa chọn một ô chƣa đƣợc giải sau đó là áp dụng các kỹ thuật ở trên, nếu vẫn chƣa giải đƣợc ta chọn một giá trị cho ô chƣa đƣợc giải kế tiếp và ta cứ lặp lại quá trình trên cho đến khi ô sudoku đƣợc giải. Bây giờ, chúng ta lại đặt ra một câu hỏi là : chúng ta sẽ phải bắt đầu từ ô nào ? Tất nhiên là chúng ta phải bắt đầu với ô ít chọn lựa nhất(giá trị có thể có cho ô đó là ít nhất) sau đó thì thực hiện quét từ trái qua phải, từ trên xuống dƣới.Nhƣ hình trên ta có thể thấy đƣợc là ô (1,1) sẽ là ô đƣợc chọn đầu tiên, trong ô này có 2 giá trị có thể có là 5 và 8, chúng ta có thể chọn 5 hoặc 8, nhƣng để đơn giản chúng ta sẽ chọn giá trị đầu tiên là 5 sau đó chúng ta sẽ sử dụng các kỹ thuật trên để giải, và cứ nhƣ vậy ô sudoku sẽ đƣợc giải. Trang 118
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7.53: Ô sudoku đã đƣợc giải Để giải đƣợc đơn giản là ta chọn một một ô nào đó và gán giá trị sau đó là giải.Giải đƣợc ô này ta lại tiếp tục qua các ô khác, đối với các Sudoku khó thì quá trình sẽ có thể phải lặp lại nhiều lần. Thỉnh thoảng vẫn gặp trƣờng hợp có lỗi xảy ra dù ta đã sử dụng tất cả các kỹ thuật để giải, ta xem xet ví dụ trên, nhƣng ta sẽ không chọn ô (1,1) mà thay vào đó là ô (5,4) với giá trị có thể có cho ô đó là 1,4. Gán giá trị 1 cho ô (5,4) và sử dụng các kỹ thuật trên để giải. Hình 7.54: Trạng thái của Grid sau khi gán giá trị 1 cho ô (5,4) Trong trƣờng hợp này chúng ta sẽ phát hiện ra một lỗi, nếu sử dụng kỹ thuật CRME cho ô (5,5) thì chúng ta thấy rõ là không có giá trị nào có thể có cho ô (5,5) này vì tất cả các số từ 1 đến 9 đều đã đƣợc sử dụng. Trang 119
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Hình 7.55: Một tình huống gặp lỗi cho ô (5,5) Trong trƣờng hợp này chúng ta phải Backtrack (quay lui) lại giá trị lúc trƣớc của ô. Chúng ta cần Backtrack lại ô (5,4) và chúng ta sẽ phải xóa các ô mà ta đã Confirmed dựa vào việc gán giá trị 1 cho ô (5,4), sau đó là thử một con số khác là 4. Cứ theo cách này chúng ta sẽ giải đƣợc tất cả các Sudoku. Dựa vào phần mô tả về Brute-Force trên chúng ta sẽ phải tuân theo các bƣớc sau để có thể giải Sudoku.  Kỹ thuật khử bằng Brute-Force có thể đƣợc lập trình bằng cách sử dụng kỹ thuật đệ quy (Recusion), chúng cho phép ta quay lui lại, chúng ta cần “Nhớ” trạng thái của Grid trƣớc khi gán giá trị cho một ô, mục đích chính là cho phép ta Restore (phục hồi) lại trạng thái lúc trƣớc của Grid.  Chọn con số đúng và gán nó cho một ô là rất quan trọng, nhƣ trong ví dụ trên khi ta gán giá trị 1 cho (5,4) thì sẽ không có lời giải, nhƣng khi gán 4 cho (5,4) thì hoàn toàn giải đƣợc. Để giải, chúng ta luôn bắt đầu với giá trị có thể có đầu tiên cho ô đó.  Mặc dù chúng ta có thể áp dụng kỹ thuật Brute-Force để giải Sudoku nhƣng kỹ thuật này thì không đơn giản để giải Sudoku, trong thực tế chúng ta chỉ sử dụng kỹ thuật này cho một số trƣờng hợp và việc giải sudoku vẫn sẽ dựa vào các kỹ thuật phổ biến nhƣ đã trình bày ở trên. Trang 120
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Chúng ta sẽ sử dụng 3 biến sau cho thuật giải này: private bool BruteForceStop = false; private Stack PossibleStack = new Stack (); // lƣu các giá trị có thể có của các ô trong Grid. private Stack ActualStack = new Stack ();//lƣu các giá trị hiện hành trong grid. Thuật giải Bƣớc 1: Khởi tạo các giá trị hiện tại và lƣu vào Stack Khởi tạo các giá trị có thể có cho Grid và lƣu vào Stack Bƣớc 2: Thử chọn một giá trị và giải Bƣớc 2.1: Nếu giải đƣợc thì thoát BruteForceStop=true return Nếu không giải đƣợc thì thực hiện qua ô kế tiếp Thực hiện gọi đệ quy if(BruteForceStop) Return //Ket thuc thuat giai Trang 121
Tr ƣờng CĐ Nguyễn Tất Thành Các bài toán SUDOKU Kết luận: Thông qua đề tài đã tìm hiểu, chúng em phần nào đã giải quyết đƣợc vấn đề mấu chốt nhất là tìm cách giải bài toán sudoku, chúng em đã thực hiện các kỹ thuật nhƣ: CRME – kỹ thuật để tìm đƣợc các giá trị có thể có cho một ô Sudoku , kỹ thuật này là cơ sở để cho chúng ta có thể giải đƣợc các bài toán Sudoku phức tạp hơn, tiếp đến là các kỹ thuật nhƣ: Tìm con số duy nhất trong hàng, cột, minigrid, tìm kiếm cặp đôi trong hàng, cột, minigrid, tìm cặp 3 trong hàng , cột, minigrids. Tuy nhiên khóa luận chỉ dừng lại ở mức độ giải các bài toán Sudoku với kích thƣớc thông dụng nhất là 9*9 do hạn chế về thời gian thực hiện đề tài và đề tài này còn mới mẻ với chúng em. Hƣớng phát triển: Hƣớng phát triển của đề tài trong tƣơng lai là sử dụng thuật giải này để áp dụng cho các sudoku với kích thƣớc lớn hơn nhƣ : 16 *16 và 25*25 và sẽ xây dựng trò chơi trên web để có thể nhiều ngƣời chơi đƣợc cùng lúc. Danh mục tài liệu tham khảo [1] Wei .Meng Lee. Programming Sudoku 2006 [2] Bertran Felgenhauer Departerment of Computer Sciences TU Dresden Enumerating possible Sudoku Grids , June 20 , 2005 [3] [4] [5] Trang 122