---
author: nguyencter
tags: NQUEEN2
title: NQUEEN2 Solution
---

$\Huge\text{NQUEEN2 Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/1hd2nVEXdIBanfRu1fT2Gy_Ypv255BVP2/view?usp=sharing)
📌 Tags: `back tracking` `brute force`
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::

-----

## Giới Thiệu Đề Bài

Cho $1$ bàn cờ vua $n*n$ ô và $n$ quân hậu. Cho trước vị trí của một số quân hậu.

**Yêu cầu:** Tìm cách xếp các quân hậu còn lại sao cho không có hai quân hậu nào chiếu nhau.

-----

## Thuật toán

Với mỗi hàng ta chỉ được đặt một quân hậu nên ta duyệt qua tất cả trường hợp đặt quân hậu trên một hàng.

Mỗi lượt ta chọn hàng chưa được đặt hậu và có ít ô chưa bị chiếu nhất để đặt hậu tránh trường hợp cấu hình đang xét là sai mà vẫn duyệt.

Nếu có nhiều hàng có cùng số chưa ô bị chiếu là ít nhất thì chọn hàng có thứ tự bé nhất.

Độ phức tạp là $O(n!)$ nhưng cách duyệt theo như trên nên vẫn đủ thời gian.

----
Tham khảo code mẫu ở [đây](https://github.com/nguyencter/CODE/blob/main/NQUEEN2.cpp).