[Problem Solving #6/7] Solving the N-Puzzle

[gauvinic]

update: as an alternative to the Pattern DB solution i found another heuristic function (Walking Distance) that should be much more accurate than the manhattan distance, and that makes use of a lookup table of around 25k elements for a 15-puzzle

 

the problem is that the euristhic was invented by a japanese guy who cannot speak english. i found something, but i'm having a hard time wrapping my head around it, so i'll leave some links here for now, go to sleep and try again tomorrow

 

have fun reading the japanese article, eventually translated with google translator. if it's not clear enough, here you have the C source code and a picture that shows how the Walking Distance heuristics works

 

 

Well now I have to use 78 pattern database. If you want another (perhaps easier to read) link for WD, here it is: http://juropollo.xe0.ru/stp_wd4x4_en.htm

 

Also, I found a program that shows the difference between some heuristics and databases: http://kociemba.org/fifteen/fifteensolver.html

 

And finally, for anyone interested: http://heuristicswiki.wikispaces.com/file/view/Searching%20with%20pattern%20database%20%28Culberson%20%26%20Schaeffer%201996%29.pdf/92790472/Searching%20with%20pattern%20database%20%28Culberson%20%26%20Schaeffer%201996%29.pdf

 

I'm not gonna get time this weekend to work on the problems, because I have tests to study for, a resume to write, and work. Next week I should have time. I'm just not sure how I'll find info on the 78 pattern database. None of the CS professors at my school had heard of it, and a little time spent on Google seemed fruitless.

[Ciccioo]

Well now I have to use 78 pattern database. If you want another (perhaps easier to read) link for WD, here it is: http://juropollo.xe0.ru/stp_wd4x4_en.htm

oh, thanks! something i can actually understand!

[Avratz]

My IDA* implementation doesn't appear to ever find a solution for the 3x3 puzzles  :huh:

 

SECTION "NPUZZLE"GET "utils"GET "utils.b"MANIFEST{   board   = 0    childs  = 1    nchild  = 2    hash    = 3    cost    = 4        nodeupb        found   = maxint-1}STATIC{   s.SZ    s.SZ2    s.node.start    s.node.end    s.atree        s.f    s.fpH    s.result        s.dbgNode    s.dbgIter}LET start() = VALOF{   s.fpH := taxicab    //s.fpH := ham    //s.fpH := mixit        do_file("npdata\input1.txt", "npdata\o1.txt")    //do_file("npdata\input2.txt", "npdata\o2.txt")    //do_file("npdata\input3.txt", "npdata\o3.txt")    //do_file("npdata\input4.txt", "npdata\o4.txt")        RESULTIS 0}AND do_file(inf, outf) BE{   init(inf)        s.dbgIter := 0        start_timer()    ida.star(s.node.start, s.node.end)    stop_timer()        writef("*n %s took %n ms *n", inf, get_time_taken_ms())        set_outfile(outf)    writef("solution: %n", s.result)    cls_outfile()        delnode(s.node.start)    delnode(s.node.end)}AND init(fname) BE{   LET i = ?    IF NOT set_infile(fname) RETURN        s.SZ    := readn()    s.SZ2   := s.SZ * s.SZ        s.node.start   := alnode()    s.node.end     := alnode()        s.node.start!hash   := hash.djb2(s.node.start!board,s.SZ2)    s.node.end!hash     := hash.djb2(s.node.end!board,  s.SZ2)        FOR i = 0 TO s.SZ2-1 DO    s.node.start!board!i   := readn()    FOR i = 0 TO s.SZ2-1 DO    s.node.end!board!i     := readn()    cls_infile()}AND alnode() = VALOF{   LET node = ?        node        := getvec(nodeupb)    node!board  := getvec(s.SZ2)    node!childs := 0    node!nchild := 0    node!hash   := 0    node!cost   := 0        RESULTIS    node}AND delnode(node) BE{   freevec(node!board)    freevec(node)}AND mktree(root) = VALOF{   LET troot = alnode()        cpyb(troot, root)    troot!hash := root!hash    RESULTIS troot}AND deltree(root) BE{   IF root!nchild > 0 DO        {   LET i = 0        FOR i = 0 TO root!nchild-1 DO deltree(root!childs!i)    }    delnode(root)}AND chkdup(r, h) = VALOF{   LET i = ?    IF r!hash = h RESULTIS TRUE        FOR i = 0 TO r!nchild-1 DO    {   IF r!childs!i!nchild > 0 RESULTIS chkdup(r!childs!i, h)    }        RESULTIS FALSE}AND expand(node) BE{   LET zx, zy, idx = ?, ?, ?    LET i, c, n     = 0, 0, ?        LET zdx = idxOf(node!board, 0)    LET t   = VEC 4        zx := b.row(zdx)    zy := b.col(zdx)        IF valid_move(zx-1, zy) DO    {   idx := ((zx-1) * s.SZ) + zy;        n   := alnode()        cpyb(n, node)        swap(@n!board!idx, @n!board!zdx)        n!hash := hash.djb2(n!board, s.SZ2)         TEST NOT chkdup(s.atree, n!hash)        THEN    { t!c := n; c := c + 1 }        ELSE    delnode(n)    }        IF valid_move(zx+1, zy) DO    {   idx := ((zx+1) * s.SZ) + zy;        n   := alnode()        cpyb(n, node)        swap(@n!board!idx, @n!board!zdx)        n!hash := hash.djb2(n!board, s.SZ2)        TEST NOT chkdup(s.atree, n!hash)        THEN    { t!c := n; c := c + 1 }        ELSE    delnode(n)    }        IF valid_move(zx, zy-1) DO    {   idx := (zx * s.SZ) + (zy-1);        n   := alnode()        cpyb(n, node)        swap(@n!board!idx, @n!board!zdx)        n!hash := hash.djb2(n!board, s.SZ2)        TEST NOT chkdup(s.atree, n!hash)        THEN    { t!c := n; c := c + 1 }        ELSE    delnode(n)    }        IF valid_move(zx, zy+1) DO    {   idx := (zx * s.SZ) + (zy+1);        n   := alnode()        cpyb(n, node)        swap(@n!board!idx, @n!board!zdx)        n!hash := hash.djb2(n!board, s.SZ2)        TEST NOT chkdup(s.atree, n!hash)        THEN    { t!c := n; c := c + 1 }        ELSE    delnode(n)    }        s.dbgNode := s.dbgNode + c        node!nchild := c    node!childs := getvec(c)    FOR i = 0 TO c-1 DO node!childs!i := t!i}AND cpyb(to, from) BE{   LET i = ?    FOR i = 0 TO s.SZ2-1 DO to!board!i := from!board!i}AND cmpnode(a, b) = VALOF{   LET i = ?    FOR i = 0 TO s.SZ2-1 IF a!board!i ~= b!board!i RESULTIS FALSE        RESULTIS TRUE}AND ida.star(root, goal) = VALOF{       LET is_goal(node) = node!hash = s.node.end!hash -> TRUE, FALSE    //LET is_goal(node) = cmpnode(node, s.node.end)        LET dfs.contour(n, g, b) = VALOF    {   LET min, i, t = ?, ?, ?        s.f := g + s.fpH(n, s.node.end)               IF s.f > b      RESULTIS s.f        IF is_goal(n)   DO {s.result := n!cost; RESULTIS found}                    min := maxint        expand(n)        FOR i = 0 TO n!nchild-1 DO        {   n!childs!i!cost := n!cost + 1            t := dfs.contour(n!childs!i, g + n!childs!i!cost, b)            IF t = found RESULTIS found                IF t < min DO min := t        }        RESULTIS min    }        LET bound   = s.fpH(root, goal)    LET t       = ?        {   s.atree     := mktree(s.node.start)          s.dbgNode   := 1        t           := dfs.contour(s.atree, 0, bound)        deltree(s.atree)        IF t = found    RESULTIS found        IF t = maxint   RESULTIS ~found        bound := t                s.dbgIter := s.dbgIter + 1        writef("*nIteration [%n] Bound [%n] Nodes [%n]...", s.dbgIter, bound, s.dbgNode)            }   REPEAT        RESULTIS 0}AND b.row(pos) = pos / s.SZAND b.col(pos) = pos MOD s.SZAND idxOf(b, c) = VALOF{   LET i = ?    FOR i = 0 TO s.SZ2-1 IF b!i = c RESULTIS i}AND swap(to, from) BE{   LET t = !to    !to     := !from    !from   := t}AND valid_move(x, y) = x >= 0 & x < s.SZ & y >= 0 & y < s.SZ -> TRUE, FALSE AND taxicab(n, e) = VALOF{   LET m, i = 0, ?        FOR i = 0 TO s.SZ2-1 DO    {   LET nx, ny, ex, ey = ?, ?, ?, ?                nx := b.row(idxOf(n!board, i))        ny := b.col(idxOf(n!board, i))                ex := b.row(idxOf(e!board, i))        ey := b.col(idxOf(e!board, i))                m := m + (ABS(ex - nx) + ABS(ey - ny))    }    RESULTIS m }AND ham(n, e) = VALOF{   LET h, i = 0, ?    FOR i = 0 TO s.SZ2-1 IF n!board!i ~= e!board!i DO h := h + 1    RESULTIS h}AND mixit(n, e) = taxicab(n, e) + ham(n, e)AND hash.djb2(b, l) = VALOF{   LET h = 5381    LET i = ?    FOR i = 0 TO l-1 DO h := ((h << 5) + h) + b!i    RESULTIS h} 

[Ciccioo]

i spent the last two nights getting this PDB implementation to work, and now that it's done, it's slower that my manhattan distance

even if i use the PDB  as a cached manhattan distance, it's still slower than my manhattan distance

and it's a memory hog

the amount of disappointment in my head is very noticeable right now, but i'll go back on it and find out what the hell is wrong

 

 

 

 

 

 

also, the forum doesn't like the empty lines in my code and this time around it's too much effort to insert them manually, so i'll leave it as is

#ifndef HEADERS_H#define HEADERS_H#include <unordered_map>#include <queue>class Pattern;class Map{        private:                size_t C, S;                size_t heuristicDistance = 0, currentDistance = 0;                std::vector<char> map;                std::vector<char> indexOf;                Map swap(size_t i, size_t j) const;        public:                size_t hash() const;                bool operator == (const Map& rhs) const;                bool operator < (const Map& rhs) const;                void read(std::istream& in, size_t n);                void computeIndexOf();                size_t getIndexOf(char tile) const;                char getTile(size_t i) const;                void computeHeuristicDistance(std::vector<Pattern>& patterns);                void keepOnly(std::vector<size_t> v);                std::vector<Map> getNextMoves() const;                std::vector<Map> getNextMoves(char tileToSwap) const;                void setDistance(size_t d);                size_t getDistance() const;                size_t getHeuristicDistance() const;};class Pattern{        private:                static std::vector<Pattern> patterns;                std::vector<char> members;                std::unordered_map<unsigned int, unsigned char> DB;                unsigned int hash(const Map&) const;                void precompute(Map);        public:                Pattern(Map goal, std::vector<size_t> positions);                size_t getDistance(const Map& node) const;                static std::vector<Pattern>& getAllPatterns();                static void addPattern(Pattern p);};#endif

#include <iostream>#include <algorithm>#include "headers.h"Map Map::swap(size_t i, size_t j) const {        Map newNode (*this);        newNode.currentDistance++;        char tmp = map[i];        newNode.map[i] = newNode.map[j];        newNode.indexOf[newNode.map[j]] = i;        newNode.map[j] = tmp;        newNode.indexOf[tmp] = j;        return newNode;}size_t Map::hash() const{        size_t value = 0;        for(const auto tile: map){                value <<= 4;                value |= tile;        }        return value;}bool Map::operator == (const Map& rhs) const {        return map == rhs.map;}bool Map::operator < (const Map& rhs) const {        return getHeuristicDistance() + currentDistance > rhs.getHeuristicDistance() + rhs.currentDistance;}void Map::read(std::istream& in, size_t n){        C = n;        S = C * C;        map.resize(S);        for(auto& tile: map){                int tmp;                in >> tmp;                tile = tmp;        }               computeIndexOf();}void Map::computeIndexOf(){        indexOf.resize(S);        for(size_t i = 0; i < S; i++)                indexOf[map[i]] = i;}void Map::computeHeuristicDistance(std::vector<Pattern>& patterns){        heuristicDistance = 0;        for(auto& pattern: patterns)                heuristicDistance += pattern.getDistance(*this);}void Map::keepOnly(std::vector<size_t> v){        std::sort(v.begin(), v.end());        size_t i, j;        for(i = 0, j = 0; i < map.size() && j < v.size(); i++)                if(i != v[j])                        map[i] = 0;                else                        j++;        while(i < map.size()) map[i++] = 0;}std::vector<Map> Map::getNextMoves() const { return getNextMoves(0); }std::vector<Map> Map::getNextMoves(char tileToSwap) const {        size_t i;        for(i = 0; map[i] != tileToSwap; i++);        std::vector<Map> v;        if(i % C != 0 && map[i] * map[i - 1] == 0)          v.push_back(swap(i, i - 1));        if(i / C != 0 && map[i] * map[i - C] == 0)          v.push_back(swap(i, i - C));        if(i % C != C - 1 && map[i] * map[i + 1] == 0)      v.push_back(swap(i, i + 1));        if(i / C != C - 1 && map[i] * map[i + C] == 0)      v.push_back(swap(i, i + C));        return v;}size_t Map::getIndexOf(char tile) const { return indexOf[tile]; }char Map::getTile(size_t i) const { return map[i]; }size_t Map::getDistance() const { return currentDistance; }size_t Map::getHeuristicDistance() const { return heuristicDistance; }

#include <algorithm>#include "headers.h"std::vector<Pattern> Pattern::patterns;Pattern::Pattern(Map goal, std::vector<size_t> positions){        for(auto position: positions)                if(goal.getTile(position))                        members.push_back(goal.getTile(position));        if(members.size()){                goal.keepOnly(positions);                precompute(goal);        }}void Pattern::precompute(Map goal){        std::deque<Map> queue;        queue.push_back(goal);        DB[hash(goal)] = 0;        while(!queue.empty()){                Map& currentNode = queue.front();                for(auto tile: members){                        auto nextNodes = currentNode.getNextMoves(tile);                        for(const auto& nextNode: nextNodes){                                size_t currentHash = hash(nextNode);                                if(DB.find(currentHash) != DB.end()) continue;                                queue.push_back(nextNode);                                DB[currentHash] = nextNode.getDistance();                        }                }                queue.pop_front();        }}unsigned int Pattern::hash(const Map& m) const {        unsigned int hash = 0;        for(auto tile: members)                hash = (hash << 4) | m.getIndexOf(tile);        return hash;}size_t Pattern::getDistance(const Map& node) const {        return  DB.find(hash(node)) -> second;}std::vector<Pattern>& Pattern::getAllPatterns(){ return patterns; }void Pattern::addPattern(Pattern p){        if(p.members.size())                patterns.push_back(p);}

#include <iostream>#include "headers.h"class Astar{        private:                Map start, goal;                std::unordered_map<size_t, unsigned char> visitedNodes;                std::priority_queue<Map> nodesToVisit;        public:                Astar(Map& start, Map& goal): start{start}, goal{goal} {                        start.computeHeuristicDistance(Pattern::getAllPatterns());                        nodesToVisit.push(start);                }                ssize_t execute(){                        while(!nodesToVisit.empty()){                                Map current{nodesToVisit.top()};                                nodesToVisit.pop();                                if(current == goal)                                        return current.getDistance();                                auto nextMoves = current.getNextMoves();                                for(auto& move: nextMoves){                                        size_t currentHash = move.hash();                                        auto it = visitedNodes.find(currentHash);                                        if(it == visitedNodes.end() || it -> second > move.getDistance()){                                                visitedNodes[currentHash] = move.getDistance();                                                move.computeHeuristicDistance(Pattern::getAllPatterns());                                                nodesToVisit.push(move);                                        }                                }                        }                        return -1;                }};int main(){        size_t n;        std::cin >> n;        Map start, goal;        start.read(std::cin, n);        goal.read(std::cin, n);/*      manhattan distance        for(size_t i = 0; i < n * n; i++)                Pattern::addPattern({goal, std::vector<size_t>{i}});*/        if(n == 4){//                Pattern::addPattern({goal, std::vector<size_t>{0, 1, 4, 5, 6, 8, 9, 12}});//                Pattern::addPattern({goal, std::vector<size_t>{2, 3, 7, 10, 11, 13, 15}});                Pattern::addPattern({goal, std::vector<size_t>{0, 1, 2, 4, 5}});                Pattern::addPattern({goal, std::vector<size_t>{3, 6, 7, 10, 11}});                Pattern::addPattern({goal, std::vector<size_t>{8, 9, 12, 13, 14, 15}});/*                Pattern::addPattern({goal, std::vector<size_t>{0, 1, 2, 4}});                Pattern::addPattern({goal, std::vector<size_t>{3, 7, 11, 6}});                Pattern::addPattern({goal, std::vector<size_t>{5, 8, 9, 12}});                Pattern::addPattern({goal, std::vector<size_t>{10, 13, 14, 15}});*/        }        if(n == 3){                Pattern::addPattern({goal, std::vector<size_t>{0, 1, 2}});                Pattern::addPattern({goal, std::vector<size_t>{3, 4, 5}});                Pattern::addPattern({goal, std::vector<size_t>{6, 7, 8}});        }        if(n == 2){                Pattern::addPattern({goal, std::vector<size_t>{0, 1}});                Pattern::addPattern({goal, std::vector<size_t>{2, 3}});        }        Astar search(start, goal);        size_t result = search.execute();        std::cout << result << std::endl;}

[Avratz]

Translated my code to C fixing a couple bugs in the process. Still can't figure out why it never finds a solution. Runs a lot faster now though 

 

I feel like I'm overlooking something really simple.

 

#include <stdio.h>#include <stdlib.h>#include <time.h>#include <limits.h>#include <string.h>#define found UINT_MAX-1#define notfnd UINT_MAX-2#define _DEBUG#undef  _DEBUG#define _CHKDUP#undef  _CHKDUPtypedef enum {FALSE = 0, TRUE = -1} BOOL;struct Node{    size_t*         board;    struct Node**   childs;    size_t          nchild;    size_t          hash;    size_t          cost;} ;typedef struct Node Node_t;size_t  g_SZ,        g_SZ2,        g_f,        g_dbgNode,        g_dbgIter,        g_result;Node_t* g_atree,      * g_start,      * g_end;size_t  (*fpH)(const Node_t*, const Node_t*);size_t  taxicab     (const Node_t* n, const Node_t* e);size_t  ham         (const Node_t* n, const Node_t* e);size_t  mixit       (const Node_t* n, const Node_t* e);void    init        (const char* fname);void    do_file     (const char* inf, const char* outf);Node_t* alnode      (void);void    delnode     (Node_t* node);Node_t* mktree      (const Node_t* root);void    deltree     (Node_t* root);BOOL    chkdup      (const Node_t* r, const size_t h);void    expand      (Node_t* node);void    cpyb        (Node_t* to, const Node_t* from);BOOL    cmpnode     (const Node_t* a, const Node_t* b);size_t  ida_star    (const Node_t* root, const Node_t* goal);size_t  dfs_contour (Node_t* n, const size_t g, const size_t b);size_t  b_row       (const size_t pos);size_t  b_col       (const size_t pos);int     idxOf       (const size_t* b, const size_t c);void    swap        (size_t* to, size_t* from);BOOL    valid_move  (const int x, const int y);BOOL    is_goal     (const Node_t* n);size_t  hash_djb2   (const size_t* b, const size_t l);void    start_timer (void);void    stop_timer  (void);size_t  get_time_taken_ms(void);float   get_time_taken_sec(void);void    ndump       (Node_t* n);intmain(void){    fpH = &taxicab;    //fpH = &ham;    //fpH = &mixit;    do_file("npdata\\input1.txt", "npdata\\o1.txt");    do_file("npdata\\input2.txt", "npdata\\o2.txt");    do_file("npdata\\input3.txt", "npdata\\o3.txt");    do_file("npdata\\input4.txt", "npdata\\o4.txt");    return 0;}voiddo_file(const char* inf, const char* outf){    init(inf);    g_dbgIter = 0;    start_timer();    ida_star(g_start, g_end);    stop_timer();    printf("\n %s took %f ms", inf, get_time_taken_sec());    FILE* ofp;    if((ofp = fopen(outf, "w")) == 0)    {        printf("\nCouldn't open file. result = %d\n", g_result);    }    else    {        fprintf(ofp, "result = %d", g_result);        fclose(ofp);    }    delnode(g_start);    delnode(g_end);}voidinit(const char* fname){    FILE* fp;    if((fp = fopen(fname, "r")) == 0)        return;    char* p;    char buf[64];    fgets(buf, 64, fp);    g_SZ = strtol(buf, &p, 10);    g_SZ2 = g_SZ * g_SZ;    g_start = alnode();    g_end   = alnode();    int i, j;    for(i = 0; i < g_SZ; i++)    {        size_t n;        memset(buf, 0, 64);        fgets(buf, 64, fp);        p = buf;        for(j = 0; j < g_SZ; j++)        {            n = strtol(p, &p, 10);            g_start->board[j + i * g_SZ] = n;        }    }    for(i = 0; i < g_SZ; i++)    {        size_t n;        memset(buf, 0, 64);        fgets(buf, 64, fp);        p = buf;        for(j = 0; j < g_SZ; j++)        {            n = strtol(p, &p, 10);            g_end->board[j + i * g_SZ] = n;        }    }    g_start->hash   = hash_djb2(g_start->board, g_SZ2);    g_end->hash     = hash_djb2(g_end->board, g_SZ2);    ndump(g_start);    ndump(g_end);    fclose(fp);}Node_t*alnode(void){    Node_t* node;    node            = malloc(sizeof(Node_t));    node->board     = malloc(sizeof(*node->board) * g_SZ2);    node->childs    = NULL;    node->nchild    = 0;    node->hash      = 0;    node->cost      = 0;    return node;}voiddelnode(Node_t* node){    free(node->board);    free(node->childs);    free(node);}Node_t*mktree(const Node_t* root){    Node_t* node = alnode();    cpyb(node, root);    node->hash = root->hash;    return node;}voiddeltree(Node_t* root){    if(root->nchild > 0)    {        size_t i = 0;        for(; i < root->nchild; i++)            deltree(root->childs[i]);    }    delnode(root);}//slowBOOLchkdup(const Node_t* r, const size_t h){#ifdef _CHKDUP    if(r->hash == h)        return TRUE;    if(r->nchild > 0)    {        size_t i = 0;        for(; i < r->nchild; i++)        {            chkdup(r->childs[i], h);        }    }#endif    return FALSE;}voidexpand(Node_t* node){    size_t zx, zy, idx;    size_t c = 0;    size_t zdx = idxOf(node->board, 0);    Node_t* t[4];    Node_t* n;    zx = b_row(zdx);    zy = b_col(zdx);    if(valid_move(zx-1, zy))    {        idx = (zx-1) * g_SZ + zy;        n = alnode();        cpyb(n, node);        swap(&n->board[idx], &n->board[zdx]);        n->hash = hash_djb2(n->board, g_SZ2);        if(!chkdup(g_atree, n->hash))            t[c++] = n;        else            delnode(n);    }    if(valid_move(zx+1, zy))    {        idx = (zx+1) * g_SZ + zy;        n = alnode();        cpyb(n, node);        swap(&n->board[idx], &n->board[zdx]);        n->hash = hash_djb2(n->board, g_SZ2);        if(!chkdup(g_atree, n->hash))            t[c++] = n;        else            delnode(n);    }    if(valid_move(zx, zy-1))    {        idx = zx * g_SZ + (zy-1);        n = alnode();        cpyb(n, node);        swap(&n->board[idx], &n->board[zdx]);        n->hash = hash_djb2(n->board, g_SZ2);        if(!chkdup(g_atree, n->hash))            t[c++] = n;        else            delnode(n);    }    if(valid_move(zx, zy+1))    {        idx = zx * g_SZ + (zy+1);        n = alnode();        cpyb(n, node);        swap(&n->board[idx], &n->board[zdx]);        n->hash = hash_djb2(n->board, g_SZ2);        if(!chkdup(g_atree, n->hash))            t[c++] = n;        else            delnode(n);    }    g_dbgNode += c;    node->childs = malloc(sizeof(node->childs) * c);    node->nchild = c;    int i = 0;    for(; i < c; i++)    {        node->childs[i] = t[i];        ndump(node->childs[i]);    }}voidcpyb(Node_t* to, const Node_t* from){    size_t i = 0;    for(; i < g_SZ2; i++)        to->board[i] = from->board[i];}BOOLcmpnode(const Node_t* a, const Node_t* b){    size_t i = 0;    for(; i < g_SZ2; i++)        if(a->board[i] != b->board[i])            return FALSE;    return TRUE;}size_tida_star(const Node_t* root, const Node_t* goal){    size_t bound    = fpH(root, goal);    size_t t        = 0;    while(TRUE)    {        g_atree     = mktree(g_start);        g_dbgNode   = 1;        t           = dfs_contour(g_atree, 0, bound);        deltree(g_atree);        if(t == found)            return found;        if(t == notfnd)            return notfnd;        bound = t;        g_dbgIter++;        printf("\nIteration [%d] Bound [%d] Nodes [%d]...", g_dbgIter, bound, g_dbgNode);    }}size_tdfs_contour(Node_t* n, const size_t g, const size_t b){    size_t min, i = 0, t;    g_f = g + fpH(n, g_end);    if(g_f > b)        return g_f;    if(is_goal(n))    {        g_result = n->cost;        return found;    }    min = UINT_MAX;    expand(n);    for(; i < n->nchild; i++)    {        n->childs[i]->cost = n->cost + 1;        t = dfs_contour(n->childs[i], g + n->childs[i]->cost, b);        if(t == found)            return found;        if(t < min)            min = t;    }    return min;}BOOLis_goal(const Node_t* n){    return cmpnode(n, g_end);//n->hash == g_end->hash ? TRUE : FALSE;}size_tb_row(const size_t pos){    return pos / g_SZ;}size_tb_col(const size_t pos){    return pos % g_SZ;}intidxOf(const size_t* b, const size_t c){    int i = 0;    for(; i < g_SZ2; i++)        if(b[i] == c)            return i;    return -1;}voidswap(size_t* to, size_t* from){    size_t t = *to;    *to = *from;    *from = t;}BOOLvalid_move(const int x, const int y){    return x >= 0 && x < g_SZ && y >= 0 && y < g_SZ ? TRUE : FALSE;}size_ttaxicab(const Node_t* n, const Node_t* e){    size_t m = 0, i = 0;    for(; i < g_SZ2; i++)    {        size_t nx, ny, ex, ey;        nx = b_row(idxOf(n->board, i));        ny = b_col(idxOf(n->board, i));        ex = b_row(idxOf(e->board, i));        ey = b_col(idxOf(e->board, i));        m += (abs(ex - nx) + abs(ey - ny));    }    return m;}size_tham(const Node_t* n, const Node_t* e){    size_t h = 0, i = 0;    for(; i < g_SZ2; i++)        if(n->board[i] != e->board[i])            h++;    return h;}size_tmixit(const Node_t* n, const Node_t* e){    return taxicab(n, e) + ham(n, e);}clock_t g_start_time;clock_t g_stop_time;voidstart_timer(void){    g_start_time = clock();}voidstop_timer(void){    g_stop_time = clock();}size_tget_time_taken_ms(void){    return g_stop_time - g_start_time;}floatget_time_taken_sec(void){    return ((float)(g_stop_time - g_start_time)) / CLOCKS_PER_SEC;}size_thash_djb2(const size_t* b, const size_t l){    size_t h = 5381;    size_t i = 0;    for(; i < l; i++)        h = ((h << 5) + h) + b[i];    return h;}voidndump(Node_t* n){#ifdef _DEBUG    printf("\n*******************************\n\NODE PTR    %d\n\NODE HASH   %x\n\NODE COST   %d\n\NODE NCHILD %d\n\NODE BOARD  ", n, n->hash, n->cost, n->nchild);    int i = 0;    for(; i < g_SZ2; i++)        printf("%d ", n->board[i]);    puts("\n*******************************");#endif}

[Ciccioo]

Translated my code to C fixing a couple bugs in the process. Still can't figure out why it never finds a solution. Runs a lot faster now though 

 

I feel like I'm overlooking something really simple.

i think it's just performance: it took a few seconds to solve a 14-moves problem, and it did solve input3.txt (16 moves), but it took 2 minutes and 8 secs, and more than 3 gigs of ram

edit: "benchmarks" ran with -O3

 

anyway, i still didn't get 100% how IDA* works, but i know for sure that it should be very efficient on memory, so your implementation must have some problem in the traversal function that makes it so expensive on memory

[Avratz]

Wow, I made a stupid mistake.

 

For my g cost I was adding g + <total node cost> not the cost to get to that node for the dfs_contour call. It should be a constant g + 1 in this case.

 

Now it works 

 

BCPL code

SECTION "NPUZZLE"GET "utils"GET "utils.b"MANIFEST{   board   = 0    childs  = 1    nchild  = 2    hash    = 3    cost    = 4        nodeupb        found   = maxint-1}STATIC{   s.SZ    s.SZ2    s.node.start    s.node.end    s.atree        s.f    s.fpH    s.result        s.dbgNode    s.dbgIter}LET start() = VALOF{   s.fpH := taxicab    //s.fpH := ham    //s.fpH := mixit        do_file("npdata\input1.txt", "npdata\o1.txt")    do_file("npdata\input2.txt", "npdata\o2.txt")    do_file("npdata\input3.txt", "npdata\o3.txt")    do_file("npdata\input4.txt", "npdata\o4.txt")        RESULTIS 0}AND do_file(inf, outf) BE{   init(inf)        s.dbgIter := 0        start_timer()    ida.star(s.node.start, s.node.end)    stop_timer()        writef("*n %s took %n ms *n", inf, get_time_taken_ms())        set_outfile(outf)    writef("solution: %n", s.result)    cls_outfile()        delnode(s.node.start)    delnode(s.node.end)}AND init(fname) BE{   LET i = ?    IF NOT set_infile(fname) RETURN        s.SZ    := readn()    s.SZ2   := s.SZ * s.SZ        s.node.start   := alnode()    s.node.end     := alnode()        FOR i = 0 TO s.SZ2-1 DO    s.node.start!board!i   := readn()    FOR i = 0 TO s.SZ2-1 DO    s.node.end!board!i     := readn()    s.node.start!hash   := hash.djb2(s.node.start!board,s.SZ2)    s.node.end!hash     := hash.djb2(s.node.end!board,  s.SZ2)        cls_infile()}AND alnode() = VALOF{   LET node = ?        node        := getvec(nodeupb)    node!board  := getvec(s.SZ2)    node!childs := 0    node!nchild := 0    node!hash   := 0    node!cost   := 0        RESULTIS    node}AND delnode(node) BE{   freevec(node!board)    freevec(node!childs)    freevec(node)}AND mktree(root) = VALOF{   LET troot = alnode()        cpyb(troot, root)    troot!hash := root!hash    RESULTIS troot}AND deltree(root) BE{   IF root!nchild > 0 DO        {   LET i = 0        FOR i = 0 TO root!nchild-1 DO deltree(root!childs!i)    }    delnode(root)}AND chkdup(r, h) = VALOF{   LET i = ?    IF r!hash = h RESULTIS TRUE        FOR i = 0 TO r!nchild-1 DO    {   IF r!childs!i!nchild > 0 RESULTIS chkdup(r!childs!i, h)    }        RESULTIS FALSE}AND expand(node) BE{   LET zx, zy, idx = ?, ?, ?    LET i, c, n     = 0, 0, ?        LET zdx = idxOf(node!board, 0)    LET t   = VEC 4        zx := b.row(zdx)    zy := b.col(zdx)        IF valid_move(zx-1, zy) DO    {   idx := ((zx-1) * s.SZ) + zy;        n   := alnode()        cpyb(n, node)        swap(@n!board!idx, @n!board!zdx)        n!hash := hash.djb2(n!board, s.SZ2)         TEST NOT chkdup(s.atree, n!hash)        THEN    { t!c := n; c := c + 1 }        ELSE    delnode(n)    }        IF valid_move(zx+1, zy) DO    {   idx := ((zx+1) * s.SZ) + zy;        n   := alnode()        cpyb(n, node)        swap(@n!board!idx, @n!board!zdx)        n!hash := hash.djb2(n!board, s.SZ2)        TEST NOT chkdup(s.atree, n!hash)        THEN    { t!c := n; c := c + 1 }        ELSE    delnode(n)    }        IF valid_move(zx, zy-1) DO    {   idx := (zx * s.SZ) + (zy-1);        n   := alnode()        cpyb(n, node)        swap(@n!board!idx, @n!board!zdx)        n!hash := hash.djb2(n!board, s.SZ2)        TEST NOT chkdup(s.atree, n!hash)        THEN    { t!c := n; c := c + 1 }        ELSE    delnode(n)    }        IF valid_move(zx, zy+1) DO    {   idx := (zx * s.SZ) + (zy+1);        n   := alnode()        cpyb(n, node)        swap(@n!board!idx, @n!board!zdx)        n!hash := hash.djb2(n!board, s.SZ2)        TEST NOT chkdup(s.atree, n!hash)        THEN    { t!c := n; c := c + 1 }        ELSE    delnode(n)    }        s.dbgNode := s.dbgNode + c        node!nchild := c    node!childs := getvec(c)    FOR i = 0 TO c-1 DO node!childs!i := t!i}AND cpyb(to, from) BE{   LET i = ?    FOR i = 0 TO s.SZ2-1 DO to!board!i := from!board!i}AND cmpnode(a, b) = VALOF{   LET i = ?    FOR i = 0 TO s.SZ2-1 IF a!board!i ~= b!board!i RESULTIS FALSE        RESULTIS TRUE}AND ida.star(root, goal) = VALOF{       LET is_goal(node) = node!hash = s.node.end!hash -> TRUE, FALSE    //LET is_goal(node) = cmpnode(node, s.node.end)        LET dfs.contour(n, g, b) = VALOF    {   LET min, i, t = ?, ?, ?        s.f := g + s.fpH(n, s.node.end)               IF s.f > b      RESULTIS s.f        IF is_goal(n)   DO {s.result := n!cost; RESULTIS found}                    min := maxint        expand(n)        FOR i = 0 TO n!nchild-1 DO        {   n!childs!i!cost := n!cost + 1            t := dfs.contour(n!childs!i, g + 1, b)            IF t = found RESULTIS found                IF t < min DO min := t        }        RESULTIS min    }        LET bound   = s.fpH(root, goal)    LET t       = ?        {   s.atree     := mktree(s.node.start)          s.dbgNode   := 1        t           := dfs.contour(s.atree, 0, bound)        deltree(s.atree)        IF t = found    RESULTIS found        IF t = maxint   RESULTIS ~found        bound := t                s.dbgIter := s.dbgIter + 1        writef("*nIteration [%n] Bound [%n] Nodes [%n]...", s.dbgIter, bound, s.dbgNode)            }   REPEAT        RESULTIS 0}AND b.row(pos) = pos / s.SZAND b.col(pos) = pos MOD s.SZAND idxOf(b, c) = VALOF{   LET i = ?    FOR i = 0 TO s.SZ2-1 IF b!i = c RESULTIS i}AND swap(to, from) BE{   LET t = !to    !to     := !from    !from   := t}AND valid_move(x, y) = x >= 0 & x < s.SZ & y >= 0 & y < s.SZ -> TRUE, FALSE AND taxicab(n, e) = VALOF{   LET m, i = 0, ?        FOR i = 1 TO s.SZ2-1 DO    {   LET nx, ny, ex, ey = ?, ?, ?, ?                nx := b.row(idxOf(n!board, i))        ny := b.col(idxOf(n!board, i))                ex := b.row(idxOf(e!board, i))        ey := b.col(idxOf(e!board, i))                m := m + (ABS(ex - nx) + ABS(ey - ny))    }    RESULTIS m }AND ham(n, e) = VALOF{   LET h, i = 1, ?    FOR i = 0 TO s.SZ2-1 IF n!board!i ~= e!board!i DO h := h + 1    RESULTIS h}AND mixit(n, e) = taxicab(n, e) + ham(n, e)AND hash.djb2(b, l) = VALOF{   LET h = 5381    LET i = ?    FOR i = 0 TO l-1 DO h := ((h << 5) + h) + b!i    RESULTIS h} 

 

C code

#include <stdio.h>#include <stdlib.h>#include <time.h>#include <limits.h>#include <string.h>#define found UINT_MAX-1#define notfnd UINT_MAX-2#define _DEBUG#undef  _DEBUG#define _CHKDUP#undef  _CHKDUPtypedef enum {FALSE = 0, TRUE = -1} BOOL;struct Node{    size_t*         board;    struct Node**   childs;    size_t          nchild;    size_t          hash;    size_t          cost;} ;typedef struct Node Node_t;size_t  g_SZ,        g_SZ2,        g_f,        g_dbgNode,        g_dbgIter,        g_result;Node_t* g_atree,      * g_start,      * g_end;size_t  (*fpH)(const Node_t*, const Node_t*);size_t  taxicab     (const Node_t* n, const Node_t* e);size_t  ham         (const Node_t* n, const Node_t* e);size_t  mixit       (const Node_t* n, const Node_t* e);void    init        (const char* fname);void    do_file     (const char* inf, const char* outf);Node_t* alnode      (void);void    delnode     (Node_t* node);Node_t* mktree      (const Node_t* root);void    deltree     (Node_t* root);BOOL    chkdup      (const Node_t* r, const size_t h);void    expand      (Node_t* node);void    cpyb        (Node_t* to, const Node_t* from);BOOL    cmpnode     (const Node_t* a, const Node_t* b);size_t  ida_star    (const Node_t* root, const Node_t* goal);size_t  dfs_contour (Node_t* n, const size_t g, const size_t b);size_t  b_row       (const size_t pos);size_t  b_col       (const size_t pos);int     idxOf       (const size_t* b, const size_t c);void    swap        (size_t* to, size_t* from);BOOL    valid_move  (const int x, const int y);BOOL    is_goal     (const Node_t* n);size_t  hash_djb2   (const size_t* b, const size_t l);void    start_timer (void);void    stop_timer  (void);size_t  get_time_taken_ms(void);float   get_time_taken_sec(void);void    ndump       (Node_t* n);intmain(void){    fpH = &taxicab;    //fpH = &ham;    //fpH = &mixit;    //  do_file("npdata\\test.txt", "npdata\\ot.txt");    do_file("npdata\\input1.txt", "npdata\\o1.txt");    do_file("npdata\\input2.txt", "npdata\\o2.txt");    do_file("npdata\\input3.txt", "npdata\\o3.txt");    do_file("npdata\\input4.txt", "npdata\\o4.txt");    return 0;}voiddo_file(const char* inf, const char* outf){    init(inf);    g_dbgIter = 0;    start_timer();    ida_star(g_start, g_end);    stop_timer();    printf("\n %s took %f ms", inf, get_time_taken_sec());    FILE* ofp;    if((ofp = fopen(outf, "w")) == 0)    {        printf("\nCouldn't open file. result = %d\n", g_result);    }    else    {        fprintf(ofp, "result = %d", g_result);        fclose(ofp);    }    delnode(g_start);    delnode(g_end);}voidinit(const char* fname){    FILE* fp;    if((fp = fopen(fname, "r")) == 0)        return;    char* p;    char buf[64];    fgets(buf, 64, fp);    g_SZ = strtol(buf, &p, 10);    g_SZ2 = g_SZ * g_SZ;    g_start = alnode();    g_end   = alnode();    int i, j;    for(i = 0; i < g_SZ; i++)    {        size_t n;        memset(buf, 0, 64);        fgets(buf, 64, fp);        p = buf;        for(j = 0; j < g_SZ; j++)        {            n = strtol(p, &p, 10);            g_start->board[j + i * g_SZ] = n;        }    }    for(i = 0; i < g_SZ; i++)    {        size_t n;        memset(buf, 0, 64);        fgets(buf, 64, fp);        p = buf;        for(j = 0; j < g_SZ; j++)        {            n = strtol(p, &p, 10);            g_end->board[j + i * g_SZ] = n;        }    }    g_start->hash   = hash_djb2(g_start->board, g_SZ2);    g_end->hash     = hash_djb2(g_end->board, g_SZ2);    ndump(g_start);    ndump(g_end);    fclose(fp);}Node_t*alnode(void){    Node_t* node;    node            = malloc(sizeof(Node_t));    node->board     = malloc(sizeof(*node->board) * g_SZ2);    node->childs    = NULL;    node->nchild    = 0;    node->hash      = 0;    node->cost      = 0;    return node;}voiddelnode(Node_t* node){    free(node->board);    free(node->childs);    free(node);}Node_t*mktree(const Node_t* root){    Node_t* node = alnode();    cpyb(node, root);    node->hash = root->hash;    return node;}voiddeltree(Node_t* root){    if(root->nchild > 0)    {        size_t i = 0;        for(; i < root->nchild; i++)            deltree(root->childs[i]);    }    delnode(root);}//slowBOOLchkdup(const Node_t* r, const size_t h){#ifdef _CHKDUP    if(r->hash == h)        return TRUE;    if(r->nchild > 0)    {        size_t i = 0;        for(; i < r->nchild; i++)        {            chkdup(r->childs[i], h);        }    }#endif    return FALSE;}voidexpand(Node_t* node){    size_t zx, zy, idx;    size_t c = 0;    size_t zdx = idxOf(node->board, 0);    Node_t* t[4];    Node_t* n;    zx = b_row(zdx);    zy = b_col(zdx);    if(valid_move(zx-1, zy))    {        idx = (zx-1) * g_SZ + zy;        n = alnode();        cpyb(n, node);        swap(&n->board[idx], &n->board[zdx]);        n->hash = hash_djb2(n->board, g_SZ2);        if(!chkdup(g_atree, n->hash))            t[c++] = n;        else            delnode(n);    }    if(valid_move(zx+1, zy))    {        idx = (zx+1) * g_SZ + zy;        n = alnode();        cpyb(n, node);        swap(&n->board[idx], &n->board[zdx]);        n->hash = hash_djb2(n->board, g_SZ2);        if(!chkdup(g_atree, n->hash))            t[c++] = n;        else            delnode(n);    }    if(valid_move(zx, zy-1))    {        idx = zx * g_SZ + (zy-1);        n = alnode();        cpyb(n, node);        swap(&n->board[idx], &n->board[zdx]);        n->hash = hash_djb2(n->board, g_SZ2);        if(!chkdup(g_atree, n->hash))            t[c++] = n;        else            delnode(n);    }    if(valid_move(zx, zy+1))    {        idx = zx * g_SZ + (zy+1);        n = alnode();        cpyb(n, node);        swap(&n->board[idx], &n->board[zdx]);        n->hash = hash_djb2(n->board, g_SZ2);        if(!chkdup(g_atree, n->hash))            t[c++] = n;        else            delnode(n);    }    g_dbgNode += c;    node->childs = malloc(sizeof(node->childs) * c);    node->nchild = c;    int i = 0;    for(; i < c; i++)    {        node->childs[i] = t[i];        ndump(node->childs[i]);    }}voidcpyb(Node_t* to, const Node_t* from){    size_t i = 0;    for(; i < g_SZ2; i++)        to->board[i] = from->board[i];}BOOLcmpnode(const Node_t* a, const Node_t* b){    size_t i = 0;    for(; i < g_SZ2; i++)        if(a->board[i] != b->board[i])            return FALSE;    return TRUE;}size_tida_star(const Node_t* root, const Node_t* goal){    size_t bound    = fpH(root, goal);    size_t t        = 0;    while(TRUE)    {        g_atree     = mktree(g_start);        g_dbgNode   = 1;        t           = dfs_contour(g_atree, 0, bound);        deltree(g_atree);        if(t == found)            return found;        if(t == notfnd)            return notfnd;        g_dbgIter++;        printf("\nIteration [%d] Bound [%d] Nodes [%d]...", g_dbgIter, bound, g_dbgNode);        bound = t;    }}size_tdfs_contour(Node_t* n, const size_t g, const size_t b){    size_t min, i = 0, t;    g_f = g + fpH(n, g_end);    if(g_f > b)        return g_f;    if(is_goal(n))    {        g_result = n->cost;        return found;    }    min = UINT_MAX;    expand(n);    for(; i < n->nchild; i++)    {        n->childs[i]->cost = n->cost + 1;        t = dfs_contour(n->childs[i], g + 1, b);        if(t == found)            return found;        if(t < min)            min = t;    }    return min;}BOOLis_goal(const Node_t* n){    return n->hash == g_end->hash ? TRUE : FALSE;//cmpnode(n, g_end);}size_tb_row(const size_t pos){    return pos / g_SZ;}size_tb_col(const size_t pos){    return pos % g_SZ;}intidxOf(const size_t* b, const size_t c){    int i = 0;    for(; i < g_SZ2; i++)        if(b[i] == c)            return i;    return -1;}voidswap(size_t* to, size_t* from){    size_t t = *to;    *to = *from;    *from = t;}BOOLvalid_move(const int x, const int y){    return x >= 0 && x < g_SZ && y >= 0 && y < g_SZ ? TRUE : FALSE;}size_ttaxicab(const Node_t* n, const Node_t* e){    size_t m = 0, i = 1;    for(; i < g_SZ2; i++)    {        size_t nx, ny, ex, ey;        nx = b_row(idxOf(n->board, i));        ny = b_col(idxOf(n->board, i));        ex = b_row(idxOf(e->board, i));        ey = b_col(idxOf(e->board, i));        m += (abs(nx - ex) + abs(ny - ey));    }    return m;}size_tham(const Node_t* n, const Node_t* e){    size_t h = 0, i = 1;    for(; i < g_SZ2; i++)        if(n->board[i] != e->board[i])            h++;    return h;}size_tmixit(const Node_t* n, const Node_t* e){    return taxicab(n, e) + ham(n, e);}clock_t g_start_time;clock_t g_stop_time;voidstart_timer(void){    g_start_time = clock();}voidstop_timer(void){    g_stop_time = clock();}size_tget_time_taken_ms(void){    return g_stop_time - g_start_time;}floatget_time_taken_sec(void){    return ((float)(g_stop_time - g_start_time)) / CLOCKS_PER_SEC;}size_thash_djb2(const size_t* b, const size_t l){    size_t h = 5381;    size_t i = 0;    for(; i < l; i++)        h = ((h << 5) + h) + b[i];    return h;}voidndump(Node_t* n){#ifdef _DEBUG    printf("\n*******************************\n\NODE PTR    %d\n\NODE HASH   %x\n\NODE COST   %d\n\NODE NCHILD %d\n\NODE BOARD  ", n, n->hash, n->cost, n->nchild);    int i = 0;    for(; i < g_SZ2; i++)        printf("%d ", n->board[i]);    puts("\n*******************************");#endif} 

 

 

What's interesting is the difference in node counts in my C vs BCPL implementations. I guess my heuristic is slightly different? They both get correct results.

 

BCPL is way slower for sure. Yes, that's 27 minutes for the last one.

 

eta: Not checking for duplicates made the C implementation run significantly faster. input4 went from ~400 seconds to 0.278. Oddly BCPL runs slower, but the node counts match up.

 

eta2: BCPL just finished. ~94 minutes(5698395ms) for input4. Most impressive.

[Avratz]

Last solution was incapable of solving 15-puzzles due to horrible memory efficiency. Storing the entire visited tree is dumb and defeats the purpose of IDA*.

 

New solution ditches trees and allocation altogether. Not only is memory performance infinitely better, it's faster too.

 

#include <stdio.h>#include <stdlib.h>#include <time.h>#include <limits.h>#include <string.h>#include <stdint.h>#define found UINT_MAX-1#define notfnd UINT_MAX-2typedef enum {kLeft, kRight, kUp, kDown, kNone} Direction;typedef enum {FALSE = 0, TRUE = -1} BOOL;typedef uint64_t State_t;size_t  g_SZ,        g_SZ2,        g_f,        g_dbgState,        g_dbgIter,        g_result;State_t g_start,        g_end;uint8_t (*fpH)(const State_t, const State_t);uint8_t  taxicab     (const State_t n, const State_t e);uint8_t  ham         (const State_t n, const State_t e);uint8_t  mixit       (const State_t n, const State_t e);void    init        (const char* fname);void    do_file     (const char* inf, const char* outf);size_t  ida_star    (const State_t root, const State_t goal);size_t  dfs_contour (State_t n, const uint8_t g, const uint8_t b, Direction d);BOOL    valid_move  (const uint8_t x, const uint8_t y);uint8_t idx         (const State_t s, const uint8_t i);uint8_t row         (const uint8_t i);uint8_t col         (const uint8_t i);void    start_timer (void);void    stop_timer  (void);size_t  get_time_taken_ms(void);float   get_time_taken_sec(void);intmain(void){    fpH = &taxicab;    //fpH = &taxicablin;    //fpH = &ham;    //fpH = &mixit;    do_file("npdata\\input1.txt", "npdata\\o1.txt");    do_file("npdata\\input2.txt", "npdata\\o2.txt");    do_file("npdata\\input3.txt", "npdata\\o3.txt");    //do_file("npdata\\input4.txt", "npdata\\o4.txt");    return 0;}voiddo_file(const char* inf, const char* outf){    init(inf);    g_dbgIter = 0;    start_timer();    ida_star(g_start, g_end);    stop_timer();    printf("\n %s took %f seconds", inf, get_time_taken_sec());    FILE* ofp;    if((ofp = fopen(outf, "w")) == 0)    {        printf("\nCouldn't open file. result = %d\n", g_result);    }    else    {        fprintf(ofp, "result = %d", g_result);        fclose(ofp);    }}voidinit(const char* fname){    FILE* fp;    if((fp = fopen(fname, "r")) == 0)        return;    char* p;    char buf[64];    fgets(buf, 64, fp);    g_SZ    = strtol(buf, &p, 10);    g_SZ2   = g_SZ * g_SZ;    g_start = g_end = 0;    int i, j;    for(i = 0; i < g_SZ; i++)    {        State_t n;        memset(buf, 0, 64);        fgets(buf, 64, fp);        p = buf;        for(j = 0; j < g_SZ; j++)        {            n = strtol(p, &p, 10);            g_start |= n << ((j + i * g_SZ) * 4);        }    }    for(i = 0; i < g_SZ; i++)    {        State_t n;        memset(buf, 0, 64);        fgets(buf, 64, fp);        p = buf;        for(j = 0; j < g_SZ; j++)        {            n = strtol(p, &p, 10);            g_end |= n << ((j + i * g_SZ) * 4);        }    }    fclose(fp);}size_tida_star(const State_t root, const State_t goal){    uint8_t bound   = fpH(root, goal);    size_t  t       = 0;    State_t start   = root;    while(TRUE)    {        g_dbgState  = 1;        t           = dfs_contour(start, 0, bound, kNone);        g_dbgIter++;        printf("\nIteration [%d] Bound [%d] States [%d]...", g_dbgIter, bound, g_dbgState);        if(t == found)            return found;        if(t == notfnd)            return notfnd;        bound = t;    }}size_tdfs_contour(State_t st, const uint8_t g, const uint8_t b, Direction d){    size_t min, t;    g_f = g + fpH(st, g_end);    if(g_f > b)        return g_f;    if(st == g_end)    {        g_result = g;        return found;    }    min = UINT_MAX;    uint8_t zx  = col(idx(st, 0));    uint8_t zy  = row(idx(st, 0));    uint8_t idx, zdx;    State_t tmp;    uint8_t tv;    if(d != kRight && valid_move(zx-1, zy))    {        idx = ((zx-1) + zy * g_SZ) * 4;        zdx = (zx + zy * g_SZ) * 4;        tmp = st;        tv = (tmp & ((State_t)0xF<<idx)) >> idx;        tmp ^= (((State_t)tv) << idx);        tmp |= (((State_t)tv) << zdx);        g_dbgState++;        t   = dfs_contour(tmp, g + 1, b, kLeft);        if(t == found)            return found;        if(t < min)            min = t;    }    if(d != kLeft && valid_move(zx+1, zy))    {        idx = ((zx+1) + zy * g_SZ) * 4;        zdx = (zx + zy * g_SZ) * 4;        tmp = st;        tv = (tmp & ((State_t)0xF<<idx)) >> idx;        tmp ^= (((State_t)tv) << idx);        tmp |= (((State_t)tv) << zdx);        g_dbgState++;        t   = dfs_contour(tmp, g + 1, b, kRight);        if(t == found)            return found;        if(t < min)            min = t;    }    if(d != kDown && valid_move(zx, zy-1))    {        idx = (zx + (zy-1)*g_SZ) * 4;        zdx = (zx + zy*g_SZ) * 4;        tmp = st;        tv = (tmp & ((State_t)0xF<<idx)) >> idx;        tmp ^= (((State_t)tv) << idx);        tmp |= (((State_t)tv) << zdx);        g_dbgState++;        t   = dfs_contour(tmp, g + 1, b, kUp);        if(t == found)            return found;        if(t < min)            min = t;    }    if(d != kUp && valid_move(zx, zy+1))    {        idx = (zx + (zy+1) * g_SZ) * 4;        zdx = (zx + zy * g_SZ) * 4;        tmp = st;        tv = (tmp & ((State_t)0xF<<idx)) >> idx;        tmp ^= (((State_t)tv) << idx);        tmp |= (((State_t)tv) << zdx);        g_dbgState++;        t   = dfs_contour(tmp, g + 1, b, kDown);        if(t == found)            return found;        if(t < min)            min = t;    }    return min;}BOOLvalid_move(const uint8_t x, const uint8_t y){    return x >= 0 && x < g_SZ && y >= 0 && y < g_SZ ? TRUE : FALSE;}uint8_t idx(const State_t s, const uint8_t i){    uint8_t it = 0;    for(; it < g_SZ2; it++)    {        uint8_t t = (s >> (it * 4)) & 0xF;        if(t == i)            return it;    }    return -1;}uint8_t row(const uint8_t i){    return i / g_SZ;}uint8_t col(const uint8_t i){    return i % g_SZ;}uint8_ttaxicab(const State_t n, const State_t e){    uint8_t m = 0, i = 1;    for(; i < g_SZ2; i++)    {        uint8_t nx, ny, ex, ey;        nx = col(idx(n, i));        ny = row(idx(n, i));        ex = col(idx(e, i));        ey = row(idx(e, i));        m += (abs(nx - ex) + abs(ny - ey));    }    return m;}uint8_tham(const State_t n, const State_t e){    size_t h = 0, i = 1;    for(; i < g_SZ2; i++)        if( ((n>>(i*4)) & 0xF) != ((e>>(i*4)) & 0xF) )            h++;    return h;}uint8_tmixit(const State_t n, const State_t e){    return taxicab(n, e) + ham(n, e);}clock_t g_start_time;clock_t g_stop_time;voidstart_timer(void){    g_start_time = clock();}voidstop_timer(void){    g_stop_time = clock();}size_tget_time_taken_ms(void){    return g_stop_time - g_start_time;}floatget_time_taken_sec(void){    return ((float)(g_stop_time - g_start_time)) / CLOCKS_PER_SEC;} 

 

Could use a better heuristic, but performance is satisfactory.