Mô Phỏng Thuật Toán N Quân Hậu

Nếu bạn là người chưa nghe qua thuật ngữ “Thuật toán N quân hậu”, hoặc chưa biết thuật toán đó hoạt động như thế nào, thì hôm nay trong bài viết này mình sẽ chia sẻ cho các bạn hiểu về thuật toán này bằng một chương trình mô phỏng dễ hiểu

Thuật toán N quân hậu là gì?

Thuật toán N quân hậu là gì ?
Như các bạn đã biết thì một quân hầu trên bàn cờ hoàn toàn có thể vận động và di chuyển theo hàng ngang, cột dọc và 2 đường chéo .

Bài toán được đặt ra như sau : Cho một bàn cờ có size NxN ( N ≥ 1 ), Bạn hoàn toàn có thể đặt đúng N quân hậu lên bàn cờ ( mỗi ô chỉ chứa tối đa một quân hậu ), hãy đưa ra cách đặt N quân hậu sao cho không có 2 quân hậu nào ăn được nhau, nói cách khác là trên mỗi hàng, một cột, mỗi đường chéo của bàn cờ chỉ chứa tối đa một quân hậu .
Ví dụ với N = 4 thì có 2 cách đặt thỏa mãn nhu cầu như sau :

Thuật toán giải bài toán N quân hậu

Nhận xét bài toán : Chúng ta cần đặt N quân hậu sau cho trên mỗi hàng, một cột, mỗi đường chéo của bàn cờ chỉ chứa tối đa một quân hậu, như vậy trên mỗi hàng sẽ có đúng 1 quân hậu được đặt, ta sẽ đánh số quân hậu đặt trên hàng i là quân thậu thứ i .
Như vậy tất cả chúng ta hoàn toàn có thể làm như sau :
Xét toàn bộ các trường hợp đặt quân hậu của thứ nhất ( có N trường hợp ), với mỗi trường hợp đặt quân hậu thứ nhất, ta xét các cách đặt quân hậu thứ 2, Q. hậu thứ 2 cũng cũng hoàn toàn có thể đặt ở N ví trị trên hàng thứ 2, nhưng nó phải tránh mặt sau cho không bị quân hậu thứ nhất ăn được nó, … với quân hậu thứ i nó cũng sẽ có N cách đặt, và nó cũng phải tránh mặt những ô mà i – 1 quân hậu trước đó hoàn toàn có thể ăn được nó. Như vậy tất cả chúng ta hoàn toàn có thể hình dùng là ta sẽ dùng N vòng for lồng nhau, với mỗi vòng for sẽ tìm chỉ số cột của quân hậu đó, để làm được việc này thì sử dụng đệ quy quay lui là hài hòa và hợp lý .

Cách kiểm tra một ô vuông có nằm trong tầm ngắm của các quân hậu trước đó hay không:

• Sử dụng mảng boolean c để đánh dấu các cột của bàn cờ (c[i] = true nếu trên cột i chưa đặt quân hậu nào)
• Sử dụng màng bool c1 để đánh dấu các đường chéo song song với đường chéo chính của bạn cờ (c[i – j + N -1] = true, nghĩa là đường chéo đi qua ô(i, j) và song song với đường chéo chính chưa được đặt quân hậu nào.
• Sử dụng màng bool c2 để đánh dấu các đường chéo song song với đường chéo phụ của bạn cờ (c[i + j – 2] = true, nghĩa là đường chéo đi qua ô(i, j) và song song với đường chéo phụ chưa được đặt quân hậu nào.

Sau tìm xong vị trí của quân hậu thứ N thì ta lưu output đó lại .
Hàm đệ quy được viết như sau :

bool check(int i, int j) {
    if (c[j] == false || c1[i - j + N - 1] == false || c2[i + j - 2] ==  false)
        return false;
    return true;
}

void NQueen(int i) {
    for (int j = 1; j <= N; j++)
        if (check(i, j)) {
            x[i] = j;
            c[j] = c1[i - j + N - 1] = c2[i + j - 2] = false;
            if (i == N)
                a.push_back(x);
            else
                NQueen(i + 1);
            c[j] = c1[i - j + N - 1] = c2[i + j - 2] = true;
        }
}

Các bạn hoàn toàn có thể xem full source code tại đây .

Mô phỏng thuật toán N quân hậu

Để mô phỏng thuật toán này mình đã sử dụng java swing, giao diện chính của phần này sẽ như thế này :

Tại mỗi bước tìm vị trị của của các quân cờ ta sẽ cập nhật là bàn cờ, nhưng quá trình cập nhật bàn cờ lien tục như thế sẽ rất mất thời gian nên mình chỉ cập nhật những ô nào thay đổi sau mỗi bước, mình đã sử dụng lớp Timer để dễ dừng lại khi cập nhật sau mỗi bước hơn.

		timer = new Timer(delay, new ActionListener() {
			public void actionPerformed(ActionEvent e) {
				if (k == K) {
					Vector v = new Vector();
					if (!st.empty())
						v = st.peek();
					int I = (int)v.get(0);
					int J = (int)v.get(1) + 1;
					if (J > 1) {
						bt[I][J - 1].setBackground(Color.white);
						cl[I][J - 1] = 0;
						seticonSquar(I, J - 1);
						J--;
						if (Q[I][J] == 1) {
							c[J] = c1[I - J + N] = c2[I + J - 2] = true;
							Q[I][J] = 0;
							cl[I][J] = 0;
						}
						J++;
					}
					if (J == N + 1 ) {
						st.pop();
						if (st.empty())
							timer.stop();
					} else {
						v.set(1, J);
						bt[I][J].setBackground(Color.green);
						if (check(I, J)) {
							Q[I][J] = cl[I][J] = 1;
							seticonSquar(I, J);
							c[J] = c1[I - J + N] = c2[I + J - 2] = false;
							Vector vv = new Vector();
							vv.add(I + 1);
							vv.add(0);
							st.pop();
							st.push(v);
							if (I == N) {
								Stack> ST = st;
								tf.setText(tf.getText() + (count++) + ": " + getChess(ST) + "\n");
								k = 0;
//								timer.stop();
							} else {
								st.push(vv);
							}
						} else {
							cl[I][J] = 2;
							seticonSquar(I, J);
						}
					}
				}
				else k++;
			}
		});

	public String getChess(Stack> stt) {
		Vector> Vec = new Vector();
		String s = "";
		while (!stt.empty()) {
			Vector v = stt.pop();
			Vec.add(v);
			int I = (int) v.get(0);
			int J = (int) v.get(1);
			s = " ("  + I + ", " + J + ") " + s;
		}
		for (int i = Vec.size() - 1; i >= 0; i--)
			stt.add(Vec.elementAt(i));
		return s;
	}

Các bạn hoàn toàn có thể tìm hiểu thêm full source Tại đây .
Video demo :

Source: https://vh2.com.vn
Category : Tin Học