int Counter;

CharAndCounter(char char =

, int counter = 0) : Char( char), Counter( countei-) {}

И элемент словаря struct VocElement {

string String; слово

bool Busy; флаг занято/не занято

VocElement (const strings str = , bool b = false)

: String(str), Busy(b) {}

Зачем букве счётчик? Дело в том, что на уровне псевдокода не видна одна проблема, связанная с операциями разместить слово и снять слово . Предположим, в некоторую позицию кроссворда процедура Solve () решает вписать слово ПОРТ (рис. 4.10).

Рис 4.10. Размещение очередн€>го слова в клетках кроссворда

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

Рис 4.11. Использование счетчиков букв

vector<WordCoords> Crossword; описание кроссворда

Функция ReadData () считывает описание кроссворда из файла crossword, txt и словаря из файла vocabulary, txt:

служебная функция для сортировки слов по длине

bool Less(const VocElementb Ihs, const VocElementb rhs)

return Ihs.String.length0 < rhs.String.length();

----------------------------------------------------------------

void ReadData() {

ifstream crossw( crossword.txt*), voc( vocabulary.txt ); string temp;

считать последовательно все слова словаря

while(!voc.eof())

При снятии слова с поля все соответствующие счётчики уменьшаются на единицу. Если счётчик равен нулю, буква заменяется пробельным символом.

Поле кроссворда представляет собой двумерный массив объектов типа CharAndCounter, а словарь - массив объектов VocElement:

vector<vector<CharAndCounter> > Field; vector<VocElement> Vocabulary;

Кроссворд состоит из элементов, описывающих расположение, направление и длину каждого слова:

struct WordCoords {

static const char VERTICAL = v, HORIZONTAL = h; int X, Y; расположение слова

char Dir; направление слова (горизонтальное /

вертикальное) int Length; длина слова

WordCoords(int x, int y, int len, char dir)

: X( x), Y( y), Dir( dir), Length( len) {} горизонтальное и вертикальное смещение очередной буквы слова относительно предыдущей int dx() { return (Dir == HORIZONTAL) ? 1 : 0; ) int dyO { return (Dir == VERTICAL) ? 1 : 0; )

----------------------------------------------------------------

разместить слово word в позиции с (предполагается, что это возможно)

void PlaceWord(WordCoords с, const strings word)

for(unsigned i = 0; i < word.length(); i++) {

Fi.eld[c.X + i*c.dx() ] [c.Y + i*c.dy () ] .Char = word[i]; Field[c.X + i*c.dx()][c.Y + i*c.dy()1.Counter++;

-----------------------------------------------------------------

снять слово word с позиции с

void RemoveWord(WordCoords с, const strings word) (

for(unsigned i = 0; i < word.length(); i++) {

if(--Field[c.X + i*c.dx()][c.Y + i*c.dy()].Counter == 0) Field[c.X + i*c.dx()][c.Y + i*c.dy()].Char = ;

Основная функция решения Solve () соответствует псевдокоду, приведённому выше:

bool Solve(unsigned CoordNo) {

if(CoordNo == Crossword.sizeO) если подкроссворд пуст return true;

получить диапазон слов, длина каждого из которых равна Crossword[CoordNo].Length

pair<vector<VocElement>::iterator, vector<VocEleinent>::iterator> range = equal range(Vocabulary.begin(), Vocabulary.end(),

string(Crossword[CoordNo].Length, ), Less);

цикл no словам словаря

for (vector<VocElement>: .-iterator p = range, first;

p != range.second; p++) if(!p->Busy && CanPlace(Crossword[CoordNo], p->String)) { если слово не занято

и его можно разместить на позиции Crossword[CoordNo] PlaceWord(Crossword[CoordNo], p->String); разместить

слово

p->Busy = true; теперь слово занято

if(Solve(CoordNo + 1)) если подкроссворд решается return true;

RemoveWord(Crossword[CoordNo], p->String); снять

слово

voc temp;

Vocabulary.push back(VocElement(temp, false));

отсортировать словарь по длине слов

sort(Vocabulary.begin(), Vocabulary.end(), Less);

считать описание кроссворда int W, Н, X, у, len; char dir;

ширина и высота поля crossw W; crossw H;

for(;;) {

считать очередной элемент описания crossw х; crossw у; crossw len; crossw dir; if(crossw.eof()) break;

Crossword.push back(WordCoords(X, y, len, dir));

заполнить всё поле пустыми символами

for(int i = 0; i < W; i++)

vector<CharAndCounter> col(H);

fill(col.begin(), col.endO, CharAndCounter()); Field.push back(col);

Сортировка словаря по длине слов поможет в дальнейшем ускорить работу программы. Впрочем, об этом позже, а сейчас рассмотрим три важные функции - CanPlace(), PlaceWord() и RemoveWord():

можно ли разместить слово word на позиции с?

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

bool CanPlace(WordCoords с, const strings word) {

for(unsigned i = 0; i < word.length(); i++) {

если очередная просматриваемая ячейка непуста и при этом символ в ней не соответствует i-му символу слова if(Field[c.X + i*c.dx()][с.У + i*c.dy()].Char !=&& Field[c.X + i*c.dx()][c.Y + i*c.dy()].Char 1= word[i]) return false; слово нельзя разместить на позиции с

return true;

p->Busy = false;

пометить слово как незанятое

return false;

Как указано в псевдокоде, алгоритм Solve () перебирает все незанятые слова словаря. Для ускорения работы процраммы я внёс небольшое улучшение: зачем перебирать все слова, если заведомо известно, что лишь слова длины Crossword [CoordNo] . Length могут быть успешно размещены в позиции Crossword [CoordNo ] кроссворда?

С помощью функции equal range () из сортированного словаря можно за один присест извлечь поддиапазон слов, длины которых равны Crossword [CoordNo] .Length, Поскольку определённая выше функция Less О сравнивает длины слов, в качестве третьего аргумента equalrange () может использоваться любая строка требуемой длины -например, строка, заполненная Crossword [CoordNo] . Length пробелами.

Осталось лишь запрограммировать простую функцию main ():

int main(int argc, char* argv[]) {

считать параметры кроссворда ReadData(); if(Solve(O)) {

если решение найдено,

распечатать содержимое Field

for(unsigned у = 0; у < Field[0].size(); y++)

for(unsigned x = 0; x < Field.size(); x++)

cout Field[x][y].Char; cout << endl;

else

cout << нет решений

return 0;

Пример входных данных:

содержимое файла crossword, txt:

13 4

2 О 4 V

0 1 9 h 8 1 3 V

1 3 3 h 7 3 б h

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

0птими9ир0ванный перебор с возвратами

Требуется написать программу, способную решать классические (чёрно-белые) японские кроссворды.

Суть разгадывания японского кроссворда состоит в нахождении изображения по числовым подсказкам. Изначально игровое поле - белая клетчатая доска - пусто (на рис. 4.12 показан уже решённый кроссворд).

Рис. 4.12. Пример японского кроссворда

содержимое файла vocabulary. txt:

компьютер омар бра рот

утварь

крот

сервер

аромат

радио

В результате работы программы получится следующий кроссворд:

компьютер а о

бра утварь