From d9012a8bbda95de5e3b7b12a135d6c42f55d86ec Mon Sep 17 00:00:00 2001 From: Kamil Kaminski Date: Mon, 14 Mar 2011 02:30:40 -0500 Subject: do some more work --- Makefile | 7 +- README | 16 ++ grid.cpp | 36 ++++ grid.h | 7 +- klotski.cpp | 595 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ klotski.h | 50 +++++ main.cpp | 590 ++--------------------------------------------------------- main.h | 21 +-- 8 files changed, 723 insertions(+), 599 deletions(-) create mode 100644 README create mode 100644 klotski.cpp create mode 100644 klotski.h diff --git a/Makefile b/Makefile index b9cbc01..91e13ea 100644 --- a/Makefile +++ b/Makefile @@ -7,7 +7,7 @@ # Makefile PROG = klotski -OBJS = main.o piece.o grid.o +OBJS = main.o klotski.o piece.o grid.o CC = g++ DBGFLAGS = -g -O0 ifdef DEBUG @@ -20,7 +20,10 @@ LDFLAGS = -lm $(PROG): $(OBJS) $(CC) $(LDFLAGS) $(OBJS) -o $(PROG) -main.o: %.o: %.cpp %.h piece.h grid.h +main.o: %.o: %.cpp %.h klotski.h piece.h grid.h + $(CC) -c $(CFLAGS) $< + +klotski.o: %.o: %.cpp %.h klotski.h piece.h grid.h $(CC) -c $(CFLAGS) $< piece.o: %.o: %.cpp %.h diff --git a/README b/README new file mode 100644 index 0000000..52e955b --- /dev/null +++ b/README @@ -0,0 +1,16 @@ +# Kamil Kaminski +# NetID: kkamin8 +# +# CS340 +# Project 3, Sliding Block Puzzles +# + +Project can be compiled by issuing: +$ make + +The main binary is called "klotski" and can by ran by issuing: +$ ./klotski + +I used Breadth First Search to find the first optimal solution, when found, the +main loop breaks out and halts the program. + diff --git a/grid.cpp b/grid.cpp index df835c1..50d59b3 100644 --- a/grid.cpp +++ b/grid.cpp @@ -57,3 +57,39 @@ void Grid::markPiecesPos(void) { } +void Grid::setlastMoved(int dir) +{ + lastMoved = dir; +} + +int Grid::getlastMoved(void) +{ + return lastMoved; +} + +void Grid::printMoves(void) +{ + vector::iterator iter; + for (iter = moves.begin(); iter != moves.end(); ++iter) + cout << *iter; +} + + + + + + + + + + + + + + + + + + + + diff --git a/grid.h b/grid.h index d2a066b..db87a39 100644 --- a/grid.h +++ b/grid.h @@ -1,11 +1,11 @@ #ifndef _GRID_H_ #define _GRID_H_ -#include "piece.h" #include #include #include #include +#include "piece.h" using std::string; using std::cout; @@ -18,7 +18,7 @@ class Grid int rows; int cols; int numOfMoves; - int lastMoved; + int lastMoved; /* 0 = left, 1 = right, 2 = up, 3 = down */ int lastMoveDir; vector pieces; vector moves; @@ -39,6 +39,9 @@ class Grid void addMove(string); void markPiecesPos(void); + void setlastMoved(int); + int getlastMoved(void); + void printMoves(void); }; #endif diff --git a/klotski.cpp b/klotski.cpp new file mode 100644 index 0000000..a04eee2 --- /dev/null +++ b/klotski.cpp @@ -0,0 +1,595 @@ +/* + * klotski.cpp + * + * + */ + +#include "klotski.h" + +string err_msg[4] = {"piece is correct", "piece has wrong dimensions", "piece has wrong direction", "piece is out of bounds"}; + +string piece_tag[] = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", + "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", + "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "A", + "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", + "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", + "Z"}; + +/* check if Z piece spans last column */ +bool checkSoln(Grid grid) +{ + Piece tmp(""); + for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix) + { + tmp = (*(grid.getPieces()))[ix]; + if (tmp.getName() == "Z") + break; + } + + if ( (tmp.getCol() + tmp.getW()) == (*(grid.getCols())+1) ) + return true; + + return false; +} + +/* validate piece */ +int checkPiece(int rows, int cols, Piece piece) +{ + /* wrong direction */ + if ( piece.getDir() != 'v' && piece.getDir() != 'h' && piece.getDir() != 'b') + { + return 2; + } + + /* out of bonds */ + if ( (piece.getRow() + piece.getH()) > rows+1 || (piece.getCol() + piece.getW()) > cols+1) + return 3; + + /* wrong dimensions */ + if ( (piece.getH() != 1) && (piece.getW() != 1) ) + return 1; + + return 0; +} + +/* take in a grid and return a string representation of it */ +string *fillBoard(Grid grid) +{ + int grid_h = *grid.getRows(); + int grid_w = *grid.getCols(); + string *board = new string[grid_h * grid_w + 1]; + int k; + for (k = 0; k < grid_h * grid_w; k++) + board[k] = "."; + + int i = 0; + Piece tmp(""); + string name; + int row; + int col; + int w; + int h; + char dir; + int offset; + + for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix, i++) + { + tmp = (*(grid.getPieces()))[ix]; + name = tmp.getName(); + row = tmp.getRow(); + col = tmp.getCol(); + w = tmp.getW(); + h = tmp.getH(); + dir = tmp.getDir(); + + int j; + offset = (grid_w * (row-1)) + col; + if (w == 1) + { + for (j = 0; j < h; j++) + board[offset + (j * grid_w) - 1] = name; + } + else if (h == 1) + { + for (j = 0; j < w; j++) + board[offset - 1 + j] = name; + } + else + cout << "oops in fillBoard(), height or width of a piece is not 1!\n"; + } + + board[grid_h * grid_w] = ""; + + return board; +} + +/* take 1D grid, create 1D representation of it, and print it */ +void printGrid(Grid grid) +{ + int grid_h = *grid.getRows(); + int grid_w = *grid.getCols(); + string padding = string(grid_w + 1, '*'); + string *board = new string[grid_h * grid_w]; + int k; + for (k = 0; k < grid_h * grid_w; k++) + board[k] = "."; + + int i = 0; + Piece tmp(""); + string name; + int row; + int col; + int w; + int h; + char dir; + int offset; + + for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix, i++) + { + tmp = (*(grid.getPieces()))[ix]; + name = tmp.getName(); + row = tmp.getRow(); + col = tmp.getCol(); + w = tmp.getW(); + h = tmp.getH(); + dir = tmp.getDir(); + + int j; + offset = (grid_w * (row-1)) + col; + if (w == 1) + { + for (j = 0; j < h; j++) + board[offset + (j * grid_w) - 1] = name; + } + else if (h == 1) + { + for (j = 0; j < w; j++) + board[offset - 1 + j] = name; + } + else + cout << "oops in printGrid(), height or width of a piece is not 1!\n"; + } + + cout << padding << "*\n*"; + for (int k = 1; k <= grid_h * grid_w; k++) + { + cout << board[k-1]; + if (k % grid_w == 0) + cout << "*\n*"; + } + cout << padding << endl << endl; + + delete [] board; +} + +/* load grid from a file */ +Grid loadGrid(char **argv) +{ + FILE *fname = fopen(argv[1], "r"); + if (fname == NULL) + { + perror("fopen"); + exit(EXIT_FAILURE); + } + + Grid grid; + Piece piece_tmp(""); + + /* used for line reading */ + size_t line_sz = 0; + char *line = NULL; + int matched_inputs = 0; + + if (getline(&line, &line_sz, fname) != -1) + sscanf(line, "%d %d\n", grid.getRows(), grid.getCols()); + + if (*grid.getRows() < 1 || *grid.getCols() < 1) + { + cout << "invalid grid dimensions, read in: " << *grid.getRows() << "h, " + << *grid.getCols() << "w" << endl; + exit(EXIT_FAILURE); + } + + /* parse grid's dimensions */ + int piece_row = -1; + int piece_col = -1; + int piece_w = -1; + int piece_h = -1; + char piece_dir = 0; + int line_cnt = 0; + string piece_name; + bool foundGoalPiece = false; + int ret; + int i; + + for (i = 0; getline(&line, &line_sz, fname) != -1; i++) + { + matched_inputs = sscanf(line, "%d %d %d %d %c\n", &piece_row, + &piece_col, &piece_w, &piece_h, &piece_dir); + + if (matched_inputs != 5) + { + cout << "failed to parse line " << i+2 << ", skipping: " << line; + continue; + } + else if (!foundGoalPiece) + { + piece_name = string("Z"); + piece_tmp = Piece(piece_name, piece_row, piece_col, piece_w, piece_h, piece_dir); + ret = checkPiece(*grid.getRows(), *grid.getCols(), piece_tmp); + if (ret != 0) + { + cout << "failed to parse line " << i+2 << ", " << err_msg[ret] << endl; + continue; + } + + grid.getPieces()->push_back(piece_tmp); + foundGoalPiece = true; + } + else + { + piece_name = string(piece_tag[line_cnt-1]); + piece_tmp = Piece(piece_name, piece_row, piece_col, piece_w, piece_h, piece_dir); + ret = checkPiece(*grid.getRows(), *grid.getCols(), piece_tmp); + if (ret != 0) + { + cout << "failed to parse line " << i+2 << ", " << err_msg[ret] << endl; + continue; + } + + grid.getPieces()->push_back(piece_tmp); + } + + line_cnt++; + } + + cout << "info: read in " << line_cnt << " pieces" << endl << endl; + fclose(fname); + + return grid; +} + +/* can piece move to left? If so, have many spaces */ +int canMoveLeft(string board[], int row_sz, int col_sz, Piece piece) +{ + int ret = 0; + int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; + + if (piece.getH() == 1) + { + if (!offset || (offset % col_sz == 0)) + return 0; + + while (board[offset-1] == ".") + { + offset--; + ret++; + + if (offset % col_sz == 0) + break; + } + + return ret; + } + else if (piece.getW() == 1) + { + int offset2 = offset + col_sz; /* fix me later */ + + if (!offset || (offset % col_sz == 0)) + return 0; + +#if 0 /* XXX: unimplemented */ + int i; + while(1) + for (i = 0; i < piece.getH()) + { + + } +#endif + + while (board[offset-1] == "." && board[offset2-1] == ".") + { + offset--; + offset2--; + ret++; + + if (offset % col_sz == 0) + break; + } + + return ret; + } + else + cout << "oops in canMoveLeft(), height or width of a piece is not 1!\n"; + + return 0; +} + +/* can piece move to right? If so, have many spaces */ +int canMoveRight(string board[], int row_sz, int col_sz, Piece piece) +{ + int ret = 0; + int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; + + if (piece.getH() == 1) + { + offset += piece.getW(); + offset--; + + if (!offset || ((offset+1) % col_sz == 0)) + return 0; + + while (board[offset+1] == ".") + { + offset++; + ret++; + + if (offset % col_sz == 0) + break; + } + + return ret; + } + else if (piece.getW() == 1) + { + offset += piece.getW(); + offset--; + + int offset2 = offset + col_sz; /* fix me later */ + + if (!offset || ((offset+1) % col_sz == 0)) + return 0; + + while (board[offset+1] == "." && board[offset2+1] == ".") + { + offset++; + offset2++; + ret++; + + if (offset % col_sz == 0) + break; + } + + return ret; + } + else + cout << "oops in canMoveRight(), height or width of a piece is not 1!\n"; + + return 0; +} + +/* can piece move up? If so, have many spaces */ +int canMoveUp(string board[], int row_sz, int col_sz, Piece piece) +{ + int ret = 0; + int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; + + if (piece.getW() == 1) + { + if (!offset || offset < col_sz) + return 0; + + while (board[offset-col_sz] == ".") + { + offset -= col_sz; + ret++; + + if (offset-col_sz < 0) + break; + } + + return ret; + } + else if (piece.getH() == 1) + { + int offset2 = offset + piece.getW() - 1; /* fix me later */ + + if (!offset || offset < col_sz) + return 0; + + while (board[offset-col_sz] == "." && board[offset2-col_sz] == ".") + { + offset -= col_sz; + offset2 -= col_sz; + ret++; + + if (offset-col_sz < 0) + break; + } + + return ret; + } + else + cout << "oops in canMoveUp(), height or width of a piece is not 1!\n"; + + return 0; +} + +/* can piece move down? If so, have many spaces */ +int canMoveDown(string board[], int row_sz, int col_sz, Piece piece) +{ + int ret = 0; + int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; + + if (piece.getW() == 1) + { + if (piece.getH() != 1) + offset = col_sz * piece.getH(); + + if (offset + col_sz > row_sz * col_sz) + return 0; + + while (board[offset+col_sz] == ".") + { + offset += col_sz; + ret++; + + if (offset+col_sz > row_sz * col_sz) + break; + } + + return ret; + } + else if (piece.getH() == 1) + { + int offset2 = offset + piece.getW() - 1; /* fix me later */ + + if (offset + col_sz > row_sz * col_sz) + return 0; + + while (board[offset+col_sz] == "." && board[offset2+col_sz] == ".") + { + offset += col_sz; + offset2 += col_sz; + ret++; + + if (offset+col_sz > row_sz * col_sz) + break; + } + + return ret; + } + else + cout << "oops in canMoveDown(), height or width of a piece is not 1!\n"; + + return 0; +} + +/* fill in a queue with grids to be checked */ +int possibleMoves(Grid grid, queue &kway) +{ + Piece tmp(""); + Piece tmp2(""); + string *filled = fillBoard(grid); + char dir; + int ret = 0; + char move[100]; + int howMany = 0; + + int i; + /* for all pieces in Grid grid */ + for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix) + { + tmp = (*(grid.getPieces()))[ix]; + dir = tmp.getDir(); + + /* check where piece can go and create a new grid */ + if (dir == 'h' || dir == 'b') + { + /* right */ + if (grid.getlastMoved() != 1) + { + ret = canMoveRight(filled, *grid.getRows(), *grid.getCols(), tmp); + howMany += ret; + + for (i = 0; i < ret; i++) + { + Grid new_grid = grid; + new_grid.setlastMoved(1); + + tmp2 = (*(new_grid.getPieces()))[ix]; + tmp2.setCol(tmp2.getCol() + (i+1)); + (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ + + /* update movement */ + sprintf(move, "Piece %s right %d space(s)\n", tmp2.getName().c_str(), i+1); + new_grid.addMove(string(move)); + +#ifdef DEBUG + cout << "pushing new grid, \"" << tmp2.getName() << "\"" + << " can move " << i+1 << " space(s)" << " to the right" << endl; +#endif + kway.push(new_grid); + } + } + + /* left */ + if (grid.getlastMoved() != 0) + { + ret = canMoveLeft(filled, *grid.getRows(), *grid.getCols(), tmp); + howMany += ret; + + for (i = 0; i < ret; i++) + { + Grid new_grid = grid; + new_grid.setlastMoved(0); + + tmp2 = (*(new_grid.getPieces()))[ix]; + tmp2.setCol(tmp2.getCol() - (i+1)); + (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ + + /* update movement */ + sprintf(move, "Piece %s left %d space(s)\n", tmp2.getName().c_str(), i+1); + new_grid.addMove(string(move)); + +#ifdef DEBUG + cout << "pushing new grid, \"" << tmp2.getName() << "\"" + << " can move " << i+1 << " space(s)" << " to the left" << endl; +#endif + kway.push(new_grid); + } + } + } + + if (dir == 'v' || dir == 'b') + { + /* down */ + if (grid.getlastMoved() != 3) + { + ret = canMoveDown(filled, *grid.getRows(), *grid.getCols(), tmp); + howMany += ret; + + for (i = 0; i < ret; i++) + { + Grid new_grid = grid; + new_grid.setlastMoved(3); + + tmp2 = (*(new_grid.getPieces()))[ix]; + tmp2.setRow(tmp2.getRow() + (i+1)); + (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ + + /* update movement */ + sprintf(move, "Piece %s down %d space(s)\n", tmp2.getName().c_str(), i+1); + new_grid.addMove(string(move)); + +#ifdef DEBUG + cout << "pushing new grid, \"" << tmp2.getName() << "\"" + << " can move " << i+1 << " space(s)" << " down" << endl; +#endif + kway.push(new_grid); + } + } + + /* up */ + if (grid.getlastMoved() != 2) + { + ret = canMoveUp(filled, *grid.getRows(), *grid.getCols(), tmp); + howMany += ret; + + for (i = 0; i < ret; i++) + { + Grid new_grid = grid; + new_grid.setlastMoved(2); + + tmp2 = (*(new_grid.getPieces()))[ix]; + tmp2.setRow(tmp2.getRow() - (i+1)); + (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ + + /* update movement */ + sprintf(move, "Piece %s up %d space(s)\n", tmp2.getName().c_str(), i+1); + new_grid.addMove(string(move)); + +#ifdef DEBUG + cout << "pushing new grid, \"" << tmp2.getName() << "\"" + << " can move " << i+1 << " space(s)" << " up" << endl; +#endif + kway.push(new_grid); + } + } + } + + } + + return howMany; +} + diff --git a/klotski.h b/klotski.h new file mode 100644 index 0000000..60b9108 --- /dev/null +++ b/klotski.h @@ -0,0 +1,50 @@ +#ifndef _KLOTSKI_H +#define _KLOTSKI_H_ + +#include +#include +#include +#include +#include + +#include "grid.h" +#include "piece.h" + +using std::vector; +using std::queue; + +extern string err_msg[4]; +extern string piece_tag[]; + +/* check if Z piece spans last column */ +bool checkSoln(Grid); + +/* validate piece */ +int checkPiece(int, int, Piece); + +/* take in a grid and return a string representation of it */ +string *fillBoard(Grid); + +/* take 1D grid, create 1D representation of it, and print it */ +void printGrid(Grid); + +/* load grid from a file */ +Grid loadGrid(char **); + +/* can piece move to left? If so, have many spaces */ +int canMoveLeft(string [], int, int, Piece); + +/* can piece move to right? If so, have many spaces */ +int canMoveRight(string [], int, int, Piece); + +/* can piece move up? If so, have many spaces */ +int canMoveUp(string [], int, int, Piece); + +/* can piece move down? If so, have many spaces */ +int canMoveDown(string [], int, int, Piece); + +/* fill in a queue with grids to be checked */ +int possibleMoves(Grid, queue &); + +#endif + diff --git a/main.cpp b/main.cpp index 3b80c54..8ccbf73 100644 --- a/main.cpp +++ b/main.cpp @@ -9,556 +9,6 @@ #include "main.h" -/* check if Z piece spans last column */ -bool checkSoln(Grid grid) -{ - Piece tmp(""); - for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix) - { - tmp = (*(grid.getPieces()))[ix]; - if (tmp.getName() == "Z") - break; - } - - if ( (tmp.getCol() + tmp.getW()) == (*(grid.getCols())+1) ) - return true; - - return false; -} - -/* validate piece */ -int checkPiece(int rows, int cols, Piece piece) -{ - /* wrong direction */ - if ( piece.getDir() != 'v' && piece.getDir() != 'h' && piece.getDir() != 'b') - { - return 2; - } - - /* out of bonds */ - if ( (piece.getRow() + piece.getH()) > rows+1 || (piece.getCol() + piece.getW()) > cols+1) - return 3; - - /* wrong dimensions */ - if ( (piece.getH() != 1) && (piece.getW() != 1) ) - return 1; - - return 0; -} - -/* take in a grid and return a string representation of it */ -string *fillBoard(Grid grid) -{ - int grid_h = *grid.getRows(); - int grid_w = *grid.getCols(); - string *board = new string[grid_h * grid_w + 1]; - int k; - for (k = 0; k < grid_h * grid_w; k++) - board[k] = "."; - - int i = 0; - Piece tmp(""); - string name; - int row; - int col; - int w; - int h; - char dir; - int offset; - - for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix, i++) - { - tmp = (*(grid.getPieces()))[ix]; - name = tmp.getName(); - row = tmp.getRow(); - col = tmp.getCol(); - w = tmp.getW(); - h = tmp.getH(); - dir = tmp.getDir(); - - int j; - offset = (grid_w * (row-1)) + col; - if (w == 1) - { - for (j = 0; j < h; j++) - board[offset + (j * grid_w) - 1] = name; - } - else if (h == 1) - { - for (j = 0; j < w; j++) - board[offset - 1 + j] = name; - } - else - cout << "oops in fillBoard(), height or width of a piece is not 1!\n"; - } - - board[grid_h * grid_w] = ""; - - return board; -} - -/* take 1D grid, create 1D representation of it, and print it */ -void printGrid(Grid grid) -{ - int grid_h = *grid.getRows(); - int grid_w = *grid.getCols(); - string padding = string(grid_w + 1, '*'); - string *board = new string[grid_h * grid_w]; - int k; - for (k = 0; k < grid_h * grid_w; k++) - board[k] = "."; - - int i = 0; - Piece tmp(""); - string name; - int row; - int col; - int w; - int h; - char dir; - int offset; - - for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix, i++) - { - tmp = (*(grid.getPieces()))[ix]; - name = tmp.getName(); - row = tmp.getRow(); - col = tmp.getCol(); - w = tmp.getW(); - h = tmp.getH(); - dir = tmp.getDir(); - - int j; - offset = (grid_w * (row-1)) + col; - if (w == 1) - { - for (j = 0; j < h; j++) - board[offset + (j * grid_w) - 1] = name; - } - else if (h == 1) - { - for (j = 0; j < w; j++) - board[offset - 1 + j] = name; - } - else - cout << "oops in printGrid(), height or width of a piece is not 1!\n"; - } - - cout << padding << "*\n*"; - for (int k = 1; k <= grid_h * grid_w; k++) - { - cout << board[k-1]; - if (k % grid_w == 0) - cout << "*\n*"; - } - cout << padding << endl << endl; - - delete [] board; -} - -/* load grid from a file */ -Grid loadGrid(char **argv) -{ - FILE *fname = fopen(argv[1], "r"); - if (fname == NULL) - { - perror("fopen"); - exit(EXIT_FAILURE); - } - - Grid grid; - Piece piece_tmp(""); - - /* used for line reading */ - size_t line_sz = 0; - char *line = NULL; - int matched_inputs = 0; - - if (getline(&line, &line_sz, fname) != -1) - sscanf(line, "%d %d\n", grid.getRows(), grid.getCols()); - - if (*grid.getRows() < 1 || *grid.getCols() < 1) - { - cout << "invalid grid dimensions, read in: " << *grid.getRows() << "h, " - << *grid.getCols() << "w" << endl; - exit(EXIT_FAILURE); - } - - /* parse grid's dimensions */ - int piece_row = -1; - int piece_col = -1; - int piece_w = -1; - int piece_h = -1; - char piece_dir = 0; - int line_cnt = 0; - string piece_name; - bool foundGoalPiece = false; - int ret; - int i; - - for (i = 0; getline(&line, &line_sz, fname) != -1; i++) - { - matched_inputs = sscanf(line, "%d %d %d %d %c\n", &piece_row, - &piece_col, &piece_w, &piece_h, &piece_dir); - - if (matched_inputs != 5) - { - cout << "failed to parse line " << i+2 << ", skipping: " << line; - continue; - } - else if (!foundGoalPiece) - { - piece_name = string("Z"); - piece_tmp = Piece(piece_name, piece_row, piece_col, piece_w, piece_h, piece_dir); - ret = checkPiece(*grid.getRows(), *grid.getCols(), piece_tmp); - if (ret != 0) - { - cout << "failed to parse line " << i+2 << ", " << err_msg[ret] << endl; - continue; - } - - grid.getPieces()->push_back(piece_tmp); - foundGoalPiece = true; - } - else - { - piece_name = string(piece_tag[line_cnt-1]); - piece_tmp = Piece(piece_name, piece_row, piece_col, piece_w, piece_h, piece_dir); - ret = checkPiece(*grid.getRows(), *grid.getCols(), piece_tmp); - if (ret != 0) - { - cout << "failed to parse line " << i+2 << ", " << err_msg[ret] << endl; - continue; - } - - grid.getPieces()->push_back(piece_tmp); - } - - line_cnt++; - } - - cout << "read in " << line_cnt << " pieces" << endl; - fclose(fname); - - return grid; -} - -/* can piece move to left? If so, have many spaces */ -int canMoveLeft(string board[], int row_sz, int col_sz, Piece piece) -{ - int ret = 0; - int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; - - if (piece.getH() == 1) - { - if (!offset || (offset % col_sz == 0)) - return 0; - - while (board[offset-1] == ".") - { - offset--; - ret++; - - if (offset % col_sz == 0) - break; - } - - return ret; - } - else if (piece.getW() == 1) - { - int offset2 = offset + col_sz; /* fix me later */ - - if (!offset || (offset % col_sz == 0)) - return 0; - -#if 0 /* XXX: unimplemented */ - int i; - while(1) - for (i = 0; i < piece.getH()) - { - - } -#endif - - while (board[offset-1] == "." && board[offset2-1] == ".") - { - offset--; - offset2--; - ret++; - - if (offset % col_sz == 0) - break; - } - - return ret; - } - else - cout << "oops in canMoveLeft(), height or width of a piece is not 1!\n"; - - return 0; -} - -/* can piece move to right? If so, have many spaces */ -int canMoveRight(string board[], int row_sz, int col_sz, Piece piece) -{ - int ret = 0; - int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; - - if (piece.getH() == 1) - { - offset += piece.getW(); - offset--; - - if (!offset || ((offset+1) % col_sz == 0)) - return 0; - - while (board[offset+1] == ".") - { - offset++; - ret++; - - if (offset % col_sz == 0) - break; - } - - return ret; - } - else if (piece.getW() == 1) - { - offset += piece.getW(); - offset--; - - int offset2 = offset + col_sz; /* fix me later */ - - if (!offset || ((offset+1) % col_sz == 0)) - return 0; - - while (board[offset+1] == "." && board[offset2+1] == ".") - { - offset++; - offset2++; - ret++; - - if (offset % col_sz == 0) - break; - } - - return ret; - } - else - cout << "oops in canMoveRight(), height or width of a piece is not 1!\n"; - - return 0; -} - -/* can piece move up? If so, have many spaces */ -int canMoveUp(string board[], int row_sz, int col_sz, Piece piece) -{ - int ret = 0; - int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; - - if (piece.getW() == 1) - { - if (!offset || offset < col_sz) - return 0; - - while (board[offset-col_sz] == ".") - { - offset -= col_sz; - ret++; - - if (offset-col_sz < 0) - break; - } - - return ret; - } - else if (piece.getH() == 1) - { - int offset2 = offset + piece.getW() - 1; /* fix me later */ - - if (!offset || offset < col_sz) - return 0; - - while (board[offset-col_sz] == "." && board[offset2-col_sz] == ".") - { - offset -= col_sz; - offset2 -= col_sz; - ret++; - - if (offset-col_sz < 0) - break; - } - - return ret; - } - else - cout << "oops in canMoveUp(), height or width of a piece is not 1!\n"; - - return 0; -} - -/* can piece move down? If so, have many spaces */ -int canMoveDown(string board[], int row_sz, int col_sz, Piece piece) -{ - int ret = 0; - int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; - - if (piece.getW() == 1) - { - if (piece.getH() != 1) - offset = col_sz * piece.getH(); - - if (offset + col_sz > row_sz * col_sz) - return 0; - - while (board[offset+col_sz] == ".") - { - offset += col_sz; - ret++; - - if (offset+col_sz > row_sz * col_sz) - break; - } - - return ret; - } - else if (piece.getH() == 1) - { - int offset2 = offset + piece.getW() - 1; /* fix me later */ - - if (offset + col_sz > row_sz * col_sz) - return 0; - - while (board[offset+col_sz] == "." && board[offset2+col_sz] == ".") - { - offset += col_sz; - offset2 += col_sz; - ret++; - - if (offset+col_sz > row_sz * col_sz) - break; - } - - return ret; - } - else - cout << "oops in canMoveDown(), height or width of a piece is not 1!\n"; - - return 0; -} - -/* fill in a queue with grids to be checked */ -int possibleMoves(Grid grid, queue &kway) -{ - Piece tmp(""); - Piece tmp2(""); - string *filled = fillBoard(grid); - char dir; - int ret; - char move[100]; - int howMany = 0; - - int i; - /* for all pieces in Grid grid */ - for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix) - { - tmp = (*(grid.getPieces()))[ix]; - dir = tmp.getDir(); - - /* check where piece can go and create a new graph */ - if (dir == 'h' || dir == 'b') - { - /* left */ - ret = canMoveLeft(filled, *grid.getRows(), *grid.getCols(), tmp); - howMany += ret; - - for (i = 0; i < ret; i++) - { - Grid new_grid = grid; - tmp2 = (*(new_grid.getPieces()))[ix]; - tmp2.setCol(tmp2.getCol() - (i+1)); - (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ - - /* update movement */ - sprintf(move, "Piece %s left %d space(s)\n", tmp2.getName().c_str(), i+1); - new_grid.addMove(string(move)); - - cout << "pushing new grid, \"" << tmp2.getName() << "\"" - << " can move " << i+1 << " space(s)" << " to the left" << endl; - kway.push(new_grid); - } - - /* right */ - ret = canMoveRight(filled, *grid.getRows(), *grid.getCols(), tmp); - howMany += ret; - - for (i = 0; i < ret; i++) - { - Grid new_grid = grid; - tmp2 = (*(new_grid.getPieces()))[ix]; - tmp2.setCol(tmp2.getCol() + (i+1)); - (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ - - /* update movement */ - sprintf(move, "Piece %s right %d space(s)\n", tmp2.getName().c_str(), i+1); - new_grid.addMove(string(move)); - - cout << "pushing new grid, \"" << tmp2.getName() << "\"" - << " can move " << i+1 << " space(s)" << " to the right" << endl; - kway.push(new_grid); - } - } - - if (dir == 'v' || dir == 'b') - { - /* up */ - ret = canMoveUp(filled, *grid.getRows(), *grid.getCols(), tmp); - howMany += ret; - - for (i = 0; i < ret; i++) - { - Grid new_grid = grid; - tmp2 = (*(new_grid.getPieces()))[ix]; - tmp2.setRow(tmp2.getRow() - (i+1)); - (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ - - /* update movement */ - sprintf(move, "Piece %s up %d space(s)\n", tmp2.getName().c_str(), i+1); - new_grid.addMove(string(move)); - - cout << "pushing new grid, \"" << tmp2.getName() << "\"" - << " can move " << i+1 << " space(s)" << " up" << endl; - kway.push(new_grid); - } - - /* down */ - ret = canMoveDown(filled, *grid.getRows(), *grid.getCols(), tmp); - howMany += ret; - - for (i = 0; i < ret; i++) - { - Grid new_grid = grid; - tmp2 = (*(new_grid.getPieces()))[ix]; - tmp2.setRow(tmp2.getRow() + (i+1)); - (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ - - /* update movement */ - sprintf(move, "Piece %s down %d space(s)\n", tmp2.getName().c_str(), i+1); - new_grid.addMove(string(move)); - - cout << "pushing new grid, \"" << tmp2.getName() << "\"" - << " can move " << i+1 << " space(s)" << " down" << endl; - kway.push(new_grid); - } - } - - } - - return howMany; -} - int main(int argc, char *argv[]) { /* seed rand() */ @@ -570,6 +20,8 @@ int main(int argc, char *argv[]) return -1; } + cout << "\tSliding Block Puzzles" << endl << endl; + Grid grid = loadGrid(argv); printGrid(grid); queue toCheck; @@ -578,37 +30,25 @@ int main(int argc, char *argv[]) /* kickstart the queue */ possibleMoves(grid, toCheck); - while (1) + /* main algorithm */ + while (!toCheck.empty()) { - while (!toCheck.empty()) + Grid popped = toCheck.front(); + toCheck.pop(); + + if (checkSoln(popped)) { - Grid popped = toCheck.front(); - toCheck.pop(); - checked.push(popped); + cout << "Solution: " << endl; + printGrid(popped); - if (checkSoln(popped)) - { - cout << "Solution: " << endl; - printGrid(popped); - exit(0); - } - else - { - cout << "The below was not a solution: " << endl; - printGrid(popped); - } + cout << "Steps: " << endl; + popped.printMoves(); + break; } - possibleMoves(checked.front(), toCheck); - checked.pop(); + else + possibleMoves(popped, toCheck); } -#if 0 - if (memcmp(&grid, ©, sizeof(Grid)) == 0) - cout << "victory" << endl; - else - cout << "else" << endl; -#endif - cout << "\n\tBye!" << endl; return 0; } diff --git a/main.h b/main.h index eb53e21..e5130d3 100644 --- a/main.h +++ b/main.h @@ -1,14 +1,7 @@ #ifndef _MAIN_H_ #define _MAIN_H_ -#include -#include -#include -#include -#include - -#include "piece.h" -#include "grid.h" +#include "klotski.h" #define ANSI_COLOR_RED "\x1b[31m" #define ANSI_COLOR_GREEN "\x1b[32m" @@ -19,17 +12,5 @@ #define ANSI_COLOR_RESET "\x1b[0m" #define PRINT_COLOR(C, S) printf("%s%s%s", C, S, ANSI_COLOR_RESET) -using std::vector; -using std::queue; - -string piece_tag[] = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", - "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", - "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "A", - "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", - "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", - "Z"}; - -string err_msg[4] = {"piece is correct", "piece has wrong dimensions", "piece has wrong direction", "piece is out of bounds"}; - #endif -- cgit v1.2.3