Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: Có một chút trục trặc với 8 queens-backtracking!

  1. #1
    Ngày gia nhập
    05 2008
    Bài viết
    24

    Mặc định Có một chút trục trặc với 8 queens-backtracking!

    Code tui viết rồi nhưng ko chạy được! Mọi người xem giúp thế nào. Thanks!!!
    Dùng backtracking mới học có 3 ngày nghĩ ko ra!
    Thêm một câu hỏi nữa! Tui có đọc code 8 queens trên 4rum, hơi khó hiểu ở chỗ sao đường chéo = kích thước*2-1; trong một code tui đọc có biến số gia =kích thước-1 cũng ko hiểu. Và có code như thế này
    Code:
    if (cot[j] == 1 && cheoxuoi[i+j] ==1 && cheonguoc[i-j+7] == 1)
    Vì sao lại có cái điều kiện lạ như thế này? Đọc code thì mãi chỉ như nước đổ đầu vịt. Mọi người có thể chia sẻ một số sách hay về backtracking hay là giải thuật bài toán 8 queens cho tui với được ko?

    Đây là code tui viết(Ko chạy được!!!)
    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <math.h>
    main()
    {
    	int i,j,k,ok;
    	int x[9];
    	i=1;
    	x[i]=0;
    	while(i>=1)
    	{
    		x[i]=x[i+1];
    		ok=0;
    		while((x[i]<=8)&&(!ok))
    		{
    			k=1;
    			ok=1; //bien ok de biet co chon duoc hay ko
    			while((k<=i-1)&&ok)
    				if((x[i]!=x[k])&&(abs(i-k)!=abs(x[i]-x[k]))) k++;
                //k chay tu 1 den i-1 kiem tra xem x[i]!=x[k] va |i-k| != |x[i]-x[k]|
                //thi x[i] duoc chon
    				else ok=0;
    		}
    		if(ok)
    			if(i==8)
    				{
    					printf("\n");
    					for(j=1;j<=8;j++) printf("%d ",x[i]);
    
    				}
    			else 	{
    						i++; //xet tiep cho du 8
    						x[i]=0;
    					}
    		else i--; //quay lui
    	}
    	getch();
    }

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    - Bài này tuy nổi tiếng và nhiều sách cho là dành cho newbie nhưng theo kinh nghiệm của tui nó là bài khó ! Cậu mới học thì cố viết cũng chỉ chép và chỉnh sữa, tui bảo đảm vì cái này tui cũng đã từng làm y chang cậu hồi mới học.
    - Cậu để 1,2 năm sau quay lại làm cũng chẳng có vấn đề gì, vì cái này đòi hỏi cậu hiểu sâu về đệ qui mà đệ qui là vấn đề chẳng dễ gì trong lập trình.
    PHP Code:
    1. if (cot[j] == 1 && cheoxuoi[i+j] ==1 && cheonguoc[i-j+7] == 1)
    Chỗ này vì 1 ô nó sẽ có 15 đường chéo.
    - Cậu chỉ cần google "8 Queen Puzzle" nó sẽ ra 1 đống cho cậu tha hồ mà đọc.
    - Đệ qui chỉ là cách cơ bản bài này còn rất nhiều cách hay.
    Và đây là 1 cách cơ bản nhất mà hồi xưa tui từng làm, tui nghĩ nó sẽ dễ đọc hơn cho cậu :
    PHP Code:
    1. #include <iostream>
    2.  
    3. const int size = 8;
    4.  
    5. void queen( int row );
    6. void put( int row, int col );
    7. void un_put( int row, int col );
    8. void print();
    9. bool check( int row, int col );
    10.  
    11.  
    12. bool a[ size ][ size ], colunm[ size ], diag[ 2*size - 1 ], back_diag[ 2*size - 1 ];
    13.  
    14. int main()
    15. {
    16.     int i;
    17.     for( i = 0; i < size; ++i ) {
    18.         for ( int j = 0; j < size; ++j )
    19.             a[ i ][ j ] = false;
    20.     }
    21.     for( i = 0; i < size; ++i )
    22.         colunm[ i ] = true;
    23.  
    24.     for( i = 0; i < 2*size - 1; ++i ) {
    25.         diag[ i ]      = true;
    26.         back_diag[ i ] = true;
    27.     }
    28.     queen( 0 );
    29. }
    30.  
    31. void put( int row, int col ) {
    32.     a[ row ][ col ]                  = true;
    33.     colunm[ col ]                    = false;
    34.     diag[ ( size - 1 ) - col + row ] = false;
    35.     back_diag[ col + row ]           = false;
    36. }
    37.  
    38. void un_put( int row, int col ) {
    39.     a[ row ][ col ]                  = false;
    40.     colunm[ col ]                    = true;
    41.     diag[ ( size - 1 ) - col + row ] = true;
    42.     back_diag[ col + row ]           = true;
    43. }
    44.  
    45. bool check( int row, int col ) {
    46.     if( colunm[ col ]                   == false
    47.         || diag[ size - 1 - col + row ] == false
    48.             || back_diag[ col + row ]   == false
    49.     )
    50.         return false;
    51.     else
    52.         return true;
    53. }
    54.  
    55. void queen( int row ) {
    56.     if( row == size ) {
    57.         print();
    58.     }
    59.     else {
    60.         for( int col = 0; col < size; ++col ) {
    61.             if( check ( row, col ) ) {
    62.                 put( row, col );
    63.                 queen( row + 1 );
    64.                 un_put( row, col );
    65.             }
    66.         }
    67.     }
    68. }
    69.  
    70. void print() {
    71.     std::cout << "\n\n\n[--] BOARD SHOW \n";
    72.     for( int i = 0; i < size; ++i ) {
    73.         for ( int j = 0; j < size; ++j ) {
    74.             ( a[ i ][ j ] == false ) ? std::cout << " - " : std::cout << " Q ";
    75.         }
    76.         std::cout << std::endl;
    77.     }
    78. }

Các đề tài tương tự

  1. Queens Park Rangers vs Arsenal: 23h30, ngày 04/05
    Gửi bởi phuongthythy trong diễn đàn Giải trí - Thư giãn
    Trả lời: 0
    Bài viết cuối: 04-05-2013, 02:23 PM
  2. Mã nguồn C Lỗi Dùng backtracking lập trình bài 8 con hậu không chạy được?
    Gửi bởi darkangeldn trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 25-08-2011, 02:33 PM
  3. BackTracking Giải thuật tìm đường đi sao cho thời gian ngắn nhất?
    Gửi bởi y5k72pk trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 16-06-2011, 06:31 AM
  4. giải thích về backtracking?. Ai giúp mình với!!!
    Gửi bởi vanduong91 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 02-12-2010, 10:25 AM
  5. cho em hỏi một chút về mảng
    Gửi bởi boyhello456 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 26-02-2009, 01:09 AM

Quyền hạn của bạn

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