10181 - 15-Puzzle Problem

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

masta_lu
New poster
Posts: 3
Joined: Sun May 14, 2006 11:01 pm

Post by masta_lu »

Testcases are of course also welcome.
My algorithmus seems to be ok, I modificated the puzzle from the problem definition by "moving" randomly.
But it is sooooooooooo slow:

Solution: LDDRRUURULLLDRRDLLDRRRUUULLLDRDRDR
22.66 real 21.67 user 0.17 sys

Solution: RULLDLDDRRULLDRRRUUULLLDRRRULLLDRDRDR
440.39 real 379.77 user 2.16 sys

as you can see, i just made the solution 2 moves longer.... this is frustrating :(

I tried to find more information about IDA*... it seems that IDA* is not faster but just needs less memory.... ?_?

masta_lu
New poster
Posts: 3
Joined: Sun May 14, 2006 11:01 pm

Post by masta_lu »

I realize I sort of only talk to myself but this problem really goes on my nerves and I still hope someone can give me a hint!
I found out why I get TLE, my programm did not solve the a problem instance where every tile already is in place :oops: .
I again modified my code and now I get MLE... :(
I will post the full code here and hope someone can point out a mistake. I am really not so much interested in performance, I'd be totally happy with 44,99999999 secounds running time... I just want to get it over with :( ;)

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;
}
When I try for example a puzzle where the solution is 50 moves long the programm runs quite fast but needs a lot of memory... and I don't see why... since basically I use DFS with the extension that the state with smalles f(n) = g(n) + h(n) is expanded and the start depth is h( start_state )... so I think that for every call of idaS there is basically one state in memory and the states are "deleted" before idaS returns there should only be, for example, 55 states in memory "at the same time" when idaS goes down to depth 55... when idaS goes back up the states are deleted...
There must something I don't see... can someone help me please???

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

IDA*

Post by wanderley2k »

I was reading and trying solve this problem with tricks that were posted in this list. But I only recive TLE.

I implemented IDA*.

This is my code:

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;
}
Thanks

gradientcurl
New poster
Posts: 16
Joined: Mon Jun 26, 2006 9:33 am
Contact:

heuristic function

Post by gradientcurl »

i guess you need to augment your manhatten heuristic with linear conflict. it will speed up a lot

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 10181 - 15-Puzzle Problem

Post by tryit1 »

i implemented A*. Its quite fast if i change the DEPTHLIM but the problem asks for not more than 50 moves. I either given WA or TLE. I get TLE when i increase the size of priority_queue other wise WA. Can someone give me testcases.

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;
    }
}


tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 10181 - 15-Puzzle Problem

Post by tryit1 »


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


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.
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.

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re:

Post by lighted »

I got acc. :lol: :lol: :lol:

Posts below helped me
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? :wink:
Thanks in advance.
Observer wrote:
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.
The heuristic function for 10181 is very famous. It has something to due with the "manhattan distances" of tiles...
Google search please...
I solved with IDA* with Manhattan distance as heuristic function. My runtime is 2.762
I implemented pseudocode that written here http://en.wikipedia.org/wiki/IDA*

f(n) = g(n) + h(n),

where g(n) is number of moves we made from initaial state to current state
h(n) is manhattan distance of current state and final state.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10181 - 15-Puzzle Problem

Post by lighted »

tryit1 wrote:
Sat Dec 06, 2008 2:26 pm

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


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.
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.
Using f = g + h, where h is manhattan distance accepted in 1.3 sec.
It passes 2 tests above.

Code: Select all

UURULDLDRURDDLLUUURRDLDRRDLLLURRURDLULLDRRURDLDR
RRULLDLURURRDDLURDLLURUULDLURRRDLLURRDLLLDRRRULDDR
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10181 - 15-Puzzle Problem

Post by lighted »

tryit1 wrote:
Sat Dec 06, 2008 2:26 pm

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


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.
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.
Using f = g + h, where h is manhattan distance accepted in 1.3 sec.
My output for 2 tests above.

Code: Select all

UURULDLDRURDDLLUUURRDLDRRDLLLURRURDLULLDRRURDLDR
RRULLDLURURRDDLURDLLURUULDLURRRDLLURRDLLLDRRRULDDR
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 101 (10100-10199)”