summaryrefslogtreecommitdiffstats
path: root/main.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'main.cpp')
-rw-r--r--main.cpp590
1 files changed, 15 insertions, 575 deletions
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<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 << "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<Grid> &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<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 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<Grid> 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, &copy, sizeof(Grid)) == 0)
- cout << "victory" << endl;
- else
- cout << "else" << endl;
-#endif
-
cout << "\n\tBye!" << endl;
return 0;
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-14 20:58:03 +0000