algorithm - Numbrix 生成器算法

Question

我一直在尝试编写一个 Numbrix具有两个条件的生成器:

• 方形网格 10 x 10
• 数字 1 在网格的底行，100 在顶行

Numbrix 的规则是每个数字必须有一个边(在网格中)与后面的数字相同。

我一直在尝试制作一种算法来生成满足我所说的随机网格，但我一直无法做到。我的主要尝试是简单地继续随机尝试一条路径，在需要时返回，直到我找到一条以 100 结束在第一行的路径，但这似乎效率太低。

我希望在这里找到有关如何构建此类算法的指南。

我一直在尝试用 C++ 这样做，但由于这里的主要问题是算法，所以语言不应该是问题。

这是我现在的算法:

int nrow = 10;
int ncol = 10;

typedef vector< vector<int> > matrix;

bool generate_path(int x, int y, matrix &grid, int value, int maxused)
{
    if(x == 0) maxused++;
    if(maxused == ncol && value != nrow*ncol) return(false);
    grid[x][y] = value;
    if(grid[x][y] == nrow * ncol)
    {
        if(x == 0) return(true);
        grid[x][y] = 0;
        return(false);
    }
    // 0: North, 1: East, 2: South, 3: West
    bool directions[4];
    directions[0] = y+1 < ncol && grid[x][y+1] == 0;
    directions[1] = x+1 < nrow && grid[x+1][y] == 0;
    directions[2] = y > 0      && grid[x][y-1] == 0;
    directions[3] = x > 0      && grid[x-1][y] == 0;
    while(directions[0] || directions[1] || directions[2] || directions[3])
    {
        int direction = rand() % 4;
        while(!directions[direction]) direction = rand() % 4;
        switch(direction)
        {
            case 0:
                if(generate_path(x, y+1, grid, value+1, maxused)) return(true);
                directions[direction] = false;
                break;
            case 1:
                if(generate_path(x+1, y, grid, value+1, maxused)) return(true);
                directions[direction] = false;
                break;
            case 2:
                if(generate_path(x, y-1, grid, value+1, maxused)) return(true);
                directions[direction] = false;
                break;
            case 3:
                if(generate_path(x-1, y, grid, value+1, maxused)) return(true);
                directions[direction] = false;
                break;
        }
    }
    grid[x][y] = 0;
    return(false);
}

matrix generate_grid(const int &mult)
{
    matrix grid(nrow, vector<int> (ncol, 0));
    int x = nrow-1;
    int y = rand() % ncol;
    generate_path(x, y, grid, 1, 0);
    for(int i = 0; i < nrow; i++) for(int j = 0; j < ncol; j++) grid[i][j] = grid[i][j] * mult;
    return grid;
}

Answer 1

当我使用 Numbrix 时，我注意到数字通常位于随机位置，但总是有一个数字桥可以到达另一个数字，而且没有阻塞。

您可以自己在纸上写出一个 Numbrix，而不是尝试在计算机上计算出来。或者，您可以查找 Numbrix 并写下他们的，但根据自己的喜好稍作修改。希望这对您有所帮助!