Как написать программу кроссворд

Люди надо написать программу для сост. кроссворда помогите хотя бы начало а то ваще не врубаюсь.

Код к задаче: «Программа для составления кроссворда»

Листинг программы

Program kross; uses graph,crt,mouse; var gd,gm:integer; begin gd:=detect; initgraph(gd,gm,»); setbkcolor (4); setcolor(blue); rectangle(7,7,630,470); rectangle(10,10,626,468); settextstyle(5,0,0); setcolor(7); outtextxy(50,50,’Kyrsovoy proekt’); outtextxy(100,150,’Tema: Krossvord’); outtextxy(100,250,’Gruppa: T*****’); outtextxy(100,300,’Vypolnil: ****’); rectangle(495,450,585,405); outtextxy(520,420,’NEXT’); repeat readmouse; if (mousex<495); and (mousex>585); and (mousey<450); and (mouse>405); and leftpressbutton then begin hidemouse; clrscr; showmouse; readln; end.

Источник: studassistent.ru

Построение поля для кроссворда

Как именно вставлять слова, да так чтобы одно слово могло не просто пересекаться с другим, а с несколькими?

Как создать кроссворд самому?

Посмотрел на кроссворды и понял, что количество вертикальных и горизонтальных слов всегда пропорционально, плюс/минус одно-два. Значит, необходимо реализовать две функции — одну для горизонтальных, другую для вертикальных. И вызывать их друг за другом через рекурсию пока не будут использованы все слова.

UPD (прошу прощения за качество изображения, рисовал в гимпе быстро)

Необходимо ввести такое понятие как красная зона, чтобы не было «слипания» слов.

Нашел статью http://habrahabr.ru/post/166471/, прочтение исходного кода ничего не дало.

Еще одна зацепка найдена. Книга : Мозговой М.В. «C++ Мастер класс 85 нетривиальных проектов, решений и задач». Есть способ реализации построения кроссворда, только он завязан на том что у нас уже дана определенная сетка и достаточной большой список слов, который не будет использоваться весь.

Отслеживать
Peter Lavreniuk
задан 29 сен 2015 в 2:37
Peter Lavreniuk Peter Lavreniuk
2,921 6 6 золотых знаков 25 25 серебряных знаков 55 55 бронзовых знаков

Я как-то давно искал решение на C#, здесь есть небольшое описание алгоритма codingcraft.ru/open_source/crossword/generator.php, там же можно взглянуть на исходник и саму программу

3 окт 2015 в 22:46

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

У меня есть некоторая идея алгоритма, но скорее всего она не самая оптимальная.

1. Сортируем базу слов, чтобы самые длинные располагались в начале;
2. Создаем двумерный символьный массив размерностью N x N, где N можно взять в 1.5 — 2 раза больше, чем самое длинное слово из имеющегося списка;
3. По горизонатли в середину массива помещаем самое длинное слово;
4. Выбираем следующие по длине слово, у которого хоть 1 буква совпадает с первым, и размещаем его в нужном месте по вертикали;
5. Далее реализуем цикл, пока не выберем все слова из нашей базы, или не завершатся возможные позиции для добавления слов:
6. Поочередно выбираем, добавляем ли мы новое слово по вертикали, или по горизонтали;
7. Проходим по строкам, или столбцам массива, через 1 (так обеспечим отсутствие «слипания» слов, если добавляем по горизонтали, двигаемся по строкам, иначе — по столбцам), ищем стоки/столбцы, в которых присутствуют обрамленные пустыми ячейками единичные символы, сохраняем эти символы и размер промежутков между ними в элемент некоторого списка, например, из комбинации строк:

Как сделать кроссворд в ворде

.гиппопотам. . . . .пароход. . .комод.

Можно было бы составить вот такие элементы списка: г-3-п-1-к , п-3-р-1-м , о-3-х-1-д , о-3-д , и т.д. (Как именно формировать такие элементы списка, чтобы их потом было удобно разбирать — отдельный вопрос, можно формировать регулярное выражение, а может даже лучше не переносить сами буквы из массива, а добавлять в список структуру вида

UPD:
Пример для добавления слова, пересекающегося с двумя по вертикали:

. ..г. ф.. ..р. а.. ..а. в.. ..ф. н..

передвигаясь по строкам через одну, мы можем составить элементы списка р-3-а, ф-3-н для этих двух слов, если мы будем использовать в качестве элемента списка вышеописанную структуру, то для строки номер 3 мы получим :
направление — горизонталь
количество букв — 2
номер строки начала — 2 (если учесть привычный отсчет в массиве с 0)
номер столбца начала — 2

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

Источник: ru.stackoverflow.com

Написание генератора кроссвордов на Delphi

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

Текст программы снабжен большим количеством подробных комментариев, так что разобраться в деталях будет не трудно. Сама база всех вопросов и ответов содержится в файле 1.txt, если кто либо решит пополнить эту базу нужно не забыть отредактировать строчку Cnt=56 в начале.

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

Алгоритм генерации кроссворда

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

При размещении слова, алгоритм учитывает некоторые ограничения. Например нельзя размещать два слова одно за другим впритык, иначе не будет понятно где заканчивается одно и начинается другое.

Процедуры MapWord и MapWordCheck — содержат основную часть алгоритма размещения слов на доске.

procedure TMainForm.MapWord(WUindex: integer); var Len : integer; x,y,n : integer; i : integer; cnt : integer; // Количество найденых вариантов размещения POst : integer; // Оставшееся число попыток подобрать слово из словаря // Массив для запоминания возможных вариантов размещения слова на доске MX : array[1..Tmax*Tmax] of integer; // Координата X на доске MY : array[1..Tmax*Tmax] of integer; // Координата Y на доске MN : array[1..Tmax*Tmax] of integer; // направление слова — 1 горизонтально, 2 — вертикально begin // Выбрать из словаря и расположить слово на доске // WUindex — порядковый номер размещаемого слова POst := Pmax; // Берем заданное в переменной число попыток выбрать слово cnt := 0; // Изначально количество вариантов, которыми можно разместить слово на доске = 0 while cnt=0 do begin // крутим цикл пока не найдем слово, которое сможем разместить хотябы одним способом POst := POst-1; // Уменьшаем оставшееся число попыток if POst1)and(T[x-1,y]<>’ ‘)and(T[x-1,y]<>’#’) then begin // слово не должно лепится вплотную к другому слову Result := false; // размещение невозможно Exit; end; if (x’ ‘)and(T[x+Len,y]<>’#’) then begin // слово не должно лепится вплотную к другому слову Result := false; // размещение невозможно Exit; end; for i := 1 to Len do begin // проверяем символ за символом if T[x+i-1,y]<>’ ‘ then begin // клетка чемто занята if T[x+i-1,y]<>S[i] then begin // символ в клетке не совпадает с символом в слове — размещение невозможно Result := false; Exit; end else begin if (TS[x+i-1,y]=3)or(TS[x+i-1,y]=1) then begin // символ совпал, но тут уже есть пересечение слов, либо тут есть слово, расположенное в том же направлении Result := false; // размещение невозможно Exit; end else begin p := p + 1; // регистрируем удачное пересечение проверяемого слова с уже размещенными end; end; end; end; end else begin // ВЕРТИКАЛЬНО if (y>1)and(T[x,y-1]<>’ ‘)and(T[x,y-1]<>’#’) then begin // слово не должно лепится вплотную к другому слову Result := false; // размещение невозможно Exit; end; if (y’ ‘)and(T[x,y+Len]<>’#’) then begin // слово не должно лепится вплотную к другому слову Result := false; // размещение невозможно Exit; end; for i := 1 to Len do begin // проверяем символ за символом if T[x,y+i-1]<>’ ‘ then begin // клетка чемто занята if T[x,y+i-1]<>S[i] then begin // символ в клетке не совпадает с символом в слове — размещение невозможно Result := false; Exit; end else begin if (TS[x,y+i-1]=3)or(TS[x,y+i-1]=2) then begin // символ совпал, но тут уже есть пересечение слов, либо тут есть слово, расположенное в том же направлении Result := false; // размещение невозможно Exit; end else begin p := p + 1; // регистрируем удачное пересечение проверяемого слова с уже размещенными end; end; end; end; end; if p>0 then begin Result := true; // размещение с такими параметрами возможно end else begin Result := false; // размещение невозможно — нчего не мешает, но и пересечений нет end; end;

function TMainForm.RandWord: integer; var r : integer; i : integer; begin // Выбираем слово из словаря, которое еще не использовано r := 0; while r=0 do begin r := 1 + Random(wCnt-1); for i := 1 to WUmax do begin if WU[i]=r then r := 0; // Если выбранное слово уже использовано, сбрасываем выбор, чтобы взять другое end; end; Result := r; end;
procedure TMainForm.SetWord(WUindex: integer); var Len : integer; S : string; i : integer; x,y : integer; begin // Вписываем слово в сетку, при этом (в таблицы T и TS) // WUindex — его порядковый номер в таблицах WU, WX, WY, WN (эти ьаблицы должны быть заполнены предварительно) S := W[WU[WUindex]]; // достаем слово Len := Length(S); // достаем его длину x := WX[WUindex]; y := WY[WUindex]; // помечаем клетки перед и после слова как занятые (чтоб слова своим началом или концом не лепились вплотную к уже размещенным словам) if WN[WUindex]=1 then begin // ГОРИЗОНТАЛЬНО if (x-1)>0 then begin // Ставим ограничительный знак перед словом TS[x-1,y] := 3; T[x-1,y] := ‘#’; end; if x+Len0 then begin // Ставим ограничительный знак перед словом TS[x,y-1] := 3; T[x,y-1] := ‘#’; end; if y+Len

Источник: blog.a7in.com