Numbrix生成算法

我一直試圖編程Numbrix發生器與兩個條件：Numbrix生成算法

方格網10×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; 
}

來源

2016-04-13 Albert Masclans

一個回溯算法 - 你有一個味道 - 是一個完全合理的方法來解決這個問題。 [這是實現Sudoku解算器的常用方法]（https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Backtracking），這是一個類似的問題。你覺得這個問題是什麼？ –

雖然它似乎適用於6x6網格（例如），但對於10x10網格，它需要**太長時間**。 –

也許有一種方法可以比你現在做的更快？ – Simon

-1

當我做Numbrix，我注意到，這些數字通常是隨機的地方，但總是有編號的橋才能到其他號碼，並沒有堵塞。

你可以在紙上寫出一個Numbrix，而不是試圖在計算機上找出它。或者，你可以查閱Numbrix並寫下它們，但根據自己的喜好改變它。希望這可以幫助！

來源

2017-02-12 15:14:03 user7553779

Numbrix生成算法

回答

相關問題