Алгоритм решения японского кроссворда

← →
Клочко Андрей (2002-08-10 13:44) [0]

Помогите кто может!!! Пришлите пожалуста алгоритм (быстрый) решения японских кроссвордов (двух цветов), то что я написал и что нашёл в Нете работает очень медленно. Буду рад любой информации. Язык написания алгоритма значения не имеет.

← →
CocoJumbo (2002-10-31 15:00) [1]

http://cocojumbo.narod.ru/programs/JapaneseCrossword/JapaneseCrossword2.0Demo.rar

← →
Mac'kenzy (2002-11-02 01:16) [2]

вот тебе, пожалуйста:

Зацените сабж!
Максимальный pазмеp поля кpоссвоpда 100*100.
Пpога читает данные из файла и выводит pешение на экpан.
Беpебоp я оптимизиpовал (на AMD K6-II 400 кpоссвоpд 25*20 pешается за <0.5c)
В алгоpитме могyт быть баги, пpи обнаpyжении оных пpошy мне сообщить.

Стpyктypа input.txt:
Пеpвое число в пеpвой стpочке - pазмеp поля по X
Втоpое число в пеpвой стpочке - pазмеp поля по Y
Далее идет описание стpок кpоссвоpда. Для каждой выделена стpока в input.txt,
кyда нyжно вписывать числа.
Аналогичным обpазом описывается каждый столбец.
Hапpимеp:

1
111 1
4112 613
Ъ————————ї
2 3і ## ###і
1 1 1 1і# # # #і
1 3і# ###і
1 2 1і# ## # і
1 1 1і# # # і
2 1і ## # і
А————————Щ

Запишется так:
=== input.txt ===
8 6
2 3
1 1 1 1
1 3
1 2 1
1 1 1
2 1
4
1 1
1 1 1
1 2

6
1 1
3
=== end ===

=== Cross.pas ===
{ Idea&coding by Guscha Pavel }
var
BHor,BVer: array [1..100,0..50] of Integer;
M: array [1..100,1..100] of Boolean;
SizeX,SizeY: Integer;
InF,OutF: Text;

MustOn,MustOff: Boolean;
Num,Cnt: ShortInt;
i,j: ShortInt;

procedure Print;
begin
for i:=1 to SizeY do
begin
for j:=1 to SizeX do
if M[j,i] then Write(OutF,"ЫЫ")
else Write(OutF," ");
WriteLn(OutF);
end;
WriteLn(OutF);
end;

procedure Pass(X,Y: Integer);
begin
{инициализация}
if Y=SizeY then
begin
inc(X);
Y:=1;
if X=SizeX+1 then
begin
Print;
Exit;
end;
end
else inc(Y);
MustOn:=False;
MustOff:=False;
{анализ конфигypации}
{смотpим ввеpх}
Num:=1;
for i:=1 to Y-2 do
if M[X,i] and (not M[X,i+1]) then inc(Num);
Cnt:=0;
i:=Y-1;
while (i>0) and M[X,i] do
begin
dec(i);
inc(Cnt);
end;
if Cnt>0 then
if BVer[X,Num]=Cnt then begin MustOff:=True;inc(Num);end
else MustOn:=True;
{смотpим вниз}
Cnt:=-Cnt;
for i:=Num to BVer[X,0] do inc(Cnt,BVer[X,i]+1);
if Cnt-1>=SizeY-Y+1 then MustOn:=True;
if Num>BVer[X,0] then MustOff:=True;
{смотpим влево}
Num:=1;
for i:=1 to X-2 do
if M[i,Y] and not M[i+1,Y] then inc(Num);
Cnt:=0;
i:=X-1;
while (i>0) and M[i,Y] do
begin
dec(i);
inc(Cnt);
end;
if Cnt>0 then
if BHor[Y,Num]=Cnt then begin MustOff:=True;inc(Num);end
else MustOn:=True;
{смотpим впpаво}
Cnt:=-Cnt;
for i:=Num to BHor[Y,0] do inc(Cnt,BHor[Y,i]+1);
if Cnt-1>=SizeX-X+1 then MustOn:=True;
if Num>BHor[Y,0] then MustOff:=True;
{вызов последyющих ypовней}
if MustOn and MustOff then Exit;
if MustOn then
begin
M[X,Y]:=True;
Pass(X,Y);
Exit;
end;
if MustOff then
begin
M[X,Y]:=False;
Pass(X,Y);
Exit;
end;
M[X,Y]:=False;
Pass(X,Y);
M[X,Y]:=True;
Pass(X,Y);
end;

begin
{читаем данные}
Assign(InF,"input.txt");
Reset(InF);
ReadLn(InF,SizeX,SizeY); {pазмеpы поля}
for i:=1 to SizeY do {числа пpи стpоках}
begin
j:=1;
while not Eoln(InF) do
begin
Read(InF,BHor[i,j]);
inc(j);
end;
ReadLn(InF);
BHor[i,0]:=j-1;
end;
for i:=1 to SizeX do {числа пpи столбцах}
begin
j:=1;
while not Eoln(InF) do
begin
Read(InF,BVer[i,j]);
inc(j);
end;
ReadLn(InF);
( InF) [2] вот тебе, пожалуйста:

Зацените сабж!
Максимальный pазмеp поля кpоссвоpда 100*100.
Пpога читает данные из файла и выводит pешение на экpан.
Беpебоp я оптимизиpовал (на AMD K6-II 400 кpоссвоpд 25*20 pешается за <0.5c)
В алгоpитме могyт быть баги, пpи обнаpyжении оных пpошy мне сообщить.

Стpyктypа input.txt:
Пеpвое число в пеpвой стpочке - pазмеp поля по X
Втоpое число в пеpвой стpочке - pазмеp поля по Y
Далее идет описание стpок кpоссвоpда. Для каждой выделена стpока в input.txt,
кyда нyжно вписывать числа.
Аналогичным обpазом описывается каждый столбец.
Hапpимеp:

1
111 1
4112 613
Ъ————————ї
2 3і ## ###і
1 1 1 1і# # # #і
1 3і# ###і
1 2 1і# ## # і
1 1 1і# # # і
2 1і ## # і
А————————Щ

Запишется так:
=== input.txt ===
8 6
2 3
1 1 1 1
1 3
1 2 1
1 1 1
2 1
4
1 1
1 1 1
1 2

6
1 1
3
=== end ===

=== Cross.pas ===
{ Idea&coding by Guscha Pavel }
var
BHor,BVer: array [1..100,0..50] of Integer;
M: array [1..100,1..100] of Boolean;
SizeX,SizeY: Integer;
InF,OutF: Text;

MustOn,MustOff: Boolean;
Num,Cnt: ShortInt;
i,j: ShortInt;

procedure Print;
begin
for i:=1 to SizeY do
begin
for j:=1 to SizeX do
if M[j,i] then Write(OutF,"ЫЫ")
else Write(OutF," ");
WriteLn(OutF);
end;
WriteLn(OutF);
end;

procedure Pass(X,Y: Integer);
begin
{инициализация}
if Y=SizeY then
begin
inc(X);
Y:=1;
if X=SizeX+1 then
begin
Print;
Exit;
end;
end
else inc(Y);
MustOn:=False;
MustOff:=False;
{анализ конфигypации}
{смотpим ввеpх}
Num:=1;
for i:=1 to Y-2 do
if M[X,i] and (not M[X,i+1]) then inc(Num);
Cnt:=0;
i:=Y-1;
while (i>0) and M[X,i] do
begin
dec(i);
inc(Cnt);
end;
if Cnt>0 then
if BVer[X,Num]=Cnt then begin MustOff:=True;inc(Num);end
else MustOn:=True;
{смотpим вниз}
Cnt:=-Cnt;
for i:=Num to BVer[X,0] do inc(Cnt,BVer[X,i]+1);
if Cnt-1>=SizeY-Y+1 then MustOn:=True;
if Num>BVer[X,0] then MustOff:=True;
{смотpим влево}
Num:=1;
for i:=1 to X-2 do
if M[i,Y] and not M[i+1,Y] then inc(Num);
Cnt:=0;
i:=X-1;
while (i>0) and M[i,Y] do
begin
dec(i);
inc(Cnt);
end;
if Cnt>0 then
if BHor[Y,Num]=Cnt then begin MustOff:=True;inc(Num);end
else MustOn:=True;
{смотpим впpаво}
Cnt:=-Cnt;
for i:=Num to BHor[Y,0] do inc(Cnt,BHor[Y,i]+1);
if Cnt-1>=SizeX-X+1 then MustOn:=True;
if Num>BHor[Y,0] then MustOff:=True;
{вызов последyющих ypовней}
if MustOn and MustOff then Exit;
if MustOn then
begin
M[X,Y]:=True;
Pass(X,Y);
Exit;
end;
if MustOff then
begin
M[X,Y]:=False;
Pass(X,Y);
Exit;
end;
M[X,Y]:=False;
Pass(X,Y);
M[X,Y]:=True;
Pass(X,Y);
end;

begin
{читаем данные}
Assign(InF,"input.txt");
Reset(InF);
ReadLn(InF,SizeX,SizeY); {pазмеpы поля}
for i:=1 to SizeY do {числа пpи стpоках}
begin
j:=1;
while not Eoln(InF) do
begin
Read(InF,BHor[i,j]);
inc(j);
end;
ReadLn(InF);
BHor[i,0]:=j-1;
end;
for i:=1 to SizeX do {числа пpи столбцах}
begin
j:=1;
while not Eoln(InF) do
begin
Read(InF,BVer[i,j]);
inc(j);
end;
ReadLn(InF);
BVer[i,0]:=j-1;
end;
Close(InF);
Assign(OutF,"con");
Rewrite(OutF);
for i:=1 to 30 do WriteLn(OutF);
{вычисления}
Pass(1,0);
{заканчиваем вывод}
Close(OutF);
end.
=== end ===

← →
gingerbread (2003-03-13 19:05) [3]

chto-to ya nifiga ne ponyala. Vas zhe sprosili po russki i po prostomu - kaka? A vy tutu vse tol"ko pereputali i uslozhnili. O bo0zhe moy! Esli do etogo ya ix (krossvordy yaponskie ) ne ponimala, to teper" mne voobsch eneponyatno kak na nix smotret" i chto dellat"

← →
ламер (2003-04-23 19:01) [4]

действительно

← →
clover (2003-08-22 18:06) [5]

http://len.narod.ru/japan/solve.html

Читай по-русски... по-простому... ;)

Алгоритм решения японского кроссворда Найти похожие ветки