Puzzle solving all start the whole process, the most difficult start to 138 steps (Interesting

//本程序的输入为 457 号代码的输出
//参见：生成华容道所有可求解的开局含镜像263977种，不含镜像132156种
// http://www.fayaa.com/code/view/457/
//
//终于调试完了，计算132156种开局耗时两分钟左右
//很扫兴的是，计算出来的最难布局居然是138步
//也就是：峰回路转( http://www.fayaa.com/youxi/hrd/55/ )
//
#pragma warning(disable:4530)
#include <stdio.h>
#include <set>
#include <map>
#include <deque>
#include <fstream>
#include <string>
//@@on linux machine
//@@#include <linux/types.h>
using namespace std;
//@@on linux machine
//@@typedef int64 INT64;
typedef __int64 INT64;
typedef unsigned char BYTE;
//!assume int is 32-bit

//block item type
enum BIT {EMPTY=0, DOT, VBAR, HBAR, BOX};

class Board;
//----------------------------------------
//Global variables
map<INT64, int> g_steps;
set<INT64> g_mbd;
deque<Board*> g_bfs; //Broad-First-Search to ensure shortest path
unsigned int g_index = 0;

//CI is short for Cell Index
#define VALID_CI(x) (x >= 0 && x < 10)
#define IS_BOX(x) (items[x-1]>>5 == BOX)
#define BUILD_BYTE(type, x, y) ((type) << 5 | (x) << 3 | (y))

class Board {
public:
Board(){}
Board(int *layout) {
memset(this, 0, sizeof(*this));
index = -1; //set to BAD value
beg_level = -1; //set to BAD beg level
parent = -1; //set to Invalid
//0xFF mean's boundary
for (int i=0; i<6; i++) {
matrix[0][i] = (BYTE)0xFF;
matrix[6][i] = (BYTE)0xFF;
}
for (int i=0; i<7; i++) {
matrix[i][0] = (BYTE)0xFF;
matrix[i][5] = (BYTE)0xFF;
}
//init the matrix and items
BYTE type = 0;
BYTE x = 0;
BYTE y = 0;
for (int i=0; i<10; i++) {
type = layout[i*3];
x = layout[i*3+1];
y = layout[i*3+2];
items[i] = BUILD_BYTE(type, x, y);
switch (type) {
case DOT: matrix[y+1][x+1] = i+1; break;
case VBAR: matrix[y+1][x+1] = i+1; matrix[y+2][x+1] = i+1; break;
case HBAR: matrix[y+1][x+1] = i+1; matrix[y+1][x+2] = i+1; break;
case BOX: matrix[y+1][x+1] = i+1; matrix[y+1][x+2] = i+1;
matrix[y+2][x+1] = i+1; matrix[y+2][x+2] = i+1; break;
}
}
//find out the empty block
int count = 0;
for (int i=0; i<7; i++)
for (int k=0; k<6; k++)
if (matrix[i][k] == 0)
empty[count++] = k << 4 | i;
}

inline INT64 GetValue() const {
INT64 val = 0;
int index = 0;
BYTE bt = 0;
for (int i=1; i<6; i++) {
for (int k=1; k<5; k++) {
index = matrix[i][k] - 1;
bt = VALID_CI(index) ? items[index] >> 5 : 0;
val = val << 3 | bt;
}
}
return val;
}
inline INT64 GetRValue() const {
INT64 val = 0;
int index = 0;
BYTE bt = 0;
for (int i=1; i<6; i++) {
for (int k=4; k>0; k--) {
index = matrix[i][k] - 1;
bt = VALID_CI(index) ? items[index] >> 5 : 0;
val = val << 3 | bt;
}
}
return val;
}
//spawn new Board by moving the cells around empty cells
// return false if not found
// return true if we got the solution
// the last board in the deque is the solution
bool Spawn() {
if (beg_level > 0) {
Board *pnewb = new Board();
*pnewb = (*this);
pnewb->beg_level = beg_level - 1;
pnewb->parent = g_index;
g_bfs.push_back(pnewb);
return pnewb->beg_level == 0;
}
//collect the cells around empty cells
BYTE around[8] = {0};
int count = 0;
//DO NOT change the order of ulrd, it's been depended
int ulrd[4][2] = {{0,-1}, {-1,0}, {1,0}, {0,1}};
for (int i=0; i<2; i++) {
int x = empty[i] >> 4;
int y = empty[i] & 0xF;
for (int k=0; k<4; k++) {
int nx = x + ulrd[k][0];
int ny = y + ulrd[k][1];
int index = matrix[ny][nx] - 1;
if (index == this->index)
continue; //move same step with last step doesn't helps solving it
if (VALID_CI(index)) {
Board *pnewb = new Board();
*pnewb = (*this);
pnewb->parent = g_index;
if (pnewb->TryAndMove(index, -ulrd[k][0], -ulrd[k][1])) {
pnewb->index = index;
INT64 value = 0;
//in Hua-Rong-Dao's rule, move a cell continously
// multi-times, only count as ONE step, so,
// let's give it another chance to move
int moveBack = k ^ 3; //3==0b11, the reverse direction of last move
Board *pnewb2 = new Board();
*pnewb2 = (*pnewb);
//pnewb2->parent = g_bfs.size() - 1;
int d = 0;
for (; d<4; d++) {
if (d == moveBack) continue;
//copy data and add parent
if (pnewb2->TryAndMove(index, -ulrd[d][0], -ulrd[d][1])) {
value = pnewb2->GetValue();
if (g_mbd.find(value) == g_mbd.end()) {
//add new board to bfs and set the board value to map
g_bfs.push_back(pnewb2);
g_mbd.insert(value);
g_mbd.insert(pnewb2->GetRValue());
//Do we win?
if (pnewb2->Win())
return true;
}
break;//ONLY one direction is good due to the rule
}
}
if (d == 4) delete pnewb2;
//-------------------------------------

value = pnewb->GetValue();
if (g_mbd.find(value) == g_mbd.end()) {
//add new board to bfs and set the board value to map
g_bfs.push_back(pnewb);
g_mbd.insert(value);
g_mbd.insert(pnewb->GetRValue());
//Do we win?
if (pnewb->Win())
return true;
continue;
}
}
delete pnewb;
}
}
}
return false;
}

bool Win() {
//cut the search if we find current matrix privous solutions
INT64 val = GetValue();
if (g_steps.find(val) != g_steps.end()) {
beg_level = g_steps[val];
return beg_level == 0;
}
//return true if the following cell's type is BOX
// 2,4, 3,4, 2,5, 3,5
return IS_BOX(matrix[4][2]) && IS_BOX(matrix[4][3]) &&
IS_BOX(matrix[5][2]);// && IS_BOX(matrix[5][3]);
}

bool TryAndMove(int index, int dx, int dy) {
BYTE item = items[index];
BYTE type = item >> 5;
int x = item >> 3 & 0x03; //0x03==0b11
int y = item & 0x07; //0x07==0b111
bool bRet = false;
//ci is short for cell index
int ci1, ci2, ci3, ci4;
ci1 = ci2 = ci3 = ci4 = 0;
switch (type) {
case DOT:
ci1 = matrix[y+dy+1][x+dx+1];
bRet = !ci1 || ci1==index+1;
if (bRet) {
matrix[y+1][x+1] = 0;
matrix[y+dy+1][x+dx+1] = index + 1;
items[index] = BUILD_BYTE(type, x+dx, y+dy);
SetEmpty(x+1, y+1);
}
break;
case VBAR:
ci1 = matrix[y+dy+1][x+dx+1];
ci2 = matrix[y+dy+2][x+dx+1];
bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1);
if (bRet) {
matrix[y+1][x+1] = 0;
matrix[y+2][x+1] = 0;
matrix[y+dy+1][x+dx+1] = index + 1;
matrix[y+dy+2][x+dx+1] = index + 1;
items[index] = BUILD_BYTE(type, x+dx, y+dy);
if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
if (matrix[y+2][x+1] == 0) SetEmpty(x+1, y+2);
}
break;
case HBAR:
ci1 = matrix[y+dy+1][x+dx+1]; ci2 = matrix[y+dy+1][x+dx+2];
bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1);
if (bRet) {
matrix[y+1][x+1] = 0; matrix[y+1][x+2] = 0;
matrix[y+dy+1][x+dx+1] = index + 1;
matrix[y+dy+1][x+dx+2] = index + 1;
items[index] = BUILD_BYTE(type, x+dx, y+dy);
if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
if (matrix[y+1][x+2] == 0) SetEmpty(x+2, y+1);
}
break;
case BOX:
ci1 = matrix[y+dy+1][x+dx+1]; ci2 = matrix[y+dy+1][x+dx+2];
ci3 = matrix[y+dy+2][x+dx+1]; ci4 = matrix[y+dy+2][x+dx+2];
bRet = (!ci1 || ci1==index+1) && (!ci2 || ci2==index+1) &&
(!ci3 || ci3==index+1) && (!ci4 || ci4==index+1);
if (bRet) {
matrix[y+1][x+1] = 0; matrix[y+1][x+2] = 0;
matrix[y+2][x+1] = 0; matrix[y+2][x+2] = 0;
matrix[y+dy+1][x+dx+1] = index+1; matrix[y+dy+1][x+dx+2] = index+1;
matrix[y+dy+2][x+dx+1] = index+1; matrix[y+dy+2][x+dx+2] = index+1;
items[index] = BUILD_BYTE(type, x+dx, y+dy);
if (matrix[y+1][x+1] == 0) SetEmpty(x+1, y+1);
if (matrix[y+1][x+2] == 0) SetEmpty(x+2, y+1);
if (matrix[y+2][x+1] == 0) SetEmpty(x+1, y+2);
if (matrix[y+2][x+2] == 0) SetEmpty(x+2, y+2);
}
break;
}
return bRet;
}

void SetEmpty(int ex, int ey) {
int x = empty[0] >> 4;
int y = empty[0] & 0xF;
BYTE *pB = &empty[1];
if (matrix[y][x] != 0)
pB = &empty[0];
(*pB) = (ex<<4) + ey;
}

//Member variables====^_^====^_^====^_^====^_^====^_^====^_^====
int beg_level; //not-1 means it's level is got from previous solutions
int parent; //parent node position in the deque
BYTE index; //moved cell's index
BYTE matrix[7][6]; //[1+5+1][1+4+1] of byte, each byte is the (index+1) in items
BYTE empty[2]; //2 empty slot's position in matrix, x = p >> 4, y = p & 0xF
BYTE items[10]; //BIT:3,x:2,y:3), x,y is zero-based
};

//----------------------------------------
//return the board index in g_bfs if succeed
bool SolveTheBoard(const Board &bd) {
Board *pnewb = new Board();
*pnewb = bd;
if (pnewb->Win()) {
g_bfs.push_back(pnewb);
g_steps[pnewb->GetValue()] = 0;
g_steps[pnewb->GetRValue()] = 0;
return true;
}

INT64 value = pnewb->GetValue();
if (g_steps.find(value) != g_steps.end()) {
return true; //already been solved in the middle of previous problems
}
g_bfs.push_back(pnewb);
g_mbd.insert(value);
g_mbd.insert(pnewb->GetRValue());
while (g_index < g_bfs.size()) {
bool bRet = g_bfs[g_index]->Spawn();
if (bRet) return bRet;
g_index++;
}
return false;
}

void WriteSolution() {
if (g_bfs.size() == 0) {
return;
}
//put all the matrix level values to the steps
Board *pBd = g_bfs[g_bfs.size() - 1];
int level = pBd->beg_level;
if (level < 0) {
level = 0;
//} else if (pBd->beg_level == -1) { //calc out, otherwise beg out
g_steps[pBd->GetValue()] = 0;
g_steps[pBd->GetRValue()] = 0;
}
while (pBd->parent >= 0) {
level ++;
pBd = g_bfs[pBd->parent];
g_steps[pBd->GetValue()] = level;
g_steps[pBd->GetRValue()] = level;
}
}

int main(int argc, char**argv) {
ifstream fin("input.log");
//ofstream fout("output.log");
string s;
int count = 0;
while (getline(fin, s)) {
//calculate
//s = "200410230202312232113123104134";
int layout[30] = {0};
for (size_t i=0; i<30; i++)
layout[i] = s[i] - '0';
Board bd(layout);
bool bRet = SolveTheBoard(bd);
if (bRet)
WriteSolution();
else
printf("Can't solve: %s\n", s.c_str());

count++;
if (count % 100 == 0) {
printf("%d\n", count);
}

//else
//printf("NOT:%s\n", s);

//clean up
g_mbd.clear();
//delete all items, needed? cosuming time?
for (unsigned int i=0; i<g_bfs.size(); i++)
delete g_bfs[i];
g_bfs.clear();
g_index = 0;
}
fin.close();

//write the g_steps down
ofstream fout("output.log");
map<INT64, int>::const_iterator itor;
char buff[100] = {0};
for (itor=g_steps.begin(); itor!=g_steps.end(); itor++) {
INT64 value = itor->first;
int step = itor->second;
sprintf(buff, "%04d:%lld\n", step, value);
fout << buff;
}
fout.close();

//HengDaoLiMa: 200410230202312232113123104134
//BiYiHengKong:300420301302322103123233104124
return 0;
}

AllStuffON

Puzzle solving all start the whole process, the most difficult start to 138 steps (Interesting

Learn More :

AllStuffON

Puzzle solving all start the whole process, the most difficult start to 138 steps (Interesting

Learn More :

Share this