•
(PFHUWRVFDVRVTXDQGRQmRpFRQKHFLGRQHQK
L WHUDWL Y
([
RpQHFHVVi
DXVWL Y
D %
DFN
UL RJ
WUDFN
HUDUXPS
L QJ
XPDO J
RUL WPR
URFHVVRUHFRUUHQWHGH3
HVTXL VD
2
3
U
RE
O HP
D
GD
5
D
LQKD
V
1
XPWDE
XO HL URGH;
DGUH]
D5
DL QK
DGRPL QDWRGDDO L QK
FRO XQDHDVGXDVGL DJ
RQDL VGDFDVDRQGHHVWL Y
&
DV QmRGRPL QDGDV QXPWDE
DD
HUFRO RFDGD 3
([
U
RPRFRO RFDU
RFHV
V
L VWHP
RGH%
D
FN
5
DL QK
VRO Xo
W U
D
FN
}
HVS
LQJ
RVVt Y
HL V Tentar pôr Rainha na linha (i):
para cada coluna j
se a casa [i, j] estiver livre
pôr Rainha na casa [i, j]
i<8
Tentar pôr Rainha
na linha (i+1)
i=8
Imprimir
Solução
retirar Rainha da casa [i, j]
XO HL UR"
&RPRDVVLQDODUDVFDVDVTXHHVWmRRXQmROLYUHV"
&RQVLG
3
HUHPRVXPFRQM XQWRG
DUDDVFROXQDV RWLS
boolean, RQG H true ⇒ FDVDOLYUH
false ⇒ FDVDG RPLQDG
R
D
var a : array [1..8] of boolean;
3
HYHFWRUHVG
DUDDVG
LDJ
RQDLVDVFHQG
HQWHV
(i+j):
var b : array [2..16] of boolean;
3
DUDDVG
LDJ
RQDLVG
HVFHQG
HQWHV
(i-j):
var c : array [-7..7] of boolean;
2
S
URFHVVRWHQWDVXFHVVLYDPHQWHFRORFDUXPD5
DLQK
DHPFDG
DOLQK
3
DUDUHJ
LVWDUDS
RVLo
mR FROXQD RFXS
DG
DS
RUFDG
var x : array [1..8] of 1..8;
D5
DLQK
DE
DVWD D program OitoRainhas(output);
type linha, coluna = 1..8;
var a : array [coluna] of boolean;
var b : array [2..16] of boolean;
var c : array [-7..7] of boolean;
var x : array [linha] of coluna;
var i : integer;
procedure EscreverSolucao;
begin ... { Como? } ...
end;
procedure Tentar(i : linha);
var j : coluna;
begin for j:= 1 to 8 do
{ Se a casa [i, j] estiver livre }
if a[j] and b[i+j] and c[i-j]
then begin { Pôr Rainha em [i, j] }
x[i]:= j;
a[j]:= false;
b[i+j]:= false;
c[i-j]:= false;
if i < 8
then Tentar(i+1)
else EscreverSolucao;
{ Retirar Rainha de [i, j] }
x[i]:= 0;
a[j]:= true;
b[i+j]:= true;
c[i-j]:= true
end
end { Tentar };
begin for i:= 1
for i:= 2
for i:= -7
for i:= 1
Tentar(1)
end.
to
to
to
to
8
16
7
8
do
do
do
do
a[i]:= true;
b[i]:= true;
c[i]:= true;
x[i]:= 0;
([HUFtFLR&LUFXLWRGH&DYDOR
2XWURSUREOHPDFOiVVLFRDVVRFLDGRDR;DGUH]FRQVLVWH
HP SDUWLQGRGHXPDGDGDFDVDHVHPSUHHP³ 6
&
DY
Vy
Y
DOWRGH
DOR´ SHUFRUUHUFDGDXPDGDVFDVDVGRWDEXOHLURXPD
H] DFDEDQGRQDFDVDLQLFLDO
&
RQVWUXDXPDDERUGDJ
HPGRWLSR³ %
DFN
WUDFN
LQJ
´ SDUD
HVWHSUREOHPD
([HUFtFLR&RORUDo
e
m
RGH0
DS
DV
VDELGR HHVWiM iGHPRQVWUDGR T
VXI LFLHQWHVSDUDFRORULUT
&
XDWURFRUHV
Vm
R
XHUPDSD
RQWXGR RSURFHVVRGHFRORULUXPGDGRPDSDFRP
T
&
XDOT
XHT
XDWURFRUHVp
XP3
UREOHPDT
RQVWUXDXPDDERUGDJ
HVWHSUREOHPD
XHVHGHPRQVWUDVHUGLI tFLO
HPGRWLSR³ %
DFN
WUDFN
LQJ
´ SDUD