抽象的な擬似コードバックトラッキングの要点を理解するために

bool Solve(configuration conf)
{
    if (no more choices) // BASE CASE
       return (if conf is goal state);

    for (all available choices)
    {
        try one choice c;
        // recursively solve after making choice
        ok = Solve(updated conf with choice c made);
        if (ok)
           return true;
        else
           unmake choice c;
    }

return false; // tried all choices, no soln found
}

すべての可能な解決策を見つける必要があるとき

void Solve(configuration conf,solutions& sols)
{
    if (no more choices) // BASE CASE
       if conf is goal state
           sols.add(conf);
       return;

    for (all available choices)
    {
        try one choice c;
        // recursively solve after making choice
        Solve(updated conf with choice c made);
        unmake choice c;
    }

return; // tried all choices, no soln found
}

例:

クィーンズ

問題声明

女王が他を攻撃しないように、サイズNXNはグリッドでnクィーンを配置します.
入力

N = 4

出力:

0  1  0  0
0  0  0  1
1  0  0  0
0  0  1  0

Pseudo Code

bool solve(grid,queens)
{
    //if(no more choices) //conf is goal state // BASE CASE
    if(queens==0)           
        return true;

    //for (all available choices)
    for(all safe grid cell c)
    {
        //try one choice c;
        // recursively solve after making choice
        put queen at cell c;
        // ok = Solve(updated conf with choice c made);
        ok = solve(grid,queens-1);

        if(ok)
            return true;
        else
            remove queen from cell c;   //unmake choice c;
    }

    return false;       // tried all choices, no soln found
}

Cpp code

//checks whether the cell (i,j) is unsafe or safe
bool is_Atttacked(int i, int j, vector<vector<int>>& grid)
{
    int N = grid.size();
    for (int ele : grid[i])
    {
        if (ele == 1)
            return true;
    }


    for (int row = 0; row < N; row++)
    {
        if (grid[row][j] == 1)
            return true;
    }

    for (int y = 0; y < N; y++)
    {
        int x = (i - j) + y;
        if (x >= 0 and x < N)
        {
            if (grid[x][y] == 1)
                return true;
        }
    }


    for (int y = 0; y < N; y++)
    {
        int x = (i + j) - y;
        if (x >= 0 and x < N)
        {
            if (grid[x][y] == 1)
                return true;
        }
    }

    return false;
}

//main recursive function
bool NQueens(vector<vector<int>>& grid, int N)
{
    if (N == 0)
        return true;

    for (int i = 0; i < grid.size(); i++)
    {
        for (int j = 0; j < grid.size(); j++)
        {
            if (is_Atttacked(i, j, grid))
                continue;

            grid[i][j] = 1;

            if (NQueens(grid, N - 1))
                               return true;
                        else
                    grid[i][j] = 0;
        }
    }
    return false;
}

ナイトツアー

問題声明

空のボードの最初のブロックに置かれた騎士とNXNボードを与えた.チェス騎士のルールに従って移動するたびに、各広場を訪問する必要があります.それぞれのセルの順番を表示します.
入力

N = 5

出力:

0  5  14 9  20 
13 8  19 4  15 
18 1  6  21 10 
7  12 23 16 3 
24 17 2  11 22

Pseudo code

//grid filled with -1 and grid[0][0] = 0 , steps = 1 , x=y=0
bool solve(grid,steps,x,y)
{
    if(steps==grid.size()^2)
    {
        print(grid);
        return true;
    }

    for(all possible/safe moves from (x,y))
    {
        grid[move.x][move.y] = steps;
        ok = solve(grid,steps+1,move.x,move.y);
        if(ok)
            return true;
        else
            grid[move.x][move.y] = -1;
    }
    return false;
}

Cpp code

#include <iostream>
#include <vector>

using namespace std;


void print(vector<vector<int>> &grid)
{
    for(auto row:grid)
    {
        for(auto ele:row)
        {
            cout<<ele<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}


int isSafe(int x, int y,vector<vector<int>>& grid )
{
    return (x >= 0 && x < grid.size() && y >= 0 && y < grid.size()
            && grid[x][y] == -1);
}

bool solve(vector<vector<int>> grid,int steps,int x,int y,vector<int> &xMove,vector<int> &yMove)
{

    if(steps == grid.size()*grid.size())
    {
        print(grid);
        return true;
    }
    for(int i=0;i<8;i++)    //for all possible moves from (x,y)
    {
        int Xnext = x+xMove[i];
        int Ynext = y+yMove[i];
        if(isSafe(Xnext,Ynext,grid))
        {
            grid[Xnext][Ynext]=steps;
            int ok = solve(grid,steps+1,Xnext,Ynext,xMove,yMove);
            if(ok)
                return true;
            else
                grid[Xnext][Ynext] = -1;
        }
    }

    return false;
}


int main() {
    int N = 5;
    vector<vector<int>> grid(N,vector<int>(N,-1));
    grid[0][0] = 0;
    vector<int> xMove{ 2, 1, -1, -2, -2, -1, 1, 2 };
    vector<int> yMove{ 1, 2, 2, 1, -1, -2, -2, -1 };

    solve(grid,1,0,0,xMove,yMove);
}

Cpp code for all possible solutions

#include <iostream>
#include <vector>

using namespace std;

void print(vector<vector<int>> &grid)
{
    for(auto row:grid)
    {
        for(auto ele:row)
        {
            cout<<ele<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}


int isSafe(int x, int y,vector<vector<int>>& grid )
{
    return (x >= 0 && x < grid.size() && y >= 0 && y < grid.size()
            && grid[x][y] == -1);
}


void solve(vector<vector<int>> grid,int steps,int x,int y,vector<int> &xMove,vector<int> &yMove)
{

    if(steps == grid.size()*grid.size())
    {
        print(grid);
        return;
    }
    for(int i=0;i<8;i++)    //for all possible moves from (x,y)
    {
        int Xnext = x+xMove[i];
        int Ynext = y+yMove[i];
        if(isSafe(Xnext,Ynext,grid))
        {
            grid[Xnext][Ynext]=steps;
            solve(grid,steps+1,Xnext,Ynext,xMove,yMove);
            grid[Xnext][Ynext] = -1;
        }
    }

    return;
}


int main() {
    int N = 5;
    vector<vector<int>> grid(N,vector<int>(N,-1));
    grid[0][0] = 0;
    vector<int> xMove{ 2, 1, -1, -2, -2, -1, 1, 2 };
    vector<int> yMove{ 1, 2, 2, 1, -1, -2, -2, -1 };

    solve(grid,1,0,0,xMove,yMove);
}

迷路内のすべてのパスを見つける/迷路のラット

問題文:

左上隅から右下隅までのサイズnxn findとprint pathのバイナリ行列を与えます.
入力

1 0 0 0
1 1 1 1
0 1 0 1
1 1 1 1

出力:

1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

1 0 0 0
1 1 1 1
0 0 0 1
0 0 0 1

Cpp code for all Possible Paths

#include <iostream>
#include <vector>

using namespace std;

void print(vector<vector<int>>& grid)
{
    for(int i=0;i<grid.size();i++)
    {
        for(int j=0;j<grid.size();j++)
        {
            cout<<grid[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}


bool isValid(vector<vector<int>> &maze,vector<vector<int>> &ans,int x,int y)
{
    return (x>=0 and x<maze.size() and y>=0 and y<maze.size() and maze[x][y]==1 and ans[x][y]==0);
}

void findPath(vector<vector<int>> &maze,vector<vector<int>> ans,int x,int y)
{
    if(ans[maze.size()-1][maze.size()-1] == 1)
        {
            print(ans);
            return;
        }

    if(isValid(maze,ans,x+1,y))     //down
    {
        ans[x+1][y] = 1;
        findPath(maze,ans,x+1,y);
        ans[x+1][y] = 0;
    }

    if(isValid(maze,ans,x-1,y))     //up
    {
        ans[x-1][y] = 1;
        findPath(maze,ans,x-1,y);
        ans[x-1][y] = 0;
    }

    if(isValid(maze,ans,x,y+1))     //right
    {
        ans[x][y+1] = 1;
        findPath(maze,ans,x,y+1);
        ans[x][y+1] = 0;
    }

    if(isValid(maze,ans,x,y-1))     //left
    {
        ans[x][y-1] = 1;
        findPath(maze,ans,x,y-1);
        ans[x][y-1] = 0;
    }
    return;
}

int main() {
    int x,y;
    x=0,y=0;

    vector<vector<int>> maze = { 
                    { 1, 0, 0, 0 },
                    { 1, 1, 1, 1 },
                    { 0, 1, 0, 1 },
                    { 1, 1, 1, 1 } };
    int N = maze.size();
    vector<vector<int>> ans(N,vector<int>(N,0));
    ans[0][0] = 1;

    findPath(maze,ans,x,y);
}

与えられた制約を満たすすべての可能な組み合わせを見つける

問題声明

1 nから2 nまでのすべての要素が正確に2回、それらの間の距離がその数に等しいように、数nが与えられる2 n数のすべての可能な組合せを見つけてください.
入力

N = 3

出力:

 3 1 2 1 3 2
 2 3 1 2 1 3

この問題において、再帰木は2通りに形成することができる.最初の方法では、最初の選択肢としてn要素を考慮すると他の選択肢として2 nの位置を考慮しています.最初の方法では、n個の要素のうちの1つを選び、配列の0番目の位置に置きます.次に、他のすべてのインデックス(ここでは、1回以上の数を指定しないようにする必要があります)を再帰します.第2の方法では、Nから最初の要素を取り、2 nの場所の1つを選択して、すべての他のn - 1の数字のための最初の要素と回帰を置く.第二の方法として、我々はそれを実装する簡単に思える.Pseudo Code

void solve(array,n)
{
    if(n becomes 0)
    {
        print array
        return;
    }

    for(all indices i in array)
    {
        if(inserting in n in array at index i is safe)  // safe means array[i] and array[i+n+1] is free
        {
            array[i] = n;       // put n at i and i+n+1
            array[i+n+1] = n;

            solve(array,n-1);   //recur for all n-1 numbers

            array[i] = -1;      //unmake choice
            array[i+n+1] = -1;
        }
    }
    return; //no soln found
}

Cpp code

#include <iostream>
#include <vector>

using namespace std;

void print(vector<int> ar)
{
    for(auto e:ar)
    {
        cout<<e<<" ";
    }
    cout<<endl;
}

bool is_safe(vector<int> array,int n,int i)
{
    return (i<array.size() and i+n+1<array.size() and array[i]==-1 and array[i+n+1]==-1);
}


void solve(vector<int> array,int n)
{
    if(n==0)
    {
        print(array);
        return;
    }

    for(int i=0;i<array.size();i++)
    {
        if(is_safe(array,n,i))
        {
            array[i] = n;
            array[i+n+1]=n;
            solve(array,n-1);
            array[i] = -1;
            array[i+n+1] = -1;
        }
    }
    return;
}

int main() {
    int N = 7;
    vector<int> v(2*N,-1);
    solve(v,N);
}

パーティション

問題声明

整数の配列が与えられると、配列は等しい和を持つk個のサブセットに分割されます.
入力

k = 3
array = 7 3 5 12 2 1 5 3 8 4 6 4

出力:

7 3 5 2 3 
12 8 
1 5 4 6 4 

この問題では、各要素ごとにkパーティションを選択しなければなりません.したがって、選択はKパーティションです、そして、我々は他のすべての要素のために再発します.Pseudo code

bool solve(partitons,sums,array,index,k)
{
    if(index is at end of array +1 and all the sums are equal)
    {
        print partitions;
        return true;
    }
    else if(index is at the ened of array +1 and all sums are not equal)
        return false;

    //choices for arrray[index] element
    for(all the part in partitions)
    {
        part.add(array[index])
        correspnding sum in sums+= array[index]
        //recurs for next element
        ok = solve(partitions,sums,array,index+1,k);    
        if(ok)
            return true;
        else
        {
            part.pop()
            correspnding sum in sums-= array[index];
        }
    }
    return false;   //all choices tried no solutions.
}

Cpp code

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void print(vector<vector<int>> grid)
{
    for(auto row:grid)
    {
        for(auto ele:row)
        {
            cout<<ele<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

void print(vector<int> v)
{
    for(auto ele:v)
        cout<<ele<<" ";
        cout<<endl;
}

bool solve(vector<vector<int>> parts,vector<int> sums,vector<int> vec,int index,int k)
{
   // if reached the end and all partition sum is equal
    if(index == vec.size() and all_of(begin(sums),end(sums),[&sums](int val){return val==sums[0];}))
    {
        print(parts);
        return true;
    }
    // if reached the end but all partition sum is not equal
    else if(index>=vec.size())
    {
        return false;
    }

    for(int i=0;i<k;i++)
    {
        parts[i].push_back(vec[index]);
        sums[i] += vec[index];
       // print(sums);
        bool ok = solve(parts,sums,vec,index+1,k);
        if(ok)
        {
            return true;
        }
        else
        {
            parts[i].pop_back();
            sums[i] -= vec[index]; 
        }
    }

    return false;
}

int main() {
    vector<int> vec{7, 3, 5, 12, 2, 1, 5, 3, 8, 4, 6, 4};
    int k = 3;
    vector<int> sums(k,0);
    vector<vector<int>> parts(k,vector<int>());
    solve(parts,sums,vec,0,k);
}

繰り返し使用可能なすべての組み合わせを印刷する

問題声明

配列と整数kが与えられたなら、すべてのk要素の組み合わせを繰り返します.
更新:私はこの問題についてのより一般的な考えを得て、それについて別々のポストを作りました.チェックアウト.
入力

k = 2
array = { 1, 2, 3 }

出力

1 1  1 2  1 3  2 2  2 3  3 3  

入力

k = 3
array = { 1, 2, 3, 4 }

出力

1 1 1  1 1 2  1 1 3  1 1 4  1 2 2  1 2 3  1 2 4  1 3 3   1 3 4  1 4 4  2 2 2  2 2 3  2 2 4  2 3 3  2 3 4  2 4 4   3 3 3  3 3 4  3 4 4  4 4 4

まず最初に、これが標準的な順列と組合せ物であることに注意してください.下の図を見てください.

我々の問題が順序と繰り返しを必要としないので、公式は第3のもの(あなたがthis pageをチェックする方法を知っていたいならば)です.そして、その式は、我々の問題のために数答えを与えます.しかし、それは助けません.
3番目の表の最初の列のパターンに注意してください.再帰を使用してこの問題を解決するには、まず我々は何を選択しているのかを考える.hmmm,より大きい入力データ配列からk個の要素のより小さな配列を作っている.そして、より小さな配列のインデックスの各々のために、我々はそのインデックスで何を置くべきかについて選択をしています.k - element配列のインデックス0には、より大きな配列からすべての要素を持つことができます.次のインデックス(子プロセスを参照)では、その要素(現在の親ノードを参照)の後にのみ要素を持つことができます.その小さな混乱.上記の最初の入力のために再帰木を理解するのをより簡単にするために.

次のレベルでノード2という音を観測した場合、2を含めて要素を持つことができます.(これは12と21が同じことであるため、逆コピーを避けるためです).Cpp Code

#include <iostream>
#include <vector>

using namespace std;

void print(vector<int> data)
{
    for (auto e : data)
    {
        cout << e << " ";
    }
    cout << endl;
}

//data index is the index for the actual data and out_index is for output k-element array
void solve(vector<int> data, int data_index, vector<int> out, int out_index)
{
    if (out_index == out.size())
    {
        print(out);
        return;
    }

    for (int i = data_index; i < data.size(); i++)
    {
        if(out[out_index]==-1)
            out[out_index] = data[i];
        solve(data,i, out, out_index + 1);
        out[out_index] = -1;
    }

    return;
}

int main() {
    vector<int> data{ 1,2,3,4 };
    int r = 3;
    vector<int> out(r, -1);
    solve(data, 0, out, 0);
}

1からnまでの数字のすべての組み合わせを合計n

問題声明

1からnまでの数字のすべての組み合わせを合計n
入力

n = 3

出力:

1 1 1
1 2
3

入力

n = 4

出力:

1 1 1 1
1 1 2
1 3
2 2
4

この問題を注意深く観察し、私の置換と組み合わせを読んでください.
この問題では、繰り返しが許可され、順序が重要ではないことは明らかです.そして、要素を選ぶセットは1です.合計.したがって、Nは合計です、しかし、我々は組合せの長さであるRを知りません.(PNC(Permutation and Combination)に示されている再帰木の中で覚えているのは、中間ノードを持っていることを覚えていてください.これらのノードは、例えば、4番目の組み合わせの木のすべてのノードを取ると、PowerSet(すべてのサブセットの集合)と呼ばれるものを見つけます.私たちは、私たちが深く行くように合計を減少させます、そして、各々のノードで、我々はサム= = 0かどうかチェックします、そして、それがそうであるならば、部分的な解決は可能な解決の我々の1つです.順序を気にするには、forループで親ノードから始めます.(もしあなたが私が何を話しているかわからないなら、私のPNCをチェックアウトしてください).Cpp code

#include <iostream>
#include <vector>


using namespace std;

void print(vector<int> data)
{
    for (auto e : data)
    {
        cout << e << " ";
    }
    cout << endl;
}


void solve(int i,int n,int sum,vector<int> out)
{

    if (sum == 0)
    {
        print(out);
        return;
    }
    if (sum < 0)
    {
        return;
    }

    for (int x = i; x <= n; x++)
    {
        out.push_back(x);
        sum -= x;
        solve(x, n, sum, out); 
        sum += x;
        out.pop_back();
    }
    return;
}


int main() {
    int sum = 4;
    solve(1, sum, sum, vector<int>());
}

与えられた目標以下の合計で配列のすべての三重項を印刷する

問題声明

与えられた目標以下の合計で配列Vのすべてのトリプレットを印刷する
入力

target = 10
v = { 2, 7, 4, 9, 5, 1, 3 }

出力:

2 7 1
2 4 1
2 4 3
2 5 1
2 5 3
2 1 3
4 5 1
4 1 3
5 1 3

この場合、Rは3に固定される.nは配列のサイズです.そして、値を選ぶセットは配列です.この問題では、順序は重要でありません、そして、繰り返しも許されません.これは4番目の組み合わせです.Cpp code

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void print(vector<int> data)
{
    for (auto e : data)
    {
        cout << e << " ";
    }
    cout << endl;
}

void solve(vector<int> v, int target, int r, int sum, vector<int> out = {}, int i = -1)
{
    if (r == 0 and sum <= target)
    {
        print(out);
        return;
    }
    if (sum > target)
    {
        return;
    }

    for (int x = (i==-1?0:i); x < v.size(); x++)
    {
        if (x == i) continue;
        out.push_back(v[x]);
        sum += v[x];
        r--;
        solve(v,target,r,sum,out,x);
        r++;
        sum -= v[x];
        out.pop_back();
    }
    return;
}


int main()
{
    vector<int> v{ 2, 7, 4, 9, 5, 1, 3 };
    int target = 10;
    solve(v, target,3,0);
    return 0;
}

文字列の非重複部分文字列のすべての組み合わせを検索する

問題声明

文字列の非重複括弧で囲まれた部分文字列のすべての組み合わせを検索する
入力

"ABC"

出力:

(ABC)
(AB) (C)
(A) (BC)
(A) (B) (C)

この質問を解決するために、スペースを置く場所に注意してください.を実行します.Cpp code

void solve(string data,int index,int n)
{
    if (n == 1)
    {
        cout <<"(" << data <<")" << endl;
        return;
    }
    n--;
    solve(data, index + 1, n);
    data.insert(index, ") (");
    solve(data, index + 4, n);  // +4 because insert added 3 extra chars
    //no need to remove em because this is the last choice
}

int main()
{
    string s = "ABC";
    solve(s,1,s.length());
    return 0;
}

//続く