algorithm - solution to standard puzzle -

algorithm - solution to standard puzzle -

there board in there m*m boxes each assigned non 0 integer except 1 box marked 0 , treated vacant .only vertical , horizontal neighbors of vacant box can move towards leaving place vacant.to solve puzzle have arrange boxes in increasing order of value vacant box(box marked 0 ) coming @ end(lower right corner of board).but other engineers lazy , wants solve in minimum number of steps.

so approach should follow except backtracking.

m of order 500.. ie 500x500 board.

you can find goal state sorting array. allow goal state g simple inefficient algorithm solve puzzle be:

void solve() { if(current_state == g) return; foreach(choice c in shifting_choices) { // shift neighbour apply choice; solve(); undo choice; } }

in above algorithm choices moving blocks surrounded zeroth block.

to improve algorithm can utilize a* (best first). in order find best selection can utilize manhattan distance. steps required reach 1 block within puzzle. consider below:

6 2 1 5 0 3 4 7 8

in above situation, move 2, 5, 3, 7 find best move consider goal state:

8 7 6 5 4 3 2 1 0

when move block zeroth block changing position of 2 blocks. calculate sum of manhattan distance of these 2 blocks position within goal state. selection within to the lowest degree sum preferable:

moving 2: 2 + 3 = 5 moving 3: 1 + 1 = 2 moving 7: 1 + 1 = 2 moving 5: 1 + 2 = 3

you can break tie between 3 , 7 checking previous positions, 3 @ right place hence 7 makes locally optimal choice.

algorithm puzzle