N-Rooksバックトラック数バックトラッキング

Question

これらのメソッドは、非攻撃的な配置でボード上に任意の数のルーキが持つ可能性のあるアレンジ数を与えることになっています。 私はここで何か愚かな行方を見つけなければならないことを知っています。私を助けてください。何らかの理由で私の返されたソリューションの数はオフになっていますが、printステートメント6の解決策が見つかったとしても...解決策が見つかったら印刷してみました。

EDIT *：ユーザーインターフェイスが不完全です。その中にある間違ったエラーを無視してください。私がfindnumsolution（）メソッドから得ている不正確な結果にもっと関心があります。私は直接コンストラクタを介して値を渡してみましたが、それでも私には間違った答えが与えられます。 3x3ボード、3枚、返品5、4x4、返品数：4返品13：

EDIT **：無関係なコードが削除されました。

NRooks(int board[8][8], int n, int k) 
{ 
    numRooks = n; 
    boardSize = k; 
    numSolutions = 0; 
    for(int i = 0; i < 8; i++) 
     for(int j = 0; j < 8; j++) 
      board[i][j] = 0; 
    numSolutions = findNumSolutions(board, 0, numRooks); 
} 

bool canPlace(int col, int row, int board[8][8]) 
{ 
    for(int i = col-1; i >= 0; i--){ 
     if(board[i][row] == 1){ 
      return false; 
     } 
    } 
    return true; 
} 

int findNumSolutions(int board[8][8], int col, int rooksLeft) 
{ 
    if(col > boardSize||rooksLeft ==0) 
     return 1; 
    int nsolutions = 0; 
    for(int i = 0; i < boardSize; i++){ 
     board[col][i] = 1; 
     if(!canPlace(col, i, board)){ 
      continue; 
     } 
     nsolutions += findNumSolutions(board, col + 1, rooksLeft - 1); 
     board[col][i] = 0; 
    } 
    return nsolutions; 
} 

Answer 1

最初のエラーは、ローカル変数を使用する必要がある再帰関数でメンバー変数を使用することです。ここには2つの変種があります：各呼び出しから数値を返すか、グローバル関数またはメンバ関数を持ち、そこで解を累積します。これらのアプローチを混在させないでください。

オリジナルのポストではありませんでした2番目のエラー、がありますが、全体のコードを掲示したときに導入された、ここにある：

// try placing piece in row of col 
for (int i = 0; i < boardSize; i++){ 
    board[col][i] = 1; 
    if (canPlace(col, i, board)) { 
     nsolutions += findNumSolutions(board, col + 1, rooksLeft - 1); 
     board[col][i] = 0; 
    } 
} 

：

// try placing piece in row of col 
for(int i = 0; i < boardSize; i++){ 
    board[col][i] = 1; 
    if(!canPlace(col, i, board)){ 
     continue; 
    } 
    nsolutions += findNumSolutions(board, col + 1, rooksLeft - 1); 
    board[col][i] = 0; 
} 

これは同等です

ルークの設定と復元は対称でなければなりません。ルーキーが置かれるたびに、新しいルーキーを置こうとする前に、または再びルーキーをやり直す前に、それを休まなければなりません。ルークはすべての場合に配置されているが、配置できるときにのみクリーンアップされていることがわかります。この結果、より多くのルークがボード上にある必要があります。

このチェックでは現在の列は考慮されないため、両方のルックプレースメントを中かっこの外側に配置することができます。私は次のように提案します：

for (int i = 0; i < boardSize; i++){ 
    if (canPlace(col, i, board)) { 
     board[col][i] = 1; 
     nsolutions += findNumSolutions(board, col + 1, rooksLeft - 1); 
     board[col][i] = 0; 
    } 
} 

補足として、私はそのクラスが自分のボードを管理すべきだと思います。これは多くの混乱を避けるでしょうboardパラメータ。ヒープにボードサイズを割り当てる場合は、MAXSIZEも必要ありません。しかし、注意：ボードのサイズが大きくなると、アレンジの数はintをオーバーフローします。

#include <iostream> 

class NRooks { 
public: 
    NRooks(int n, int k); 
    ~NRooks(); 

    int getSolutionTotal(); 

private: 
    bool canPlace(int col, int row); 
    int findNumSolutions(int col, int rooksLeft); 

    int numSolutions; 
    int numRooks; 
    int boardSize; 
    int *data; 
    int **board; 
}; 

NRooks::NRooks(int n, int k) 
{ 
    numRooks = n; 
    boardSize = k; 
    numSolutions = 0; 

    data = new int[k*k]; 
    board = new int*[k]; 

    for (int i = 0; i < k; i++) board[i] = data + k*i; 
    for (int i = 0; i < k*k; i++) data[i] = 0; 

    numSolutions = findNumSolutions(0, numRooks); 
} 

NRooks::~NRooks() 
{ 
    delete[] data; 
    delete[] board; 
} 

int NRooks::getSolutionTotal(){ 
    return numSolutions; 
} 

bool NRooks::canPlace(int col, int row) 
{ 
    for (int i = col; i-- > 0;) { 
     if (board[i][row]) return false; 
    } 

    return true; 
} 

int NRooks::findNumSolutions(int col, int rooksLeft) 
{ 
    if (rooksLeft == 0) return 1; 
    if (col > boardSize) return (rooksLeft == 0); 

    int nsolutions = 0; 

    for (int i = 0; i < boardSize; i++) { 
     if (canPlace(col, i)) { 
      board[col][i] = 1; 
      nsolutions += findNumSolutions(col + 1, rooksLeft - 1); 
      board[col][i] = 0; 
     } 
    } 

    if (rooksLeft < boardSize - col) { 
     nsolutions += findNumSolutions(col + 1, rooksLeft); 
    } 

    return nsolutions; 
} 

int main() 
{ 
    for (int boardSize = 2; boardSize <= 6; boardSize++) { 
     for (int numPieces = 1; numPieces <= boardSize; numPieces++) { 
      NRooks r = NRooks(numPieces, boardSize); 

      std::cout << boardSize << " board, " 
         << numPieces << " rooks, " 
         << r.getSolutionTotal() << " solutions" 
         << std::endl; 
     } 
    } 

    return 0; 
} 

Answer 2

私はこのコードのバグを教えていませんが、私はバックトラッキングなしで効率的なソリューションを持っています。それは唯一の数学問題です。

この問題は、整数NとKが与えられた場合、K * KボードにN個のルークを入れる方法の数を見つけることです。

N> Kの場合、答えはゼロです。
N = Kの場合、答えはK！です。各列で1つのルークを選択できるので、ウェイ数は置換の数に等しいp={1, 2, 3,..., K}

N < Kケースについて考えてみましょう。
実際には、答えはP(K, N) * C(K, N)です。 ボードサイズがN * Kの場合、1 < = p [i] < = Kとp [i]の値が異なるパーミュテーションのみを選択できます。
したがって、P(K, N)の方法があります。
ルークを置くK行のN行も選択します。そして、C(K, N)方法があります。
はその後、最終的な答えは、あなたがP（順列）またはC（コンビネーション）を知らない場合は、hereをお読みくださいP(K, N) * C(K, N)

です。
最後に、N < = Kなら答えはP(K, N) * C(K, N)、そうでない場合は答えはゼロです。
時間複雑度はO(K)であり、O(P(K, N) * C(K, N))ブルートフォースアルゴリズムよりも優れています。

Answer 3

私はsquare1001

#include <iostream> 
using namespace std; 

long long fact(int n) 
{ 
    long long factorial=1; 
    if(n<=0) 
    { 
     return 1; 
    } 
    for(int i=1; i<=n; ++i) 
    { 
     factorial *= i;    // factorial = factorial*i; 
    } 
    return factorial; 
} 
long long permutation(int n, int r) { 
    if(n<=0 || r<= 0) 
    { 
     return 1; 
    } 
    return fact(n)/fact(n-r); 
} 

long long combination(int n, int r) { 
    if(r > n/2) r = n - r; // because C(n, r) == C(n, n - r) 
    long long ans = 1; 
    int i; 

    for(i = 1; i <= r; i++) { 
     ans *= n - r + i; 
     ans /= i; 
    } 

    return ans; 
} 

long long findNumSolutions(int boardSize,int numberofRooks) 
{ 
    if(numberofRooks>boardSize || numberofRooks <=0) 
    { 
     return 0; 
    } 
    long long comb=combination(boardSize,numberofRooks); 
    long long perm=permutation(boardSize,numberofRooks); 
    cout<<"comb : "<<comb<<endl; 
    cout<<"perm : "<<perm<<endl; 
    return comb*perm; 
} 

int main() 
{ 
    std::cout <<findNumSolutions(3,3)<<endl; 

    return 0; 
}