Month

Brief Information about the May '03 CSIG Meeting

Xword -- A Program to Create Crossword Puzzles

B. Arnold

The subject for this month is the continuation of a program that creates crossword puzzles. It is an SDI MFC program written in Visual C++ version 6.0 Foundation Classes.

Last month the meeting discussed the graphical part of the program: How to put the information on the screen and how to interact with the document, view, and frame paradigm. Now there is enough visual coding so that the actual crossword algorithm and coding details can be discussed.

Algorithm

  Create a grid of squares in an array.
  Read a file containing words into vector m_words.
  For each word (m_words),
		check if it fits on the grid horizontally or vertically.
		if so, fill a vector (m_results) with ORIENTATION, XY CORDS, and WORD
  Sort the m_results vector.
  Build an "id" table
		check if XY CORD corresponds to a word in m_results.
		if so,
			Build a table of ORIENT's, id's and XY CORD's (m_ids).
  When drawing to the output device
		check if XY CORD corresponds to a word in m_results.
		if so,
			Add an ID value to the corner of the square.
  When outputing the m_results vector,
		Use the id's table rather that the m_results table.

Sample Code

void CXwordDoc::Process(char *pRawData, unsigned int count)
	{
	CString buff;			char *p;
	// Fill the words vector
	p = pRawData;

	for(int words=0; words<5000; ++words)	// Now get the first 5000 words.
		{
		p = getNextWord(&buff, p, m_pFileData+m_nDocLength, DELIM);
		if (buff.GetLength() >= m_MINLEN && buff.GetLength() < m_MAXLEN)
			m_words.push_back(buff.GetBuffer(30));	   // Add to vector.
		if (!p) break;
		}
	m_wordCount = words;

	std::vector<CString>::iterator words_end;

	std::sort(m_words.begin(), m_words.end());
	words_end = std::unique(m_words.begin(), m_words.end());
	std::random_shuffle(m_words.begin(), words_end);

	std::vector<CString>::iterator vi;

	// for debugging, cycle through the vector
	//for (vi = m_words.begin(); vi != words_end;  ++vi)
	//	{
	//	p = (*vi).GetBuffer(30);
	//	TRACE( "%3d %s\n", i++, p);
	//	}

	// Create an empty puzzle
	m_parray = (char *) calloc(m_NX * m_NY, sizeof(char) );
	memset((void *)m_parray, ' ', m_NX * m_NY * sizeof(char) );

	// make the puzzle
	vi = m_words.begin();
	if (vi != words_end)
		{
		p = (*vi).GetBuffer(30);
		fstwrd(p);	// Put the first word in the middle of the field.
		TRACE( "First Word => %s\n", p);
		++vi;
		while (vi != words_end)
			{
			BOOL failure;
			p = (*vi).GetBuffer(30);

			failure = tryver(p);
			if (!failure)
				{
				TRACE( "Vertical ===> %s\n", p);
				}
			else
				{
				failure = tryhor(p);
				if (!failure) TRACE( "Horizontal => %s\n", p);
				}
			++vi;
			}
		}
	std::sort(m_results.begin(), m_results.end());
	Build_ids();
	}

SOURCE CODE

Source Code Files