-1

I am trying to solve the "N Queen Problem" using backtracking but due to some error it is showing runtime error. On compilation it displays runtime error and gives the message dynamic-stack-buffer-overflow on address ******

Checked the code many times but was unable to find the source of the problem

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> temp;
        int arr[n]={0};
        arr[0]=99;
        vector<int> queen;
        calc(result,n,temp,arr,0,queen);
        return result;
    }

    void calc(
        vector<vector<string>>& result,
        int n, vector<string>& temp,
        int * arr,
        int count,
        vector<int>& queen
    ) {
        if(count==n)
        {
            for(int k=0;k<queen.size();k++)
            {
                string s="";
                for(int m=1;m<=n;m++)
                {
                    if(m==queen[k])
                        s=s+'Q';
                    else
                        s=s+'.';
                }
                temp.push_back(s);
            }
            result.push_back(temp);
        }
        else{
            for(int i=1;i<=n;i++)
            {
                if(arr[i]==0)
                {
                    int temp1[n]={0};
                    temp1[0]=99;
                    for(int j=1;j<=n;j++)
                    {
                        temp1[j]=arr[j]+temp1[j];
                        if(arr[j]!=0)
                            temp1[j+1]++;
                    }
                    queen.push_back(i);
                    temp1[i]++;
                    calc(result,n,temp,temp1,count+1,queen);
                    queen.pop_back();
                }
            }
        }
    }
};
Skrino
  • 520
  • 2
  • 12
Jatin
  • 3
  • 1
  • 3
    "On compilation" and "runtime error" are contradictory. If the program won't compile, we'll need at least the full compiler error message to help, and a [mre] will make helping much easier. If the program compiles but something goes wrong when you execute it, it's time to debug. If you're new to debugging, there are some hints at https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ – aschepler Aug 06 '19 at 21:02
  • Just from looking at this, it could be that the compiler doesn't like that you declare `int arr[n]`. Some compilers, and newer standards I believe, will support this, but it's much safer to dynamically allocate in such a case. – anonmess Aug 06 '19 at 21:10
  • 1
    @anonmess VLAs are only in C99+, but were never accepted into C++. – Deduplicator Aug 06 '19 at 21:12
  • 1
    "newer standards I believe, will support this" - the construct is not, and never will be, part of C++ –  Aug 06 '19 at 21:13
  • @Deduplicator Ah ok I wasn't sure, I'm much more familiar with C than especially >C++11. – anonmess Aug 06 '19 at 21:17
  • There is a topic here about why `VLAs` are not part of `c++`: https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard – drescherjm Aug 06 '19 at 21:18
  • @drescherjm very interesting reading, thanks for that. – anonmess Aug 06 '19 at 21:24

1 Answers1

0
 for(int i=1;i<=n;i++)
            {
                if(arr[i]==0)

Valid indexes into arr are 0 through n-1. On the last iteration of this loop, when i == n, arr[i] exhibits undefined behavior, by way of accessing an index out of bounds.

Similarly with temp1[j] and, even more so, temp1[j+1] in the inner loop.

Igor Tandetnik
  • 50,461
  • 4
  • 56
  • 85