-1

Excuse me, my primary language isn`t English.

I wrote a recursion function to resolve the "Queens Problem".

int* Queen_Recursion(int n,int nowRow = 1, int nowColumn = 1, int* map = nullptr)
{
    if (map == nullptr)
        map = new int[n + 1]{0};
    if (nowRow > n)
    {
        std::cout << "No." << ++map[0] << " Answer：";
        for (int i = 1; i < n + 1; i++)
            std::cout << '\t' << '(' << i << ", " << map[i] << ')';
        std::cout << std::endl;
        return Queen_Recursion(n, n, map[n] + 1, map);
    }
    else if (nowColumn > n)
    {
        if (nowRow == 1)
            return map;
        map[nowRow] = 0;
        return Queen_Recursion(n, nowRow - 1, map[nowRow - 1] + 1, map);
    }
    bool CanPlace = true;
    for (int i = 1; i < nowRow; i++)
        if (map[i] == nowColumn || i - nowRow == map[i] - nowColumn || i - nowRow == nowColumn - map[i])
            CanPlace = false;
    if (CanPlace)
    {
        map[nowRow] = nowColumn;
        return Queen_Recursion(n, nowRow + 1, 1, map);
    }
    else
        return Queen_Recursion(n, nowRow, nowColumn + 1, map);
}
int main()
{
    int* temp = Queen_Recursion(8);
    delete temp;
    return 0;
}

When I choose the "debug", it shows me only 5 answers.

enter image description here

When I choose the "Release", it shows me 92 answers. Certainly, it`s correct. enter image description here

Can someone tell me the reason?

By the way, I tried to set initial values of the "map", and I think there isn`t an out of bounds array access in this function.

Unhandled exception at 0x00007FF73D68298D in 04-Some Recursion Problems.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000FA88903EC0). occurred

Community
  • 1
  • 1
RabbitLime
  • 3
  • 3
  • 1
    your program *crashed* in debug mode. Run it under the debugger ans find out where. I'm guessing it's an out of bounds array access – Botje Apr 27 '20 at 08:13
  • "_and I think there isn`t an out of bounds array access in this function._" Do you **think**, or do you **know**? Did you try stepping through it, with a debugger, to make sure, as was suggested? – Algirdas Preidžius Apr 27 '20 at 08:20
  • 3
    Error -1073741571 = STATUS_STACK_OVERFLOW, appropriately enough. Try using one recursion per row or per placement, not one per square. – Rup Apr 27 '20 at 08:21
  • The stack consuming might be higher in debug mode than in release mode. However, VS has a commandline option (as well as a property setting) to increase the stack size provided to an executable: [SO: /F (Set Stack Size)](https://learn.microsoft.com/en-us/cpp/build/reference/f-set-stack-size) – Scheff's Cat Apr 27 '20 at 08:26
  • I think you can also drop the recursion again after you've printed an answer; that can't find anything else can it? – Rup Apr 27 '20 at 08:30
  • 2
    *Can someone tell me the reason?* -- You are using Visual Studio 2019, and you didn't see the big "Exception Unhandled" box when you ran the Debug Version? It is very clear as to the error. Why didn't you report this error in your question? – PaulMcKenzie Apr 27 '20 at 08:47

1 Answers1

0

Recursive functions like this function want a lots of stack. Your function called about 18000 times to solve your problem and it means the program need to keep 18000 functions stack.

Here is some tips for your code.

As errors shown your stack become full in your recursive call of your function.

As i see your value can't get higher than 8 ( Chess is 8*8 Square) You can change all the ints to uint8_t.

You can define variables like bool CanPlace outside of the function to reduce stack usage.

You can declear uint8_t i outside of your function, for your loop counter and this can help your program working better

Finally you need to resize your stack size of your project. The default stack size in Visual Studio is 1MB. you need to change it.

You can see THIS link to increase your stack size in visual studio.

MH Alikhani
  • 110
  • 7