Bài toán N-Queen là bài toán đặt N quân hậu lên một bàn cờ NxN sao cho không có hai quân hậu nào đang ở cùng một hàng, cột hoặc đường chéo. Trong Pascal, ta có thể giải quyết bài toán này bằng thuật toán quay lui.
Dưới đây là mã của thuật toán quay lui giải bài toán N-Queen trong Pascal:
procedure NQueen(row: Integer; var count: Integer; board: array of Integer);
var
i, j: Integer;
N: Integer;
ok: Boolean;
begin
N := Length(board);
if row = N then
begin
Inc(count);
WriteLn('Solution ', count, ':');
for i := 0 to N - 1 do
begin
for j := 0 to N - 1 do
begin
if board[i] = j then Write('Q ')
else Write('. ');
end;
WriteLn;
end;
end
else
begin
for i := 0 to N - 1 do
begin
ok := True;
for j := 0 to row - 1 do
begin
if (board[j] = i) or (Abs(board[j] - i) = row - j) then
begin
ok := False;
Break;
end;
end;
if ok then
begin
board[row] := i;
NQueen(row + 1, count, board);
end;
end;
end;
end;
Trong đó, biến row là số hàng hiện tại đang xét, biến count là số lượng giải pháp tìm được, và board là một mảng chứa vị trí của các quân hậu.
Thuật toán sử dụng đệ quy để thử tất cả các cách đặt quân hậu trên bàn cờ. Đối với mỗi hàng, ta duyệt qua tất cả các cột có thể đặt quân hậu. Nếu việc đặt quân hậu vào cột đó không làm xung đột với các quân hậu trước đó, ta đặt quân hậu vào vị trí đó và tiếp tục đệ quy đến hàng tiếp theo. Nếu không có cột nào thỏa mãn, ta quay lại và thử các cột khác.
Khi duyệt đến hàng cuối cùng mà không có xung đột nào xảy ra, ta tăng biến count lên một và in ra giải pháp.
Dưới đây là cài đặt của thuật toán N-Queen trong Pascal với ví dụ N=4:
program NQueenExample;
const
N = 4;
var
count: Integer;
board: array[0..N-1] of Integer;
procedure NQueen(row: Integer; var count: Integer; board: array of Integer);
var
i, j: Integer;
ok: Boolean;
begin
if row = N then
begin
Inc(count);
WriteLn('Solution ', count, ':');
for i := 0 to N - 1 do
begin
for j := 0 to N - 1 do
begin
if board[i] = j then Write('Q ')
else Write('. ');
end;
WriteLn;
end;
end
else
begin
for i := 0 to N - 1 do
begin
ok := True;
for j := 0 to row - 1 do
begin
if (board[j] = i) or (Abs(board[j] - i) = row - j) then
begin
ok := False;
Break;
end;
end;
if ok then
begin
board[row] := i;
NQueen(row + 1, count, board);
end;
end;
end;
end;
begin
count := 0;
NQueen(0, count, board);
if count = 0 then WriteLn('No solutions');
ReadLn;
end.
Kết quả khi chạy chương trình là:
Solution 1:
. Q . .
. . . Q
Q . . .
. . Q .
Solution 2:
. . Q .
Q . . .
. . . Q
. Q . .
Chương trình sẽ in ra hai giải pháp của bài toán N-Queen với bàn cờ có kích thước 4×4.
Wow, awesome weblog format! How long have you ever been blogging
for? you made running a blog glance easy. The overall glance of your web site is
great, as neatly as the content material! You can see similar
here sklep internetowy