recursive solution not working as intended/ running into errors

I'm looking for some help on a problem that I vaguely inquired about before, which is solving 15-peg solitaire recursively. I keep getting strange errors when I compile and run it, most of them say "stack overflow" or that I'm getting a seg fault. This is what I have so far, where "board[15]" represents the 15 peg board, and "moves[36]" represents all of the possible moves that can be made. The recursion is supposed to spot when there is only one peg left.

#include <iostream> using namespace std; void solveGame(int a[15], int b[36][3], int c[15][4]); void chooseMove (int a[15], int b[36][3], int openSpace, int c[15][4]); int findEmpty (int a[15]); int pegCount (int a[15]); bool isPeg (int peg, int a[15]); int usedVals[15] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; int d = 0; int index = 0; int main () { int openSpace = 5; int board[15]= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; board[openSpace] = 0; int alreadyMoved[15][4]; int moves[36][3] = {{0, 1, 3}, {0, 2, 5}, {1, 3, 6}, {1, 4, 8}, {2, 4, 7}, {2, 5, 9}, {3, 6, 10}, {3, 7, 12}, {3, 1, 0}, {3, 4, 5}, {4, 7, 11}, {4, 8, 13}, {5, 9, 14}, {5, 8, 12}, {5, 2, 0}, {5, 4, 3}, {6, 3, 1}, {6, 7, 8}, {7, 4, 2}, {7, 8, 9}, {8, 4, 1}, {8, 7, 6}, {9, 5, 2}, {9, 8, 7}, {10, 6, 3}, {10, 11, 12}, {11, 7, 4}, {11, 12, 13}, {12, 7, 3}, {12, 8, 5}, {12, 11, 10}, {12, 13, 14}, {13, 8, 4}, {13, 12, 11}, {14, 9, 5}, {14, 13, 12}}; solveGame(board, moves, alreadyMoved); for (int i = 0; i < 13; i++) cout << alreadyMoved[i][0] << " " << alreadyMoved[i][1] << " " < <alreadyMoved[i][2] << endl; return 0; } // main recursive function void solveGame (int a[15], int b[36][3], int c[15][4] { int empSpace; int moveIndex; if (pegCount(a) < 2) { cout<<"game over"<<endl; } else { empSpace = findEmpty(a); chooseMove(a, b, empSpace, c); solveGame(a, b, c); } } // supposed to pick a move that is applicable to the board otherwise it find a new move void chooseMove (int a[15], int b[36][3], int openSpace, int c[15][4]) { int i = 0; while (1) { if (i < 36 && b[i][2] == openSpace && isPeg(b[i][0],a) && isPeg(b[i][1],a)) { a[b[i][0]] = 0; a[b[i][1]] = 0; a[b[i][2]] = 1; c[d][0] = b[i][0]; c[d][1] = b[i][1]; c[d][2] = b[i][2]; c[d][3] = i; d++; index = 0; for (int v = 0; v < 15; v++) usedVals[v] = -1; break; } else if (i > 35) { a[b[c[d-1][3]][0]] = 1; a[b[c[d-1][3]][1]] = 1; a[b[c[d-1][3]][2]] = 0; c[d-1][0] = 0; c[d-1][1] = 0; c[d-1][2] = 0; c[d-1][3] = 0; usedVals[index] = openSpace; index++; int newOpen = findEmpty(a); chooseMove(a, b, newOpen, c); } i++; } } // counts the pegs on the board in order to cancel recursion int pegCount (int a[15]) { int count = 0; for (int i = 0; i < 15; i++) if (a[i] == 1) count++; return count; } // finds an empty space that hasn't already been found faulty int findEmpty (int a[15]) { for (int i = 0; i < 15; i++) { for(int j = 0; j < 15; j++) { if(a[i] == 0 && i != usedVals[j] && usedVals[j] > -1) return i; } } } // tests if current index is a peg bool isPeg (int peg, int a[15]) { return a[peg] == 1; }

-------------Problems Reply------------

A quick glance shows a lot of potential problems, but I think it probably boils down to the way you are passing arrays. Arrays are passed by reference and not by value, so the recursive function is working with a single copy of the array, which I don't think is what you want. Therefore you are never finding the ending move, which will get you a stackoverflow from unlimited recursion.

Try allocating a new copy of the arrays at each level of recursion. Some people will want you to use new or malloc for this, because they feel an introduction to C++ should be a trial by fire where you have to master memory management to do anything useful. Instead, I would advise you not to use arrays at all; use a collection class that will work properly when passed by value (I think std::vector of POD will do this) and the collection class will create copies of your arrays the way your code seems to expect.

You may also be having a problem of doing a depth-first search in chooseMove, when you really want a breadth-first search.

Stack overfow when using recursivity is pretty common. This is due to the fact that return values for function calls are stored into the stack, and the stack keeps filling as long as function does not return. If the recursivity goes too deep, you end up filling your whole stack and overflowing it, which also causes SEGV.

Usually you get a stack overflow when your exit condition does not work, but here you are also passing your parameters by value, which might overflow your stack even in normal operation.

I suggest you pass your arrays by reference or better in a std::vector. An std::vector is a small object that holds the real data in a heap allocated space. You can even return those.

I also suggest that you start your program in a debugger, that is the simplest and most effective way to find out what exactly is going wrong.


Category:c# Views:0 Time:2012-02-08

Related post

  • Run-time error 4172 2012-10-04

    I have several groups of docs I open with macros. Now when I try to open any of them, I get run time error 4172. I have no idea what this means and I know nothing about debugging macros. Any ideas? --------------Solutions------------- I believe the R

  • run-time error '91' when closing ms word 2007 2014-12-14

    Today, I experienced having the message "run-time error '91'" when I close ms word 2007. How can I get rid of this problem? --------------Solutions------------- Anything that says "run-time error" is coming from a macro. If the message appears every

  • OLAddin run-time error '75": path/file access error 2015-03-03

    when i open outlook, i receive the following OLAddin run-time error '75': path/file access error. what does this mean? I also cannot get my incoming emails unless I turn off my Norton virus protection program -- what's with that? --------------Soluti

  • Is there a problem that has only a recursive solution? 2009-07-07

    Possible Duplicates: Is there a problem that has only a recursive solution? Can every recursion be converted into iteration? “Necessary” Uses of Recursion in Imperative Languages Is there a problem that has only a recursive solution, that is, a probl

  • What is the best way to plan a recursive solution to a problem? 2011-09-06

    I am learning about recursion. I have solved some other problems using recursion, such as creating a binary tree, Towers of Hanoi, etc. So, I understand what recursion is, but I find myself having difficulty planning and implementing a correct recurs

  • Recursive function taking too long to run when value of "n" is large 2014-07-14

    I am trying to get the value for a n-th series. such that f(n)=2014*f(n-1) + 69*f(n-2) for (n>2) and f(n)=1 for n<=2. I am using BigInteger as it is my requirement. While running code for smaller values I am getting answer. When n exceeds such

  • Iterative vs recursive solution in BST 2011-12-05

    public double FindMin() { Node current = root; while (!(current.left == null)) current = current.left; return current.Data; } public double FindMax() { Node current = root; while (!(current.right == null)) current = current.right; return current.Data

  • What is a non recursive solution for Fibonacci-like sequence in Java? 2012-02-03

    Given this pseudo code of a function f(0) = 1; f(1) = 3; f(n) = 3 * f(n - 1) - f(n - 2); // for n >= 2. Is there a non recursive way of doing this? --------------Solutions------------- Yes, all recursive algorithms can be converted into iterative

  • Recursive solution to Sudoku generator 2012-03-31

    I'm trying to code an algorithm that creates a legal Sudoku board in either Java or Javascript. Neither work, and I'm not entirely sure why. Essentially, the problem in both programs is that either x or y is getting incremented more than it should (s

  • Windows Update error code 0x800A0046. Have tried all the proposed solutions in all forums, including running MS Fix It. Nothing works. 2014-05-12

    Have tried all the proposed solutions in all forums, including running MS Fix It. Nothing works. --------------Solutions------------- Did you use this guide: Hi, 1. Which update

  • vba string assignment. WHy am I getting 1004 run time error? 2011-07-22

    On the below line in my code I am getting a 1004 run time error: Application-defined or object-defined error. I think it might be a problem on the right side of the statement. However, I've changed the way it is written a few times to no avail. As yo

  • IE shows run time error for innerHTML 2012-02-02

    I have a jsp page in which rows are created dynamically to a table using java script. It is working fine in all the browsers except IE. In IE it is showing the error Unknown run time error.. I have attached the java script function function addrow(ta

  • Run-time error '3662' This recordset is not updateable 2013-06-04

    I am building a search screen using the example posted by Allen Browne The search part works fine (at last) but I am getting the following error "Run-time error '3662' This recordset is not updateable" when I try t

  • VBA Run time error 1004 Too many different cell formats 2014-02-04

    I am posting and recalculating daily multi data on many pages. The calculations and Macros work well on each page. The entire program has worked well on one day's data, but crashed today with the following note: Run-time error '1004': Too many differ

  • Run-time error "4605" "... not a table" 2014-06-10

    I am learning VBA and am using a WORD 2007 macro-enabled template to capture hours worked and accomplishments for four tasks. I need to SUM the rows for each task and SUM the columns for each day of the week. I do not want to have to click on the tot

  • Run time error '13' type mismatch, if replace long with int then run time error '6' overflow 2014-07-17

    I'm new to VBA and am trying to design a program that will go through a column with Strings in it and for every unique String name create a new worksheet object with that String value as its name and then copy and paste the values in that row to the

  • What could cause Run-time error 1012 Error accessing application data directories 2008-09-05

    Friend of mine has a problem :). There is an application written in Visual Basic 6.0 (not by him). One of users reported that when it run on Windows 2000 and tried to scan folders on disk it raised box with message: Run-time error 1012 Error accessin

  • What could cause Vb6 run time error 430 2008-11-11

    I have a COM dll written in vb6. When I try to create a new object of a class module from this dll I get a Run timer error 430: Class does not support automation or does not support expected interface. The interesting thing is that this happens only

  • Run-time error 0 when populating a combo box in vb6 2008-11-28

    Strange error specific to a particular machine... I have a app in which a combo box's text value is set to the path of a document (i.e... cmbAIDFile.Text = clsTonyToolkit.GetSetting("ExportAIDFile",gtypmetadata.gcnnCentral) & "" Forget about all

Copyright (C), All Rights Reserved.

processed in 0.180 (s). 11 q(s)