#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
enum {
CELL_EMPTY,
CELL_ROCK
};
typedef struct {
int Width;
int Height;
int *Cells;
int RockCount;
} Board;
typedef struct {
int PosX;
int PosY;
int MoveDirectionX;
int MoveDirectionY;
} Operator;
#define verify_position(board, x, y) \
(!((x) >= 0 && (y) >= 0 && (x) < (board)->Width && (y) < (board)->Height))
#define peek_cell(board, x, y) \
(&(board)->Cells[(y) * (board)->Width + (x)])
/* 0:success, 1:fail */
int init_board(Board *board, int width, int height)
{
int i, j;
assert(width > 0);
assert(height > 0);
board->Width = width;
board->Height = height;
board->Cells = malloc(sizeof(int) * width * height);
if (board->Cells == NULL) {
return 1;
}
for (i = 0; i < height; i++) {
for (j = 0; j < width; j++) {
*peek_cell(board, j, i) = CELL_EMPTY;
}
}
board->RockCount = 0;
return 0;
}
void deinit_board(Board *board)
{
free(board->Cells);
}
int copy_board(Board *dest_board, Board *src_board)
{
int i, j;
dest_board->Width = src_board->Width;
dest_board->Height = src_board->Height;
dest_board->RockCount = src_board->RockCount;
dest_board->Cells = malloc(sizeof(int) * dest_board->Width * dest_board->Height);
if (dest_board->Cells == NULL) {
return 1;
}
for (i = 0; i < dest_board->Height; i++) {
for (j = 0; j < dest_board->Width; j++) {
*peek_cell(dest_board, j, i) = *peek_cell(src_board, j, i);
}
}
return 0;
}
void print_board(Board *board)
{
int i, j;
for (i = 0; i < board->Height; i++) {
for (j = 0; j < board->Width; j++) {
if (*peek_cell(board, j, i) == CELL_ROCK) {
printf("1 ");
} else {
printf("0 ");
}
}
printf("\n");
}
}
/* 0:success, 1:fail */
int update_cell(Board *board, int x, int y, int value)
{
int *prev_value;
if (verify_position(board, x, y)) {
return 1;
}
prev_value = peek_cell(board, x, y);
if (*prev_value == value) {
return 0;
}
if (*prev_value == CELL_EMPTY) {
assert(value == CELL_ROCK);
*prev_value = value;
board->RockCount += 1;
} else {
assert(*prev_value == CELL_ROCK);
assert(value == CELL_EMPTY);
*prev_value = value;
board->RockCount -= 1;
}
assert(board->RockCount >= 0);
return 0;
}
/* 0:success, 1:fail */
int operation(Board *board, Operator *op, int undo)
{
int pos_x, pos_y;
int jump_over_cell_x, jump_over_cell_y;
int move_to_x, move_to_y;
int direction_x, direction_y;
int ret;
if (undo) {
pos_x = op->PosX + op->MoveDirectionX * 2;
pos_y = op->PosY + op->MoveDirectionY * 2;
direction_x = -op->MoveDirectionX;
direction_y = -op->MoveDirectionY;
} else {
pos_x = op->PosX;
pos_y = op->PosY;
direction_x = op->MoveDirectionX;
direction_y = op->MoveDirectionY;
}
if (direction_x == 0 && direction_y == 0) {
return 1;
}
jump_over_cell_x = pos_x + direction_x;
jump_over_cell_y = pos_y + direction_y;
move_to_x = jump_over_cell_x + direction_x; /* == pos_x + direction_x * 2 */
move_to_y = jump_over_cell_y + direction_y;
if (verify_position(board, pos_x, pos_y)) {
return 1;
}
if (verify_position(board, move_to_x, move_to_y)) {
return 1;
}
if (*peek_cell(board, pos_x, pos_y) != CELL_ROCK) {
return 1;
}
if (undo) {
if (*peek_cell(board, jump_over_cell_x, jump_over_cell_y) != CELL_EMPTY) {
return 1;
}
} else {
if (*peek_cell(board, jump_over_cell_x, jump_over_cell_y) != CELL_ROCK) {
return 1;
}
}
if (*peek_cell(board, move_to_x, move_to_y) != CELL_EMPTY) {
return 1;
}
if (undo) {
ret = update_cell(board, pos_x, pos_y, CELL_EMPTY);
assert(ret == 0);
ret = update_cell(board, jump_over_cell_x, jump_over_cell_y, CELL_ROCK);
assert(ret == 0);
ret = update_cell(board, move_to_x, move_to_y, CELL_ROCK);
assert(ret == 0);
} else {
ret = update_cell(board, pos_x, pos_y, CELL_EMPTY);
assert(ret == 0);
ret = update_cell(board, jump_over_cell_x, jump_over_cell_y, CELL_EMPTY);
assert(ret == 0);
ret = update_cell(board, move_to_x, move_to_y, CELL_ROCK);
assert(ret == 0);
}
return 0;
}
/* 0:success, 1:fail */
int do_operation(Board *board, Operator *op)
{
return operation(board, op, 0);
}
/* 0:success, 1:fail */
int undo_operation(Board *board, Operator *op)
{
return operation(board, op, 1);
}
/* 0:solved, 1:fail */
int solver(Board *board, Operator *operator_array,
int operator_array_idx, int operator_array_length,
int *operator_array_solved_idx)
{
int i, j, u, v;
int *cellp;
Operator *op;
if (board->RockCount == 1) {
*operator_array_solved_idx = operator_array_idx;
return 0;
}
if (operator_array_length <= 0) {
fprintf(stderr, "operator_array_length too small!\n");
return 1;
}
op = &operator_array[operator_array_idx];
for (i = 0; i < board->Height; i++) {
for (j = 0; j < board->Width; j++) {
cellp = peek_cell(board, j, i);
if (*cellp == CELL_EMPTY) {
continue;
}
op->PosX = j;
op->PosY = i;
for (u = -1; u <= 1; u++) {
for (v = -1; v <= 1; v++) {
if (u == 0 && v == 0) continue;
op->MoveDirectionX = u;
op->MoveDirectionY = v;
if (do_operation(board, op) == 0) {
if (solver(board, operator_array,
operator_array_idx + 1,
operator_array_length,
operator_array_solved_idx) == 0) {
/* solved! */
return 0;
}
undo_operation(board, op);
}
}
}
}
}
return 1;
}
void print_operator(Operator *operator)
{
Operator *op = operator;
int dest_x, dest_y;
dest_x = op->PosX + op->MoveDirectionX * 2;
dest_y = op->PosY + op->MoveDirectionY * 2;
printf("move (%d, %d) to (%d, %d)\n", op->PosX, op->PosY, dest_x, dest_y);
}
void print_operator_array(Operator *operator_array, int length)
{
Operator *op = operator_array;
while (length--) {
print_operator(op++);
}
}
#define OPERATOR_ARRAY_SIZE 1024
static Operator g_operator_array[OPERATOR_ARRAY_SIZE];
#define BUFMAX 512
int main(int argc, char *argv[])
{
Board board, board_for_replay;
int width, height;
int i, j;
char input_data_buf[BUFMAX];
int input_length;
input_length = fread(input_data_buf, 1, BUFMAX, stdin);
if (input_length <= 0) {
fprintf(stderr, "invalid data?\n");
return 1;
}
input_data_buf[input_length] = '\0';
width = (strchr(input_data_buf, '\n') - input_data_buf) / 2;
height = input_length / (width*2);
printf("width: %d\n", width);
printf("height: %d\n", height);
if (init_board(&board, width, height)) {
fprintf(stderr, "init_board() failed\n");
return 1;
}
/* read data */
{
char *p = input_data_buf;
for (i = 0; i < height; i++) {
for (j = 0; j < width; j++) {
if (*p == '1') {
if (update_cell(&board, j, i, CELL_ROCK)) {
abort();
}
}
p += 2;
}
if (*p == '\n' || *p == '\r') {
/* CR/LF? */
p += 1;
}
}
}
copy_board(&board_for_replay, &board);
print_board(&board);
{
int solve_turn;
if (solver(&board, g_operator_array,
0, OPERATOR_ARRAY_SIZE, &solve_turn) == 0) {
printf("solved: %d turn\n", solve_turn);
print_operator_array(g_operator_array, solve_turn);
print_board(&board_for_replay);
printf("\nreplay solve\n");
for (i = 0; i < solve_turn; i++) {
Operator *op;
op = &g_operator_array[i];
do_operation(&board_for_replay, op);
printf("step %d : ", i);
print_operator(op);
print_board(&board_for_replay);
}
} else {
printf("couldnt solve!\n");
}
}
deinit_board(&board_for_replay);
deinit_board(&board);
return 0;
}
/*
- sample input (board_data.txt):
0 0 1 1 0 0
0 0 1 1 0 0
1 1 1 1 1 1
1 1 1 1 1 1
0 0 1 1 0 0
0 0 1 1 0 0
- result was:
$ ./solitier < board_data.txt
width: 6
height: 6
0 0 1 1 0 0
0 0 1 1 0 0
1 1 1 1 1 1
1 1 1 1 1 1
0 0 1 1 0 0
0 0 1 1 0 0
solved: 19 turn
move (2, 0) to (4, 0)
move (2, 1) to (4, 1)
move (0, 2) to (0, 4)
move (1, 2) to (1, 4)
move (2, 2) to (4, 4)
move (3, 2) to (5, 0)
move (5, 0) to (3, 0)
move (5, 2) to (3, 2)
move (3, 2) to (5, 4)
move (2, 3) to (0, 5)
move (5, 4) to (5, 2)
move (0, 5) to (0, 3)
move (2, 5) to (4, 3)
move (4, 4) to (4, 2)
move (5, 2) to (3, 2)
move (3, 5) to (1, 3)
move (0, 3) to (2, 3)
move (2, 3) to (4, 1)
move (3, 0) to (5, 2)
replay solve
0 0 1 1 0 0
0 0 1 1 0 0
1 1 1 1 1 1
1 1 1 1 1 1
0 0 1 1 0 0
0 0 1 1 0 0
step 0 : move (2, 0) to (4, 0)
0 0 0 0 1 0
0 0 1 1 0 0
1 1 1 1 1 1
1 1 1 1 1 1
0 0 1 1 0 0
0 0 1 1 0 0
step 1 : move (2, 1) to (4, 1)
0 0 0 0 1 0
0 0 0 0 1 0
1 1 1 1 1 1
1 1 1 1 1 1
0 0 1 1 0 0
0 0 1 1 0 0
step 2 : move (0, 2) to (0, 4)
0 0 0 0 1 0
0 0 0 0 1 0
0 1 1 1 1 1
0 1 1 1 1 1
1 0 1 1 0 0
0 0 1 1 0 0
step 3 : move (1, 2) to (1, 4)
0 0 0 0 1 0
0 0 0 0 1 0
0 0 1 1 1 1
0 0 1 1 1 1
1 1 1 1 0 0
0 0 1 1 0 0
step 4 : move (2, 2) to (4, 4)
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 1 1 1
0 0 1 0 1 1
1 1 1 1 1 0
0 0 1 1 0 0
step 5 : move (3, 2) to (5, 0)
0 0 0 0 1 1
0 0 0 0 0 0
0 0 0 0 1 1
0 0 1 0 1 1
1 1 1 1 1 0
0 0 1 1 0 0
step 6 : move (5, 0) to (3, 0)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 1 1
0 0 1 0 1 1
1 1 1 1 1 0
0 0 1 1 0 0
step 7 : move (5, 2) to (3, 2)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 1 0 1 1
1 1 1 1 1 0
0 0 1 1 0 0
step 8 : move (3, 2) to (5, 4)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 1
1 1 1 1 1 1
0 0 1 1 0 0
step 9 : move (2, 3) to (0, 5)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
1 0 1 1 1 1
1 0 1 1 0 0
step 10 : move (5, 4) to (5, 2)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 0
1 0 1 1 1 0
1 0 1 1 0 0
step 11 : move (0, 5) to (0, 3)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 1
1 0 0 0 0 0
0 0 1 1 1 0
0 0 1 1 0 0
step 12 : move (2, 5) to (4, 3)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 1
1 0 0 0 1 0
0 0 1 0 1 0
0 0 0 1 0 0
step 13 : move (4, 4) to (4, 2)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 1 1
1 0 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
step 14 : move (5, 2) to (3, 2)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 1 0 0
1 0 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
step 15 : move (3, 5) to (1, 3)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 1 0 0
1 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
step 16 : move (0, 3) to (2, 3)
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
step 17 : move (2, 3) to (4, 1)
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
step 18 : move (3, 0) to (5, 2)
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
*/