 |
© Иван Рощин, Москва
| ZXNet | : 500:95/462.53 |
| : bestview@mtu-net.ru | |
| WWW | : http://www.ivr.da.ru |
(«Радиомир. Ваш
компьютер» 2/2003)
Дата последнего редактирования: 8.03.2003.
Японские кроссворды (их ещё называют «японские сканворды», «японские картинки») — сравнительно недавно появившийся вид головоломок, стремительно набирающий популярность. В этой статье я хочу предложить вашему вниманию программу, которая поможет как решать такие кроссворды, так и создавать их.
Если вы до сих пор не знали, что из себя представляют японские кроссворды, то сейчас узнаете. :–) А если знаете, то всё равно прочтите этот раздел: здесь я введу термины, которые будут использованы в дальнейших рассуждениях.
В японских кроссвордах нужно отгадывать не слова, а прямоугольное
изображение, состоящее из отдельных
Будем в дальнейшем называть строку или столбец кроссворда общим словом «линия».
Группу идущих подряд чёрных клеток в линии, ограниченную с каждой стороны либо пустой клеткой, либо границей кроссворда, будем называть закрашенным участком. Участок может состоять и из единственной клетки.
Так вот, для каждой линии кроссворда приводятся сведения о длине закрашенных участков (в порядке их следования: для строк — слева направо, для столбцов — сверху вниз). По этой информации и нужно разгадать изображение, то есть узнать, какие клетки белые, а какие — чёрные.
Пример японского кроссворда вы можете увидеть на рис. 1.
|
А по какому принципу их решают? Попробуем решить, пока вручную, кроссворд, приведённый на рис. 1.
Данные о первой строке состоят лишь из одной цифры — «1». Это значит, что в этой строке находится одна чёрная клетка, а остальные — белые. Какое именно положение занимает чёрная клетка — пока не ясно.
Во второй строке находится участок из трёх чёрных клеток. Понятно, что, как его ни располагай, центральная клетка обязательно будет чёрной.
В третьей строке два закрашенных участка, из трёх и одной клетки, могут быть расположены единственным возможным образом: так, чтобы между ними находилась одна белая клетка. Итак, об этой строке мы уже знаем всё.
Из четвёртой строки, как и из первой, ничего извлечь не удаётся.
Отобразим выясненную на данный момент информацию (рис. 2). Клетки, про которые точно известно, что они белые, будем отмечать точкой.
 |
Теперь перейдём к столбцам. Положение единственной чёрной клетки в первом столбце нам уже известно. Значит, остальные клетки этого столбца — белые.
Во втором столбце находится чёрный участок из двух клеток. Положение одной из них нам известно. Вторая клетка обязательно должна примыкать к ней сверху или снизу. Следовательно, самая верхняя клетка этого столбца — точно белая.
Из следующих двух столбцов мы ничего сейчас извлечь не можем, а из последнего столбца ясно, что, как ни располагай в нём участок из трёх чёрных клеток, две средние клетки обязательно будут чёрными.
Отобразим то, что нам удалось выяснить (рис. 3).
 |
Снова просмотрим строки кроссворда. Видим, что во второй строке положение закрашенного участка (а значит, и второй белой клетки) полностью определилось. Отмечаем это (рис. 4).
 |
Тогда во втором и четвёртом столбцах положение закрашенных участков тоже однозначно определяется (рис. 5). Остались лишь четыре невыясненных клетки!
 |
При анализе нижней строки определяется положение второго закрашенного участка (рис. 6).
 |
Ну а третий и пятый столбцы теперь тоже можно однозначно определить (рис. 7).
 |
Всё, кроссворд решён! Ну а то, что в получившейся картинке не видно
Как видим, при решении японского кроссворда мы, получив некоторые сведения о строках, используем их для выяснения информации о столбцах, и наоборот. В этом японские кроссворды похожи на обычные, в которых отгаданные слова по горизонтали дают информацию для отгадывания пересекающихся с ними слов по вертикали, и наоборот.
А теперь рассмотрим, как решать кроссворды (и создавать собственные) уже не вручную, а с использованием моей программы.
После запуска вы увидите на экране меню из пяти пунктов:
1. Resolve new crossword 2. Resolve old crossword 3. Test picture 4. View data 5. Exit |
Для решения нового кроссворда выбирайте первый пункт. Сначала программа предложит вам ввести размеры кроссворда: ширину (от 1 до 62 клеток) и высоту (от 1 до 42). При необходимости кроссворд можно повернуть на 90 градусов, поменяв при этом информацию о строках и столбцах.
Затем надо ввести информацию о закрашенных участках: сначала о строках (они нумеруются сверху вниз), а потом о столбцах (нумеруются слева направо). Номер текущей вводимой строки (столбца) отображается на экране.
Длины закрашенных участков перечисляются через запятую; если
Уже введённая информация печатается в верхней части экрана, при этом через каждые пять строк выводится разделительная черта — это помогает не перепутать, информацию о какой линии кроссворда вы вводите (в сетке «бумажного» кроссворда через каждые пять клеток разделяющая их линия изображается более жирной).
На рис. 8 показано, как выглядит экран при вводе данных.
 |
Программа проверяет, являются ли корректными введённые пользователем данные о линии кроссворда. Должно выполняться следующее условие: сумма длин всех закрашенных участков и минимальных промежутков между ними (напомню, что два соседних закрашенных участка должны быть разделены как минимум одной белой клеткой) должна быть не больше длины линии.
Минимальное количество белых клеток, очевидно, на единицу меньше числа закрашенных участков. Тогда данное ограничение можно записать так:
| n | ai + n–1 <= l, |
+--- \ / +--- |
|
| i = 1 |
| где | n — количество закрашенных участков, |
| ai — длина |
|
| l — длина линии. |
То есть, например, если длина линии 8 клеток, и вы вводите информацию о закрашенных участках: «1,4», то всё в порядке: (1+4)+1<8. А если при вводе клавиша «1» случайно была нажата дважды, и оказалась введена строка «11,4», то программа укажет на некорректность введённых данных: ведь (11+4)+1>8.
При обнаружении ошибки программа предложит повторно ввести информацию о линии кроссворда.
После ввода всех данных производится ещё одна проверка. Смотрите: если сложить длины всех закрашенных участков в строках, то мы получим, очевидно, общее количество чёрных клеток в кроссворде. Но точно такое же значение должно получиться и при суммировании длин закрашенных участков в столбцах! А если они не совпадают — значит, при вводе допущена ошибка. В этом случае придётся вводить данные заново.
При такой проверке всегда обнаруживается одиночная ошибка вида
«пропущено число», «введено лишнее число»,
«введено неправильное число». Да и если таких ошибок несколько,
вероятность того, что они взаимно компенсируют друг друга, невелика. А вот
если вы при вводе случайно поменяете
Если данные успешно прошли первичную проверку на корректность, программа выдаст приглашение: «Press any key…». После нажатия любой клавиши начнётся процесс решения кроссворда.
Информация о ходе решения отображается на экране в таком же виде, как если бы вы решали кроссворд на бумаге. Если клетка кроссворда изображена белой — значит, информация о ней не известна; если в клетке стоит точка — значит, эта клетка точно белая; если клетка изображена чёрной — значит, она чёрная. :–)
Точки, расположенные на левой и верхней сторонах кроссворда, служат признаком того, что соответствующие линии кроссворда помечены для последующего просмотра. Сначала помечены все линии.
При решении кроссворда программа последовательно просматривает все помеченные строки и столбцы. Точка напротив текущей просматриваемой линии изображается более жирной.
При просмотре линии, возможно, становится известной информация о некоторых
её клетках. Если стало известно, что
Когда при просмотре строки становится известна информация о некоторых её клетках, то столбцы, где расположены эти клетки, помечаются. Аналогично, когда при просмотре столбца становится известна информация о некоторых его клетках, то строки, где расположены эти клетки, помечаются.
После просмотра линии точка напротив неё исчезает, т.е. пометка с этой линии снимается.
Процесс последовательного просмотра помеченных линий продолжается до тех пор, пока не станет известна информация о всех клетках кроссворда, то есть пока кроссворд не будет решён.
На рис. 9 вы можете увидеть несколько скриншотов, сделанных в процессе решения кроссворда.
 |
 |
 |
При нормальном завершении вы увидите на экране изображение решённого кроссворда (рис. 10), а затем (после нажатия любой клавиши) — время, потраченное на решение. После ещё одного нажатия любой клавиши программа выйдет в главное меню.
 |
Теперь обратим внимание вот на что: даже если данные кроссворда успешно прошли первичную проверку на корректность, этот кроссворд может и не иметь решения. Простейший пример такого кроссворда вы можете увидеть на рис. 11.
 |
В таком случае при решении кроссворда рано или поздно обнаружится противоречие. Для примера на рис. 11: при анализе первой (и единственной) строки получаем, что средняя клетка будет чёрной, а при анализе второго столбца — что она должна быть белой.
Программа, обнаружив такое противоречие, выводит сообщение «Incorrect data!», и после нажатия любой клавиши выходит в главное меню.
Также может быть, что кроссворд имеет несколько решений. На рис. 12 приведён пример кроссворда с тремя различными решениями.
 |
При решении такого кроссворда рано или поздно наступит момент, когда помеченных линий не останется — а кроссворд ещё не будет полностью решён. В этом случае программа выдаст сообщение «Many variants! Continue?» («Много вариантов. Продолжить?»). Если вы ответите «N» («Нет») — программа выйдет в главное меню; если «Y» («Да») — решение кроссворда будет продолжено.
Чтобы программа могла продолжить решение кроссворда, ей необходима дополнительная информация, которую она запросит у вас. Эта информация — цвет первой неизвестной клетки (то есть такой клетки, цвет которой к настоящему моменту не известен; первая такая клетка — та, которая ближе к верхней границе кроссворда, а если таких клеток несколько — та из них, которая ближе к левой границе). Вы можете выбрать, будет ли эта клетка чёрной или белой, ответив на запрос программы («(B)lack or (W)hite?») соответственно «B» или «W».
После этого вы увидите, что соответствующая клетка кроссворда примет выбранный вами цвет. Строка и столбец, где находится эта клетка, будут помечены для дальнейшего анализа, и решение кроссворда продолжится.
Момент, когда мы выбираем, чёрной или белой будет неизвестная клетка, является своеобразной точкой развилки. После него решение кроссворда может пойти по одному из двух возможных путей. На каждом из этих путей, в свою очередь, могут быть другие точки развилки. Получается, таким образом, «дерево решений» кроссворда. На рис. 13 вы можете увидеть, как выглядит дерево решений кроссворда, приведённого на рис. 12.
 |
Учтите, что некоторые ветви дерева решений могут заканчиваться тупиками, т.е. при их рассмотрении программа придёт к противоречию (рис. 14).
 |
Чтобы найти все решения кроссворда, нужно решить его столько раз, сколько ветвей у дерева решений. Для этого при каждом решении выбирайте цвета неизвестных клеток так, чтобы пройти по новому пути. После получения очередного решения (или если выяснилось, что выбранный путь привёл к противоречию), когда программа выйдет в главное меню, выбирайте пункт «Resolve old crossword» («Решить старый кроссворд»), тогда вам не придётся заново вводить информацию о кроссворде.
Теперь о том, как программа поможет вам в составлении собственных кроссвордов. Чтобы составить кроссворд, надо выполнить три шага: нарисовать картинку, получить данные о группах закрашенных участков и проверить, будет ли полученный кроссворд решаться однозначно (иначе тот, кто будет его решать, не узнает, какую именно картинку вы имели в виду). В выполнении всех этих трёх шагов вам поможет компьютер.
Рисовать картинку удобно в графическом редакторе. На ZX Spectrum это может быть, например, Art Studio или BGE. Вам нужно получить файл в стандартном экранном формате, причём картинка должна быть расположена в левом верхнем углу экрана. Каждый пиксел картинки соответствует одной клетке кроссворда.
Для выполнения следующих двух шагов как раз поможет моя программа. Выберите в главном меню пункт «Test picture» и укажите имя файла с картинкой. Программа загрузит картинку, и вы увидите её на экране. Укажите размеры кроссворда. Программа начнёт считывать информацию о пикселах картинки (то есть о клетках кроссворда), при этом обработанные пикселы будут инвертироваться, чтобы вы могли следить за ходом процесса. Затем программа начнёт формировать информацию о закрашенных участках, при этом показывая, сколько процентов информации уже сформировано.
Далее программа начнёт решать кроссворд по этой информации. Если решение однозначно, то после выхода в главное меню вы, выбрав пункт «View data», сможете переписать данные о закрашенных участках на бумажку. :–) Ну а если в процессе решения возникла неоднозначность, значит, картинку надо переделать. В таком случае загружайте графический редактор и — всё сначала…
Небольшой совет: если ваша картинка содержит участки, как на
|
|
Тем не менее, даже если таких участков нет, это ещё ни о чём не говорит (см. рис. 12 — там их нет, а решений несколько). Так что без проверки на однозначность решения всё равно не обойтись.
Программа написана на Бейсике для ZX Spectrum, но её должно быть достаточно легко адаптировать и для другого компьютера.
10 DEF FN M (x,y)=(x+y+ ABS (x-y))/2: REM max(x,y)
20 DEF FN U()= INT ((65536* PEEK 23674+256* PEEK 23673+
PEEK 23672)/50): REM Time Wrong
30 DEF FN T()= FN m( FN u(), FN u()): REM Time Right
40 LET MaxSizeX=62: LET MaxSizeY=42
50 LET MaxSize= FN M(MaxSizeX,MaxSizeY)
60 DIM A(MaxSizeY): DIM B (MaxSizeY, INT ((MaxSizeX+1)/2))
70 DIM C(MaxSizeX): DIM D (MaxSizeX, INT ((MaxSizeY+1)/2))
80 DIM P$ (MaxSizeY,MaxSizeX)
90 DIM E (MaxSizeY): DIM F(MaxSizeX)
100 DIM G$(MaxSize): DIM L$(MaxSize)
110 DIM H ( INT ((MaxSize+1)/2)): DIM P( INT
((MaxSize+1)/2)+1)
120 LET OldData=0
130 BORDER 0: PAPER 0: INK 7: CLS : PRINT "(c) Ivan Roshin,
June 2002": PRINT : PRINT "Japanese Crosswords"
140 PRINT : PRINT "1 - Resolve new crossword": PRINT "2 -
Resolve old crossword": PRINT "3 - Test picture": PRINT "4 -
View data": PRINT "5 - Exit"
150 IF INKEY$ ="1" THEN LET OldData=1: GO TO 210
160 IF ( INKEY$ ="2" AND OldData=1) THEN GO TO 700
170 IF INKEY$ ="3" THEN LET OldData=1: GO TO 740
180 IF ( INKEY$ ="4" AND OldData=1) THEN GO TO 1090
190 IF INKEY$ ="5" THEN CLEAR : STOP
200 GO TO 150
210 REM * Resolving crossword *
220 GO SUB 1230
230 PRINT : PRINT "Horisontal lines:": PRINT
240 LET CheckSum=0: LET Count5=0
250 FOR i=1 TO SizeY
260 INPUT "Horisontal line ";(i);":",a$
270 LET A(i)=0
280 IF a$="" THEN GO TO 360
290 LET j=1
300 LET A(i)=A(i)+1: LET B(i,j)=0
310 LET B(i,j)=B(i,j)*10+ VAL (a$(1))
320 IF LEN (a$)=1 THEN GO TO 360
330 LET a$=a$(2 TO )
340 IF a$(1)="," THEN LET a$=a$(2 TO ): LET j=j+1: GO TO
300
350 GO TO 310
360 REM *** Check line data ***
370 LET Sum=0
380 IF A(i)=0 THEN GO TO 430
390 FOR j=1 TO A(i)
400 LET Sum=Sum+B(i,j)
410 NEXT j
420 IF (Sum+A(i)-1)>SizeX THEN INPUT "Incorrect data!";a$:
GO TO 260
430 GO SUB 3740: LET CheckSum=CheckSum+Sum
440 NEXT i
450 PRINT : PRINT "Vertical lines:": PRINT
460 LET Count5=0
470 FOR i=1 TO SizeX
480 INPUT "Vertical line ";(i);":",a$
490 LET C(i)=0
500 IF a$="" THEN GO TO 580
510 LET j=1
520 LET C(i)=C(i)+1: LET D(i,j)=0
530 LET D(i,j)=D(i,j)*10+ VAL (a$(1))
540 IF LEN (a$)=1 THEN GO TO 580
550 LET a$=a$(2 TO )
560 IF a$(1)="," THEN LET a$=a$(2 TO ): LET j=j+1: GO TO
520
570 GO TO 530
580 REM *** Check line data ***
590 LET Sum=0
600 IF C(i)=0 THEN GO TO 650
610 FOR j=1 TO C(i)
620 LET Sum=Sum+D(i,j)
630 NEXT j
640 IF (Sum+C(i)-1)>SizeY THEN INPUT "Incorrect data!";a$:
GO TO 480
650 GO SUB 3830: LET CheckSum=CheckSum-Sum
660 NEXT i
670 IF CheckSum=0 THEN GO TO 690
680 PRINT : PRINT "Check sum error!": PAUSE 0: GO TO 120
690 PRINT : PRINT "Press any key...": PAUSE 0
700 GO SUB 1320
710 IF ErrCode=0 THEN CLS : PRINT "Time:
";TimeMin;":";TimeSec: PRINT : PRINT "Press any key...": PAUSE
0: GO TO 130
720 IF ErrCode=1 THEN INPUT "Incorrect data! Press
ENTER.";a$: GO TO 130
730 IF ErrCode=2 THEN GO TO 130
740 REM * Test and make data *
750 GO SUB 1230
760 INPUT "Screen name: ";A$
770 RANDOMIZE USR 15619: REM : LOAD A$ CODE 16384,2048
780 FOR i=1 TO SizeY
790 FOR j=1 TO SizeX
800 IF POINT (j-1,176-i)=0 THEN LET P$(i,j)="1": GO TO 820
810 LET P$(i,j)="0"
820 PLOT OVER 1,j-1,176-i
830 NEXT j
840 NEXT i
850 CLS : PRINT "Making data: 0%"
860 FOR i=1 TO SizeY
870 LET A(i)=0: LET Pos=1
880 IF P$(i,Pos)="1" THEN GO TO 910
890 LET Pos=Pos+1: IF Pos <= SizeX THEN GO TO 880
900 GO TO 950
910 LET A(i)=A(i)+1: LET B(i,A(i))=1
920 LET Pos=Pos+1: IF Pos>SizeX THEN GO TO 950
930 IF P$(i,Pos)="1" THEN LET B(i,A(i))=B(i,A(i))+1: GO TO
920
940 GO TO 890
950 PRINT AT 0,13; INT ((i*100)/(SizeX+SizeY));"%"
960 NEXT i
970 FOR i=1 TO SizeX
980 LET C(i)=0: LET Pos=1
990 IF P$(Pos,i)="1" THEN GO TO 1020
1000 LET Pos=Pos+1: IF Pos <= SizeY THEN GO TO 990
1010 GO TO 1060
1020 LET C(i)=C(i)+1: LET D(i,C(i))=1
1030 LET Pos=Pos+1: IF Pos>SizeY THEN GO TO 1060
1040 IF P$(Pos,i)="1" THEN LET D(i,C(i))=D(i,C(i))+1: GO TO
1030
1050 GO TO 1000
1060 PRINT AT 0,13; INT (((i+SizeY)*100)/(SizeX+SizeY));"%"
1070 NEXT i
1080 GO TO 700
1090 REM *** View data ***
1100 CLS
1110 PRINT "Horisontal lines:": PRINT
1120 LET Count5=0
1130 FOR i=1 TO SizeY
1140 GO SUB 3740
1150 NEXT i
1160 PRINT : PRINT "Vertical lines:": PRINT
1170 LET Count5=0
1180 FOR i=1 TO SizeX
1190 GO SUB 3830
1200 NEXT i
1210 PRINT : PRINT "Press any key..."
1220 PAUSE 0: GO TO 130
1230 REM **** Input X and Y ****
1240 CLS
1250 INPUT "X size (1-";(MaxSizeX);"): ";SizeX
1260 IF ((SizeX < 1) OR (SizeX > MaxSizeX)) THEN GO TO 1250
1270 PRINT "X size:";SizeX
1280 INPUT "Y size (1-";(MaxSizeY);"): ";SizeY
1290 IF ((SizeY < 1) OR (SizeY > MaxSizeY)) THEN GO TO 1280
1300 PRINT "Y size:";SizeY
1310 RETURN
1320 REM ****** Resolving ******
1330 CLS
1340 PLOT 0+4,175-4: DRAW SizeX*4+2,0: DRAW 0,-SizeY*4-2:
DRAW -SizeX*4-2,0: DRAW 0,SizeY*4+2
1350 FOR i=174 TO 174-SizeY*4+1 STEP -1
1360 PLOT 1+4,i-4: DRAW SizeX*4-1,0
1370 NEXT i
1380 INVERSE 1
1390 FOR i=174 TO 174-(SizeY-1)*4 STEP -4
1400 PLOT 1+4,i-4: DRAW SizeX*4-1,0
1410 NEXT i
1420 FOR i=1 TO (SizeX-1)*4+1 STEP 4
1430 PLOT i+4,174-4: DRAW 0,-SizeY*4+1
1440 NEXT i
1450 INVERSE 0
1460 FOR i=1 TO SizeX: LET P$(1,i)="?": NEXT i
1470 IF SizeY >= 2 THEN FOR i=2 TO SizeY: LET P$(i)=P$(1):
NEXT i
1480 FOR i=1 TO SizeY: LET E(i)=2: LET x=i: GO SUB 3620:
NEXT i
1490 FOR i=1 TO SizeX: LET F(i)=2: LET x=i: GO SUB 3650:
NEXT i
1500 LET NeObrab=SizeX+SizeY
1510 LET UnKnown=SizeX*SizeY
1520 POKE 23672,0: POKE 23673,0: POKE 23674,0: REM Init ZX
Spectrum timer
1530 REM ** Horisontal lines **
1540 FOR i=1 TO SizeY
1550 IF E(i)=0 THEN GO TO 1720
1560 LET x=i: GO SUB 3630
1570 LET First=0: IF E(i)=2 THEN LET First=1
1580 LET G$=P$(i): LET LenLine=SizeX: LET DataNLine=A(i)
1590 IF DataNLine <> 0 THEN FOR j=1 TO DataNLine: LET
H(j)=B(i,j): NEXT j
1600 GO SUB 2190
1610 IF ErrLine=1 THEN LET ErrCode=1: RETURN
1620 FOR j=1 TO SizeX
1630 IF NOT (P$(i,j)="?" AND G$(j) <> "?") THEN GO TO 1690
1640 LET P$(i,j)=G$(j)
1650 LET UnKnown=UnKnown-1
1660 IF F(j)=0 THEN LET NeObrab=NeObrab+1
1670 LET F(j)=1: LET x=j: GO SUB 3650
1680 LET x=j: LET y=i: GO SUB 2130
1690 NEXT j
1700 LET E(i)=0: LET x=i: GO SUB 3640: LET
NeObrab=NeObrab-1
1710 IF UnKnown=0 THEN GO TO 2080
1720 NEXT i
1730 REM *** Vertical lines ***
1740 FOR i=1 TO SizeX
1750 IF F(i)=0 THEN GO TO 1930
1760 LET x=i: GO SUB 3660
1770 LET First=0: IF F(i)=2 THEN LET First=1
1780 FOR j=1 TO SizeY: LET G$(j)=P$(j,i): NEXT j
1790 LET LenLine=SizeY: LET DataNLine=C(i)
1800 IF DataNLine <> 0 THEN FOR j=1 TO DataNLine: LET
H(j)=D(i,j): NEXT j
1810 GO SUB 2190
1820 IF ErrLine=1 THEN LET ErrCode=1: RETURN
1830 FOR j=1 TO SizeY
1840 IF NOT (P$(j,i)="?" AND G$(j) <> "?") THEN GO TO 1900
1850 LET P$(j,i)=G$(j)
1860 LET UnKnown=UnKnown-1
1870 IF E(j)=0 THEN LET NeObrab=NeObrab+1
1880 LET E(j)=1: LET x=j: GO SUB 3620
1890 LET x=i: LET y=j: GO SUB 2130
1900 NEXT j
1910 LET F(i)=0: LET x=i: GO SUB 3670: LET
Neobrab=Neobrab-1
1920 IF UnKnown=0 THEN GO TO 2080
1930 NEXT i
1940 IF NeObrab <> 0 THEN GO TO 1540
1950 INPUT "Many variants! Continue? ";a$
1960 IF (a$ <> "y") AND (a$ <> "Y") THEN LET ErrCode=2:
RETURN
1970 INPUT "(B)lack or (W)hite? ";a$
1980 REM Set first unknown element
1990 LET j=1
2000 LET i=1
2010 IF P$(j,i)="?" THEN GO TO 2040
2020 LET i=i+1: IF i <= SizeX THEN GO TO 2010
2030 LET j=j+1: GO TO 2000
2040 LET P$(j,i)="1": IF (a$="w" OR a$="W") THEN LET
P$(j,i)="0"
2050 LET x=i: LET y=j: GO SUB 2130
2060 LET E(j)=1: LET x=j: GO SUB 3620: LET F(i)=1: LET x=i:
GO SUB 3650: LET NeObrab=2: LET UnKnown=UnKnown-1
2070 GO TO 1540
2080 LET Time= FN T()
2090 LET TimeMin= INT (Time/60)
2100 LET TimeSec= Time-TimeMin*60
2110 INPUT "Press ENTER to continue...";a$
2120 LET ErrCode=0: RETURN
2130 REM ***** plot (x,y) *****
2140 IF P$(y,x) = "1" THEN GO TO 2170
2150 INVERSE 1: PLOT (x-1)*4+3+4,172-(y-1)*4-4: INVERSE 0
2160 RETURN
2170 INVERSE 1: PLOT (x-1)*4+2+4,173-(y-1)*4-4: DRAW 3,0:
DRAW 0,-1: DRAW -3,0: DRAW 0,-1: DRAW 3,0: INVERSE 0
2180 RETURN
2190 REM *** Line analysing ***
2200 IF First=0 THEN GO TO 2300
2210 IF DataNLine=0 THEN FOR k=1 TO LenLine: LET G$(k)="0":
NEXT k: LET ErrLine=0: RETURN
2220 LET SumLen=0: FOR k=1 TO DataNLine: LET
SumLen=SumLen+H(k): NEXT k
2230 LET Free=LenLine-SumLen-DataNLine+1
2240 LET Pos=1
2250 FOR k=1 TO DataNLine
2260 IF Free >= H(k) THEN GO TO 2290
2270 FOR l=Pos+Free TO Pos+H(k)-1: LET G$(l)="1": NEXT l
2280 IF Free=0 AND k < DataNLine THEN LET G$(Pos+H(k))="0"
2290 LET Pos=Pos+H(k)+1: NEXT k: LET ErrLine=0: RETURN
2300 PRINT AT 18,0;" ": PRINT AT 18,0;"G";G$( TO LenLine)
2310 PRINT AT 19,0;" "
2320 PRINT AT 20,0;" "
2330 IF DataNLine <> 0 THEN GO TO 2380
2340 LET ErrLine=0
2350 FOR k=1 TO LenLine
2360 IF G$(k)="1" THEN LET ErrLine=1
2370 LET G$(k)="0": NEXT k: RETURN
2380 LET Ngroup=1: LET NDop=0: FOR k=1 TO LenLine: LET
L$(k)=" ": NEXT k
2390 LET Lmin=1: IF Ngroup > 1 THEN FOR k=1 TO Ngroup-1:
LET Lmin=Lmin+H(k)+1: NEXT k
2400 LET Rmax=LenLine: IF Ngroup < DataNLine THEN FOR
k=Ngroup+1 TO DataNLine: LET Rmax=Rmax-H(k)-1: NEXT k
2410 IF Ngroup=1 THEN GO TO 2460
2420 LET Gr=Lmin-2
2430 GO SUB 3040: IF ResMake=0 THEN LET Lmin=Gr+2: GO TO
2460
2440 LET Gr=Gr+1: IF Gr+1+H(Ngroup) > Rmax THEN LET
ErrLine=1: RETURN
2450 GO TO 2430
2460 IF Ngroup=DataNLine THEN GO TO 2510
2470 LET Gr=Rmax+2
2480 GO SUB 3330: IF ResMake=0 THEN LET Rmax=Gr-2: GO TO
2510
2490 LET Gr=Gr-1: IF Gr-1-H(Ngroup) < Lmin THEN LET
ErrLine=1: RETURN
2500 GO TO 2480
2510 LET Begin=Lmin: LET LDop=1: LET RDop=1
2520 IF Begin+H(Ngroup)-1=Rmax THEN GO TO 2560
2530 FOR k=Begin+H(Ngroup) TO Rmax
2540 IF G$(k)="1" THEN LET RDop=0
2550 NEXT k
2560 IF Ngroup=DataNLine THEN GO TO 2580
2570 IF G$(Rmax+1)="1" THEN LET RDop=0
2580 IF Begin>1 THEN IF G$(Begin-1)="1" THEN GO TO 2960
2590 IF Begin+H(Ngroup) <= LenLine THEN IF
G$(Begin+H(Ngroup))="1" THEN GO TO 2960
2600 LET k=Begin
2610 IF G$(k)="0" THEN GO TO 2960
2620 LET k=k+1: IF k < Begin+H(Ngroup) THEN GO TO 2610
2630 IF LDop=1 THEN GO TO 2660
2640 LET Gr=Begin-2: IF Gr>0 THEN GO SUB 3040: IF ResMake=1
THEN GO TO 2960
2650 LET LDop=1
2660 IF RDop=1 THEN GO TO 2690
2670 LET Gr=Begin+H(Ngroup)+1: IF Gr <= LenLine THEN GO SUB
3330: IF ResMake=1 THEN GO TO 2960
2680 LET RDop=1
2690 LET P(Ngroup+1)=LenLine-Begin-H(Ngroup)+1: IF Ngroup <
DataNLine THEN FOR k=Ngroup+1 TO DataNLine: LET
P(Ngroup+1)=P(Ngroup+1)-H(k)-P(k+1): NEXT k
2700 IF P(Ngroup+1)=0 AND Ngroup < DataNLine THEN LET
RDop=0: GO TO 2670
2710 LET P(Ngroup)=Begin-1: IF Ngroup>1 THEN FOR k=1 TO
Ngroup-1: LET P(Ngroup)=P(Ngroup)-H(k)-P(k): NEXT k
2720 LET NDop=NDop+1
2730 REM refresh L$
2740 PRINT AT 19,1;: IF P(1)>0 THEN FOR k=1 TO P(1): PRINT
"0";: NEXT k
2750 FOR k=1 TO DataNLine
2760 FOR l=1 TO H(k)
2770 IF k=Ngroup THEN INVERSE 1: PRINT " ";: INVERSE 0: GO
TO 2790
2780 PRINT "1";
2790 NEXT l
2800 FOR l=1 TO P(k+1): PRINT "0";: NEXT l: NEXT k: PAUSE 1
2810 IF P(Ngroup)=0 THEN GO TO 2860
2820 FOR k=Begin-P(Ngroup) TO Begin-1
2830 IF L$(k)=" " THEN LET L$(k)="0": GO TO 2850
2840 IF L$(k) <> "0" THEN LET L$(k)="?"
2850 NEXT k
2860 FOR k=Begin TO Begin+H(Ngroup)-1
2870 IF L$(k)=" " THEN LET L$(k)="1": GO TO 2890
2880 IF L$(k) <> "1" THEN LET L$(k)="?"
2890 NEXT k
2900 IF P(Ngroup+1)=0 THEN GO TO 2950
2910 FOR k=Begin+H(Ngroup) TO Begin+H(Ngroup)+P(Ngroup+1)-1
2920 IF L$(k)=" " THEN LET L$(k)="0": GO TO 2940
2930 IF L$(k) <> "0" THEN LET L$(k)="?"
2940 NEXT k
2950 PRINT AT 20,0;"L";L$( TO LenLine): PAUSE 1
2960 LET Begin=Begin+1
2970 IF Begin+H(Ngroup)-1 > Rmax THEN GO TO 3010
2980 IF G$(Begin-1)="1" THEN LET LDop=0
2990 IF G$(Begin+H(Ngroup)-1)="1" THEN LET RDop=0
3000 GO TO 2580
3010 IF NDop=0 THEN LET ErrLine=1: RETURN
3020 LET Ngroup=Ngroup+1: IF Ngroup < DataNLine+1 THEN GO
TO 2390
3030 LET G$=L$: LET ErrLine=0: RETURN
3040 REM ** Make dopust. left **
3050 IF Ngroup>1 THEN GO TO 3100
3060 LET k=1
3070 IF G$(k)="1" THEN LET ResMake=1: RETURN
3080 LET k=k+1: IF k <= Gr THEN GO TO 3070
3090 LET ResMake=0: RETURN
3100 LET P(1)=0: IF Ngroup>2 THEN FOR k=2 TO Ngroup-1: LET
P(k)=1: NEXT k
3110 LET P(Ngroup)=Gr: FOR k=1 TO Ngroup-1: LET
P(Ngroup)=P(Ngroup)-P(k)-H(k): NEXT k
3120 LET Pos=1: IF P(1)=0 THEN GO TO 3150
3130 IF G$(Pos)="1" THEN LET ResMake=1: RETURN
3140 LET Pos=Pos+1: IF Pos <= P(1) THEN GO TO 3130
3150 LET k=1
3160 LET l=1
3170 IF G$(Pos)="0" THEN GO TO 3240
3180 LET Pos=Pos+1: LET l=l+1: IF l <= H(k) THEN GO TO 3170
3190 LET l=1
3200 IF G$(Pos)="1" THEN GO TO 3240
3210 LET Pos=Pos+1: LET l=l+1: IF l <= P(k+1) THEN GO TO
3200
3220 LET k=k+1: IF k <= Ngroup-1 THEN GO TO 3160
3230 LET ResMake=0: RETURN
3240 LET Now=k
3250 LET SumSp=0: FOR k=Now+1 TO Ngroup: LET
SumSp=SumSp+P(k): NEXT k
3260 IF SumSp <= Ngroup-1-Now THEN GO TO 3310
3270 LET P(Now)=P(Now)+1
3280 IF Now < Ngroup-1 THEN FOR k=Now+1 TO Ngroup-1: LET
P(k)=1: NEXT k
3290 LET P(Ngroup)=Gr: FOR k=1 TO Ngroup-1: LET
P(Ngroup)=P(Ngroup)-P(k)-H(k): NEXT k
3300 GO TO 3120
3310 LET Now=Now-1: IF Now>0 THEN GO TO 3250
3320 LET ResMake=1: RETURN
3330 REM * Make dopust. right*
3340 IF Ngroup < DataNLine THEN GO TO 3390
3350 LET k=Gr
3360 IF G$(k)="1" THEN LET ResMake=1: RETURN
3370 LET k=k+1: IF k <= LenLine THEN GO TO 3360
3380 LET ResMake=0: RETURN
3390 LET P(DataNLine+1)=0: IF Ngroup <= DataNLine-2 THEN
FOR k=DataNLine TO Ngroup+2 STEP -1: LET P(k)=1: NEXT k
3400 LET P(Ngroup+1)=LenLine-Gr+1: FOR k=DataNLine TO
Ngroup+1 STEP -1: LET P(Ngroup+1) = P(Ngroup+1)-P(k+1)-H(k):
NEXT k
3410 LET Pos=LenLine: IF P(DataNLine+1)=0 THEN GO TO 3440
3420 IF G$(Pos)="1" THEN LET ResMake=1: RETURN
3430 LET Pos=Pos-1: IF LenLine-Pos+1 <= P(DataNLine+1) THEN
GO TO 3420
3440 LET k=DataNLine
3450 LET l=1
3460 IF G$(Pos)="0" THEN GO TO 3530
3470 LET Pos=Pos-1: LET l=l+1: IF l <= H(k) THEN GO TO 3460
3480 LET l=1: IF P(k)=0 THEN GO TO 3510
3490 IF G$(Pos)="1" THEN GO TO 3530
3500 LET Pos=Pos-1: LET l=l+1: IF l <= P(k) THEN GO TO 3490
3510 LET k=k-1: IF k > Ngroup THEN GO TO 3450
3520 LET ResMake=0: RETURN
3530 LET Now=k
3540 LET SumSp=0: FOR k=Now TO Ngroup+1 STEP -1: LET
SumSp=SumSp+P(k): NEXT k
3550 IF SumSp <= Now-Ngroup-1 THEN GO TO 3600
3560 LET P(Now+1)=P(Now+1)+1
3570 IF Now > Ngroup+1 THEN FOR k=Now TO Ngroup+2 STEP -1:
LET P(k)=1: NEXT k
3580 LET P(Ngroup+1)=LenLine-Gr+1: FOR k=DataNLine TO
Ngroup+1 STEP -1: LET P(Ngroup+1) = P(Ngroup+1)-P(k+1)-H(k):
NEXT k
3590 GO TO 3410
3600 LET Now=Now+1: IF Now <= DataNLine THEN GO TO 3540
3610 LET ResMake=1: RETURN
3620 PLOT 0,175-x*4-3: RETURN : REM set passive vertical
label
3630 PLOT 0,175-x*4-3: DRAW 1,0: DRAW 0,-1: DRAW -1,0:
RETURN : REM set active vertical label
3640 INVERSE 1: PLOT 0,175-x*4-3: DRAW 1,0: DRAW 0,-1: DRAW
-1,0: INVERSE 0: RETURN : REM reset vertical label
3650 PLOT x*4+3,175: RETURN : REM set passive horisontal
label
3660 PLOT x*4+3,175: DRAW 1,0: DRAW 0,-1: DRAW -1,0: RETURN
: REM set active horisontal label
3670 INVERSE 1: PLOT x*4+3,175: DRAW 1,0: DRAW 0,-1: DRAW
-1,0: INVERSE 0: RETURN : REM reset horisontal label
3680 REM *** Print "___..." ***
3690 LET Count5=Count5+1
3700 IF Count5<5 THEN RETURN
3710 LET Count5=0
3720 PRINT "_______________________________"
3730 RETURN
3740 REM *Print horisontal data*
3750 PRINT "Line ";i;": ";
3760 IF A(i)=0 THEN GO TO 3810
3770 PRINT B(i,1);: IF A(i)=1 THEN GO TO 3810
3780 FOR j=2 TO A(i)
3790 PRINT ",";B(i,j);
3800 NEXT j
3810 PRINT : GO SUB 3680
3820 RETURN
3830 REM * Print vertical data *
3840 PRINT "Line ";i;": ";
3850 IF C(i)=0 THEN GO TO 3900
3860 PRINT D(i,1);: IF C(i)=1 THEN GO TO 3900
3870 FOR j=2 TO C(i)
3880 PRINT ",";D(i,j);
3890 NEXT j
3900 PRINT : GO SUB 3680
3910 RETURN
Для значительного ускорения работы программы (что особенно важно при решении больших кроссвордов) имеет смысл переписать на ассемблере ключевой участок — обработку одной линии кроссворда (строки 2200—3610). Для ZX Spectrum я так и сделал, записав затем откомпилированную подпрограмму в файл obj <C> (start #F600, length #05E0) и добавив в основную программу такие строки:
5 CLEAR 62975: RANDOMIZE USR 15619: REM: LOAD "obj" CODE
2195 RANDOMIZE USR 62976: RETURN
После этого строки 2200—3610 не нужны, но убирать их из программы я не
стал — вдруг вы захотите