0
Answer

Memory or looping issue

mathew davis

mathew davis
16y
3.7k
1
I am stuck! I thought I had figured it out but I still have some errors in my code I think I have an infinite looping problem or a memory management issue.  So I will try my best to explain better what I am trying to do.  First I am trying to solve the 8-Puzzle  problem.  The 8-Puzzle is identical to the 15-Puzzle only with 9 squares instead of 16.  Here is a link to 15 puzzle on Wikipedia for a good explanation I am sure all you really need to do is look at the picture and you can understand it http://en.wikipedia.org/wiki/8_puzzle.  So basically I am representing the board using a string of numbers like this.

"123456789" that is equivalent to the following board.

123
456
789

with the 9 being the blank or empty square.

So to start of with I make some random moves, so as to not make an impossible board state, that will shake up the board a little I will for simplicity sake only make one move, up.  That would change the board to "123459786" or

123
459
786

so the blank square moves up one which actually only switches the 6 and 9 places in the string.  I want to use a Breadth First Search and a Depth First Search to solve the problem.  I use a Queue to hold the states of the board for my Breadth First Search Algorithm and a Stack for my Depth First Search Algorithm, Wikipedia seems to agree that this is how to approach the problem.

I am having a terribly difficult time finding where my infinite loop is I am not good at debugging and short of walking through step by step for over a hundred iterations and checking each operation that it was correct I don't know how to track it down.  So my Breath First Search will solve many problems before I get the over flow error.  I have not yet solved a puzzle using my Depth First Algorithm.  I make sure and have a hash table to make sure I am not entering the same state over and over again.  For example taking the above random board of "123459786" if for my first move I choose left "123495786" then for my next iteration choosing right could put me into an infinite loop so I prune that option by checking to see if "123459786" is already in the tree which it is so I will not even push that move onto the stack as a possible move.  As far as I can see my logic is fine, but it obviously isn't fine.  So I will post all of my code for a bit so that maybe someone can get a better understanding it's not a whole lot.  The code may seem extra bloated that's because I took it out of a multi-threaded application that will animate the pieces for me and made it it's own application. So there will seem to be a lot of useless stuff floating around in the code but it is necessary for the whole application, but if something looks really fishy let me know I will let you know if that is ok or if your right.

Program.cs
using System; 
using System.Collections.Generic; 
using System.Collections; 
using System.Linq; 
using System.Text; 
 
namespace ConsoleApplication1 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            Hashtable Tree = Algorithms.solvePuzzle(); 
            //for now this goes backwords 
            if (Tree.Count > 0) 
            { 
                string board = "123456789"; 
                string pBoard = ""; 
                Console.WriteLine(board); 
                while (true) 
                { 
                    pBoard = (string)((State)Tree[board]).parentBoardState; 
                    if (pBoard == "") 
                        break; 
                    board = pBoard; 
                    Console.WriteLine(pBoard); 
                } 
            } 
            Console.ReadKey(); 
        } 
    } 
} 
 

State.cs
using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Collections; 
using System.Text; 
 
namespace ConsoleApplication1 
{ 
    class State 
    { 
        public Int32 hValue, depth = 0, direction = -1;  
         
        public static int currentDepth;  
        public static Stack directions = new Stack(); 
 
        public string parentBoardState; 
        public static string boardState = "123596478"; 
 
        public State(string board, string parentBoard) 
        { 
            boardboardState = board; 
            parentBoardparentBoardState = parentBoard; 
        } 
 
        public State(string board, Int32 pDirection, string parentBoard, int Depth) 
        { 
            boardboardState = board; 
            parentBoardparentBoardState = parentBoard; 
            depth = Depth; 
            direction = pDirection; 
        } 
 
        public void Copy(string board, string parentBoard) 
        { 
            parentBoardparentBoardState = parentBoard; 
            boardboardState = board; 
        } 
    } 
} 
 

Algorithms.cs - This is probably the only important one as State and Program don't really do much and Program has been working just fine.  If you want to change the board you start from you can edit the string that initially get's passed into the DFS function inside the solvePuzzle function.  If you want to do the Breadth First Search Algorithm just change the DFS to BFS and that's it.
using System; 
using System.Collections.Generic; 
using System.Text; 
using System.Collections; 
 
namespace ConsoleApplication1 
{ 
    class Algorithms 
    { 
        private static Hashtable Tree = new Hashtable(); 
 
        private static char[] charArray = new char[9]; 
 
        //the entry point method of this class. Get's called everytime a next move using DFS is required. 
        static public Hashtable solvePuzzle() 
        { 
            if (DFS("316498527", "")) 
            { 
                return Tree; 
            } 
 
            return new Hashtable(); 
        } 
 
        static private bool isValidMove(int direction, string board) 
        { 
            int pos = board.IndexOf("9"); 
            if ((pos < 0) || (pos > 8)) 
                return false; 
            else if ((direction == 0) && ((pos % 3) != 0)) //Left 
                return true; 
            else if ((direction == 2) && (((pos + 1) % 3) != 0)) //Right 
                return true; 
            else if ((direction == 3) && (!((pos + 3) > 8))) // Down 
                return true; 
            else if ((direction == 1) && (!((pos - 3) < 0))) // Up 
                return true; 
            return false; 
        } 
 
        static private bool isVisitedState(string board) 
        { 
            if (Tree.ContainsKey(board)) 
            { 
                return true; 
            } 
            return false; 
        } 
 
        static private Queue BFqueue = new Queue(); 
 
        static private bool BFS(string board, string parent) 
        { 
            string[] boardParent = new string[2]; 
            boardParent[0] = board; 
            boardParent[1] = parent; 
            State S = new State(board, parent); 
            Tree.Add(board, S); 
            BFqueue.Enqueue(boardParent); 
            return BFS(); 
        } 
        static private bool BFS() 
        { 
            string[] boardParent = (string[])BFqueue.Dequeue(); 
            if (isFinalState(boardParent[0])) 
                return true; 
            expandChildren(boardParent[0], ref BFqueue); 
            if (BFS()) 
                return true; 
            return false; //should never be hit ;) 
        } 
 
        static private Stack DFstack = new Stack(); 
 
        static private bool DFS(string board, string parent) 
        { 
            string[] boardParent = new string[2]; 
            boardParent[0] = board; 
            boardParent[1] = parent; 
            State S = new State(board, parent); 
            Tree.Add(board, S); 
            DFstack.Push(boardParent); 
            return DFS(); 
        } 
        static private bool DFS() 
        { 
            string[] boardParent = (string[])DFstack.Pop(); 
            if (isFinalState(boardParent[0])) 
                return true; 
            expandChildren(boardParent[0], ref DFstack); 
            if (DFS()) 
                return true; 
            return false; 
        } 
 
        static private void expandChildren(string board, ref Queue queue) 
        { 
            string boardboardParent = board; 
            if (isValidMove(2, board)) //test right 
            { 
                moveRight(ref board); 
                if (isVisitedState(board)) 
                { 
                    moveLeft(ref board); 
                } 
                else 
                { 
                    string[] boardParentArray = new string[2]; 
                    boardParentArray[0] = board; 
                    boardParentArray[1] = boardParent; 
                    queue.Enqueue(boardParentArray); 
                    State S = new State(board, boardParent); 
                    Tree.Add(board, S); 
                    moveLeft(ref board); 
                } 
            } 
            if (isValidMove(0, board)) //test left 
            { 
                moveLeft(ref board); 
                if (isVisitedState(board)) 
                { 
                    moveRight(ref board); 
                } 
                else 
                { 
                    string[] boardParentArray = new string[2]; 
                    boardParentArray[0] = board; 
                    boardParentArray[1] = boardParent; 
                    queue.Enqueue(boardParentArray); 
                    State S = new State(board, boardParent); 
                    Tree.Add(board, S); 
                    moveRight(ref board); 
                } 
            } 
 
            if (isValidMove(1, board)) //test up 
            { 
                moveUp(ref board); 
                if (isVisitedState(board)) 
                { 
                    moveDown(ref board); 
                } 
                else 
                { 
                    string[] boardParentArray = new string[2]; 
                    boardParentArray[0] = board; 
                    boardParentArray[1] = boardParent; 
                    queue.Enqueue(boardParentArray); 
                    State S = new State(board, boardParent); 
                    Tree.Add(board, S); 
                    moveDown(ref board); 
                } 
            } 
 
            if (isValidMove(3, board)) //test down 
            { 
                moveDown(ref board); 
                if (isVisitedState(board)) 
                { 
                    moveUp(ref board); 
                } 
                else 
                { 
                    string[] boardParentArray = new string[2]; 
                    boardParentArray[0] = board; 
                    boardParentArray[1] = boardParent; 
                    queue.Enqueue(boardParentArray); 
                    State S = new State(board, boardParent); 
                    Tree.Add(board, S); 
                    moveUp(ref board); 
                } 
            } 
        } 
        static private void expandChildren(string board, ref Stack queue) 
        { 
            string boardboardParent = board; 
            if (isValidMove(2, board)) //test right 
            { 
                moveRight(ref board); 
                if (isVisitedState(board)) 
                { 
                    moveLeft(ref board); 
                } 
                else 
                { 
                    string[] boardParentArray = new string[2]; 
                    boardParentArray[0] = board; 
                    boardParentArray[1] = boardParent; 
                    queue.Push(boardParentArray); 
                    State S = new State(board, boardParent); 
                    Tree.Add(board, S); 
                    moveLeft(ref board); 
                } 
            } 
            if (isValidMove(0, board)) //test left 
            { 
                moveLeft(ref board); 
                if (isVisitedState(board)) 
                { 
                    moveRight(ref board); 
                } 
                else 
                { 
                    string[] boardParentArray = new string[2]; 
                    boardParentArray[0] = board; 
                    boardParentArray[1] = boardParent; 
                    queue.Push(boardParentArray); 
                    State S = new State(board, boardParent); 
                    Tree.Add(board, S); 
                    moveRight(ref board); 
                } 
            } 
 
            if (isValidMove(1, board)) //test up 
            { 
                moveUp(ref board); 
                if (isVisitedState(board)) 
                { 
                    moveDown(ref board); 
                } 
                else 
                { 
                    string[] boardParentArray = new string[2]; 
                    boardParentArray[0] = board; 
                    boardParentArray[1] = boardParent; 
                    queue.Push(boardParentArray); 
                    State S = new State(board, boardParent); 
                    Tree.Add(board, S); 
                    moveDown(ref board); 
                } 
            } 
 
            if (isValidMove(3, board)) //test down 
            { 
                moveDown(ref board); 
                if (isVisitedState(board)) 
                { 
                    moveUp(ref board); 
                } 
                else 
                { 
                    string[] boardParentArray = new string[2]; 
                    boardParentArray[0] = board; 
                    boardParentArray[1] = boardParent; 
                    queue.Push(boardParentArray); 
                    State S = new State(board, boardParent); 
                    Tree.Add(board, S); 
                    moveUp(ref board); 
                } 
            } 
        } 
 
        static private void movePuzzle(int direction, ref string board) 
        { 
            if (direction == 0) //Move Left 
            { 
                moveLeft(ref board); 
            } 
            else if (direction == 1) //Move Up 
            { 
                moveUp(ref board); 
            } 
            else if (direction == 2) //Move Right 
            { 
                moveRight(ref board); 
            } 
            else if (direction == 3) //Move Down 
            { 
                moveDown(ref board); 
            } 
 
        } 
        public static void moveLeft(ref string board) 
        { 
            int pos = board.IndexOf("9"); 
 
            //char[] charArray = new char[9]; 
            charArray = board.ToCharArray(); 
            charArray[pos] = board[pos - 1]; 
            charArray[pos - 1] = '9'; 
 
            board = new string(charArray); 
        } 
 
        public static void moveRight(ref string board) 
        { 
            int pos = board.IndexOf("9"); 
 
            //char[] charArray = new char[9]; 
            charArray = board.ToCharArray(); 
            charArray[pos] = board[pos + 1]; 
            charArray[pos + 1] = '9'; 
 
            board = new string(charArray); 
        } 
 
        public static void moveUp(ref string board) 
        { 
            int pos = board.IndexOf("9"); 
 
            //char[] charArray = new char[9]; 
            charArray = board.ToCharArray(); 
            charArray[pos] = board[pos - 3]; 
            charArray[pos - 3] = '9'; 
 
            board = new string(charArray); 
        } 
 
        public static void moveDown(ref string board) 
        { 
            int pos = board.IndexOf("9"); 
 
            //char[] charArray = new char[9]; 
            charArray = board.ToCharArray(); 
            charArray[pos] = board[pos + 3]; 
            charArray[pos + 3] = '9'; 
 
            board = new string(charArray); 
        } 
 
        public static bool isFinalState(string board) 
        { 
            if (board == "123456789") 
                return true; 
            return false; 
        } 
    } 
} 
 
Next Recommended Forum