c - I am looking for how to do the two (BFS, DFS) searches for my 8 puzzle. I'm so close to done -

i've linked code here..i don't feel understand search algorithms. haven't tried attempt them, know don't have thing else. feel though simple me understand.

when read on breadth-first search, understand have search rows before move down level on tree (and same depth first moving down), how coded? i'm stumped.

basically, 8-puzzle using glut/opengl, computer search you, , supposed output moves said user. blank start in middle. save order in array, , need output moves. thing stumped on search itself.

#include <stdio.h>                         // standard c libraries #include <stdlib.h> #include <math.h> #include <time.h> #include <string.h> #include <gl/glut.h>                       // glut library #include "cs_graphics_setup.h"             // header cs4250/5250/6250 courses   // constants #define window_xs 25                       // window size #define window_ys 256 #define window_name "sliding box game"     // window name #define font_10 glut_bitmap_times_roman_10 // font size 10 #define font_24 glut_bitmap_times_roman_24 // font size 24 #define ani_msec 10                        // gap between frames   // structures typedef struct pt {     glfloat x, y; } mypoint;   // global variables mypoint bottomleftpt;  int xside = 80; int yside = 80; int innerx = 70; int innery = 70; int i, j, temp, v;  int arraynumrand[9] = {1, 2, 3, 4, 0, 5, 6, 7, 8};  //multidimensional array holds x-coordinate of big square, //y-coordinate of big square, , number displayed. int arraycoord[9][2] = {     {8, 168},     {88, 168},     {168, 168},     {8, 88},     {88, 88},     {168, 88},     {8, 8},     {88, 8},     {168, 8} };  //int goup = 0;  // 0- go up, 1- come down  // function prototypes void display_func(void); void keyboard_func(unsigned char c, int x, int y); //void animation_func(int val); void drawsquarefn(int, int, int, int, int); void display_num(int, int, int);   int main(int argc, char **argv) {     glutinit(&argc, argv);     init_setup(window_xs, window_ys, window_name);     //initial testing of arraynumrand randomization     srand(time(null));     for(i = 0; <9; i++)     {         j = (rand() %8)+1;         if(j != 4 && != 4)         {             temp = arraynumrand[i];             arraynumrand[i] = arraynumrand[j];             arraynumrand[j] = temp;         }     }     for(i = 0; <9; i++)     {         printf(" %d", arraynumrand[i]);     }     glutdisplayfunc(display_func);     glutkeyboardfunc(keyboard_func);     //gluttimerfunc(ani_msec, animation_func, 0);     glutmainloop();     return 1; }   // end of main()   void display_func(void) {     glclearcolor(0.50, 78.0, 139.0, 0.0); // background color (purple)     glclear(gl_color_buffer_bit);         // clearing buffer not keep color     for(v = 0; v <9; v ++)     {         drawsquarefn(arraycoord[v][0], arraycoord[v][1], xside, yside, v);     }     glflush();     glutswapbuffers();                    // double buffering }   // end of display_func()    void keyboard_func(unsigned char c, int x, int y) {     switch(c)     {         /*case 'b' :         case 'b' :             //breadth_first_search function              glutpostredisplay();             break;          case 'd' :         case 'd' :             //depth_first_search function              glutpostredisplay();             break;*/     case 'i' :     case 'i' :         for(i = 0; <9; i++)         {             j = (rand() %8)+1;             if(j != 4 && != 4)             {                 temp = arraynumrand[i];                 arraynumrand[i] = arraynumrand[j];                 arraynumrand[j] = temp;             }             display_func();         }         for(i = 0; <9; i++)         {             printf(" %d", arraynumrand[i]);         }         break;     case 'q' :     case 'q' :         printf("good bye !\n");         exit(0);                 // terminates program     }  // end of switch }   // end of keyboard_func()   /*void animation_func(int val) { int movegap = 5;  if( goup == 0 ) {     bottomleftpt.x += movegap;     bottomleftpt.y += movegap;      if( bottomleftpt.x+reclength > window_xs)     {         bottomleftpt.x -= movegap;         bottomleftpt.y -= movegap;          goup = 1;     }     else if( bottomleftpt.y+recheight > window_ys)     {         bottomleftpt.x -= movegap;         bottomleftpt.y -= movegap;          goup = 1;     } } else // goup = 1 {     bottomleftpt.x -= movegap;     bottomleftpt.y -= movegap;      if( bottomleftpt.x < 50)     {         bottomleftpt.x += movegap;         bottomleftpt.y += movegap;          goup = 0;     }     else if( bottomleftpt.y < 50)     {         bottomleftpt.x += movegap;         bottomleftpt.y += movegap;          goup = 0;     } }  glutpostredisplay(); gluttimerfunc(ani_msec, animation_func, 0); }//end animation_func*/  //beginning of drawsquare function create 2 nested squares , place     number on board. void drawsquarefn(int x, int y, int xside, int yside, int num) {     // draw rectangle     glcolor3f(0.0, 0.0, 0.0);           // setting pen color (black)     glbegin(gl_polygon);     glvertex2i(x, y);     glvertex2i(x+xside, y);     glvertex2i(x+xside, y+yside);     glvertex2i(x, y+yside);     glend();     // draw outline of rectangle     glcolor3f(0.0, 0.0, 0.0);           // setting pen color (black)     glbegin(gl_lines);     glvertex2i(x, y);     glvertex2i(x+xside, y);     glvertex2i(x+xside, y);     glvertex2i(x+xside, y+yside);     glvertex2i(x+xside, y+yside);     glvertex2i(x, y+yside);     glvertex2i(x, y+yside);     glvertex2i(x,y);     glend();     x += 5;     y += 5;     if(arraynumrand[num] != 0)     {         // draw inner rectangle         glcolor3f(1.0, 1.0, 1.0);           // setting pen color (black)         glbegin(gl_polygon);         glvertex2i(x, y);         glvertex2i(x+innerx, y);         glvertex2i(x+innerx, y+innery);         glvertex2i(x, y+innery);         glend();         //// draw outline of rectangle         //glcolor3f(1.0, 1.0, 1.0);         // setting pen color (black)         //glbegin(gl_lines);         //  glvertex2i(x, y);         //  glvertex2i(x+innerx, y);         //  glvertex2i(x+innerx, y);         //  glvertex2i(x+innerx, y+innery);         //  glvertex2i(x+innerx, y+innery);         //  glvertex2i(x, y+innery);         //  glvertex2i(x, y+innery);         //  glvertex2i(x,y);         //  glend();         x += 23;         y += 23;         //new x value, new y-value, , number listed above , decide upon color display_num         display_num(x, y, num);     } }  void display_num(int newx, int newy, int newnum) {     int points[10];     int = 0, j;     int pos;     int is_negative = 0;     for(j = 0; j < 10; j++)     {         points[j] = ' ';     }     if(newnum < 0)     {         is_negative = 1;         newnum *= -1;     }     while(newnum > 9)     {         points[i] = newnum % 10;         newnum = newnum / 10;         += 1;     }     points[i] = 1;     glcolor3f(0.0, 0.0, 0.0);     pos = newx;     if(is_negative == 1)     {         glrasterpos2i(pos, newy);         glutbitmapcharacter(font_24, '-');         pos += glutbitmapwidth(font_24, '-');     }     glrasterpos2i(pos, newy);     glutbitmapcharacter(font_24, (char)(arraynumrand[newnum]+48));     pos += glutbitmapwidth(font_24, (char)(arraynumrand[newnum]+48)); }  void breadthfirstsearch()  void depthfirstsearch() { } 

the tree want traverse tree of board states. implicit tree: not construct tree data structure , fill boards. each node in tree 1 position of of tiles on board. root node board 8 randomly arranged tiles around perimeter , 1 blank in center. there's no need have tree data structure traverse because can compute children of each state knowing state. root have 4 children (each of side tiles sliding hole). each of has 3 children (due edge of board). moves create cycles (e.g. undoing first move in second move) want avoid.

if imagine tree (without cycles) nodes of tree of other board states. of states solution puzzle. 1 of solution nodes set of moves path root through tree goal node.

for puzzle of size can search directly goal. more complex problems (e.g. 256x256 sliding tile puzzle, or more complex games chess) not able "see" endgame. in cases have have scoring function evaluate whether getting better or worse. navigate through tree promising areas close enough see goal state , find answer.