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.