Страница Ивана Рощина > Статьи >

© Иван Рощин, Москва

ZXNet: 500:95/462.53
E-mail: bestview@mtu-net.ru
WWW: http://www.ivr.da.ru

Японские кроссворды

Радиомир. Ваш компьютер» 2/2003)
Дата последнего редактирования: 8.03.2003.

Введение

Японские кроссворды (их ещё называют «японские сканворды», «японские картинки») — сравнительно недавно появившийся вид головоломок, стремительно набирающий популярность. В этой статье я хочу предложить вашему вниманию программу, которая поможет как решать такие кроссворды, так и создавать их.

Пример кроссворда и его решение

Если вы до сих пор не знали, что из себя представляют японские кроссворды, то сейчас узнаете. :–) А если знаете, то всё равно прочтите этот раздел: здесь я введу термины, которые будут использованы в дальнейших рассуждениях.

В японских кроссвордах нужно отгадывать не слова, а прямоугольное изображение, состоящее из отдельных квадратиков-клеток. Каждая клетка может быть либо белой, либо чёрной (бывают и многоцветные кроссворды, но здесь я буду рассматривать только чёрно-белые).

Будем в дальнейшем называть строку или столбец кроссворда общим словом «линия».

Группу идущих подряд чёрных клеток в линии, ограниченную с каждой стороны либо пустой клеткой, либо границей кроссворда, будем называть закрашенным участком. Участок может состоять и из единственной клетки.

Так вот, для каждой линии кроссворда приводятся сведения о длине закрашенных участков (в порядке их следования: для строк — слева направо, для столбцов — сверху вниз). По этой информации и нужно разгадать изображение, то есть узнать, какие клетки белые, а какие — чёрные.

Пример японского кроссворда вы можете увидеть на рис. 1.

Рис. 1

А по какому принципу их решают? Попробуем решить, пока вручную, кроссворд, приведённый на рис. 1.

Данные о первой строке состоят лишь из одной цифры — «1». Это значит, что в этой строке находится одна чёрная клетка, а остальные — белые. Какое именно положение занимает чёрная клетка — пока не ясно.

Во второй строке находится участок из трёх чёрных клеток. Понятно, что, как его ни располагай, центральная клетка обязательно будет чёрной.

В третьей строке два закрашенных участка, из трёх и одной клетки, могут быть расположены единственным возможным образом: так, чтобы между ними находилась одна белая клетка. Итак, об этой строке мы уже знаем всё.

Из четвёртой строки, как и из первой, ничего извлечь не удаётся.

Отобразим выясненную на данный момент информацию (рис. 2). Клетки, про которые точно известно, что они белые, будем отмечать точкой.

Рис. 2

Теперь перейдём к столбцам. Положение единственной чёрной клетки в первом столбце нам уже известно. Значит, остальные клетки этого столбца — белые.

Во втором столбце находится чёрный участок из двух клеток. Положение одной из них нам известно. Вторая клетка обязательно должна примыкать к ней сверху или снизу. Следовательно, самая верхняя клетка этого столбца — точно белая.

Из следующих двух столбцов мы ничего сейчас извлечь не можем, а из последнего столбца ясно, что, как ни располагай в нём участок из трёх чёрных клеток, две средние клетки обязательно будут чёрными.

Отобразим то, что нам удалось выяснить (рис. 3).

Рис. 3

Снова просмотрим строки кроссворда. Видим, что во второй строке положение закрашенного участка (а значит, и второй белой клетки) полностью определилось. Отмечаем это (рис. 4).

Рис. 4

Тогда во втором и четвёртом столбцах положение закрашенных участков тоже однозначно определяется (рис. 5). Остались лишь четыре невыясненных клетки!

Рис. 5

При анализе нижней строки определяется положение второго закрашенного участка (рис. 6).

Рис. 6

Ну а третий и пятый столбцы теперь тоже можно однозначно определить (рис. 7).

Рис. 7

Всё, кроссворд решён! Ну а то, что в получившейся картинке не видно какого-либо смысла, — так ведь это был просто пример. :–)

Как видим, при решении японского кроссворда мы, получив некоторые сведения о строках, используем их для выяснения информации о столбцах, и наоборот. В этом японские кроссворды похожи на обычные, в которых отгаданные слова по горизонтали дают информацию для отгадывания пересекающихся с ними слов по вертикали, и наоборот.

А теперь рассмотрим, как решать кроссворды (и создавать собственные) уже не вручную, а с использованием моей программы.

Руководство пользователя

После запуска вы увидите на экране меню из пяти пунктов:

1. Resolve new crossword
2. Resolve old crossword
3. Test picture
4. View data
5. Exit

Для решения нового кроссворда выбирайте первый пункт. Сначала программа предложит вам ввести размеры кроссворда: ширину (от 1 до 62 клеток) и высоту (от 1 до 42). При необходимости кроссворд можно повернуть на 90 градусов, поменяв при этом информацию о строках и столбцах.

Затем надо ввести информацию о закрашенных участках: сначала о строках (они нумеруются сверху вниз), а потом о столбцах (нумеруются слева направо). Номер текущей вводимой строки (столбца) отображается на экране.

Длины закрашенных участков перечисляются через запятую; если какая-либо линия не содержит закрашенных участков, просто нажимайте Enter.

Уже введённая информация печатается в верхней части экрана, при этом через каждые пять строк выводится разделительная черта — это помогает не перепутать, информацию о какой линии кроссворда вы вводите (в сетке «бумажного» кроссворда через каждые пять клеток разделяющая их линия изображается более жирной).

На рис. 8 показано, как выглядит экран при вводе данных.

Рис. 8

Программа проверяет, являются ли корректными введённые пользователем данные о линии кроссворда. Должно выполняться следующее условие: сумма длин всех закрашенных участков и минимальных промежутков между ними (напомню, что два соседних закрашенных участка должны быть разделены как минимум одной белой клеткой) должна быть не больше длины линии.

Минимальное количество белых клеток, очевидно, на единицу меньше числа закрашенных участков. Тогда данное ограничение можно записать так:

n ai + n–1 <= l,
+---
 \
 /
+---
i = 1
где  n — количество закрашенных участков,
ai — длина i-го закрашенного участка,
l — длина линии.

То есть, например, если длина линии 8 клеток, и вы вводите информацию о закрашенных участках: «1,4», то всё в порядке: (1+4)+1<8. А если при вводе клавиша «1» случайно была нажата дважды, и оказалась введена строка «11,4», то программа укажет на некорректность введённых данных: ведь (11+4)+1>8.

При обнаружении ошибки программа предложит повторно ввести информацию о линии кроссворда.

После ввода всех данных производится ещё одна проверка. Смотрите: если сложить длины всех закрашенных участков в строках, то мы получим, очевидно, общее количество чёрных клеток в кроссворде. Но точно такое же значение должно получиться и при суммировании длин закрашенных участков в столбцах! А если они не совпадают — значит, при вводе допущена ошибка. В этом случае придётся вводить данные заново.

При такой проверке всегда обнаруживается одиночная ошибка вида «пропущено число», «введено лишнее число», «введено неправильное число». Да и если таких ошибок несколько, вероятность того, что они взаимно компенсируют друг друга, невелика. А вот если вы при вводе случайно поменяете какие-либо числа местами, это останется незамеченным — ведь от изменения порядка слагаемых сумма не меняется.

Если данные успешно прошли первичную проверку на корректность, программа выдаст приглашение: «Press any key…». После нажатия любой клавиши начнётся процесс решения кроссворда.

Информация о ходе решения отображается на экране в таком же виде, как если бы вы решали кроссворд на бумаге. Если клетка кроссворда изображена белой — значит, информация о ней не известна; если в клетке стоит точка — значит, эта клетка точно белая; если клетка изображена чёрной — значит, она чёрная. :–)

Точки, расположенные на левой и верхней сторонах кроссворда, служат признаком того, что соответствующие линии кроссворда помечены для последующего просмотра. Сначала помечены все линии.

При решении кроссворда программа последовательно просматривает все помеченные строки и столбцы. Точка напротив текущей просматриваемой линии изображается более жирной.

При просмотре линии, возможно, становится известной информация о некоторых её клетках. Если стало известно, что какая-то клетка чёрная, она закрашивается чёрным. Если известно, что какая-то клетка белая, она помечается точкой в центре.

Когда при просмотре строки становится известна информация о некоторых её клетках, то столбцы, где расположены эти клетки, помечаются. Аналогично, когда при просмотре столбца становится известна информация о некоторых его клетках, то строки, где расположены эти клетки, помечаются.

После просмотра линии точка напротив неё исчезает, т.е. пометка с этой линии снимается.

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

На рис. 9 вы можете увидеть несколько скриншотов, сделанных в процессе решения кроссворда.

Рис. 9



При нормальном завершении вы увидите на экране изображение решённого кроссворда (рис. 10), а затем (после нажатия любой клавиши) — время, потраченное на решение. После ещё одного нажатия любой клавиши программа выйдет в главное меню.

Рис. 10

Теперь обратим внимание вот на что: даже если данные кроссворда успешно прошли первичную проверку на корректность, этот кроссворд может и не иметь решения. Простейший пример такого кроссворда вы можете увидеть на рис. 11.

Рис. 11

В таком случае при решении кроссворда рано или поздно обнаружится противоречие. Для примера на рис. 11: при анализе первой (и единственной) строки получаем, что средняя клетка будет чёрной, а при анализе второго столбца — что она должна быть белой.

Программа, обнаружив такое противоречие, выводит сообщение «Incorrect data!», и после нажатия любой клавиши выходит в главное меню.

Также может быть, что кроссворд имеет несколько решений. На рис. 12 приведён пример кроссворда с тремя различными решениями.

Рис. 12

При решении такого кроссворда рано или поздно наступит момент, когда помеченных линий не останется — а кроссворд ещё не будет полностью решён. В этом случае программа выдаст сообщение «Many variants! Continue?» («Много вариантов. Продолжить?»). Если вы ответите «N» («Нет») — программа выйдет в главное меню; если «Y» («Да») — решение кроссворда будет продолжено.

Чтобы программа могла продолжить решение кроссворда, ей необходима дополнительная информация, которую она запросит у вас. Эта информация — цвет первой неизвестной клетки (то есть такой клетки, цвет которой к настоящему моменту не известен; первая такая клетка — та, которая ближе к верхней границе кроссворда, а если таких клеток несколько — та из них, которая ближе к левой границе). Вы можете выбрать, будет ли эта клетка чёрной или белой, ответив на запрос программы («(B)lack or (W)hite?») соответственно «B» или «W».

После этого вы увидите, что соответствующая клетка кроссворда примет выбранный вами цвет. Строка и столбец, где находится эта клетка, будут помечены для дальнейшего анализа, и решение кроссворда продолжится.

Момент, когда мы выбираем, чёрной или белой будет неизвестная клетка, является своеобразной точкой развилки. После него решение кроссворда может пойти по одному из двух возможных путей. На каждом из этих путей, в свою очередь, могут быть другие точки развилки. Получается, таким образом, «дерево решений» кроссворда. На рис. 13 вы можете увидеть, как выглядит дерево решений кроссворда, приведённого на рис. 12.

Рис. 13

Учтите, что некоторые ветви дерева решений могут заканчиваться тупиками, т.е. при их рассмотрении программа придёт к противоречию (рис. 14).

Рис. 14

Чтобы найти все решения кроссворда, нужно решить его столько раз, сколько ветвей у дерева решений. Для этого при каждом решении выбирайте цвета неизвестных клеток так, чтобы пройти по новому пути. После получения очередного решения (или если выяснилось, что выбранный путь привёл к противоречию), когда программа выйдет в главное меню, выбирайте пункт «Resolve old crossword» («Решить старый кроссворд»), тогда вам не придётся заново вводить информацию о кроссворде.

Теперь о том, как программа поможет вам в составлении собственных кроссвордов. Чтобы составить кроссворд, надо выполнить три шага: нарисовать картинку, получить данные о группах закрашенных участков и проверить, будет ли полученный кроссворд решаться однозначно (иначе тот, кто будет его решать, не узнает, какую именно картинку вы имели в виду). В выполнении всех этих трёх шагов вам поможет компьютер.

Рисовать картинку удобно в графическом редакторе. На ZX Spectrum это может быть, например, Art Studio или BGE. Вам нужно получить файл в стандартном экранном формате, причём картинка должна быть расположена в левом верхнем углу экрана. Каждый пиксел картинки соответствует одной клетке кроссворда.

Для выполнения следующих двух шагов как раз поможет моя программа. Выберите в главном меню пункт «Test picture» и укажите имя файла с картинкой. Программа загрузит картинку, и вы увидите её на экране. Укажите размеры кроссворда. Программа начнёт считывать информацию о пикселах картинки (то есть о клетках кроссворда), при этом обработанные пикселы будут инвертироваться, чтобы вы могли следить за ходом процесса. Затем программа начнёт формировать информацию о закрашенных участках, при этом показывая, сколько процентов информации уже сформировано.

Далее программа начнёт решать кроссворд по этой информации. Если решение однозначно, то после выхода в главное меню вы, выбрав пункт «View data», сможете переписать данные о закрашенных участках на бумажку. :–) Ну а если в процессе решения возникла неоднозначность, значит, картинку надо переделать. В таком случае загружайте графический редактор и — всё сначала…

Небольшой совет: если ваша картинка содержит участки, как на рис. 15 а,б (где клетки, помеченные «*», — это либо белые клетки, либо граница кроссворда), то решение заведомо будет неоднозначным. Действительно, если в картинке содержится фрагмент, как на рис. 15 а, то, если заменить его на фрагмент, приведённый на рис. 15 б (или наоборот), то данные о закрашенных участках при этом не изменятся! То есть у такого кроссворда будет как минимум два различных решения. Соответственно, следите за тем, чтобы таких участков в вашей картинке не было.

Рис. 15
а)

б)

Тем не менее, даже если таких участков нет, это ещё ни о чём не говорит (см. рис. 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 не нужны, но убирать их из программы я не стал — вдруг вы захотите что-то изменить в алгоритме обработки одной линии кроссворда.

Скачать описанный вариант программы (7 КБ ZIP)

Страница Ивана Рощина > Статьи >