创建填字游戏生成器

• 下载源代码 - 105.4 KB

背景

填字游戏是一种由白色和黑色方格组成的文字游戏，单词以水平和垂直的方式放置在这些方格上，并且任何两个交叉的单词都必须在交叉点具有相同的字母。

本文档中描述和包含的应用程序，在需要创建一种将单词排列成填字游戏形式的机制时非常有用，这将是编写线索和问题的第一步，而这些线索和问题的答案将构成这些单词。

应用程序

在设计此应用程序时，需要遵守以下几项准则：

• 支持从右到左的语言，例如希伯来语。为了满足此要求，此类语言的单词在水平放置时从右到左排列，但在垂直放置时仍然从上到下排列。拉丁语单词从左到右，从上到下排列。
• 同维度的单词之间的最小距离。水平或垂直放置的两个单词之间至少会有一个黑色方格分隔。
• 优化过程，用于查找给定单词集的最佳排列方式，从而留下最少数量的黑色方格。
• 从文件加载单词，或手动放置它们。文件应为ASCII格式，每行一个单词。

代码

演示源代码是使用C#和Visual Studio 2010创建的。

有几个构建块：

首先，对于每个要放置的单词，我们检查该位置是否有效

bool IsValidPosition(int x , int y)
{  
     return x >= 0 && y >= 0 && x < _n && y < _m;
}   

即使位置有效，我们还会检查是否有其他单词与我们要放置的单词相交，如果有，则交叉点必须具有相同的字母，无论是水平放置的单词还是垂直放置的单词。

int CanBePlaced(string word, int x, int y, int dir)
{
            var result = 0;
            if (dir == 0)
            {
                for (var j = 0; j < word.Length; j++)
                {
                    int x1 = x, y1 = y + j;
                    if (!(IsValidPosition(x1, y1) && (_board[x1, y1] == ' ' || 
                                                      _board[x1, y1] == word[j])))
                        return -1;
                    if (IsValidPosition(x1 - 1, y1))
                        if (_hWords[x1 - 1, y1] > 0)
                            return -1;
                    if (IsValidPosition(x1 + 1, y1))
                        if (_hWords[x1 + 1, y1] > 0)
                            return -1;
                    if (_board[x1, y1] == word[j])
                        result++;
                }
            }
            else
            {
                for (var j = 0; j < word.Length; j++)
                {
                    int x1 = x + j, y1 = y;
                    if (!(IsValidPosition(x1, y1) && (_board[x1, y1] == ' ' || 
                                                      _board[x1, y1] == word[j])))
                        return -1;
                    if (IsValidPosition(x1, y1 - 1))
                        if (_vWords[x1, y1 - 1] > 0)
                            return -1;
                    if (IsValidPosition(x1, y1 + 1))
                        if (_vWords[x1, y1 + 1] > 0)
                            return -1;
                    if (_board[x1, y1] == word[j])
                        result++;
                }
            }
            int xStar = x - _dirX[dir], yStar = y - _dirY[dir];
            if (IsValidPosition(xStar, yStar))
                if (!(_board[xStar, yStar] == ' ' || _board[xStar, yStar] == '*'))
                    return -1;
            xStar = x + _dirX[dir]*word.Length;
            yStar = y + _dirY[dir]*word.Length;
            if (IsValidPosition(xStar, yStar))
                if (!(_board[xStar, yStar] == ' ' || _board[xStar, yStar] == '*'))
                    return -1;
            return result == word.Length ? -1 : result;
        }

然后，当我们实际放置单词时，我们会调用

void PutWord(string word , int x , int y , int dir, int value)
{
    var mat = dir==0 ? _hWords :_vWords;
    for (var i = 0; i < word.Length; i++)
    {
        int x1 = x + _dirX[dir]*i, y1 = y + _dirY[dir]*i;
        _board[x1, y1] = word[i];
        mat[x1, y1] = value;
    }
    int xStar = x - _dirX[dir], yStar = y - _dirY[dir];
    if (IsValidPosition(xStar, yStar)) _board[xStar, yStar] = '*';
    xStar = x + _dirX[dir]*word.Length;
    yStar = y + _dirY[dir]*word.Length;
    if (IsValidPosition(xStar, yStar)) _board[xStar, yStar] = '*';
}

此应用程序仅用于演示目的。它创建一个13 X 17的矩阵。“优化”按钮尝试随机放置给定的单词列表，同时寻找最佳结果，最多持续1分钟。显然，这并不是真正的优化，并且可以进行许多改进，这将受到热烈欢迎。

历史

• 2013年1月19日：初始版本

Michael Haephrati，CodeProject MVP 2013