Algorithm to solve log puzzle
Hey, dunno if anyone still visits this part of the forum, but thought you might like this nifty thing. A friend of mine was playing Puzzle Agent yesterday and decided to program something that would solve one of the latter log puzzles. As he said in the email:
So he did it! Here's the code. You can run it your favourite C++ compiler and see this cool little program in action
(Code posted with his permission.)
I had to try a few different techniques until I found one efficient enough (there are 3^18 = 387,420,489 possibilities to try!). If you're interested, below is the (somewhat ugly) code that ended up finding the right solution instantly.
So he did it! Here's the code. You can run it your favourite C++ compiler and see this cool little program in action
(Code posted with his permission.)
#include <iostream>
#include <set>
#include <algorithm>
using std::cout;
using std::endl;
using std::set;
using std::pair;
using std::make_pair;
/* Data types. */
typedef int Direction;
const Direction UP = 0;
const Direction DOWN = 1;
const Direction RIGHT = 2;
const Direction LEFT = 3;
typedef pair<int, int> Point;
struct State {
// Current position.
int x, y;
// The number of forward and backward slashes remaining.
int fwds, bwds;
// Current movement direction.
Direction dir;
// The coordinates of the stars collected so far.
set<Point> collected;
// The coordinate/direction pairs that we've passed so far. If we ever pass
// one such pair more than once, we're in an infinite loop.
set<pair<Point, Direction> > seen;
};
/* Global board, edited while trying solutions. */
char board[][6] = {
{' ', '/', '*', ' ', ' ', 'S'},
{'/', ' ', '*', '*', ' ', ' '},
{'*', '*', ' ', '*', '*', ' '},
{' ', '*', '*', '*', '*', ' '},
{' ', ' ', '*', '*', ' ', ' '},
{'D', ' ', ' ', ' ', ' ', '/'}
};
/* Prints out the board. */
void print() {
cout << endl;
for (int i=0; i<6; i++) {
for (int j=0; j<6; j++) {
cout << board[i][j];
}
cout << endl;
}
cout << endl;
}
/* Moves the coordinate x,y in direction d. */
void move(Direction d, int& x, int& y) {
if (d == UP) y--;
else if (d == DOWN) y++;
else if (d == RIGHT) x++;
else if (d == LEFT) x--;
}
/* Calculates the direction after bouncing from a given barried. */
Direction bounce(Direction d, char barrier) {
if (barrier == '/') {
if (d == UP) d = RIGHT;
else if (d == DOWN) d = LEFT;
else if (d == RIGHT) d = UP;
else if (d == LEFT) d = DOWN;
} else if (barrier == '\\') {
if (d == UP) d = LEFT;
else if (d == DOWN) d = RIGHT;
else if (d == RIGHT) d = DOWN;
else if (d == LEFT) d = UP;
} else {
// Invalid barrier. Crash and burn!
exit(1);
}
return d;
}
/* Checks whether the current board is solved. */
bool test() {
int stars_to_find = 0;
for (int i=0; i<6; i++) {
for (int j=0; j<6; j++) {
if (board[i][j] == '*') stars_to_find++;
}
}
State s;
s.x = 5;
s.y = 0;
s.dir = DOWN;
while (s.x >= 0 && s.x <= 5 && s.y >= 0 && s.y <= 5) {
pair<Point, Direction> cur = make_pair(make_pair(s.x, s.y), s.dir);
if (s.seen.count(cur)) break;
s.seen.insert(cur);
move(s.dir, s.x, s.y);
switch (board[s.y][s.x]) {
case 'D':
return s.collected.size() == stars_to_find;
case '*':
s.collected.insert(make_pair(s.x, s.y));
break;
case '/':
case '\\':
s.dir = bounce(s.dir, board[s.y][s.x]);
}
}
return false;
}
/* Traverses the board, splitting recursively on empty squares. */
void place(State s) {
while (s.x >= 0 && s.x <= 5 && s.y >= 0 && s.y <= 5) {
switch (board[s.y][s.x]) {
case 'S':
// Nothing to see here, move along.
break;
case 'D':
// Do a clean check. We have to do this because place() does not
// account for the effect of newly placed barriers on paths already
// traversed and may give false positives.
if (test()) {
cout << "Solution found:" << endl;
print();
exit(0);
}
return;
case '*':
s.collected.insert(make_pair(s.x, s.y));
break;
case '/':
case '\\':
s.dir = bounce(s.dir, board[s.y][s.x]);
break;
case ' ':
// Try filling the space with barriers if we have some available,
// recursively traversing the resulting board(s).
pair<Point, Direction> cur = make_pair(make_pair(s.x, s.y), s.dir);
if (s.fwds) {
State new_s = s;
new_s.seen.insert(cur);
new_s.fwds--;
board[s.y][s.x] = '/';
place(new_s);
}
if (s.bwds) {
State new_s = s;
new_s.seen.insert(cur);
new_s.bwds--;
board[s.y][s.x] = '\\';
place(new_s);
}
board[s.y][s.x] = ' ';
break;
}
move(s.dir, s.x, s.y);
if (s.seen.count(make_pair(make_pair(s.x, s.y), s.dir))) break;
}
}
int main() {
cout << "Starting map:" << endl;
print();
State s;
s.x = 5;
s.y = 0;
s.dir = DOWN;
s.fwds = 6;
s.bwds = 6;
place(s);
// place() exits if it finds a solution. If we've reached this, it failed.
cout << "No solution found." << endl;
}
Sign in to comment in this discussion.
Comments
Just an idea:
Initialisation: Path calculation: Solution not found, therefore, the first movable log encountered by the car must be somewhere in the sharps (#).
Loop the "sharp positions" try to replace them by either \ or /, recursion.
Example, I try to put a \ log in the (1,5) position. I assumed that it is the first log that the car will encounter. Therefore, there can't be an other log where a "S" stands. We move the car into the (1,5) position. The direction is now "up". The puzzle is not solved yet, therefore, the second log must be where a "#" stands. Loop the sharps, recursion.
I think I'll try something ^^ ...
54393 moves.
14112 configurations tried.
62 solutions found:
7 logs => 1
8 logs => 4
9 logs => 9
10 logs => 17
11 logs => 15
12 logs => 16
Processing time: 0.85s
Challenge: will you find the only solution where only 7 logs are used? (Answer in the spoiler below)
It can be helpful to make/improve your own (bigger) puzzles too. For example, Puzzle Agent could give you only 7 logs for this puzzle, it would increase the difficulty.