652 - Eight

[junjieliang]

Hi,

Can you describe how you do it by IDA*? Mine gets a TLE... even though it should be faster than BFS. Is there a way to "prune" the search like in A* where you don't repeat states?

Thanks.

[Adil]

hello. my approach with IDA* was following:

Code: Select all

1. calculate the minimum moves required (MIN) to reach the goal-state, using the "manhattan" heuristic.
2. starting searching with S as the initial state
3. for a state S
     let N = number of moves from the starting state to reach S
         M = number of minimum moves required to reach goal-state from S (using the "manhattan" heuristic, again)
  3.1. if N > MIN then goto step 4.
  3.2. if N + M > MIN then goto step 4.
  3.3. consider the states that can be reached from S using one move, and see if that state has already been reached. if not then expand the search.
4. if the solution was not found in 3.3, then increase MIN and continue with step 3.

but of course, before all this, check if the puzzle is at all solvable. (you can have a look at the link given by LittleJohn).

hope i was clear enough, and hope this helps.

[Observer]

..

[Observer]

Latest news! See this page:

http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:652

Now, ZERO submission is accepted. I reckon that there must be some flaws in the new judging data. Admins please have a look into it. Thank you.

Or, has the output requirement changed..??

[Observer]

You know what? The adminz realize the problem and they're rejudging all the submissions again!! Everything's back to normal~~

Now you can really ignore this topic lu~~~

[plamplam]

Beware this problem contains unnecessary blanks in between inputs. Be sure to handle them properly. I used something like while gets() and checked for a valid character, if so then break and continue to the next case.

[tzupengwang]

Can anyone help?
I applied the A* algorithm but got TLE. I've seen someone AC with pure BFS, which should be much slower.
Can anyone give me suggestions to speed up my program, or is there some tricky parts in the I/O?

thanks!!

Code: Select all

/*652*/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 5000000

typedef vector<int> vi;
typedef vector<char> vc;
typedef pair<int,vi> ii;
typedef pair<ii,vc> iii;
vi in;
vi anss;
int factor[10]={1,1,2,6,24,120,720,5040,40320,362880};
int manhatton[10][10];
int h[MAXN];
bool vis[MAXN];
int dis[MAXN];

priority_queue<iii,vector<iii>,greater<iii> >pq;

int abs(int k)
{
    if (k>0)return k;
    else return -k;
}
void MANHATTON()
{
    for (int i=0;i<3;i++)
    {
        for (int j=0;j<3;j++)
        {
            for (int k=0;k<3;k++)
            {
                for (int l=0;l<3;l++)
                {
                    manhatton[i*3+j+1][k*3+l+1]=manhatton[k*3+l+1][i*3+j+1]=abs(i-k)+abs(j-l);
                }
            }
        }
    }
}
int hash(vi s)
{
    int ret=0;
    for (int i=0;i<9;i++)
    {
    //printf("1\n");
        int temp=0;
        for (int j=i+1;j<9;j++)
        {
            if (s[i]>s[j])temp++;
        }
        ret+=temp*factor[8-i];
    }
    return ret;
}
int tot_MANHATTON(vi s)
{
    int ret=0;
    for (int i=0;i<9;i++)
    {
        if (s[i]==9)continue;
        ret+=manhatton[i+1][s[i]];
    }
    return ret;
}
vc Astar()
{
    while (!pq.empty())pq.pop();
    //int count=0;

    memset(vis,false,sizeof vis);

    int ind=hash(in);
    dis[ind]=0;
    h[ind]=tot_MANHATTON(in);
    vc nn;
    pq.push(iii(ii(h[ind],in),nn));
    vis[ind]=true;
    while (!pq.empty())
    {
        //count++;
        //if (count>50)break;

        iii front=pq.top();
        pq.pop();
        vi str=front.first.second;
        vc ansstr=front.second;
        int now=hash(str);
        if (now==hash(anss))return ansstr;
        int nine;
        for (int i=0;i<9;i++)
        {
            if (str[i]==9)nine=i;
        }
        if (nine>2)
        {
            swap(str[nine],str[nine-3]);
            ansstr.push_back('u');
            int index=hash(str);
            if (vis[index]==false)
            {
                vis[index]=true;
                dis[index]=dis[now]+1;
                h[index]=tot_MANHATTON(str);
                pq.push(iii(ii(h[index]+dis[index],str),ansstr));
            }
            ansstr.pop_back();
            swap(str[nine],str[nine-3]);
        }
        if (nine<6)
        {
            swap(str[nine],str[nine+3]);
            ansstr.push_back('d');
            int index=hash(str);
            if (vis[index]==false)
            {
                vis[index]=true;
                dis[index]=dis[now]+1;
                h[index]=tot_MANHATTON(str);
                pq.push(iii(ii(h[index]+dis[index],str),ansstr));
            }
            ansstr.pop_back();
            swap(str[nine],str[nine+3]);
        }
        if (nine%3!=0)
        {
            swap(str[nine],str[nine-1]);
            ansstr.push_back('l');
            int index=hash(str);
            if (vis[index]==false)
            {
                vis[index]=true;
                dis[index]=dis[now]+1;
                h[index]=tot_MANHATTON(str);
                pq.push(iii(ii(h[index]+dis[index],str),ansstr));
            }
            ansstr.pop_back();
            swap(str[nine],str[nine-1]);
        }
        if (nine%3!=2)
        {
            swap(str[nine],str[nine+1]);
            ansstr.push_back('r');
            int index=hash(str);
            if (vis[index]==false)
            {
                vis[index]=true;
                dis[index]=dis[now]+1;
                h[index]=tot_MANHATTON(str);
                pq.push(iii(ii(h[index]+dis[index],str),ansstr));
            }
            ansstr.pop_back();
            swap(str[nine],str[nine+1]);
        }
    }
}
bool unsolvable()
{
    int k=0;
    for (int i=0;i<9;i++)
    {
        if (in[i]==9)continue;
        for (int j=i+1;j<9;j++)
        {
            if (in[j]==9)continue;
            if (in[i]>in[j])k++;
        }
    }
    if (k%2==1)return true;
    return false;
}
int main()
{
    //freopen("in.txt","r",stdin);

    for (int i=0;i<9;i++)anss.push_back(i+1);
    MANHATTON();
    int amm;
    bool first=true;
    scanf("%d",&amm);
    while (amm--)
    {

        in.clear();
        char s[5];
        for (int i=0;i<9;i++)
        {
            scanf("%s",s);
            if (s[0]=='x')in.push_back(9);
            else in.push_back(s[0]-'0');
        }

        if (unsolvable())
        {
            puts("unsolvable");
            first=false;
            continue;
        }
        vc ans=Astar();
        if (first)first=false;
        else puts("");
        for (int i=0;i<ans.size();i++)
            printf("%c",ans[i]);
        puts("");
    }
    return 0;
}

[brianfry713]

I got AC in 1.228 sec using BFS. Precompute all reachable states from the solution, store them into a map with the reverse path taken.