Tài liệu Khóa luận tốt nghiệp các bài toán về 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