[C++] Knight tour !

[rox_rook]

Chắc ai cũng biết bài này rồi phải không? vấn đề của mình ở đây là khi mình gọi đệ qui times == 64 lần thì nó báo error: dumping stack ? Nhưng dòng
K[next_row][next_col] = false; thì mình nghĩ đã backtrack rồi! Các bạn có ý kiến hay giải pháp nào thì xin giúp mình ! thanks so much !

Đề bài here -> http://www.ececs.uc.edu/~annexste/Co...-2003/Lab7.htm

Đây là code của mình:

#include<iostream>



/* Knight Tour */


  const int size = 8;
  void initialization();
  void print();
  void Knight ( int times, int row, int col );

  bool K[size][size];
  bool check( int row, int col);
  int move_col[] = {-2, -1, +1, +2, +2, +1, -1, -2};
  int move_row[] = {+1, +2, +2, +1, -1, -2, -2, -1};

  int row, col, index, next_row, next_col; 
  int times;
void initialization()
{
    index =0;
    times = 0;
    row = 0;
    col = 0;
   
    for ( int i=0; i < size; i++)
    {
        for ( int j=0; j < size; j++)
        {
            K[i][j] = false;
        }
    }

  K[row][col] = true;
}


bool check ( int row, int col )
{
    if ( row > 7 || row < 0 || col > 7 || col < 0 || K[row][col] == true )
        return false;
    else
        return true;
}

void print ()
{
    index++;
    cout << " Let's go Knight ^^" << endl;
    cout << " The : "<< index << "th"<< endl;
    for ( int k = 0; k < size; k++ )
    {
        for ( int m = 0; m < size; m++ )
        {
              if ( K[k][m] == true )
              {    
                cout << " K " ;
               
              }    
              else 
                cout << " * ";
        }
    cout << endl;
    }
}
void Knight ( int times, int row, int col)
{
      
      if ( times == 64 )
          print();
      else
      {
              for ( int i = 0; i < 8; i++ )  
              {
              
                  cout << " col : " << col << endl;
                  cout << " row : " << row << endl;
                             
                  next_col = col + move_col[i];
                  next_row = row + move_row[i];
                  
                  cout << "next-----------:" << next_row << endl;
                  cout << "next-----------:" << next_col << endl;
                  
                  if (check( next_row,next_col ))
                  { 
                     
                      K[next_row][next_col] = true;  
                      Knight (times+1, next_row, next_col);
                      K[next_row][next_col] = false;// is it backtracking here?                  }
                  
              } 
      }                 
}                  
void main()
{
   initialization();
   Knight (0,0,0);

// 2 dòng cuối này chỉ để stop screen vì mình dùng Scite để viết //
int x;
cin >> x;

}

[rox_rook]

Bài này là bài con Hậu, mình đã viết thành công với 92 trường hợp! Các bạn cứ so sánh với bài con Knight! mình thấy backtrack ở 2 bài này tương tự nhưng vẫn không hiểu sao bài Knight lại sai! hic hic !
Code của Queen đây !

#include <iostream>

void initialization();			// khoi tao cac gia tri cua array
bool check(int row, int col);	// kiem tra o (row, col) co dat duoc quan hau khong
void put(int row, int col);		// dat quan hau len ban co, danh dau col va 2 duong cheo
void unput(int row, int col);	// phuc hoi lai ban co nhu truoc khi dat quan hau
void queen(int row);			// chuong trinh dat 8 hau len ban co
void print();					// in ket qua ra man hinh

const int size = 8
;
int index;

bool a[size][size], cols[size], fwd_dias[2 * size - 1], bwd_dias[2 * size - 1];

void main()
{
	initialization();
	queen(0);
	cout << "\n\nNhu vay co tat ca " << index << " truong hop ung voi size = " << size;
	
        int x;
	cin >> x;
}


// khoi tao gia tri
void initialization()
{
	index = 0;


	// a[i][j] == true neu co quan hau dat tren no
	for (int i = 0; i < size; i++)
	{
		for(int j = 0; j < size; j++)
			a[i][j] = false;
	}

	// cols[i] == true neu khong co quan hau nao an cot` i
	for (i = 0; i < size; i++)
		cols[i] = true;
	
	// truong hop hai duong cheo cung tuong tu voi col
	for (i = 0; i < 2 * size - 1; i++)
	{
		fwd_dias[i] = true;
		bwd_dias[i] = true;
	}
}




// kiem tra xem co the dat quan hau len o a[row][col] hay khong
bool check(int row, int col)
{
	// chi can col hay 1 trong 2 duong cheo di qua a[row][col] thi tra ve false
	if (cols[col] == false || fwd_dias[(size - 1) - col + row] == false || bwd_dias[col + row] == false)
            return false;			// khong dat duoc quan hau
	else 
            return true;			// co the dat duoc quan hau
}




// dat quan hau vao o a[row][col]
void put(int row, int col)
{
	a[row][col] = true;
	cols[col] = false;
	fwd_dias[(size - 1) - col + row] = false;
	bwd_dias[col + row] = false;
}



// phuc hoi lai ban co nhu truoc khi dat quan hau
void unput(int row, int col)
{
	a[row][col] = false;
	cols[col] = true;
	fwd_dias[(size - 1) - col + row] = true;
	bwd_dias[col + row] = true;
}



// chuong trinh dat quan hau
void queen(int row)
{
	if (row == size)
		print();
	else
	{
		for (int col = 0; col < size; col++)
		{
			if (check(row, col))
			{
				put(row, col);		// dat quan hau len ban co va danh dau col va 2 duong cheo
									// tuong ugn
				queen(row + 1);		// dat tiep quan hau o hang ke tiep
				unput(row, col);	// phuc hoi lai col va 2 duong cheo nhu truoc khi dat quan hau-> BACKTRACKING ?			}
		}
	}
}




// in ra truong hop thu index
void print()
{
	index++;  // so truong hop tang len 1

	cout << endl << "truong hop thu " << index << " :" << endl;
	for (int i = 0; i < size; i++)
	{
		for(int j = 0; j < size; j++)
		{
			if (a[i][j] == false)
				cout << "_ ";
			else cout << "Q ";
		}
		cout << endl;
	}

}

      




/*////// 15 duong cheo thuan//////////////////
7 8 9 10 11 12 13 14
6
5
4
3
2
1
0
////////////////////////////////////////////*/
/*////// 15 duong cheo nguoc//////////////////
0 1 2 3 4 5 6 7
              8
			  9
			  10
			  11
			  12
			  13
			  14
////////////////////////////////////////////*/

[rox_rook]

hix,hix ! Cao thủ đâu hết rồi! Huynguyen có idea gì không! Kẹt cứng rồi ! hix hix

[Kevin Hoang]

Cụ Euler có vẻ cũng mê cờ lắm nhỉ?

Ở bài này họ đã đưa ra 8 vị trí hành trình đầu tiên của quân cờ Knight, mình sẽ đi tiếp để quân cờ Knight đi hết 64 ô của bàn cờ mà nó chỉ có đi qua mỗi ô của bàn cờ một và chỉ một lần. Dreaminess không sửa được bài của bạn, nhưng theo Dreaminess bạn làm thế chưa đúng với yêu cầu. Mọi người cùng giải xem nhé.

Theo Dreaminess hiểu đề ra như sau: Đây là một thế cờ mà nhà toán học Euler đưa ra. Thế cờ đã xác định 8 vị trí đầu tiên của hành trình Knight như hình vẽ, có thể nào đi tiếp hành trình của quân cờ Knight này để nó đi hết 64 ô của bàn cờ và chỉ đi qua mỗi ô một và chỉ một lần. Viết chương trình bằng C++ để giải bài toán với các hàm mà mảng.



Dreaminess thấy khó phết đó nha.

[rox_rook]

Cuối cùng sếp Dream cũng xuất hiền rồi ^^ ! Đúng là bài này là bài dạng 1, output ra tất cả trường hợp, và may mắn thay mình cũng đã viết xong, mình đang suy nghĩ tiếp 1 dạng thứ 2 chính là nó move với các hướng hoàn hào nhất

mình sẽ đi tiếp để quân cờ Knight đi hết 64 ô của bàn cờ mà nó chỉ có đi qua mỗi ô của bàn cờ một và chỉ một lần

nghĩa là sẽ không cần backtrack ở đây , cái này khó hơn, hic hic! nếu có bạn nào hứng thú thì xin cho mình tí ý tưởng nhé! thanks so much

[hailoc12]

Nếu có nhiều thời gian hơn thì mình sẽ thảo luận cùng các bạn về bài này, trước mình giải bài này dùng backtrackking chỉ giải được với các trường hợp nhỏ với n<=6 với n=8 chạy rất lâu.
Mình chỉ có thể cung cấp cho bạn một số tài liệu mình có về bài này thôi ( nguồn Tin học nhà trường ), mình cũng chưa đọc qua nhưng có lẽ nó sẽ thoả mãn được những thắc mắc của bạn.

Tản mạn xung quanh bài toán mã đi tuần

Trịnh Thanh Hải


Tản mạn xung quanh bài toán mã đi tuần

Đối với các bạn say mê môn Tin học thì bài toán phỏng theo quy luật di chuyển của con mã trên bàn cờ quốc tế rất quen thuộc. Đã có nhiều thuật toán để giải bài toán này. Trong bài viết này chúng tôi muốn trình bày thêm một số suy luận nhằm sáng tỏ câu hỏi: "Từ một vị trí bất kỳ trên bàn cờ, liệu con mã có thể đi đến tất cả các vị trí trên bàn cờ được không?".

Trước tiên ta xét bài toán: "Nếu đặt con mã ở một vị trí bất kỳ trên bàn cờ và chọn một vị trí đích thì liệu con mã có thể đi đến được vị trí đó không? Nếu đi được thì số bước đi tối thiểu là bao nhiêu?"

Để minh hoạ đường đi của con mã ta lập một hệ toạ độ mà gốc toạ độ O(0,0) là vị trí ban đầu của con mã, vị trí kết thúc sau khi di chuyển của con mã là M(x,y).

Ta xét từng trường hợp

+ Số bước đi là 1: từ quy luật di chuyển của con mã trên bàn cờ ta thấy ngay con mã sẽ có 8 khả năng di chuyển khác nhau. Khi đó toạ độ điểm đích của nó sẽ là một trong các trường hợp sau: M1(2,1); M2(1,2); M3(-1,2); M4(-2,1); M5(-2,-1); M6(-1,-2); M7(1,-2); M8(2,-1). Xét toạ độ x và y ta có: |x| +| y| = 3. Mặt khác khi di chuyển một bước, số ô theo bất kỳ hàng hoặc cột đều không quá 2, so với vị trí xuất phát số hàng, cột chênh lệch chỉ là 1 hoặc 2: |x| =< 2 và |y| =< 2. Hơn nữa x,y không cùng lẻ hoặc chẵn. Vậy với x, y không cùng chẵn hoặc lẻ thoả mãn { |x| =< 2, |y| =< 2; |x|+|y| = 3} thì con mã chỉ cần di chuyển một bước để đến vị trí M(x,y).




+ Số bước đi là 2 Sau 2 bước đi toạ độ x, y chỉ có một trong hai khả năng: x, y cùng lẻ hoặc x, y cùng chẵn và thoả mãn:{| x| =< 4 ; |y| =< 4; |x|+|y| =< 6}. Ngược lại nếu ta cho trước toạ độ điểm đích M(x,y) thoả mãn điều kiện trên thì con mã chỉ cần sau 2 bước là có thể đến được điểm M. (riêng để di chuyển tới vị trí M(2,2), N(-2,-2), P(2,2), Q(2,-2) cần 4 lần di chuyển).
+ Số bước đi là 3: Sau 3 bước di chuyển toạ độ x, y không cùng lẻ hoặc cùng chẵn và thoả mãn: {|x| =< 6; |y| =< 6; 3 * |x|+|y| =< 9} và đây cũng là điều kiện toạ độ x, y của điểm M để con mã có thể đến được sau 3 bước di chuyển.

Tiếp tục quá trình xét tương tự, chẳng hạn sau 5 bước di chuyển của con mã ta có |x| +|y| =< 15 trong đó x, y không cùng lẻ hoặc cùng chẵn... Ta có bảng sau:

Điều kiện ràng buộc với toạ độ x, y của điểm đích M(x,y)
Số bước ít nhất để con mã đi tới đích

|x|+|y| = 3; |x| =< 2; |y| =< 2; x, y không cùng lẻ hoặc chẵn
1

|x|+|y| =< 6; |x| =< 4; |y| =< 4; x,y cùng chẵn hoặc lẻ
2

3 * |x|+|y| =< 9; |x| =< 6; |y| =< 6; x,y không cùng chẵn hoặc lẻ
3

6< |x|+|y| =< 12; |x| =< 6; |y| =< 6; x,y cùng chẵn hoặc lẻ
4

9<|x|+|y| =< 15; |x| =< 7; |y| =< 7; x,y không cùng chẵn hoặc lẻ
5

12< |x|+|y| =< 15; |x| =< 7; |y| =< 7; x,y cùng chẵn hoặc lẻ
6


Ta minh hoạ bảng trên qua một vài ví dụ cụ thể:




Hình 2

Giả sử vị trí xuất phát của con mã là góc dưới bên trái, như vậy các ô được gắn toạ độ từ (0,0)... (7,7) ( hình 2)

+ Vị trí ô đích là (3,3). Vì |3|+|3| = 6, hơn nữa cả hai toạ độ x, y đều lẻ nên ta chỉ cần 2 bước để di chuyển từ (0,0) đến (3,3).

+ Vị trí đích là ô (1,6). Ta có |1| + |6| = 7, mặt khác trong 2 số x, y có một số lẻ, một số chẵn. Vậy con mã chỉ cần 3 bước để từ (0,0) đến (1,6)

+ Vị trí đích là ô (2,6). Ta có |2|+|6| = 8, mặt khác x, y cùng chẵn. Vậy để đi từ (0,0) đến (2,6) cần tối thiểu 4 lần di chuyển.

+ Vị trí ô đích là (7,6). Ta có |7| + |6| = 13, mặt khác x, y một số chẵn, một số lẻ. Căn cứ vào bảng trên ta có cố bước di chuyển tối thiểu là 5.

+ Ví trí ô đích là (7,7). Vì |7| + |7| = 14 và x, y cùng là số lẻ nên có bước tối thiểu để đi từ (0,0) đến (7,7) là 6 bước.

Chú ý rằng đây là số bước đi tối thiểu chứ không phải là cách di chuyển duy nhất. Có thể có nhiều cách đi với số bước trên để đến vị trí đích.

Vậy là nếu đặt con mã vào một vị trí bất kỳ trên bàn cờ (ta coi là gốc toạ độ) và chọn một ô bất kỳ (có toạ độ (x,y) với hệ toạ độ đã xác định) làm ô đích thì ta xét thấy x,y chỉ có thể là một trong các khả năng đã liệt kê trong bảng. Do đó con mã hoàn toàn có thể di chuyển tới đích và số lần di chuyển tối thiểu đã được nêu trong bảng.

Căn cứ quy luật di chuyển của con mã sau một bước, so với vị trí xuất phát số hàng, cột chênh lệch chỉ là 1 hoặc 2. Hơn nữa x, y không cùng lẻ hoặc chẵn. |x|+|y|=3; |x|<= 2; |y|<= 2 điều này tương đương với điều kiện x2 + y2 = 5, nên ta có thuật toán tìm vị trí ô có toạ độ (x[i],y[i]) cho bước di chuyển thứ i (i>=1) của con mã là:

for dong:=- 2 to 2 do
for cot:=- 2 to 2 do
if (dong*dong+cot*cot=5) then
begin
a:=x[i-1]+dong;
b:=y[i-1]+cot;
if (ô( a,b) vẫn thuộc bàn cờ) then
Begin
x[i]:=a;
y[i]:=b;
end;
end;
Cuối cùng ta giải quyết bài toán:"Đặt con mã vào một vị trí bất kỳ trên bàn cờ. Tìm chu trình của con mã để ghé thăm một lần duy nhất tất cả các ô còn lại". Kết quả ta tìm được nhiều chu trình đi khác nhau nhưng số bước đi đều là 63.

Để đơn giản ta chọn ô góc dưới bên trái là gốc toạ độ. Như vậy các cột, các dòng được gắn số thứ tự từ 0 đến 7 (hình 2). Theo trên ta có thủ tục Try_ma như sau:

Procedure Try_ma(i:integer);
var
dong,cot:-2..2;
a,b:integer;
Begin
for dong:=-2 to 2 do
for cot:=-2 to 2 do
if (dong*dong+cot*cot=5) then
begin
a:=x[i-1]+dong;
b:=y[i-1]+cot;
if (0=<a)and(a<=7)and(0=<b)and(b<=7)and(bc[a,b]) then
begin
x[i]:=a;
y[i]:=b;
bc[a,b]:=false;
if i< 63 then Try_ma(i+1)
else xuat;{thu tuc Xuat viet chu trinh con ma ra man hinh}
bc[a,b]:=true
end;
end;
end;

Trong bài trên sử dụng bc là mảng 2 chiều kiểu Boolean: bc[x,y]:=true nếu con mã chưa đi qua ô [x,y]. Trong thủ tục này, số bước duyệt cho một lần lựa chọn là 25, để giảm bớt số lần duyệt ta có thể căn cứ vào quy luật di chuyển cuả con mã sau một bước đã phân tích ở trên. Thiết lập mảng C, D lưu trữ toạ độ tương ứng 8 khả năng di chuyển của con mã:

c[1]:=2;c[2]:=1;c[3]:=-1;c[4]:=-2;c[5]:=-2;c[6]:=-1;c[7]:= 1; c[8]:= 2;

d[1]:=1;d[2]:=2; d[3]:=2;d[4]:= 1;d[5]:=-1;d[6]:=-2;d[7]:=-2; d[8]:=-1;

Mảng 2 chiều bc[x,y] ghi nhận con mã đã đi đến vị trí (x,y) sau bước di chuyển thứ i. Khởi đầu các giá trị của mảng bc[x,y]=0. Vị trí ban đầu con mã (io,jo).

Procedure Try_ma(i:byte);
begin
if i>63 then xuat {thủ tục Xuat viết chu trình con mã ra màn hình}
else
for j:=1 to 8 do
begin
x:=i0+c[j];
y:=j0+d[j];
then
begin
bc[x,y]:=i;
i0:=x;
j0:=y;
Try_ma(i+1);
i0:=x-c[j];
j0:=y-d[j];
bc[x,y]:=0;
end;
end;
end;
Từ đây ta đặt ra các bài toán khác, chẳng hạn: "Trên bàn cờ n x n ô (n>3) ta đặt con mã vào một vị trí (io,jo) bất kỳ trên bàn cờ. Hỏi trên bàn cờ đó còn sắp được thêm bao nhiêu con mã để không con nào ăn được con nào?. Hoặc cho trước vị trí xuất phát (io,jo) và một ô đích cần tới (x,y) trên bàn cờ. Liệu có thể tính trước được sẽ có bao nhiều đường đi khác nhau với cùng một số bước tối thiểu?... Rất mong được trao đổi với các bạn.

Xin liên hệ với địa chỉ haisp@.edu.vnn.vn hoặc Trịnh Thanh Hải - Khoa Toán trường Đại học sư phạm - ĐH Thái Nguyên.

Trịnh Thanh Hải.

Thuật toán hiệu quả giải bài toán Mã đi tuần

Nguyễn Văn Trung


Hẳn các bạn học lập trình pascal đã biết đến bài toán ″Mã đi tuần″:
Cho bàn cờ tổng quát nxn và một quân mã. Hãy chỉ ra một hành trình của Mã xuất phât từ ô (x,y), đi qua tất cả các ô còn lại của bàn cờ, mỗi ô đúng một lần (luật đi của mã như luật cờ vua).

Và hẳn bạn đã biết thuật giải củabài toán này. Đó là dùng kỹ thuật duyệt quay lui xét các ô con. Mã có thể đi tới để tìm ra một hành trình. Tuy nhiên, việc duyệt như vậy là hết sức chậm bởi phải xét quá nhiều trường hợp. Và với thuật toán như vậy, khi kích thước bàn cờ vượt quá 8(n>8) thì có thể nói bạn sẽ phải ngồi chờ đợi máy tính cho đến khi mất hết kiên nhẫn. Vì vậy mục đích của bài toán này là nêu ra một thuật giải hiệu quả hơn cho bài toán Mã đi tuần.

Ta coi bàn cờ nxn như một đồ thị vô hướng và thừa nhận ô (i,j) của bàn cờ là đỉnh (i-1xn+j) của đồ thị.

Ví dụ: ô (1,n) là đỉnh thứ (1-1)xn+n=n của đồ thị
ô (2,3) của bàn cờ 3x3 là đỉnh thứ (2-1)x3+3 = 6 của đồ thị.
Như vậy việc tìm hành trình để con mã đi hết các ô của bàn cờ <-> Tìm ra một hành trình đi hết các đỉnh của đồ thị, mỗi đỉnh chỉ đi qua một lần.
+) Việc kiểm tra xem từ đỉnh u có thể tới đỉnh v hay không ta có thể thấy như sau:
Giả sử ô(x1,y1) có đỉnh ở đồ thì là u <-> (x1 -1)xn +y1 =u
Dễ thấy nếu (u mod n =0) thì x1 = u div n; y1 =n
Còn nếu (u mod n <>0) thì x1 = u div n -1, y1 =u mod n. (Bạn có thể thấy nếu vẽ hình ra)

Có hai cách để chúng ta tìm ra xem hai đỉnh u và v có thể đi đến từ nhau hay không:
- Dùng mảng để lưu lại (mảng logic), như vậy nhanh hơn nhưng do không gian nhớ hạn chế của Pascal, nếu ta khai báo b[1..nxn,1..nxn] thì sẽ không thể giải khi n >10.
- Vậy ta sẽ viết 1 hàm kt(u,v) kiểu boolean xem từ u có thể tới v không. Đoạn mã như sau.

Function kt(u,v:integer):boolean;
Var x1,x2,y2,y1:integer;
Begin
x1:= (u-1)div n +1;
If u mod n =0 then y1:=n
Else y1:=u mod n;
X2:=(v-1) div n+1;
If v mod n =0 then y2:=n
Else y2:=u mod n;
Kt:= (abs (x1-x2)*abs(y1=y2)=2);
End;
+) Khác với cách duyệt xét tất cả các ô có thể đến từ ô đang đứng, ở đây ta chỉ xét và chọn ô để đi tiếp theo từ ô đang đứng khi bậc của ô đó là nhỏ nhất. (Ta gọi bậc của ô (x,y) là số ô có thể đến từ sô này mà chưa hề đi qua).

Như vậy số bậc của đỉnh u là số đỉnh có thể đến từ đỉnh u mà các đỉnh chưa hề đi qua.
Ta có thể dùng hàm Dembac(u) để đếm từ đỉnh u và hàm Bacnhonhat(u) để lưu giá trị của bậc của đỉnh v nào đó có thể đến từ u và bậc của nó là nhỏ nhất.
Dùng biến count để đếm bước đi của mã. Khi count=nxn nghĩa là ta đã được hành trình.
Mảng b: array[1..nxn] để lưu số x với x là chỉ số x bước thì mã đến đỉnh b[i]=x,b[i]=0 nếu như ô đó chưa đi qua. Ta cũng dùng luôn mảng này để kiểm tra xem một đỉnh đã được đi qua hay chưa.
Toàn bộ văn bản chương trình như sau:

Program Ma_di_tuan;
Const
max =50;
Var
b:array[1..max*max] of integer;
N,x,y,count:integer;
Function kt(u,v:integer):boolean;
Var
x1,x2,y2,y1:integer;
Begin
x1:=(u-1)div n +1;
If u mod n =0 then y1:=n
Else y1:=u mod n;
X2:=(v-1) div n+1;
If v mod n =0 then y2:=n
Else y2:=u mod n;
Kt:= (abs (x1-x2)*abs(y1=y2)=2);
End;
Function Dembac(u:integer):integer; {dem so dinh co the den tu u ma chua di qua}
Var
tg,v:integer;
Begin
tg:=0;
For v:=1 to n*n do {Duyet mo dinh}
If (b[v]=0) and kt(u,v) then inc(tg);
Dembac:=tg;
End;
Function Bacnhonhat(u:integer):integer;
Var
v,tg:integer
Begin
tg:=10;
For v:=1 to n*n do
If (b[v]=0) and kt(u,v) and (tg>Dembac(v)) then Tg:=dembac(v);
Bacnhonhat:=tg;
End;
Procedure printResult;
Var
u:integer;
Begin
For u:=1 to n*n do
If u mod n =0 then Writeln(b[u], ' ')
Else write(b[u], ' ');
Readln;
Halt;
End;
Procedure Dat(u:integer);
Var
v:integer;
Begin
For v:=1 to n*n do
If (b[v]=0)and kt(u,v) and (Dembac(v)=Bacnhonhat(u)) then
Begin
Inc(count);
b[v]:=count;
If count=n *n then PrintResult
Else Dat(v);
Dec(count);
b[v]:=0;
End;
Begin
Write('kich thuoc ban co:');
readln(n);
Write('toa do o dang dung:');
readln(x,y);
X:=(x-1)*n+y;
B[x]:=1;
count:=1;
Dat(x);
End.

Nhận xét:

Chương trình trên với 2≤n≤18 chạy với tốc độ <1 giây (trường hợp có cách đặt). Với n lớn hơn chương trình chạy khoảng>3 giây (n=30). Tuy nhiên trường hợp khó xử lý đó là nếu không có hành trình, do phải duyệt hết các trường hợp nên chạy không hơn chương trình duyệt bình thường, các bạn thử tìm cách giải xem? Nếu các bạn có thăc mắc xin liên hệ với tác giả qua mail: ngtrung882003@yahoo.com hoặc Nguyễn Văn Trung − 10A3 − Khối PTCTT − ĐH SP Hà Nội;

Thuật toán hoàn chỉnh cho bài toán mã đi tuần
và một ứng dụng quan trọng

Công Hiệp


Trong số báo tháng 6- 2003, có bài "thuật toán hiệu quả giải bài toán mã đi tuần" của tác giả Nguyễn Văn Trung, đây là một cách giải rất hay bởi bài toán này từ trước đến nay chỉ được xem xét dưới góc độ của một bài đệ quy quay lui bình thường và với kích thước quá hạn chế. Hơn thế nữa thuật giải này còn cho thấy đệ quy quay lui có thể giải được những bài toán với kích thước tương đối nếu cài đặt tốt. Về mặt ý nghĩa và hiệu quả là thế, tuy nhiên cài đặt của thuật toán này tôi thấy còn hơi thô sơ, chưa có sự chau chuốt về thuật toán và kỹ thuật lập trình.

Như tác giả bài viết đó đã nhận xét, với bài toán đó thì chỉ có thể giải được cho kích thước bàn cờ là không quá 30 (trong trường hợp có nghiệm), không những thế còn rất chậm. Sau khi nghiên cứu thuật giải này (thực chất là quay lui kết hợp với phương pháp duyệt ưu tiên Warnsdorff), tôi xin được trình bày những cải tiến có thể của thuật toán đã được trình bày và một ứng dụng có thể nói khá hay vào việc giải một bài toán đã được nhiều người biết đến: "bài toán tìm đường đi Hamilton" của một đồ thị. Việc cải tiến dưới giúp chương trình chạy được với N = 100 !

I. Cải tiến chương trình
Vẫn dựa trên tư tưởng của thuật toán đó là coi bàn cờ kích thước n x n như một đồ thị n * n đỉnh. Để hiểu một cách cặn kẽ bài viết này, các bạn nên tham khảo bài viết của tác giả đã được đăng trên số báo tháng 6.

Cải tiến 1:
Trước hết, xét một đỉnh u của đồ thị, chúng ta có thể dễ thấy là đỉnh này là biểu diễn của ô (x, y) trong đó:
x := (u- 1) div n + 1;
y := (u- 1) mod n + 1;

với x là dòng và y là cột và hoàn toàn không phải xét các trường hợp như trước, các bạn nên kiểm tra tính đúng đắn của công thức này bằng việc vẽ hình bàn cờ để minh hoạ.

Cải tiến 2:
Để tránh cho chương trình của chúng ta chạy chậm (vì cài đặt của chúng ta là đệ quy quay lui), phải hết sức tránh việc gọi các chương trình con nhiều lần trong các thủ tục chính, điều này cài đặt của tác giả chưa đạt được. Do trong thủ tục Dat(u), vòng lặp ban đầu làm cho chúng ta phải xét tất cả N2 đỉnh của đồ thị tương đương với hàm kt(u, v) được gọi tới N2 lần, hơn nữa chương trình lại là đệ quy quay lui nên sẽ có rất nhiều lần gọi đến hàm này khiến chương trình tốn rất nhiều thời gian và bộ nhớ. Đây là yếu tố chính khiến chương trình trên tuy có nhanh hơn chương trình duyệt bình thường nhưng chưa đạt được tốc độ đáng kể. Vậy nên chăng chúng ta hãy dùng một mảng để lưu xem từ đỉnh u có đến được đỉnh v không? Vấn đề đặt ra là trong trường hợp bàn cờ có kích thước lớn (chẳng hạn 100 x 100) thì đồ thị sẽ có n x n đỉnh, dù có dùng mảng động cũng không thể biểu diễn nổi. Để ý thấy rằng với một ô bất kỳ chỉ có thể tới nhiều nhất là 8 ô khác, điều này gợi ý ta nên dùng mảng 2 chiều, một mảng là số đỉnh của đồ thị, mảng kia là mảng 8 phần tử lưu lại 8 ô có thể tới được từ một đỉnh bất kì.

Khai báo như sau:

Type
Tarr = array [1..8] of integer;
Var
A : array [1..100 * 100] of ^Tarr;

Như vậy trong thủ tục Dat(u), ta sẽ xét tất cả các đỉnh có thể đến từ đỉnh u (nhiều nhất là 8 đỉnh) và các đỉnh này đã được lưu lại trong mảng A.

Caỉ tiến 3:
Với cài đặt trước đây, để kiểm tra những đỉnh nào có thể đến được từ đỉnh u, ta phải xét tất cả n x n đỉnh. Tuy nhiên chúng ta có thể hạn chế điều này dựa vào nhận xét sau:
Giả sử hai đỉnh u, v của đồ thị ở thế mã giao chân, dễ thấy |u - v| õ‰Ô 2 x n + 1(*), vậy ta chỉ xét những đỉnh thoả mãn (*).

Cải tiến 4:
Để ý kỹ hơn chút nữa, trong hàm Bacnhonhat(u), bậc của đỉnh v ở thế mã giao chân với đỉnh u sẽ phải tính hai lần do đệ quy không có tính lưu lại, vậy ta có thể dùng một biến trung gian để số lần gọi đệ quy hàm này giảm đi (về mặt thời gian, nếu bài toán ra với kích thước nhỏ của bàn cờ thì cải thiện này không đáng kể, tuy nhiên với kích thước của bàn cờ lớn thì lượng thời gian sử dụng được tiết kiệm quá nhiều). Cũng xin lưu ý các bạn khi lập trình nên tránh gọi ít lần đệ quy nếu trong quá trình xử lý có một đối tượng nào đó được gọi đệ quy nhiều lần thì nên dùng thêm biến trung để lưu lại. Có thể minh hoạ lại đoạn chương trình đó như sau:

function Bacnhonhat(u : integer) : byte;
var
v : integer;
tg, C : byte;
begin
tg := 100;
for v := 1 to 8 do
if (a[u]^[v] <> 0) and (b[a[u]^[v]] = 0) then
begin
C := Dembac(a[u]^[v]);
if tg > C then tg := C;
end;
Bacnhonhat := tg;
end ;

(Xin các bạn xem kỹ cài đặt ở sau để hiểu rõ, ở đây chỉ minh họa đó là dùng biến C để lưu kết quả của hàm Dembac(u) tránh gọi lại nó hai lần).

Cải tiến 5:
ở cuối bài viết, tác giả có nêu ra là trong trường hợp không có đường đi thì chưa xử lý được thì trong bài này chúng ta sẽ sử dụng thêm một biến đó là biến thời gian, và ta dùng cận này để đánh giá. Khi chương trình của chúng ta chạy quá cận thời gian cho phép thì ta dừng ngay chương trình và thông báo là không có đường đi. Điều này cũng dể hiểu bởi chương trình cài đặt của chúng ta có thể chạy khá nhanh trong trường hợp có nghiệm và kích thước bàn cờ lên tới 100 x 100. Tôi cũng xin lưu ý khi các bạn đặt cận thời gian nên để hợp lý (khoảng 6s, tuỳ theo cấu hình máy của bạn. Với cấu hình của máy tôi: PIV, 1.70Ghz thì chỉ cần đặt cận là 3.5s là đủ) để đảm bảo tính chính xác, tốt nhất là xét với trường hợp kích thước bàn cờ là 100 x 100, ô xuất phát là ô (1, 1) và lấy đó là cận.

Dưới đây là toàn bộ phần cài đặt chương trình:

{$S-}
{$M 65520,0,655360}
program Bai_toan_ma_di_tuan;
const
fi = 'ma.inp ';
fo = 'ma.out ';
max = 100;

type
TArr = array [1..8] of integer;
var
b : array [1..max * max] of integer;
a : array [1..max * max] of ^TArr;
n, x, y, count : integer;
L : longint;

function kt(u, v : integer) : boolean;
var
x1, y1, x2, y2 : integer;
begin
x1 := (u - 1) div n + 1;
y1 := (u - 1) mod n + 1;
x2 := (v - 1) div n + 1;
y2 := (v - 1) mod n + 1;

kt := (abs(x1 - x2) * abs(y1 - y2) = 2);
end;

procedure init;
var
u, i, m1, m2 : integer;
j : byte;
begin
for i := 1 to n * n do
begin
new(a[i]);
fillchar(a[i]^, sizeof(a[i]^), 0);
end;
for u := 1 to n * n do
begin
if u - 2 * n - 1 < 0 then m1 := 0
else m1 := u - 2 * n - 1;
if u + 2 * n + 1 > n * n then m2 := n * n
else m2 := u + n * 2 + 1;
j := 0;
for i := m1 to m2 do
if kt(u, i) then
begin
inc(j);
a[u]^[j] := i;
end;
end;
end;

function Dembac(u : integer) : byte;
var
v : integer;
dem : byte;
begin
dem := 0;
for v := 1 to 8 do
if (a[u]^[v] <> 0) and (b[a[u]^[v]] = 0) then inc(dem);

Dembac := dem;
end;

function Bacnhonhat(u : integer) : byte;
var
v : integer;
tg, C : byte;
begin
tg := 100;
for v := 1 to 8 do
if (a[u]^[v] <> 0) and (b[a[u]^[v]] = 0) then
begin
C := Dembac(a[u]^[v]);
if tg > C then tg := C;
end;

Bacnhonhat := tg;
end;

{thu tuc nay dung chuong trinh khi thoi gian cho phep chay chuong trinh de
tim ra nghiem bi vuot qua}

procedure Error;
begin
writeln('No solution');
halt;
end;

procedure PrintResult;
var
i, j : integer;
begin
for i := 1 to n * n do
if i mod n = 0 then writeln(b[i] : 5)
else write(b[i] : 5);
writeln('Time : ', (MemL[0 : $46C] - L)/18.21 : 3 : 1);
close(output);
halt;
end;

procedure dat(u : integer);
var
v : byte;
begin
if (MemL[0 : $46C] - L)/18.21 > 3 then Error;
for v := 1 to 8 do {xet tat ca cac dinh den duoc tu dinh u}
if (a[u]^[v] <> 0) and (b[a[u]^[v]] = 0) and (Dembac(a[u]^[v]) = Bacnhonhat(u)) then
begin
inc(count);
b[a[u]^[v]] := count;
if count = n * n then PrintResult
else dat(a[u]^[v]);
dec(count);
b[a[u]^[v]] := 0;
end;
end;

begin
assign(input, fi);
reset(input);
assign(output, fo);
rewrite(output);
readln(n, x, y);
L := MemL[0 : $46C];
Init;
x := (x - 1) * n + y;
b[x] := 1;
count := 1;
dat(x);
close(input);
close(output);
end .

II. ứng dụng của thuật giải này vào bài toán tìm đường đi Hamilton
Bài toán phát biểu một cách đơn giản như sau:

Cho đồ thị G với n đỉnh và có một số cạnh nối hai đỉnh. Xuất phát từ 1 đỉnh, hãy tìm một đường đi đi qua tất cả các đỉnh của đồ thị. Đường đi tìm được chính là đường đi Hamilton.

Chúng ta có thể liên hệ bài toán này với thuật toán đã sử dụng để giải bài toán mã đi tuần để giải bài này. Tuy nhiên bài này có phần đơn giản hơn đó là giải với đồ thị, khác với bài trên đó là bài toán mã đi tuần phải biểu diễn bàn cờ bằng đồ thị. Bài toán tìm đường đi Hamilton vẫn thường được giải bằng đệ quy quay lui, và tất nhiên với cách bình thường thì yêu cầu khi số đỉnh của đồ thị lớn là không thể.

Vậy tôi xin trình bày với các bạn lại thuật toán cơ sở để giải bài mã đi tuần đã nói và bài đường đi Hamilton như sau: Với một đỉnh u bất kì, xét tất cả các đỉnh kề với nó và chọn ra đỉnh mà có bậc nhỏ nhất để xét tiếp, cứ như vậy cho đến khi tìm ra đường đi hoặc thông báo là không có. Cài đặt của bài này có phần đơn giản hơn bài trên, tôi xin phép không trình bày. Bạn nào cần thiết chương trình xin liên hệ với tác giả qua email. Mong nhận được ý kiến của các bạn đọc.

[rox_rook]

Thanks Hailoc nhiều lắm! Những bài viết này rất có ích^^ con Knight này đúng là giải bằng backtrack chạy hết tất cả trường hợp thì lâu dã man! máy mình AMD 42+ mà hơn 5 phút, hic hic
Đây là code giải bằng backtrack mình phải dùng getch() để giữ lại ! không biết enter tới chừng nào mới xong đây !

#include<iostream>
#include<iomanip>
#include<conio.h>


using std::cout;
using std::endl;
using std::setw;
using std::cin;

  
  const int size = 8;
  void initialization();
  void print();
  void Knight ( int times, int row, int col );
 
  int K[size][size];
  bool check( int row, int col);
  int move_col[] = {-2, -1, +1, +2, +2, +1, -1, -2};
  int move_row[] = {+1, +2, +2, +1, -1, -2, -2, -1};
  int count,index;
 
void initialization()
{
    count = 0;
   
    for ( int i=0; i < size; i++)
    {
        for ( int j=0; j < size; j++)
        {
            K[i][j] = 0;
        }
    }
}
 
 
bool check ( int row, int col )
{
    if ( row > 7 || row < 0 || col > 7 || col < 0 || K[row][col] != 0 )
        return false;
    else
        return true;
}
 
void print()
{
    index++;
    cout << " Let's go Knight ^^" << endl;
    cout << " The : "<< index << "th"<< endl;
    for ( int i = 0; i < size; i++ )
    {
        for ( int j = 0; j < size; j++ )
        {
              cout << setw(3) << K[i][j] ;
        }
                cout << endl;
    }
}
void Knight ( int times, int row, int col)
{
        int next_row, next_col;
        K[row][col] = times + 1; 
        
 
        if ( times >=63 )
        {
                cout << "-----------------------" << endl;
                print();
                getch();
        }
        else
        {
                for ( int i = 0; i < size; i++ )  
                {		
                        next_col = col + move_col[i];
                        next_row = row + move_row[i];
 
                      if (check( next_row,next_col ))
                       { 
                           Knight (times+1, next_row, next_col);
                       }
 
                } 
        }                 
        K[row][col] = 0;
}                  
void main()
{
   initialization();
   Knight (0,0,0);

getch();
}

[rox_rook]

Knight Tour dùng giải thuật Heuristic :

#include<iostream>#include<iomanip>using namespace std; const int _mSize = 8;void PossibleAprroach();void HeuristicApproach(int, int &, int &);void ShowBoard(ostream &);const int ver[] = {-1, -2, -2, -1, +1, +2, +2, +1},          hor[] = {+2, +1, -1, -2, -2, -1, +1, +2};  int board[_mSize][_mSize],    nextStep[8][8][8],    accessibleStep[8][8]; int main(){    int _mRow, _mCol;    int count = 1;    cout << "Starting position [from (0,0) to (7,7)]: ";    cin >> _mRow >> _mCol;    cout << endl;    board[_mRow][_mCol] = count;    while(count != _mSize * _mSize){        count++;        PossibleAprroach();        HeuristicApproach(count, _mRow, _mCol);        for(int dx = 0; dx <= 7; ++dx)        {            for(int dy = 0; dy <= 7; ++dy)                cout <<  setw(3) << accessibleStep[dx][dy];            cout << "\t";            for(int pos = 0; pos <= 7; ++pos)                cout <<  setw(3) << board[dx][pos];            cout << "\n\n";        }        cout << "\n\n";         }    ShowBoard(cout);    return 0;} void ShowBoard(ostream &oss){    cout << "Successfully Heuristic Approach.\n\n";    for(int x = 0; x < _mSize; ++x)    {        for(int y = 0; y < _mSize; ++y)            oss <<  setw(3) << board[x][y];        oss << "\n\n";    }} void PossibleAprroach(){    int update_position;    for(int dx = 0; dx < _mSize; ++dx)    {        for(int dy = 0; dy < _mSize; ++dy)        {            update_position = 0;            for(int position = 0; position <= 7; position++)            {                if(((dx + ver[position] >= 0) && (dx + ver[position] <= _mSize-1))                    &&((dy + hor[position] >= 0) && (dy + hor[position] <= _mSize-1))                    &&(board[dx + ver[position]][dy + hor[position]] == 0))                {                    nextStep[dx][dy][update_position] = position;                    update_position++;                }            }            accessibleStep[dx][dy] = update_position;           }    }} void HeuristicApproach(int position, int &_mRow, int &_mCol){    int min_step = accessibleStep[_mRow + ver[nextStep[_mRow][_mCol][0]]][_mCol + hor[nextStep[_mRow][_mCol][0]]];    int r = _mRow + ver[nextStep[_mRow][_mCol][0]],        c = _mCol + hor[nextStep[_mRow][_mCol][0]];     for(int i = 1; i < accessibleStep[_mRow][_mCol]; ++i)    {        if(min_step >= accessibleStep[_mRow+ver[nextStep[_mRow][_mCol][i]]][_mCol + hor[nextStep[_mRow][_mCol][i]]] )        {            min_step = accessibleStep[_mRow + ver[nextStep[_mRow][_mCol][i]]][_mCol + hor[nextStep[_mRow][_mCol][i]]];            r = _mRow + ver[nextStep[_mRow][_mCol][i]];            c = _mCol + hor[nextStep[_mRow][_mCol][i]];         }                cout << "\n min step = " << min_step << " ("              << r << ',' << c << ") \n";    }       board[r][c] = position;    _mRow = r;    _mCol = c;}