User Tag List

+ Trả lời chủ đề
Hiện kết quả từ 1 tới 6 của 6

Chủ đề: Thuật toán quay lui giải Sudoku

  1. #1
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Thuật toán quay lui giải Sudoku

    Mấy hôm nay mình đang code 1 chương trình giải Sudoku bằng thuật toán quay lui trên C, đây là code của mình:

    PHP Code:
    /* Filename: sudoku.c
     * Author: heroandtn3
     * Date: 7/2012
     * Description: Chuong trinh giai sudoku
     */
    #include <stdio.h>
    #define SIZE 9 //kich thuoc o sudoku la SIZE x SIZE
    #define DELTA 2
    int a[SIZE+DELTA][SIZE+DELTA];
    int n SIZE;
    int lastK;

    int Nhap(); //nhap de bai sudoku
    int Xuat(); //xuat bang sudoku
    int Try(int k);
    int isOK(int iint jint x); //kiem tra xem vi tri i, j dat gia tri x co hop le khong
    int findLastK(); //tra ve chi so k cuoi cung ma khong phai la de bai

    int main()
    {
        
    printf("Nhap so lieu de bai...\n");
        
    Nhap();
        
    lastK findLastK();
        
    printf("De bai:\n");
        
    Xuat();
        
    printf("Bam enter de bat dau giai...");
        
    getchar();
        Try(
    0);
        
    getchar();
        return 
    0;
    }

    int Nhap()
    {
        
    int ijtmp;
        
    FILE *fp NULL;
        
    fp fopen("input""r");
        for (
    i=0i<ni++)
        {
            
    //printf("Nhap %d so hang thu %d, o nao trong thi nhap 0:\n", n, i+1);
            
    for (j=0j<nj++)
            {
                
    //scanf("%d", &tmp);
                
    fscanf(fp"%d", &tmp);
                
    a[i][j] = tmp;
            }
        }
        
    fclose(fp);
        return 
    0;
    }

    int Xuat()
    {
        
    int ij;
        for (
    i=0i<ni++)
        {
            for (
    j=0j<nj++)
                
    printf(" %d"a[i][j]);
            
    printf("\n");
        }
        return 
    0;
    }

    int Try(int k)
    {
        
    int ijx;
        while (
    a[k/n][k%n]!=0//bo qua cac o de bai
            
    k++;
        
    k/nk%n;
        for (
    x=1x<=nx++)
            if (
    isOK(ijx)) 
            {
                
    a[i][j] = x;
                if (
    k==lastK)
                    
    Xuat();
                else
                    Try(
    k+1);
                
    a[i][j] = 0;
            }
        return 
    0;
    }

    int isOK(int iint jint x)
    {
        
    int kt;
        
    int tmpXtmpY;
        
    //kiem tra hang thu i da co cai nao trung chua
        
    for (k=0k<nk++)
            if (
    a[i][k] == x)
                return 
    0;
        
    //kiem tra cot thu j da co cai nao trung chua
        
    for (k=0k<nk++)
            if (
    a[k][j] == x)
                return 
    0;

        
    //kiem tra trong o 3x3
        
    tmpX i%3tmpY j%3;
        for (
    k=i-tmpXk<=i-tmpX+2k++)
            for (
    t=j-tmpYt<=j-tmpY+2t++)
                if (
    a[k][t] == x)
                    return 
    0;
        return 
    1;
    }

    int findLastK()
    {
        
    int ij;
        for (
    i=n-1i>=0;i--)
            for (
    j=n-1j>=0j--)
                if (
    a[i][j]==0)
                {
                    return (
    i*j);
                }

    Đề bài lưu trữ trong file input đặt ngang hàng với file thực thi sau khi biên dịch mã nguồn, ví dụ đây là một đề bài:

    Mã:
    3 0 0 0 0 0 5 0 0
    0 0 0 8 0 6 0 0 0
    0 2 5 0 0 0 6 0 1
    7 0 9 0 3 8 0 0 4
    0 0 0 0 0 0 0 0 0
    1 0 0 9 4 0 3 0 6
    8 0 3 0 0 0 7 6 0
    0 0 0 3 0 4 0 0 0
    0 0 1 0 0 0 0 0 9
    Mời mọi người test và góp ý thêm.
    Contact me:
    Email: sangnd [at] svBK.vn
    Personal website: My Blog | Chat với người lạ
    Facebook Page của Bách Khoa Forum: http://www.facebook.com/svbk.vn

  2. Có 2 thành viên cảm ơn bài viết của 1973 có chất lượng:


  3. #2
    HUT's Student
    Tham gia ngày
    Feb 2012
    Bài gửi
    272

    Mặc định Re: Thuật toán quay lui giải Sudoku

    Với sodoku thì cách giải tốt nhất hiện nay là sử dụng kỹ thuật dancing link kết hợp với thuật toán quay lui.
    Như trong bài trên, cứ mỗi lần thử một ô số thì ta phải kiểm tra xem có hợp lệ hay không (hàm isOk(), mất O(n^2) thời gian), và còn một số vấn đề nữa.
    Với kỹ thuật dancing link, mỗi lần xác định được một kết quả thì nó cũng loại được các trường hợp không khả dĩ khỏi danh sách các lựa chọn cho lần thử tiếp theo, nhờ đó hiệu năng tăng lên.

    Giải thích và code mẫu: http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/

    Còn đây là code của mình đã tối ưu một chút, nhanh hơn khoảng 2-3 lần so với code trên:

    PHP Code:
    // =====================================================================================
    // 
    //       Filename:  sodoku_dlx.cc
    // 
    //    Description:  
    // 
    //        Version:  1.0
    //        Created:  07/04/2012 04:28:34 PM
    //       Revision:  none
    //       Compiler:  g++
    // 
    //         Author:  YOUR NAME (), boss14420@gmail.com
    //        Company:  
    // 
    // =====================================================================================

    #include <iostream>
    #include <fstream>
    #include <cstdlib>
    #include <ctime>

    #define SIZE 9
    #define SQ_SZ (SIZE*SIZE)
    #define SQRT_SZ 3

    #define COLS (SIZE*SIZE*4)
    #define ROWS (SIZE*SIZE*SIZE)

    #define SQ_OFFSET 0
    #define RW_OFFSET (SIZE*SIZE)
    #define CL_OFFSET (2*RW_OFFSET)
    #define BX_OFFSET (3*RW_OFFSET)


    struct node {
        
    node *left, *right, *up, *down;
        
    nodehead;
        
    int idx;
    };

    node Column[COLS];
    node *Row[ROWS];
    node ObjectPool[SIZE*COLS];
    node RootNode;
    int Result[SQ_SZ];
    int nResult 0;

    // Functions that extract data from a given 3-digit integer index number in the format [N] [R] [C].
    inline int retNb(int N) { return N/SQ_SZ; }
    inline int retRw(int N) { return (N/SIZE)%SIZE; }
    inline int retCl(int N) { return N%SIZE; }
    inline int retBx(int N) { return ((retRw(N)/SQRT_SZ)*SQRT_SZ) + (retCl(N)/SQRT_SZ); }
    inline int retSq(int N) { return retRw(N)*SIZE retCl(N); }
    inline int retRn(int N) { return retNb(N)*SIZE retRw(N); }
    inline int retCn(int N) { return retNb(N)*SIZE retCl(N); }
    inline int retBn(int N) { return retNb(N)*SIZE retBx(N); }
    // Function that get 3-digit integer index from given info
    inline int getCand(int Nbint Rwint Cl) { return Nb*SQ_SZRw*SIZE Cl; }


    void BuildMatrix() {
        
    node *LastCandidate[COLS];
        for(
    int i 0!= COLS; ++i) {
            
    LastCandidate[i] = &Column[i];
            
    Column[i].up = &Column[i];
            
    Column[i].down = &Column[i];
            
    Column[i].head = &Column[i];
    //        Column[i].size = 0;
        
    }

        
    Column[0].left = &RootNodeRootNode.right = &Column[0];
        for(
    int i 1!= COLS; ++i) {
            
    Column[i].left = &Column[i-1];
            
    Column[i-1].right = &Column[i];
        }
        
    Column[COLS-1].right = &RootNodeRootNode.left = &Column[COLS-1];

        
    node *nds ObjectPool;
        for(
    int a 0!= SIZE; ++a)
            for(
    int b 0!= SIZE; ++b)
                for(
    int c 0!= SIZE; ++c) {
                    
    int Candidate getCand(c,a,b);
                    
                    
    node **tmp;
                    
                    
    //Constraint 1: Only 1 per square
                    
    Row[Candidate] = nds;
                    
    nds->left nds+3, (nds+3)->right nds;
                    
    tmp = &LastCandidate[SQ_OFFSET retSq(Candidate)];
                    
    nds->head = (*tmp)->head;//, ++nds->head->size;
                    
    nds->up = *tmp, (*tmp)->down nds, *tmp ndsnds->idx Candidate;
                    
                    
    //Constraint 2: Only 1 of per number per Row
                    
    tmp = &LastCandidate[RW_OFFSET retRn(Candidate)];
                    
    nds->right nds+1, (nds+1)->left nds, ++nds;
                    
    nds->head = (*tmp)->head;//, ++nds->head->size;
                    
    nds->up = *tmp, (*tmp)->down nds, *tmp ndsnds->idx Candidate;
                    
                    
    //Constraint 3: Only 1 of per number per Column
                    
    tmp = &LastCandidate[CL_OFFSET retCn(Candidate)];
                    
    nds->right nds+1, (nds+1)->left nds, ++nds;
                    
    nds->head = (*tmp)->head;//, ++nds->head->size;
                    
    nds->up = *tmp, (*tmp)->down nds, *tmp ndsnds->idx Candidate;
                    
                    
    //Constraint 4: Only 1 of per number per Box
                    
    tmp = &LastCandidate[BX_OFFSET retBn(Candidate)];
                    
    nds->right nds+1, (nds+1)->left nds, ++nds;
                    
    nds->head = (*tmp)->head;//, ++nds->head->size;
                    
    nds->up = *tmp, (*tmp)->down nds, *tmp nds
                        
    nds->idx Candidatends++;
                }

        for(
    int i 0!= COLS; ++i) {
            
    Column[i].up LastCandidate[i];
            
    LastCandidate[i]->down = &Column[i];
        }
    }

    void Disable(noderownode) {
        
    node *curnode rownode;
        for(; 
    curnode != rownode->leftcurnode curnode->right) {
            
    curnode->up->down curnode->down;
            
    curnode->down->up curnode->up;
    //        --curnode->head->size;
        
    }
    }

    void Enable(noderownode) {
        
    node *curnode rownode;
        for(; 
    curnode != rownode->leftcurnode curnode->right) {
            
    curnode->up->down curnode;
            
    curnode->down->up curnode;
    //        ++curnode->head->size;
        
    }
    }

    void Cover(nodecolnode) {
        
    colnode->left->right colnode->right;
        
    colnode->right->left colnode->left;
        
    node *rownode, *rightnode;
        for(
    rownode colnode->downrownode != colnoderownode rownode->down) {
    //        rownode->down->up = rownode->up, rownode->up->down = rownode->down;
            
    for(rightnode rownode->rightrightnode != rownoderightnode=rightnode->right) {
                
    rightnode->up->down rightnode->down;
                
    rightnode->down->up rightnode->up;
            }
        }
    }

    void UnCover(nodecolnode) {
        
    node *rownode, *rightnode;
        for(
    rownode colnode->downrownode != colnoderownode rownode->down) {
            for(
    rightnode rownode->rightrightnode != rownoderightnode=rightnode->right) {
                
    rightnode->up->down rightnode;
                
    rightnode->down->up rightnode;
            }
    //        rownode->down->up = rownode, rownode->up->down = rownode;
        
    }
        
    colnode->left->right colnode;
        
    colnode->right->left colnode;
    }

    void PrintResult();

    void Solve() {
        if(
    RootNode.right == &RootNode) {
            if(
    nResult == SQ_SZ)
                
    PrintResult();
            return;
        }

        
    node *min_col RootNode.right;

        
    Cover(min_col);
        
    nodecandidate min_col->down, *rightnode;
        for(; 
    candidate != min_colcandidate candidate->down) {
            
    // Cover 3 other col
            
    rightnode candidate->right;
            for(; 
    rightnode != candidaterightnode rightnode->right)
                
    Cover(rightnode->head);
            
            
    Result[nResult++] = candidate->idx;
            
    Solve(); // Recursive
            
    Result[--nResult] = 0;

            
    rightnode candidate->right;
            for(; 
    rightnode != candidaterightnode rightnode->right)
                
    UnCover(rightnode->head);
        }
        
    UnCover(min_col);
    }

    void PrintResult() {
        
    int Matrix[SIZE][SIZE];
        for(
    int a 0!= SIZE; ++a)
            for(
    int b 0!= SIZE; ++b)
                
    Matrix[a][b] = -1;

        for(
    int i 0!= SQ_SZ; ++i) {
            
    int idx Result[i];
            
    Matrix[retRw(idx)][retCl(idx)] = retNb(idx);
        }

        
    std::cout << "------------- Solution found -------------\n";

        for(
    int a=0;a<SIZE;a++) {
            for(
    int b=0;b<SIZE;b++) {
                if(
    a>0&&a%SQRT_SZ==0&&b==0) { for(int c=0;c<SIZE;c++) std::cout << "--"std::cout << '\n';} //horizontal lines
                
    if(Matrix[a][b]>=0std::cout << Matrix[a][b]+<< (b%SQRT_SZ==SQRT_SZ-1?'|':' ');
                else 
    std::cout << ". ";
            } 
            
    std::cout << '\n';
        }
    }

    void AddNumber(int rint cint number) {
    //    for(int i = 0; i != number; ++i)
    //        Disable(Row[getCand(i, r, c)]);
    //    for(int i = number + 1; i != SIZE; ++i)
    //        Disable(Row[getCand(i, r, c)]);
        
    int idx getCand(numberrc);
        
    node *rownode Row[idx], *rightnode rownode->right;
        
    Cover(rownode->head);
        for(; 
    rightnode != rownoderightnode rightnode->right)
            
    Cover(rightnode->head);
        
    Result[nResult++] = idx;
    }

    void LoadSudoku(std::istreamis) {
        
    int number;
        for(
    int a 0!= SIZE; ++a)
            for(
    int b 0!= SIZE; ++b) {
                
    is >> number;
                if( (
    number 0) && (number <= SIZE) )
                    
    AddNumber(abnumber 1);
            }
    }

    int main(int argcchar *argv[]) {

        
    BuildMatrix();
        
        if(
    argc 1) {
            
    std::ifstream f(argv[1]);
            
    LoadSudoku(f);
            
    f.close();
        } else 
    LoadSudoku(std::cin);

        
    Solve();

        return 
    0;

    Đây được coi là bài Sodoku khó nhất thế giới, chương trình trên chạy mất chưa đầy 0.1s:
    Mã:
    9 0 0 0 0 1 8 0 0
    0 6 0 0 3 0 0 0 0
    0 0 2 5 0 0 0 0 7
    0 0 9 0 0 0 0 0 6
    0 5 0 0 0 0 0 2 0
    4 0 0 0 0 0 3 0 0
    3 0 0 0 0 8 1 0 0
    0 0 0 0 4 0 0 8 0
    0 0 7 9 0 0 0 0 5

  4. Có 3 thành viên cảm ơn bài viết của boss14420 có chất lượng:


  5. #3
    Điều hành viên
    Tham gia ngày
    Mar 2012
    Bài gửi
    130

    Mặc định Re: Thuật toán quay lui giải Sudoku

    Thành ơi, ông có biết cách giải mấy ô sudoku biến thể, tức là ko phải 9 ô 3*3 mà là những khối hình thù bất kỳ tạo từ 9 ô con ko?

  6. #4
    HUT's Student
    Tham gia ngày
    Feb 2012
    Bài gửi
    272

    Mặc định Re: Thuật toán quay lui giải Sudoku

    Quote Nguyên văn bởi muteszhacker Xem bài viết
    Thành ơi, ông có biết cách giải mấy ô sudoku biến thể, tức là ko phải 9 ô 3*3 mà là những khối hình thù bất kỳ tạo từ 9 ô con ko?
    Cách làm cũng tương tự. Chỉ cần biết nguyên lý của nó là được.

    Với hình thù ô sudoku khác nhau thì phải sửa lại hàm BuildMatrix() các hàm retXX() cho phù hợp, còn lại tất cả có thể để nguyên.
    Lần sửa cuối bởi boss14420; 15-07-2012 lúc 04:43 PM

  7. #5
    svBK's Newbie Avatar của C'est La Vie
    Tham gia ngày
    Jul 2012
    Bài gửi
    16

    Mặc định Re: Thuật toán quay lui giải Sudoku

    Toàn Pro ,*** đạn Tủi thân ghê gớm

  8. #6
    HUT's Student
    Tham gia ngày
    Feb 2012
    Bài gửi
    272

    Mặc định Re: Thuật toán quay lui giải Sudoku

    Mấy cái sudoku 16x16 cho chạy cả chục phút vẫn chưa ra. Không biết code sai chỗ nào nữa:
    Mã:
    12	0	8	9	0	6	15	0	4	0	0	11	14	0	13	1
    0	0	5	0	0	8	0	0	0	13	0	16	11	0	0	3
    11	0	0	0	0	0	0	0	0	0	0	5	4	8	0	0
    0	0	6	0	0	0	10	16	0	0	0	0	0	0	0	9
    0	5	0	0	12	9	0	0	0	15	0	8	10	4	0	0
    0	0	15	4	8	13	0	0	0	0	16	14	12	0	0	5
    10	16	0	8	0	0	6	14	0	4	0	0	0	0	9	0
    6	0	0	14	0	16	4	0	3	5	11	9	13	0	1	0
    0	9	0	0	0	0	0	0	12	0	0	0	0	1	14	6
    0	0	14	0	0	0	0	0	0	9	0	0	16	0	15	0
    0	0	11	0	10	0	16	0	0	7	8	0	0	0	12	13
    0	0	0	13	0	11	12	0	0	0	0	15	8	3	5	0
    8	11	0	10	0	12	2	0	0	0	6	0	0	7	4	0
    14	0	13	15	16	0	8	0	11	0	0	0	0	9	0	0
    0	0	0	0	15	0	11	0	0	14	0	0	6	0	0	0
    0	7	4	6	1	10	13	0	0	12	0	0	15	0	0	0

+ Trả lời chủ đề

Thông tin chủ đề

Users Browsing this Thread

Hiện có 1 người đọc bài này. (0 thành viên và 1 khách)

Từ khóa (Tag) của chủ đề này

Quyền viết bài

  • Bạn không thể gửi chủ đề mới
  • Bạn không thể gửi trả lời
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình


About svBK.VN

    Bách Khoa Forum - Diễn đàn thảo luận chung của sinh viên ĐH Bách Khoa Hà Nội. Nơi giao lưu giữa sinh viên - cựu sinh viên - giảng viên của trường.

Follow us on

Twitter Facebook youtube