So I have an assignment where a user creates a maze and the computer solves it. The user first enters the size of the maze, then the maze itself ie,
rows:5
columns: 5
OXOOO
OXOXO
OOOXO
OOXXO
XXXXO
Whereas any space with an O can be navigated through, and X cannot. We have to get from the start, top left, to the finish, bottom right. First we have to output whether or not it's solvable, and then if it is solvable, how to solve it. (Start from finish and then have a list of instructions D- down, U- Up, L- Left, R- Right, you may not move diagonally.) So the solution to this puzzle would be DDRRUURRDDDD
Entering the matrix is of course easy, but as far as solving, there are a couple problems, but here's my logic:
1. create a boolean matrix of same dimensions as the maze. (true will mean that space could be part of the solution, false means no.)
2. set 0x0 and nxn = true
3. using for loops, scan through row by row, starting from the finish point. any position that has 2 o's next to it, as well as a true next to it gets a true. (this is the condition for a useful spot.)
4. In devious paths like my example step 3 won't catch every space the first time around so keep doing this until the boolean matrix before the sweep looks the same as the one after.... ie, the sweep isn't finding any more spaces.
5. After finding all potential spots, sweep through row by row again. any true spot that doesn't have 2 trues next to it (other than start and finish) are not part of the solution.
6. starting from top left find adjacent true spots and according to where they are relative to that step ad the corresponding letter to the solution array.
7. print the solution array.
Really, the only problem I have is when there are a 2x2 square of o's, as there are in my example, there is ambiguity, and if the checks for where the next true is when finding the solution are in a certain order, you'll get stuck in there.
Thanks.
rows:5
columns: 5
OXOOO
OXOXO
OOOXO
OOXXO
XXXXO
Whereas any space with an O can be navigated through, and X cannot. We have to get from the start, top left, to the finish, bottom right. First we have to output whether or not it's solvable, and then if it is solvable, how to solve it. (Start from finish and then have a list of instructions D- down, U- Up, L- Left, R- Right, you may not move diagonally.) So the solution to this puzzle would be DDRRUURRDDDD
Entering the matrix is of course easy, but as far as solving, there are a couple problems, but here's my logic:
1. create a boolean matrix of same dimensions as the maze. (true will mean that space could be part of the solution, false means no.)
2. set 0x0 and nxn = true
3. using for loops, scan through row by row, starting from the finish point. any position that has 2 o's next to it, as well as a true next to it gets a true. (this is the condition for a useful spot.)
4. In devious paths like my example step 3 won't catch every space the first time around so keep doing this until the boolean matrix before the sweep looks the same as the one after.... ie, the sweep isn't finding any more spaces.
5. After finding all potential spots, sweep through row by row again. any true spot that doesn't have 2 trues next to it (other than start and finish) are not part of the solution.
6. starting from top left find adjacent true spots and according to where they are relative to that step ad the corresponding letter to the solution array.
7. print the solution array.
Really, the only problem I have is when there are a 2x2 square of o's, as there are in my example, there is ambiguity, and if the checks for where the next true is when finding the solution are in a certain order, you'll get stuck in there.
Thanks.