Giải sudoku bằng thuật toán tô màu đồ thị java

Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. 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.

Tư tưởng

Dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.

Các bước trong việc liệt kê cấu hình dạng X[1...n]:

• Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
• Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]...tiếp tục như vậy cho tới bước:
• ...
• ....
• Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
• Thông báo cấu hình tìm được.

Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu(Depth-First Search).

Mô hình thuật toán

• Mã giả cho thuật toán quay lui.

Backtracking(k) {
  for([Mỗi phương án chọn i(thuộc tập D)]) {
    if ([Chấp nhận i]) {
      [Chọn i cho X[k]];
      if ([Thành công]) {
        [Đưa ra kết quả];
      } else {
        Backtracking(k+1);
        [Bỏ chọn i cho X[k]];
      }
    }
  }
}

Ví dụ: Trò chơi Sudoku

Sudoku là một trò chơi khá phổ biến và chắc ai cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9x9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số ô vuông con cho trước (có điền sẵn số) và còn lại là trống. Hãy điền các số từ 1-9 vào các ô con lại sao cho: hàng ngang là các số khác nhau từ 1 đến 9, hàng dọc là các số khác nhau từ 1 đến 9, và mỗi khối 3x3 chính là các số khác nhau từ 1 đến 9. Sau đây là 1 ví dụ về đề bài và lời giải:

Áp dụng quay lui để giải bài toán sudoku. Ý tưởng: Mỗi bước tìm tập các giá trị khả dĩ để điền vào ô trống, và sau đó đệ quy để điền ô tiếp theo. Giả mã của thuật toán (ở đây chú ý mảng chỉ có kích thước 9×9×9)

void solveSudoku(int S[][9], int x, int y){
    if(y == 9){
        if(x == 8){
            printSolution(S);
            exit(0);
        } else {
            solveSudoku(S, x+1,0);
        }
    } else if(S[x][y] == 0){
        for (int k = 1; k <=9; k++){
            if(checkValid(S,x,y,k)){
                S[x][y] = k;
                solveSudoku(S, x, y+1);
                S[x][y] = 0;
            }
        }
    } else {
        solveSudoku(S,x,y+1);
    }
}
boolean checkValid(int S[][9], int x, int y, int k){
    for(int i = 0; i <9 ; i++){
        if(S[x][i] == k) return false;
    }
    for(int i = 0; i <9 ; i++){
        if(S[i][y] == k) return false;
    }
    int a = x/3, b = y/3;
    for(int i = 3*a; i < 3*a+3; i++){
        for(int j = 3*b; j < 3*b+3; j++){
            if(S[i][j] == k) return false;
        }
    }
    return true;
}

Nhận xét

• -Ưu điểm: 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 trường hợp chưa hoàn chỉnh, nhờ đó giảm thời gian chạy.

Nhược điểm: Trong trường hợp xấu nhất độ phức tạp của quay lui vẫn là cấp số mũ. Vì nó mắc phải các nhược điểm sau:

• 1. NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM KHOA TIN -- PHẠM THỊ THANH HIỀN NGHIÊN CỨU PHƯƠNG PHÁP QUAY LUI VÀ ỨNG DỤNG GIẢI BÀI TOÁN SUDOKU KHÓA LUẬN TỐT NGHIỆP
• 2. ......................................................................................................1 I. LÝ DO CHỌN ĐỀ TÀI:.....................................................................1 II. MỤC TIÊU, NHIỆM VỤ: .................................................................2 III. PHƯƠNG PHÁP NGHIÊN CỨU:..................................................2 IV. BỐ CỤC CỦA ĐỀ TÀI:...................................................................2 Chương I: CƠ SỞ LÝ THUYẾT.................................3 I. CƠ SỞ LÝ THUYẾT:.........................................................................3 1. Mảng:................................................................................................3 1.1. Mô hình quan niệm:.................................................................3 1.2. Các đặc trưng cơ bản: .............................................................3 1.3. Cấu trúc lưu trữ:......................................................................3 1.4. Các phép toán cơ bản: .............................................................3 2. Hàm đệ quy:.....................................................................................4 2.1. Đệ quy là gì? .............................................................................4 2.2. Cấu trúc chính của một chương trình đệ quy:......................4 2.3. Đặc điểm: ..................................................................................5 2.4. Ví dụ:.........................................................................................5 3. Khử đệ quy: .....................................................................................6 3.1. Khái niệm:.................................................................................7 3.2. Cách thực hiện : .......................................................................7 II. NGÔN NGỮ LẬP TRÌNH:...............................................................7 1. Vài nét về Visual C#:.......................................................................7 2. Đặc điểm của ngôn ngữ C#: ...........................................................8 Chương II: PHƯƠNG PHÁP QUAY LUI .......................10 I. KHÁI NIỆM QUAY LUI: ................................................................10
• 3. của thuật toán: ..............................................................11 II. MÔ HÌNH CỦA BÀI TOÁN: .........................................................11 III. ỨNG DỤNG:...................................................................................12 1. Phương pháp : ...............................................................................12 2. Giải thuật tổng quát :....................................................................13 Chương III: BÀI TOÁN SUDOKU.................................15 I. GIỚI THIỆU BÀI TOÁN:................................................................15 1. Lịch sử ra đời: ...............................................................................15 2. Luật chơi:.......................................................................................16 3. Các biến thể:..................................................................................17 II. XÂY DỰNG CẤU TRÚC DỮ LIỆU CHO BÀI TOÁN:..............18 III. THUẬT TOÁN:..............................................................................23 1. Tổng quan:.....................................................................................23 1.1. Xác định bài toán:..................................................................23 1.1.1. Thông tin vào:..................................................................23 1.1.2. Thông tin ra:....................................................................23 1.2. Cách xác định mỗi ô số bất kỳ:.............................................23 1.2.1. Xác định các ô theo số thứ tự từ 1 đến 81:....................23 1.2.2. Xác định bằng [hàng, cột]:.............................................24 1.2.3. Xác định bằng [vùng, số thứ tự trong vùng]:...............24 2. Vấn đề đặt ra:................................................................................25 3. Giải quyết vấn đề: .........................................................................26 3.1. Vấn đề 1: .................................................................................26 3.2. Vấn đề 2: .................................................................................30 4. Giải thuật chính: ...........................................................................31 5. Các phương thức sử dụng trong chương trình:.........................32 6. Xây dựng các hàm:........................................................................33
• 4. tra cột: ..................................................................33 6.2. Hàm kiểm tra hàng:...............................................................34 6.3. Hàm kiểm tra vùng:...............................................................35 6.4. Hàm giải chương trình thủ công: .........................................36 6.5. Hàm giải chương trình bằng phương pháp quay lui:.........36 6.6. Hàm giải đến đáp án cần chọn: ............................................38 6.7. Hàm đếm số đáp án: ..............................................................38 IV. GIỚI THIỆU CHƯƠNG TRÌNH GIẢI:......................................38 1. Tổng quan:.....................................................................................38 2. Chức năng chính:..........................................................................43 3. Bảng phím tắt:...............................................................................44 V. THỬ NGHIỆM: ...............................................................................45 KẾT LUẬN................................................................................................48 TÀI LIỆU THAM KHẢO ........................................................................49
• 5. ĐẦU I. LÝ DO CHỌN ĐỀ TÀI: Ngày nay với sự phát triển không ngừng của khoa học kỹ thuật, đặc biệt trong các ngành mũi nhọn như: Điện Tử - Tin Học - Viễn Thông .v.v. Nếu chúng ta không thường xuyên cập nhật thông tin thì chúng ta không bắt kịp đà phát triển của thế giới. Đất nước ngày càng tiến bộ, khoa học kĩ thuật ngày càng phát triển đòi hỏi con người ngày nay phải có năng lực thật sự, phải có khả năng tư duy logic tốt...để tiếp cận với công nghệ hiện đại một cách nhanh chóng nhất. Vấn đề đặt ra là làm sao để phát triển khả năng tư duy của con người, đôi khi chúng không nhận ra rằng chính những trò chơi trí tuệ, trò chơi với những con số có thể giúp chúng ta rèn luyện trí não, tư duy logic. Và SuDoKu là một trò chơi trí tuệ nổi tiếng, một trò chơi không ồn ào nhưng nó vẫn âm thầm phát triển bởi nó không đơn thuần là một trò chơi mà nó giúp kích thích tư duy, suy nghĩ logic của chúng ta thông qua những con số. Ngoài những vấn đề trên, SuDoKu hấp dẫn giới trẻ bởi một lý do nữa là có thể chơi được mọi lúc mọi nơi, có thể chơi trên xe buýt, trong giờ ra chơi, thậm chí khi đi dã ngoại, du lịch... 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, trẻ em cũng có cơ hội giải được SuDoKu thành công như người lớn. Trong khi đó thuật toán quay lui là một thuật toán điển hình để giải lớp bài toán liệt kê hay bài toán tối ưu như: bài toán người giao hàng, bài toán con mã đi tuần, bài toán 8 hậu, bài toán tìm đường đi trong mê cung...Bằng việc liệt kê các tình huống, thử các khả năng có thể cho đến khi tìm thấy một lời giải đúng, thuật toán quay lui chia nhỏ bài toán, lời giải của bài toán lớn sẽ là kết quả của việc tìm kiếm theo chiều sâu của tập hợp các bài toán phần tử.
• 6. thấy tư tưởng của thuật toán rất phù hợp với cách giải của trò chơi, nên đề tài ”Nghiên cứu phương pháp quay lui và ứng dụng giải bài toán SuDoku” được thực hiện nhằm tìm hiểu về thuật toán quay lui và ứng dụng của nó. II. MỤC TIÊU, NHIỆM VỤ: Đề tài này được thực hiện nhằm đạt được mục tiêu là hiểu rõ, hiểu sâu sắc hơn về thuật toán quay lui. Xây dựng thành công chương trình giải SuDoKu với nhiều đáp án và với một thời gian nhanh nhất. III. PHƯƠNG PHÁP NGHIÊN CỨU: - Tìm hiểu thông tin trên mạng internet, sách, báo, tạp chí… - Thu thập ý kiến chuyên gia (giáo viên hướng dẫn, các giáo viên trong và ngoài khoa, ý kiến của bạn bè,…). - Kết hợp nghiên cứu lý thuyết với thực hành, rèn luyện kỹ năng phân tích chương trình và kỹ năng lập trình. IV. BỐ CỤC CỦA ĐỀ TÀI: Nội dung của đề tài được trình bày như sau: MỞ ĐẦU. Chương I: CƠ SỞ LÝ THUYẾT Chương II: PHƯƠNG PHÁP QUAY LUI. Chương III: BÀI TOÁN SUDOKU. KẾT LUẬN. TÀI LIỆU THAM KHẢO.
• 7. I: CƠ SỞ LÝ THUYẾT I. CƠ SỞ LÝ THUYẾT: 1. Mảng: 1.1. Mô hình quan niệm: Mảng là một dãy có thứ tự (về mặt vị trí) các phần tử với hai đặc điểm sau : + Số lượng phần tử cố định. + Mọi phần tử đều có cùng kiểu dữ liệu (dữ liệu cơ sở của mảng). 1.2. Các đặc trưng cơ bản: - Cho phép truy cập ngẫu nhiên đến từng phần tử. Thời gian truy cập đến mọi phần tử đều bằng nhau. - Số lượng phần tử của mảng là cố định. 1.3. Cấu trúc lưu trữ: - Cấu trúc lưu trữ đơn giản nhất là dùng địa chỉ được tính để thực hiện lưu trữ và tìm kiếm các phần tử, là mảng một chiều hay vectơ. - Các phần tử được bố trí sát nhau trong bộ nhớ và theo thứ tự tăng dần của các chỉ số nên dễ dàng tìm được địa chỉ của một phần tử bất kỳ nếu biết chỉ số. 1.4. Các phép toán cơ bản: - Thường chỉ có các phép tạo lập (create) mảng, tìm kiếm (retrieve) một phần tử của mảng, cập nhật (update) một phần tử của mảng …Ngoài giá trị, một phần tử của mảng còn được đặc trưng bởi chỉ số (index) thể hiện thứ tự của phần tử đó trong mảng. Vectơ là mảng một chiều, mỗi phần tử ai của nó ứng với một chỉ số i. Ma trận là mảng hai chiều, mỗi phần tử aij ứng với hai chỉ số i và j. Tương tự người ta cũng mở rộng ra mảng hai chiều , mảng ba chiều, …, mảng n chiều. a1 a2 ….. ai ….. an
• 8. Hàm đệ quy: 2.1. Đệ quy là gì? Ta nói: - Một đối tượng là đệ quy nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó. - Một thủ tục được gọi là đệ quy nếu trong quá trình thực hiện nó phải gọi đến chính nó nhưng với kích thước nhỏ hơn của tham số. - Trong thân của một hàm, nếu nó gọi tới chính hàm đó để xử lý bài toán thì gọi là hàm đệ quy. Ví dụ: 1) Định nghĩa số tự nhiên: - là một số tự nhiên. - n là số tự nhiên nếu n-1 là số tự nhiên. 2) Định nghĩa hàm giai thừa: - 0! = 1 - Nếu n > 0 thì n! = n(n-1)! 2.2. Cấu trúc chính của một chương trình đệ quy: Một chương trình đệ quy về căn bản gồm 2 phần: - Phần cơ sở : Trong đó, chứa các tác động của hàm hoặc thủ tục với một số giá trị cụ thể ban đầu của tham số (hay gọi trường hợp dừng). Ví dụ : if n=1 then gt:=1; - Phần đệ quy: Trong đó, tác động cần được thực hiện cho giá trị hiện thời của các tham số được định nghĩa bằng các tác động đã được định nghĩa trước đấy với kích thước nhỏ hơn của tham số. Ví dụ: if n>1 then gt:=n*gt(n-1);
• 9. Đặc điểm: - Mỗi một lần hàm tự gọi đệ quy đến nó thì máy tính sẽ tự tạo ra một biến cục bộ mới. - Có bao nhiêu lần hàm gọi đệ quy thì sẽ có bấy nhiêu lần thoát ra khỏi hàm (kiểu như lặp hàm). - Khi thoát ra ngoài hàm đệ quy thì một loạt các biến cục bộ tạo ra do dùng đệ quy lúc này mới được giải phóng, và chúng sẽ giải phóng trước các biến cục bộ (sinh ra do đệ quy) tạo ra sau. - Sử dụng đệ quy là một phương pháp làm cho chương trình ngắn gọn, dễ hiểu nhưng nó sẽ làm tốn bộ nhớ và thời gian. 2.4. Ví dụ: Hàm tính giai thừa của n (tính n!): Function giaithua(n:word):integer; begin if n=0 then giaithua:=1 else giaithua:=giaithua(n-1)*n; end; Ví dụ: Tính n! =3 Ta có giá trị truyền vào hàm gt qua biến n. Trong ví dụ này, qui trình thực hiện như sau: - Khi có lệnh gọi hàm, chẳng hạn: n := gt(3); - Thì máy sẽ ghi nhớ là: gt(3) := 3 * gt(2); và đi tính gt(2) - Kế tiếp máy lại ghi nhớ: gt(2) := 2 * gt(1); và đi tính gt(1) - Theo định nghĩa của hàm thì:
• 10. := 1; - Máy sẽ quay ngược lại: gt(2) := 2 * 1; cho kết quả là 2 - Tiếp tục: - gt(3) := 3 * 2; cho kết quả là 6 - Như vậy kết quả cuối cùng trả về là 6. Ta có: 3! = 6. Nhận xét  Ưu điểm: - Điểm mạnh lớn nhất: chương trình, code trở nên ngắn gọn, dễ hiểu, thuận lợi cho việc chỉnh sửa. - Dễ chuyển thành chương trình trên các ngôn ngữ lập trình.  Nhược điểm: - Nhược điểm lớn nhất là tốn bộ nhớ. - Mất nhiều thời gian xử lý, làm giảm tốc độ chạy chương trình. - Không áp dụng cho mọi ngôn ngữ lập trình. Đệ quy không những là một phương pháp lập trình quan trọng mà còn là một phương pháp suy nghĩ để giải quyết vấn đề một cách tổng quát dựa trên ý tưởng: + Đơn giản hoá công việc + Phân vùng để xử lý. 3. Khử đệ quy: Đệ quy là quả tim trong các nghiên cứu lý thuyết cũng như thực hành tính toán, đã thể hiện rất nhiều sức mạnh và có ưu điểm trong nhiều bài toán. Nhưng có đôi khi, sự hạn hẹp của bộ nhớ dành cho chương trình con không cho phép chúng ta làm điều đó.Vì vậy vấn đề khử đệ quy lại cần được quan tâm, xem xét.
• 11. Khái niệm: Là quá trình chuyển đổi một giải thuật đệ quy thành một giải thuật không đệ quy bằng cách chúng ta sử dụng vòng lặp hoặc bộ nhớ Stack tự tạo. 3.2. Cách thực hiện : - Sử dụng vòng lặp: Với ý tưởng là chúng ta lưu lại các giá trị của lần tính toán trước làm dữ liệu cho việc tính toán của lần sau. Ví dụ: Khử đệ quy trong bài toán giai thừa bằng cách sử dụng vòng lặp int giaithua (int n) { int k=1; For (i=2; i<=n;i++) k=k*i; return(k); } - Sử dụng bộ nhớ Stack: Đặt tất cả các giá trị của các biến cục bộ và địa chỉ của chỉ thị kế tiếp vào ngăn xếp (Stack), quy định các giá trị tham số cho thủ tục và chuyển tới vị trí bắt đầu thủ tục, thực hiện lần lượt từng câu lệnh. Sau khi thủ tục hoàn tất thì nó phải lấy ra khỏi ngăn xếp địa chỉ trả về và các giá trị của các biến cục bộ, khôi phục các biến và chuyển tới địa chỉ trả về. II. NGÔN NGỮ LẬP TRÌNH: 1. Vài nét về Visual C#: C# là một ngôn ngữ lập trình hướng đối tượng được phát triển bởi Microsoft, là phần đầu cho kế hoạch .NET của họ. Microsoft phát triển C# dựa trên C++ và Java. C# được thiết kể bởi Anders Hejlsberg kiến trúc sư phần mềm nổi tiếng với các sản phẩm Turbo Pascal. Và ông là người đứng đầu nhóm thiết kế Borland Delphi, một trong những thành công đầu tiên của việc xây dựng môi trường phát triển tích hợp (IDE) cho lập trình Client/Server.
• 12. cũng là ngôn ngữ lập trình điều khiển sự kiện, các chương trình được tạo ra sẽ sử dụng IDE (Integrated Developmen Environment). Với IDE, người lập trình có thể tạo, chạy, kiểm tra và debug các chương trình C#. Bên cạnh đó, nền .NET cho phép các thành phần của một phần mềm được viết từ các ngôn ngữ lập trình khác nhau có thể tương tác được với nhau, thậm chí người phát triển ứng dụng có thể đóng gói các phần mềm cũ để nó hoạt động với chương trình C# mới. Giống như các ngôn ngữ lập trình khác, C# cũng hỗ trợ các kiểu dữ liệu cơ bản như integer, float, boolean, string, array... và các câu lệnh điều khiển (if, while, for, switch, do…while…). Tuy nhiên, như đã trình bày ở trên, C# cũng có những đặc điểm riêng của nó. 2. Đặc điểm của ngôn ngữ C#: C#, theo một hướng nào đó, là ngôn ngữ lập trình phản ánh trực tiếp nhất đến .NET Framework mà tất cả các chương trình .NET chạy và nó phụ thuộc mạnh mẽ vào Framework này. - Không có khái niệm biến toàn cục (global variables) và hàm (functions). Tất cả các hàm, phương thức trong một chương trình viết bằng ngôn ngữ C# đều được khai báo dưới dạng một lớp. Mọi kiểu biến, kể cả các kiểu giá trị đơn giản đều được xem như các đối tượng. Tuy nhiên, ta có thể dùng thuộc tính static đối với các hàm và biến trong một lớp được khai báo public thay vì sử dụng biến toàn cục và hàm. - C# yêu cầu rất chặt chẽ đối với kiểu Boolean (bool), các câu lệnh có điều kiện như while và if đều đòi hỏi biểu thức điều kiện phải có kiểu bool. Nếu trong C++ ta có phát biểu if(a) statement, biểu thức trong điều kiện if có thể được chuyển thành giá trị kiểu bool, cho dù a có thể được khai báo kiểu int hay pointer, C# thì khác, nó không có khái niệm “a nguyên là đúng hay sai”. Điều này buộc người lập trình phải sử dụng những biểu thức có kiểu trả về chính xác là bool. Đặc tính này rất hữu ích trong việc giảm những lổi lập trình hay mắc phải.
• 13. C++ cho phép đa thừa kế (multiple interitances) và nếu được sử dụng đúng cách, đây thực sự là điểm rất mạnh. Tuy nhiên, đa thừa kế rất khó quản lý và như vậy cũng rất khó áp dụng. Đây là một trong những lý do C# chỉ phát triển thừa kế đơn (single inheritance). - Namespaces trong C#: Khái niệm Namespaces được hiểu một cách đơn giản là tập các lớp có mối liên hệ lẫn nhau. Ví dụ như ta gom các lớp có liên quan đến hoạt động của cơ sở dữ liệu lại và đặt cho chúng một không gian tên (namespace) chung gọi là DataActivity. Vì C# không cho phép có hai lớp cùng tên trong cùng một chương trình, việc dùng namespace sẽ giúp ta tránh được những đụng độ trong vấn đề đặt tên. Sẽ hoàn toàn có thể xảy ra sự đụng độ trên nếu chúng ta có nhiều lớp được khai báo trong cùng một chương trình, chẳng hạn lớp Connection trong DataActivity sẽ xung đột với lớp Connection trong InternetActivity. Để tránh sự đụng độ này, C# quy định tên lớp phải bao gồm namespace của lớp đó. Vì thế tên thích hợp của 2 lớp Connection trong trường hợp trên là DataActivity. Connection và InternetActivity.Connection. Điểm nổi bật của C# Namespace là không ánh xạ một cách vật lý như đối với Java. Các lớp với cùng một namespace có thể ở nhiều thư mục khác nhau. Và namespace có thể bao gồm các lớp, các sự kiện, các exception và thậm chí là các namespace khác.
• 14. II: PHƯƠNG PHÁP QUAY LUI I. KHÁI NIỆM QUAY LUI: Kĩ thuật quay lui (backtracking) như tên gọi của nó, là một quá trình phân tích đi xuống và quay lui trở lại theo con đường đã đi qua. Bằng việc liệt kê các tình huống, thử các khả năng có thể có cho đến khi tìm thấy một lời giải đúng, thuật toán quay lui chia nhỏ bài toán, lời giải của bài toán lớn sẽ là kết quả của việc tìm kiếm theo chiều sâu của các bài toán phần tử. Trong suốt quá trình tìm kiếm nếu gặp phải một hướng nào đó mà biết chắc không thể tìm thấy đáp án thì quay lại bước trước đó và tìm hướng khác kế tiếp hướng vừa tìm đó. Trong trường hợp không còn một hướng nào khác nữa thì thuật toán kết thúc. Thuật toán quay lui có thể được thể hiện theo sơ đồ cây tìm kiếm theo chiều sâu như hình dưới: Khả năng x1 Khả năng x 2 với x1 đã chọn Khả năng x3 với x1 và x 2 đã chọn Khả năng x 4 với x1 , x 2 và x3 đã chọn Gốc X1 X2 X4 Một đáp án X3
• 15. hình vẽ, dẽ dàng nhận thấy: - Ở một bài toán hiện tại (mỗi nốt), ta đi tìm lời giải cho bài toán đó. Ứng với lời giải, ta đi giải bài toán kế tiếp cho đến khi bài toán gốc trở nên đầy đủ. - Lời giải của bài toán gốc thường là một lối đi từ gốc đến nốt cuối cùng (không có nốt con). * Tư tưởng của thuật toán: - Nét đặc trưng của kĩ thuật quay lui là các bước hướng tới lời giải cuối cùng của bài toán hoàn toàn được làm thử. - Tại mỗi bước, nếu có một lựa chọn được chấp nhận thì ghi nhận lại lựa chọn này và tiến hành các bước thử tiếp theo. Còn ngược lại không có lựa chọn nào thích hợp thì làm lại bước trước, xóa bỏ sự ghi nhận và quay về chu trình thử các lựa chọn còn lại. - Điểm quan trọng của thuật toán là phải ghi nhớ tại mỗi bước đi qua để tránh trùng lặp khi quay lui. Các thông tin này cần được lưu trữ vào một ngăn xếp-Stack (vào sau ra trước), nên thuật toán thể hiện ý thiết kế một cách đệ quy. - Thuật toán quay lui thường được cài đặt theo lối đệ quy, mỗi lần gọi hàm đệ quy, hàm đệ quy được truyền một tham số (trong các tham số) là chỉ số của bài toán con, trong hàm sẽ cố gắng tìm lời giải cho bài toán con đó, nếu tìm thấy thì gọi hàm đệ quy để giải bài toán con tiếp theo hoặc là đưa ra đáp án bài toán lớn nếu đã đầy đủ lời giải, nếu không tìm thấy thì chương trình sẽ trở về điểm gọi hàm đó. Mục đích của việc sử dụng hàm đệ quy là để thuật toán được rỏ ràng, dễ viết, dễ hiểu hơn và cũng để bảo toàn các biến, các trạng thái lúc giải bài toán con. II. MÔ HÌNH CỦA BÀI TOÁN: Lời giải của bài toán thường biểu diễn bằng một véc tơ gồm n thành phần phải thỏa mãn các điều kiện nào đó. Để chỉ ra lời giải x, ta phải xây dựng dần các thành phần lời giải x=(x1,x2,....xn)
• 16. mỗi bước i: - Đã xây dựng xong các thành phần x=(x1,x2,....xn) - Xây dựng thành phần xi bằng cách lần lượt thử tất cả các khả năng mà xi có thể chọn: + Nếu một khả năng j nào đó phù hợp cho xi thì xác định xi theo khả năng j. Thường phải có thêm thao tác ghi nhận trạng thái mới của bài toán để hỗ trợ cho bước quay lui. Nếu i = n thì ta có được một lời giải, ngược lại thì tiến hành bước i+1 để xác định xi+1 . + Nếu không có một khả năng nào chấp nhận được cho xi thì ta lùi lại bước trước (bước i-1) để xác định lại thành phần xi-1 III. ỨNG DỤNG: Sử dụng thuật toán quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng. 1. Phương pháp : Giả thiết cấu hình cần liệt kê có dạng (x1 x2 ... xn). Khi đó thuật toán quay lui được thực hiện qua các bước sau : Bước 1: Xét tất cả các giá trị x1 có thể nhận, thử cho x1 nhận lần lượt các giá trị đó. Với mỗi giá trị thử cho x1 ta sẽ làm tiếp Bước 2. Bước 2: Xét tất cả các giá trị x2 có thể nhận, lại thử cho x2 nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x2 lại xét tiếp các khả năng chọn x3 ... cứ tiếp tục như vậy đến bước n. Bước n: Xét tất cả các giá trị xn có thể nhận, thử cho xn nhận lần lượt các giá trị đó, thông báo cấu hình tìm được (x1 x2 ... xn).
• 17. Giải thuật tổng quát : Thuật toán quay lui có thể được mô tả bằng đoạn mã sau (thủ tục này thử cho xi nhận lần lượt các giá trị mà nó có thể nhận) : void Try (int i) { for { if else { Try(i+1); // gọi đệ quy chọn tiếp x[i+1] } } } (Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1)) + Đầu tiên, Try(int i) là hàm đệ quy quay lui trong đó i là biến chạy từ 1 n tương ứng với số thứ tự của x1, x2, x3, ….., xn theo phương pháp đệ quy + Tiếp theo vòng lặp for cho các giá trị của từng phần tử x1, x2, x3,….. Tất nhiên, đối với mỗi bài toán riêng thì những giá trị này là khác nhau.
• 18. Trạng thái cuối tức là điểm dừng của thuật toán này. Thực chất thuật toán quay lui cũng là đệ quy nên việc xác định điểm dừng cực kỳ quan trọng và luôn luôn phải có. + Tiếp theo là phần xuất ra, vì như đã thấy, khi if (phần tử cuối cùng trong cấu hình) thì đã xuất ra màn hình và không chạy bất kỳ hàm đệ quy nào nữa. Tuy nhiên, khi xuất ra nó lại xuất tới nhiều dãy số (tùy từng bài tập). Lý do, nếu để ý thì chúng ta sẽ thấy phía trên có 1 vòng for, nó sẽ hoạt động giống như kiểu nhiều vòng lặp for lồng nhau. for(i =1; i<=n; i++) for(j=1; i
• 19. III: BÀI TOÁN SUDOKU I. GIỚI THIỆU BÀI TOÁN: 1. Lịch sử ra đời: Trò chơi này được kiến trúc sư Howard Garns ở New York thiết kế và được giới thiệu lần đầu tiên vào năm 1979 trên tạp chí Dell (Mỹ) với tên gọi là "Number Place". Tháng 4/1984, Number Place lần đầu tiên được giới thiệu tại Nhật trên báo Monthly Nikolist với tên gọi "Suuji wa dokusinh ni kagiru", dịch sang tiếng Anh có nghĩa là "những con số phải độc nhất" hoặc "những con số tìm thấy chỉ một lần" và được "rút gọn" thành SuDoKu (su = number, doku = single). Nhưng trò chơi này chỉ trở nên phổ biến khi người Anh nhập cuộc. Báo Times số ngày 12/11/2004 đã giới thiệu nó với tên gọi “SuDoKu” dựa trên kết quả phát triển chương trình trò chơi trên máy vi tính của một quan tòa về hưu người New Zealand sống ở Hongkong tên là Wayne Gould. Sau đó, SuDoKu lần lượt xuất hiện trên hầu hết các tờ báo hàng đầu của Anh và được "đưa" đến Australia nhờ tập đoàn báo chí Telegarph. Từ ngày 2/8/2005, chương trình Radio Times của đài BBC (Anh) có một chuyên đề hằng tuần về SuDoKu mang tên Super SuDoKu. SuDoKu đã xuất hiện trên tivi lần đầu tiên vào ngày 1/7/2005 trong chương trình SuDoKu Live trên kênh Sky One. Đây là một cuộc thi gồm 9 đội (mỗi đội 8 người cùng với một nhân vật nổi tiếng) tranh tài với nhau, tạo nên bảng SuDoKu lớn nhất thế giới (rộng 84 m với 1905 giải pháp đúng), câu đố được khắc trên một sườn đồi ở Chipping Sodbury nước Anh. Hiện nay, SuDoKu đã có mặt trên các báo, tạp chí hàng đầu và trở thành trò chơi gây sốt tại hơn 40 quốc gia và vùng lãnh thổ trên thế giới, trong đó có Việt Nam. SuDoKu xuất hiện tại Việt Nam sớm nhất là trên tạp chí Khám Phá (Trực thuộc Sở Khoa học và Công nghệ Thành phố Hồ Chí Minh), sau đó đến Thanh Niên, Hoa Học Trò, được xem như là một hình thức giải trí đầy trí tuệ của giới trẻ. Đặc biệt,
• 20. Vua trò chơi trên báo Hoa Học Trò với "món chủ lực" là SuDoKu thu hút rất đông học sinh tham gia (theo kết quả công bố của báo). 2. Luật chơi: Quy luật của trò chơi tương đối đơn giãn.Cho một bàn hình vuông được chia thành một lưới 81 ô nhỏ gồm 9 hàng và 9 cột, 81 ô nhỏ đó lại được chia thành 9 vùng, mỗi vùng có 9 ô. Đề bài SuDoKu là một bàn hình vuông như thế, trên đó tại một số ô người ta đã điền sẵn một số giá trị. Cách chơi như sau:  Phải điền các số từ 1 đến 9 vào mỗi hàng dọc, ngang không được trùng lặp.  Ở mỗi hàng dọc, mỗi hàng ngang và mỗi ô vuông 3*3 được phân cách rõ ràng ( bằng gạch đen đậm) luôn phải đảm bảo có đủ các số từ 1 đến 9.  Ở mỗi hàng dọc, mỗi hàng ngang và mỗi ô vuông 3*3 được phân cách rõ ràng (bằng gạch đen đậm) các số chỉ được sử dụng một lần và không lặp lại. Ví dụ: Cho đề bài như sau, yêu cầu dùng các số từ 1 dến 9 để điền vào các ô còn lại.
• 21. án sẽ là: 3. Các biến thể: Ngoài khuôn dạng chuẩn có kích thước 9x9 ô, chia làm 3x3 vùng, SuDoKu còn có rất nhiều biến thể khác. Một số biến thể phổ biến như: - Kích thước 4x4 ô chia làm 2x2 vùng - Kích thước 6x6 ô chia làm 2x3 vùng - Kích thước 5x5 ô chia vùng theo pentomino (được phát hành với tên goi Logi-5) - Kích thước 7x7 ô chia vùng theo heptomino - Kích thước 8x8 ô chia vùng theo qui tắc (4x2):(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 ô. Tuy theo cách bố trí các ô khác màu này, sẽ phát sinh thêm một biến thể con 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ế (Game Sudoku do người Việt Phạm Văn Hải phát triển: Sudoku Plus 8x8)
• 22. thể với kích thước lớn hơn cũng khá phổ biến: - Kích thước 16x16 ô (Monster SuDoKu) - Kích thước 12x12 ô chia làm 4x3 vùng (Dodeka SuDoKu) - Kích thước 25x25 ô (Giant SuDoKu) Biến thể với kích thước lớn nhất được phổ biến là 100x100 ô. II. XÂY DỰNG CẤU TRÚC DỮ LIỆU CHO BÀI TOÁN: 1. Một ô số SuDoKu bao gồm 9 miền con (hay còn gọi là 9 vùng), đặt theo thứ tự là 1, 2, 3, 4, 5, 6, 7, 8, 9. Chia thành 9 hàng và 9 cột như hình sau: 2. Dữ liệu sử dụng trong chương trình là dữ liệu kiểu mảng: - int [,] row = new int[10, 10]; là mảng 2 chiều dùng để đánh dấu hàng có thể điền một số nào đó hay không. Cột Hàng
• 23. đó giá trị row[i,j] nhận 2 giá trị quy ước là 0 và 1.  row[i,j]=0 tức là hàng i không thể điền thêm giá trị j vào bất cứ ô nào nữa vì giá trị j đã tồn tại trong hàng i. Ví dụ: Giả sử đề bài có hàng thứ 2 được cho như sau: Khi đó row[2,2]=0, row[2,8]=0  row[i,j]=1 tức là hàng i có thể điền thêm giá trị j vào bất cứ ô nào chưa được điền của hàng i. Ví dụ: Với ví dụ trên thì row[2,9]=1 - int [,] column=new int[10,10]; là mảng 2 chiều dùng để đánh dấu cột có thể điền một số nào đó hay không. Trong đó column[i,j] nhận 2 giá trị là 0 và 1  column[i,j]=0 cột i không thể điền giá trị j vào.  column[i,j]=1 cột i có thể điền giá trị j vào. Ví dụ: Đề bài có cột thứ 2 được cho như sau: Khi đó column[2,2]=0 column[2,9]=1 Chỉ những giá trị chưa được điền trong cột mới có thể được điền vào. Những giá trị đó sẽ có giá trị trả về là 1.
• 24. int [,] area=new int[10,10]; tương tự như đối với mảng row[i,j] và column[i,j] mảng area[i,j] cũng là mảng 2 chiều dùng để đánh dấu vùng có thể đánh một số nào đó vào hay không area[i,j] cũng nhận 2 giá trị là 0 và 1. Nếu area[i,j]=0 thì vùng i không thể điền giá trị j vào. Ngược lại nếu area[i,j]=1 thì vùng i có thể điền giá trị j vào. Ví dụ: Giả sử đề bài cho vùng thứ 2 có các giá trị sau: - int [,] AREA=new int[10,10]; là mảng cố định, dùng để thiết lập giá trị mặc định của chỉ số vùng. Trong đó AREA[i,j] nhận các giá trị từ 1 đến 9. i: chỉ số hàng j: chỉ số cột Giá trị trả về của AREA là chỉ số vùng. Khi đó area[2,7]=0 area[2,1]=0 Tức là vùng 2 chỉ được điền các giá trị chưa có trong vùng đó và giá trị 1 là có thể điền được
• 25. dụ: AREA[4,5] sẽ trả về giá trị là 5. Tức là hàng 4 cột 5 là thuộc vùng 5. - int[, ,] agree = new int[10, 10, 11]; là mảng 3 chiều dùng để đánh dấu trên từng ô trống một có bao nhiêu giá trị có thể điền được và đó là những giá trị nào. Trong đó, giá trị agree[i,j,k] nhận các giá trị từ 1 đến 9. i, j: Ô hàng i, cột j nhận giá trị từ 1 đến 9. k: Nhận giá trị từ 0 đến 9.  Với k=0 và giá trị trả về của agree[i,j,0] là h: nghĩa là ô hàng i cột j có h khả năng điền.  Với k:19 thì các giá trị agree[i,j,1], agree[i,j,2], agree[i,j,3]… agree[i,j,k] là các khả năng điền đó. Tải bản FULL (file word 53 trang): bit.ly/3amkhf9 Dự phòng: fb.com/TaiHo123doc.net
• 26. dụ: Giả sử đề bài cho vùng thứ 1 có các giá trị sau: - int[,] value = new int[10,10]; là mảng 2 chiều dùng để chỉ giá trị đang được điền hiện tại tại một ô bất kì. Value=[i,j] nhận các giá trị từ 1 đến 9. Ví dụ: Với ví dụ trên, nếu value[1,1]=2 thì ô hàng1 cột 1 đang được đánh số thứ 2 trong 5 khả năng được điền, tức là ô hàng 1 cột 1 đang được điền số 2 Với các cách đánh dấu này ta dễ dàng duyệt các khả năng điền số của một ô, cho phép loại bỏ khả năng bất kỳ khi biết khả năng đó là không thuận lợi. Value[1,1]=5 Giả sử ô hàng 1 cột 1 nhận 7 giá trị là: 1, 2, 3, 4, 6, 8, 9 Khi đó agree[1,1,0]=7 và các giá trị đó là: agree[1,1,1]=1 agree[1,1,2]=2 agree[1,1,3]=3 agree[1,1,4]=4 agree[1,1,5]=6 agree[1,1,4]=8 agree[1,1,5]=9 Tức là vùng 1 chỉ được điền các giá trị chưa có trong vùng đó và giá trị trả về là 1 nghĩa là có thể điền được Tải bản FULL (file word 53 trang): bit.ly/3amkhf9 Dự phòng: fb.com/TaiHo123doc.net
• 27. THUẬT TOÁN: 1. Tổng quan: 1.1. Xác định bài toán: 1.1.1. Thông tin vào: Đề SuDoKu, là một bảng số cho bởi file hoặc có thể nhập trực tiếp trên giao diện người dùng. 1.1.2. Thông tin ra: Là lời giải SuDoKu - Nếu đề bài có nhiều đáp án thì phải xuất được nhiều đáp án. - Nếu không có lời giải thì phải thông báo SuDoKu không có đáp án. 1.2. Cách xác định mỗi ô số bất kỳ: 1.2.1. Xác định các ô theo số thứ tự từ 1 đến 81: Cách này ta sử dụng chủ yếu để tạo ra đề bài hoặc xuất kết quả ra giao diện người dùng. Ta có bảng sau: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 5586978