recursion (backtracking) problem, knight coverings - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

recursion (backtracking) problem, knight coverings

serxaszserxasz Posts: 2Member
hello everyone,
i have problems with this program and i am praying for your help.
The task is to put given number of knights, on given size chess board, that every square of the board is covered. That is, every square on the board is either occupied by a knight or attacked by a knight. knights can attack each other. the solutions are givven here. [link=http://www.contestcen.com/knight.htm][/link]
i am using recursion. algorithm:
1. choose not occupied square
2. try every knight, which can occupy that square
3. choose another square and so on, till knight max number is reached.
basicly, i try every posibble knight positions.
i wrote program, which is below, but it crashes when i put more than 6 knights, and show nonsense in boards below 6. i know that the problem is in backtracking, when i need to delete a knight. but i dont know how to correct it.
again, praying for your help. Thanks in advance.

[code]program zirgai;
uses crt;
type lenta = array[1..8,1..8] of char;
ejimai = array[1..8] of integer;
var L:lenta;
N,M,Grizti:ejimai;
zirgu_sk,dydis,r:integer;
//******************************//
procedure nulinimas(var L:lenta; d:integer);
var x,y:integer;
begin
for x:=1 to d do
begin
for y:=1 to d do
begin
L[x,y]:='0';
end;
end;
end;
//******************************//
procedure tikrinimas(L:lenta; d:integer; var r:integer);
var x,y:integer;
begin
r:=1;
for x:=1 to d do
begin
for y:=1 to d do
begin
if L[x,y]='0' then begin r:=0; break; end;
end;
if L[x,y]='0' then begin r:=0; break; end;
end;
end;
//******************************//
procedure braizyti(L:lenta; d:integer);
var x1,x2,y1,y2,counter,x,y:integer;
begin
counter:=1;
y1:=1;
y2:=3;
for x:=1 to d do // draws a chess board
begin
x1:=1;
x2:=5;
for y:=1 to d do
begin
window(x1,y1,x2,y2);
if (counter mod 2) = 0 then textbackground(red)
else textbackground(green);
clrscr;
writeln;
writeln(' ',L[x,y]);
counter:=counter+1;
x1:=x1+5;
x2:=x2+5;
end;
y1:=y1+3;
y2:=y2+3;
if (d mod 2) = 0 then counter:=counter+1;
end;
end;
//******************************//
procedure Delioti(zirgas,x,y:integer);
var i,z:integer;
begin
tikrinimas(L,dydis,r);
if r=1 then
begin
writeln('done'); // checks if all sqaures are covered
braizyti(L,dydis);
readln;
exit;
end;
///////////////////////////////////////////////////////////
if (x<>1) and (y<>1) and (zirgas<>0) then
begin
if (x>=1) and (y>=1) and (x<=dydis) and (y<=dydis) then
begin
L[x,y]:='Z'; // puts knight, and marks covered squares
for i:=1 to 8 do
begin
if (x+N[i]>=1) and (y+M[i]>=1) and (x+N[i]<=dydis) and (y+M[i]<=dydis)
and (L[x+N[i],y+M[i]]<>'Z') and (L[x+N[i],y+M[i]]<>'.') then
begin
L[x+N[i],y+M[i]]:='.'; Grizti[i]:=1;
end;
end;
end;
end;

///////////////////////////////////////////////////////////
for x:=1 to dydis do
begin
for y:=1 to dydis do
begin
if (L[x,y]<>'Z') and (L[x,y]<>'.') then break; // finds not occupied square
end;
if (L[x,y]<>'Z') and (L[x,y]<>'.') then break;
end;

if zirgas<=zirgu_sk then
begin
for i:=1 to 8 do // recursion. calls procedure again and again
begin
Delioti(zirgas+1,x+N[i],y+M[i]);
end;
end;
///////////////////////////////////////////////////////////
if (x<>1) and (y<>1) and (zirgas<>0) then
begin
if (x>=1) and (y>=1) and (x<=dydis) and (y<=dydis) then
begin
L[x,y]:='0';
for i:=1 to 8 do
begin
if Grizti[i]=1 then
begin // deletes knight, and his covered squares
L[x+N[i],y+M[i]]:='0';
end;
end;
end;
end;
for z:=1 to 8 do
begin
Grizti[z]:=0;
end;
///////////////////////////////////////////////////////////
end;
//******************************//
begin
N[1]:=1; M[1]:=2;
N[2]:=1; M[2]:=-2;
N[3]:=2; M[3]:=-1;
N[4]:=2; M[4]:=1;
N[5]:=-2; M[5]:=-1;
N[6]:=-2; M[6]:=1;
N[7]:=-1; M[7]:=-2;
N[8]:=-1; M[8]:=2;
for dydis:=1 to 8 do
begin
Grizti[dydis]:=0;
end;
writeln('zirgu skaicius:');
readln(zirgu_sk);
writeln('lentos dydis:');
readln(dydis);
nulinimas(L,dydis); // changes all squares value to '0'
Delioti(0,1,1);
readln;
end.
[/code]

Comments

Sign In or Register to comment.