Moderator: Board moderators
. 
Code: Select all
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
// only needed for calculating manhatten distance
typedef struct {
unsigned short int r;
unsigned short int c;
} coord;
// state data type. pretty much obvious
typedef struct s_d {
unsigned short int puzzle[4][4];
unsigned short int zero_r;
unsigned short int zero_c;
short int cost;
string* path;
} state;
// retuns true if state is goal state
bool goal_test( state* );
// expands a node and returns of the max 3 possible nodes (the 4th node
// would be a circle
state* expand( state*, bool[4] );
// manhatten distance heuristic
int h( state* );
// find_puzzle_solution increases maximum depth until idaS returns true
bool find_puzzle_solution( state& );
// does the searching
bool idaS( state*, int );
// just needed for checking wether problem is solvable
unsigned short int calc_inversions( unsigned short int, unsigned short int, state* );
static coord solution[16] = { {3, 3}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {2, 0}, {2, 1}, {2, 2}, {2, 3}, {3, 0}, {3, 1}, {3, 2} };
static unsigned short int permutation_inversions;
static string* solution_p;
bool find_puzzle_solution( state& start ) {
int c = h( &start );
while ( 1 ) {
if ( idaS( &start, c ) == false ) {
c++;
} else {
return true;
}
}
}
bool idaS( state* s, int depth ) {
state* next;
bool done[4];
done[0] = false;
done[1] = false;
done[2] = false;
done[3] = false;
if ( goal_test( s ) == true ) {
solution_p = new string( *((*s).path) );
return true;
}
while ( ( next = expand( s, done ) ) != NULL ) {
if ( (*next).cost + h( next ) <= depth ) {
if ( idaS( next, depth ) == false ) {
delete (*next).path;
delete next;
continue;
} else {
delete (*next).path;
delete next;
return true;
}
}
}
return false;
}
int h( state* s ) {
int i;
int j;
int m_dist = 0;
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
m_dist = m_dist + abs( ((solution[ ((*s).puzzle[i][j]) ]).r - i) ) + abs( ((solution[ ((*s).puzzle[i][j]) ]).c - j) );
}
}
return ((5 * m_dist)/3);
}
bool goal_test( state* s ) {
if ( h( s ) == 0 ) {
return true;
}
return false;
}
// this is probably the most confussing part of my code
// expand keeps track of already expanded nodes by use
// of a bool array and returns the cheapest, on next call secound cheapest
// and so one successor state of "s"
// repetitions like "UD", "LR" or anything like that are avoided
// at the end all states which are not needed are deleted
// this part itself is probably inefficent (one could probably
// make the code shorter but I think that is not the problem...
state* expand( state* s, bool done[4] ) {
state* ns[4];
state* ret;
int i;
int j;
int c = -1;
int d;
if ( done[0] == true && done[1] == true && done[2] == true && done[3] == true ) {
return NULL;
}
ns[0] = new state();
ns[1] = new state();
ns[2] = new state();
ns[3] = new state();
if ( done[0] == false ) {
if ( (*s).zero_r > 0 ) {
if ( !((*((*s).path)).empty()) ) {
if ( ((*((*s).path)).at( (*((*s).path)).length() - 1 ) != 'D') ) {
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
(*ns[0]).puzzle[i][j] = (*s).puzzle[i][j];
}
}
(*ns[0]).puzzle[(*s).zero_r][(*s).zero_c] = (*s).puzzle[(*s).zero_r - 1][(*s).zero_c];
(*ns[0]).puzzle[(*s).zero_r - 1][(*s).zero_c] = 0;
(*ns[0]).cost = (*s).cost + 1;
(*ns[0]).zero_r = (*s).zero_r - 1;
(*ns[0]).zero_c = (*s).zero_c;
(*ns[0]).path = new string( *((*s).path) + 'U' );
} else {
done[0] = true;
}
} else {
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
(*ns[0]).puzzle[i][j] = (*s).puzzle[i][j];
}
}
(*ns[0]).puzzle[(*s).zero_r][(*s).zero_c] = (*s).puzzle[(*s).zero_r - 1][(*s).zero_c];
(*ns[0]).puzzle[(*s).zero_r - 1][(*s).zero_c] = 0;
(*ns[0]).cost = (*s).cost + 1;
(*ns[0]).zero_r = (*s).zero_r - 1;
(*ns[0]).zero_c = (*s).zero_c;
(*ns[0]).path = new string( *((*s).path) + 'U' );
}
} else {
done[0] = true;
}
}
if ( done[1] == false ) {
if ( (*s).zero_r < 3 ) {
if ( !((*((*s).path)).empty()) ) {
if (((*((*s).path)).at( (*((*s).path)).length() - 1 ) != 'U') ) {
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
(*ns[1]).puzzle[i][j] = (*s).puzzle[i][j];
}
}
(*ns[1]).puzzle[(*s).zero_r][(*s).zero_c] = (*s).puzzle[(*s).zero_r + 1][(*s).zero_c];
(*ns[1]).puzzle[(*s).zero_r + 1][(*s).zero_c] = 0;
(*ns[1]).cost = (*s).cost + 1;
(*ns[1]).zero_r = (*s).zero_r + 1;
(*ns[1]).zero_c = (*s).zero_c;
(*ns[1]).path = new string( *((*s).path) + 'D' );
} else {
done[1] = true;
}
} else {
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
(*ns[1]).puzzle[i][j] = (*s).puzzle[i][j];
}
}
(*ns[1]).puzzle[(*s).zero_r][(*s).zero_c] = (*s).puzzle[(*s).zero_r + 1][(*s).zero_c];
(*ns[1]).puzzle[(*s).zero_r + 1][(*s).zero_c] = 0;
(*ns[1]).cost = (*s).cost + 1;
(*ns[1]).zero_r = (*s).zero_r + 1;
(*ns[1]).zero_c = (*s).zero_c;
(*ns[1]).path = new string( *((*s).path) + 'D' );
}
} else {
done[1] = true;
}
}
if ( done[2] == false ) {
if ( (*s).zero_c > 0 ) {
if ( !((*((*s).path)).empty()) ) {
if ( ((*((*s).path)).at( (*((*s).path)).length() - 1 ) != 'R') ) {
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
(*ns[2]).puzzle[i][j] = (*s).puzzle[i][j];
}
}
(*ns[2]).puzzle[(*s).zero_r][(*s).zero_c] = (*s).puzzle[(*s).zero_r][(*s).zero_c - 1];
(*ns[2]).puzzle[(*s).zero_r][(*s).zero_c - 1] = 0;
(*ns[2]).cost = (*s).cost + 1;
(*ns[2]).zero_r = (*s).zero_r;
(*ns[2]).zero_c = (*s).zero_c - 1;
(*ns[2]).path = new string( *((*s).path) + 'L' );
} else {
done[2] = true;
}
} else {
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
(*ns[2]).puzzle[i][j] = (*s).puzzle[i][j];
}
}
(*ns[2]).puzzle[(*s).zero_r][(*s).zero_c] = (*s).puzzle[(*s).zero_r][(*s).zero_c - 1];
(*ns[2]).puzzle[(*s).zero_r][(*s).zero_c - 1] = 0;
(*ns[2]).cost = (*s).cost + 1;
(*ns[2]).zero_r = (*s).zero_r;
(*ns[2]).zero_c = (*s).zero_c - 1;
(*ns[2]).path = new string( *((*s).path) + 'L' );
}
} else {
done[2] = true;
}
}
if ( done[3] == false ) {
if ( (*s).zero_c < 3 ) {
if ( !((*((*s).path)).empty()) ) {
if ( ((*((*s).path)).at( (*((*s).path)).length() - 1 ) != 'L') ) {
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
(*ns[3]).puzzle[i][j] = (*s).puzzle[i][j];
}
}
(*ns[3]).puzzle[(*s).zero_r][(*s).zero_c] = (*s).puzzle[(*s).zero_r][(*s).zero_c + 1];
(*ns[3]).puzzle[(*s).zero_r][(*s).zero_c + 1] = 0;
(*ns[3]).cost = (*s).cost + 1;
(*ns[3]).zero_r = (*s).zero_r;
(*ns[3]).zero_c = (*s).zero_c + 1;
(*ns[3]).path = new string( *((*s).path) + 'R' );
} else {
done[3] = true;
}
} else {
ns[3] = new state();
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
(*ns[3]).puzzle[i][j] = (*s).puzzle[i][j];
}
}
(*ns[3]).puzzle[(*s).zero_r][(*s).zero_c] = (*s).puzzle[(*s).zero_r][(*s).zero_c + 1];
(*ns[3]).puzzle[(*s).zero_r][(*s).zero_c + 1] = 0;
(*ns[3]).cost = (*s).cost + 1;
(*ns[3]).zero_r = (*s).zero_r;
(*ns[3]).zero_c = (*s).zero_c + 1;
(*ns[3]).path = new string( *((*s).path) + 'R' );
}
} else {
done[3] = true;
}
}
for ( i = 0; i < 4; i++ ) {
if ( done[i] == false ) {
if ( c == -1 ) {
d = i;
ret = ns[i];
c = (*ns[i]).cost + h( ns[i] );
} else if ( c > (*ns[i]).cost + h( ns[i] ) ) {
d = i;
ret = ns[i];
c = (*ns[i]).cost + h( ns[i] );
}
}
}
for ( i = 0; i < 4; i++ ) {
if ( i != d ) {
delete (*ns[i]).path;
delete ns[i];
} else {
done[i] = true;
}
}
return ret;
}
unsigned short int calc_inversions( unsigned short int row, unsigned short int column, state* s )
{
unsigned short int i, j, ret(0);
for ( i = row; i < 4; i++ ) {
if ( i == row ) {
for ( j = column + 1; j < 4; j++ ) {
if ( (*s).puzzle[i][j] != 0 && (*s).puzzle[i][j] < (*s).puzzle[row][column] ) {
ret++;
}
}
} else {
for ( j = 0; j < 4; j++ ) {
if ( (*s).puzzle[i][j] != 0 && (*s).puzzle[i][j] < (*s).puzzle[row][column] ) {
ret++;
}
}
}
}
return ret;
}
int main()
{
unsigned int cases;
unsigned short int i;
unsigned short int j;
state* s;
cin >> cases;
while ( cases > 0 ) {
s = new state();
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
cin >> (*s).puzzle[i][j];
if ( (*s).puzzle[i][j]== 0 ) {
(*s).zero_r = i;
(*s).zero_c = j;
}
}
}
permutation_inversions = 0;
for ( i = 0; i < 4; i++ ) {
for ( j = 0; j < 4; j++ ) {
permutation_inversions += calc_inversions( i, j, s );
}
}
if ( ((permutation_inversions + (*s).zero_r + 1) % 2) != 0 ) {
cases--;
delete (*s).path;
delete s;
continue;
}
(*s).path = new string( "" );
(*s).cost = 0;
find_puzzle_solution( *s );
cout << *solution_p << endl;
delete solution_p;
cases--;
delete (*s).path;
delete s;
}
return 0;
}
Code: Select all
#include <iostream>
#include <set>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define CORD(i,j) (i * 4 + j)
#define OK(i,j,v) ((CORD(i,j)+1==v) ? 1:0)
typedef unsigned long long ll;
typedef struct Tabuleiro {
ll tab;
int dist;
char oks;
ll s1, s2;
char nivel;
} Tabuleiro;
int DistM (Tabuleiro *t);
double f (Tabuleiro *a) {
return (15 - a->oks) * 0 + a->nivel * 1 + a->dist * 1.33;
}
struct Cmp {
Cmp () {}
bool operator () (Tabuleiro *a, Tabuleiro *b) {
double sa = f (a);
double sb = f (b);
if (sa != sb)
return sa > sb;
return a->nivel > b->nivel;
}
};
int c2i (char c) {
switch (c) {
case 'D': return 0;
case 'U': return 1;
case 'R': return 2;
case 'L': return 3;
}
}
char i2c (int i) {
switch (i) {
case 0: return 'D';
case 1: return 'U';
case 2: return 'R';
case 3: return 'L';
}
}
void Set (Tabuleiro *t, char c) {
if (t->nivel > 30 && t->s2 == 0) {
t->s2 = t->s1;
t->s1 = 0;
}
t->s1 = (t->s1 << 2) + c2i (c);
}
void Set(ll &x, int a, int i, int j)
{
int p = 4 * (4 * i + j );
x &= ~( ll(15) << p);
x |= ll(a) << p;
}
void Get(ll &x, int a, int &i, int &j) {
ll y = x;
int k = 0;
while( (y % 16) != a && k < 16) {
// printf("%d -- %d\n", k, y % 16);
k++;
y >>= 4;
}
i = k / 4;
j = k % 4;
}
int Get (ll &x, int i, int j) {
int p = 4 * (4 * i + j );
return (x >> p) % 16;
}
/* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 */
int mi[] = {3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3};
int mj[] = {3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2};
int dx[] = {+0, +0, +1, -1};
int dy[] = {+1, -1, +0, +0};
char dc[] = "DURL";
int CalcDist (int i, int j, int v) {
return abs(i - mi[v]) + abs (j - mj[v]);
}
int DistM (Tabuleiro *t) {
int i, j, ret;
ret = 0;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
ret += CalcDist (i, j, Get (t->tab, i, j));
}
}
return ret;
}
int resolvivel (Tabuleiro *t) {
int i, j, cnt;
Get (t->tab, 0, i, j);
cnt = i + 1;
for (i = 1; i < 17; i++) {
for (j = i + 1; j < 17; j++) {
if (Get (t->tab, mi[i % 16], mj[i % 16]) > Get (t->tab, mi[j % 16], mj[j % 16]) &&
Get (t->tab, mi[j % 16], mj[j % 16]) != 0) {
cnt++;
}
}
}
if ((cnt % 2) == 1)
return 0;
return 1;
}
void imprime_solucao (Tabuleiro *no) {
char c;
if (no->nivel == 0)
return;
c = i2c (no->s1 % 4);
no->s1 = no->s1 >> 2;
no->nivel--;
if (no->s1 == 0)
no->s1 = no->s2;
imprime_solucao (no);
printf ("%c", c);
}
void imprimir_tabuleiro (Tabuleiro *t) {
int i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
printf ("%2d ", Get (t->tab, i, j));
}
printf ("\n");
}
Get (t->tab, 0, i, j);
int nivel = t->nivel;
ll s1 = t->s1, s2 = t->s2;
printf ("saida: "); imprime_solucao (t);
t->nivel = nivel;
printf ("\noks: %d\nzi: %d zj: %d\ndist: %d nivel:%d f:%.2lf\n\n",
t->oks, i, j, DistM (t), t->nivel, f (t));
t->s1 = s1; t->s2 = s2;
}
bool fcmp (const Tabuleiro &a, const Tabuleiro &b) {
double sa = (15 - a.oks) * 0 + a.nivel * 1 + a.dist * 1.33;
double sb = (15 - b.oks) * 0 + b.nivel * 1 + b.dist * 1.33;
if (sa != sb)
return sa < sb;
return a.nivel < b.nivel;
}
set<ll> memop;
/*
IDA*
*/
double
profundidadeLimitada (Tabuleiro *atual,
int ultimo, double limite, ll *final,
Tabuleiro *encontrado) {
Tabuleiro prox[4];
int i, j, k, m, zi, zj;
double novo_limite = f (atual);
if (memop.find (atual->tab) != memop.end ())
goto fim;
memop.insert (atual->tab);
if (atual->tab == *final) {
memcpy (encontrado, atual, sizeof (Tabuleiro));
goto fim;
}
if (prox[k].nivel < 50 || f (&prox[k]) <= limite)
goto fim;
Get(atual->tab, 0, i, j);
for (k = 0, m = 0; k < 4; k++) {
zi = i + dy[k];
zj = j + dx[k];
if (zi < 0 || zj < 0 || zi > 3 || zj > 3)
continue;
memcpy (&(prox[m]), atual, sizeof (Tabuleiro));
int xx = Get (atual->tab, zi, zj);
Set (prox[m].tab, xx, i, j);
Set (prox[m].tab, 0, zi, zj);
prox[m].dist -= CalcDist (i, j, 0);
prox[m].dist += CalcDist (zi, zj, 0);
prox[m].dist -= CalcDist (zi, zj, xx);
prox[m].dist += CalcDist (i, j, xx);
prox[m].oks -= OK (zi, zj, xx);
prox[m].oks += OK (i, j, xx);
prox[m].nivel++;
Set (&prox[m], dc[k]);
m++;
}
sort (prox, prox + m, fcmp);
for (k = 0; k < m; k++) {
novo_limite = min (novo_limite,
profundidadeLimitada (&prox[k], -1, limite, final, encontrado));
if (encontrado->tab == *final)
break;
}
fim:
memop.erase (atual->tab);
return novo_limite;
}
int main () {
int i, j, zi, zj, tmp, testes, k;
Tabuleiro ini, prox, atual;
ll inicial = 0;
ll final;
for (i = 0; i < 4; i++)
for (j = 0; j < 4; j++) {
tmp = (4 * i + j + 1) % 16;
Set (final, tmp, i, j);
}
scanf ("%d", &testes);
while (testes--) {
memset (&ini, 0, sizeof (ini));
for (i = 0; i < 4; i++)
for (j = 0; j < 4; j++) {
scanf ("%d", &tmp);
Set (ini.tab, tmp, i, j);
if (tmp == 0) {
}
else {
ini.oks += OK (i, j, tmp);
}
ini.dist += CalcDist (i, j, tmp);
}
if (!resolvivel (&ini)) {
printf ("This puzzle is not solvable.\n");
continue;
}
double limite = f (&atual);
atual.tab = 0;
while (atual.tab != final) {
memop.clear ();
limite = profundidadeLimitada (&ini, -1, limite, &final, &atual);
}
imprime_solucao (&atual);
printf ("\n");
}
return 0;
}
Code: Select all
#include<iostream>
#include<list>
#include<deque>
#include<queue>
#include<cassert>
#include<cstdio>
#include<vector>
#include<ext/hash_map>
#include<ext/hash_set>
#include<map>
#include<cmath>
#include<set>
#include<string>
#include<algorithm>
using namespace std;
using namespace __gnu_cxx;
typedef unsigned long long ull;
typedef long long ll;
/* BOARD SIZE */
#define MAX (4)
#define DEPTHLIM 50
#define HASHSIZE 1000000
#define CON (2)
#define CON2 (1)
#define MAX2 (16)
#define MAXI (15)
#define DELIM (0)
set <ull > ss1;
void swap(int &a,int &b)
{
int tmp;
tmp=a;
a=b;
b=tmp;
return;
}
int isvalid (int x, int y)
{
if ((x >= MAX) || (x < 0) || (y >= MAX) || (y < 0))
return 0;
return 1;
}
/* ENCODE the board in a 64 bit number with 4 bits for each state */
#define BASE 16
/* DIRECTION VECTORS */
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char dir[4]={'R','D','L','U'};
int mx[MAX2]={3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3};
int my[MAX2]={3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2};
#define N (1ULL)
/* COEFFS */
long long powerindex[MAX2]={N,N<<4,N<<8,N<<12,N<<16,N<<20,N<<24,N<<28,N<<32,N<<36,N<<40,N<<44,N<<48,N<<52,N<<56,N<<60};
inline int get(const int idx,const ull val) { return (val/powerindex[idx])%BASE; }
inline ull myset(const int idx,const ull val,const ull x){ return val + x*powerindex[idx]; }
/* CALCULATE MANHATTAN DISTANCE OF c */
int calc(int x,int y,int c){
return abs(x-mx[c]) + abs(y-my[c]);
}
/* CALCULATE MANHATTAN DISTANCE OF c if it is moved from (x1,y1)->(x2,y2) */
int h(int x1,int y1,int x2,int y2,int c){
return calc(x2,y2,c) - calc(x1,y1,c) ;
}
/* LINEAR index of the board if this were put in a single array */
#define LIN(x,y) (MAXI-((x*MAX) + y))
/* Given a board encoded as unsigned long long calculate the manhattan distance from target board */
int mhd(ull num){
int i,j,ts=0,x;
for(i=MAX-1;i>-1;i--)
for(j=MAX-1;j>-1;j--) {
x=num%BASE;
ts+=h(i,j,mx[x],my[x],x);
num/=BASE;
}
return ts;
}
/* Change hole from x1,y1 to x2,y2 and calculate the new value */
int chim(int x1,int y1,int x2,int y2,ull v,ull &newval){
int v1=get(LIN(x1,y1),v);
int v2=get(LIN(x2,y2),v);
newval=v;
newval=myset(LIN(x1,y1),newval,v2-v1);
newval=myset(LIN(x2,y2),newval,v1-v2);
return h(x2,y2,x1,y1,v2) + h(x1,y1,x2,y2,v1);
}
/* Store the backtrack indexes and the values, Better than a string in each level */
int bt[5000000];
int ct[5000000];
/*
* Structure of a board
* x,y is where the hole (DELIM or 0) is
* cost is the manhattan cost
* val is the encoded value of board ,so target value is 0x123456789ABCDEF
* lvl is the depth of the board , idx is the index for backtracking
* tcost is COEFF1*cost + lvl
*
*
*/
struct board{
int x,y;
int cost;
ull val;
int lvl,idx;
double tcost;
};
/* Is the position good , if yes then store the newval of the board and the
* total cost
*/
int isgood(int x1,int y1,int x2,int y2,ull val,ull &newval,int& tc){
if(!isvalid(x2,y2)) return 0;
tc=chim(x1,y1,x2,y2,val,newval);
if(ss1.find(newval)!=ss1.end()) return 0;
ss1.insert(newval);
return 1;
}
#define MYEPS 1e-6
bool operator<(const board &a,const board &b){
return (a.tcost > b.tcost && fabs(a.tcost-b.tcost)>MYEPS);
}
#define TARGET 0x123456789ABCDEF0ULL
/* The coeffs for the heuristic */
#define COEFF1 4
#define COEFF2 1
/* Print the solution */
void backfind(int ve){
if(ve==1) return;
backfind(bt[ve]);
printf("%c",ct[ve]);
}
/* Astar is bfs with priority queue */
int astar(ull num,int hx,int hy){
board tmp,tmp1;
int x,y,nx,ny,last=1;
ull val;
/* Priority queue orderd by least total cost at the top */
priority_queue<board> pq;
/* Initialize the board */
x=tmp.x=hx;
y=tmp.y=hy;
tmp.idx=last++;
bt[tmp.idx]=0;
ct[tmp.idx]=0;
tmp.lvl=1;
tmp.val=num;
tmp.cost=tmp.tcost=mhd(num);
tmp.tcost=COEFF1*tmp.cost + COEFF2*tmp.lvl;
isgood(x,y,x,y,tmp.val,val,y);
/* Push the board */
pq.push(tmp);
int notimes=0;
if(tmp.val==TARGET){
goto fail;
}
while(pq.size()){
tmp1=tmp=pq.top();
if(pq.size()>notimes) notimes=pq.size();
/* If the queue size is too big break, we are going to run out of memory */
if(notimes>HASHSIZE) break;
pq.pop();
x=tmp.x; y=tmp.y;
val=tmp.val;
/* There is no point using boards at greater depth than DEPTHLIM */
if(tmp.lvl > DEPTHLIM) continue;
/* Push the valid boards into the queue */
for(int i=0;i<4;i++){
nx=x+dx[i];
ny=y+dy[i];
if(isgood(x,y,nx,ny,val,tmp1.val,tmp1.cost)){
tmp1.x=nx;
tmp1.y=ny;
tmp1.lvl=tmp.lvl + 1;
tmp1.idx=last++;
tmp1.cost=tmp1.cost+tmp.cost;
tmp1.tcost=COEFF1*tmp1.cost + COEFF2*tmp1.lvl;
bt[last-1]=tmp.idx;
ct[last-1]=dir[i];
if(tmp1.val==TARGET){
backfind(last-1);
goto fail;
}
if(tmp1.lvl>DEPTHLIM) continue;
pq.push(tmp1);
}
}
}
fail:
//cout <<notimes<<endl;
if(notimes>HASHSIZE) return 0;
return 1;
}
/* Just a structure to see if the board is solvable
* otherwise it is not used. It
* just checks for feasibility of the board
*/
struct cell
{
int arr[MAX][MAX], u, v, lvl;
int cc;
ull hash;
};
cell target;
int parityh(int x,int y){
if(x&1) return 1;
return 0;
}
int paritya(int arr[MAX][MAX]){
int i,j,x,y,p,q;
int lc=0;
for(i=0;i<(MAX)*(MAX);i++){
x=i/MAX;
y=i%MAX;
if(arr[x][y]==(DELIM)) continue;
for(j=i+1;j<MAX*MAX;j++){
p=j/MAX;
q=j%MAX;
if(arr[p][q]==(DELIM)) continue;
if(arr[x][y]> arr[p][q]) lc++;
}
}
return lc &1;
}
int
main ()
{
int i, j;
for (i = 0; i < MAX; i++)
for (j = 0; j < MAX; j++)
target.arr[i][j] = (i) * MAX + j + 1;
target.u = target.v = MAX - 1;
target.arr[target.u][target.v] = DELIM;
int no=1;
cin >> no;
while (no--)
{
cell c;
ull num=0;
/* Encode the input value into a number */
for (i = 0; i < MAX; i++)
for (j = 0; j < MAX; j++)
{
int z = -1;
scanf (" %d", &z);
if (z == 0)
{
c.u = i;
c.v = j;
c.arr[i][j] = DELIM;
z=DELIM;
}
else
c.arr[i][j] = z;
num=num*BASE + z;
}
/* Parity is even the board is not solvable */
int k=paritya(c.arr) + parityh(c.u,c.v);
if((k&1)==0){ cout <<"This puzzle is not solvable."<<endl; continue; }
ss1.clear();
if(!astar(num,c.u,c.v)){
;
}
cout <<endl;
}
}
The second test case is quite good because it doesn't depend of the order of direction in which you expand where as the second one does.
2
6 2 8 4
12 14 1 10
13 15 3 9
11 0 5 7
6 8 4 2
12 14 1 10
13 15 3 9
11 0 5 7
uzioriluzan wrote:Hi, how can I use this information? I've implemented A* with the Manhattan Distance heuristic and it still gives time limit.
Your help is welcome
Regards!
Ivan Golubev wrote:Read description for problem 652.Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing `x' tile, of course).
LittleJohn wrote:Hi, uzioriluzan:
You would like this web page: "http://mathworld.wolfram.com/15Puzzle.html".
By the way, could you briefly introduce the heuristic method to me?
Thanks in advance.
I solved with IDA* with Manhattan distance as heuristic function. My runtime is 2.762Observer wrote:The heuristic function for 10181 is very famous. It has something to due with the "manhattan distances" of tiles...DJWS wrote:But it still exists a problem -- how to find suitable approximation function?
I have no idea to find the approximation function in 10181 and 10422.
Google search please...
Using f = g + h, where h is manhattan distance accepted in 1.3 sec.tryit1 wrote: ↑Sat Dec 06, 2008 2:26 pmThe second test case is quite good because it doesn't depend of the order of direction in which you expand where as the second one does.
2
6 2 8 4
12 14 1 10
13 15 3 9
11 0 5 7
6 8 4 2
12 14 1 10
13 15 3 9
11 0 5 7
My AC solution passes the first one but fails the second one but there are solutions for both of them within 50 moves.The uvatoolkit soln passes both.
The current testcases depend on the direction vectors and the coefficients very much.
I used 5*manhattandistance + 3*level , and the ordering of direction as RULD in order. It gets AC < 1 s whereas other direction order are giving problems.
Code: Select all
UURULDLDRURDDLLUUURRDLDRRDLLLURRURDLULLDRRURDLDR
RRULLDLURURRDDLURDLLURUULDLURRRDLLURRDLLLDRRRULDDRUsing f = g + h, where h is manhattan distance accepted in 1.3 sec.tryit1 wrote: ↑Sat Dec 06, 2008 2:26 pmThe second test case is quite good because it doesn't depend of the order of direction in which you expand where as the second one does.
2
6 2 8 4
12 14 1 10
13 15 3 9
11 0 5 7
6 8 4 2
12 14 1 10
13 15 3 9
11 0 5 7
My AC solution passes the first one but fails the second one but there are solutions for both of them within 50 moves.The uvatoolkit soln passes both.
The current testcases depend on the direction vectors and the coefficients very much.
I used 5*manhattandistance + 3*level , and the ordering of direction as RULD in order. It gets AC < 1 s whereas other direction order are giving problems.
Code: Select all
UURULDLDRURDDLLUUURRDLDRRDLLLURRURDLULLDRRURDLDR
RRULLDLURURRDDLURDLLURUULDLURRRDLLURRDLLLDRRRULDDR