summaryrefslogtreecommitdiffstats
path: root/klotski.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'klotski.cpp')
-rw-r--r--klotski.cpp595
1 files changed, 595 insertions, 0 deletions
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<Piece>::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<Piece>::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<Piece>::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<Grid> &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<Piece>::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;
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-14 21:04:30 +0000