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

[wolfsinner]

Problem #6/7 - Solving the N-Puzzle

 

So here's Problem #6 and #7 of the series. This is a two-parter, where #6 has easier test cases than #7.

I'm back, and with a vengeance. This is a problem classified as NP-Hard. However, it is so famous that there's great documentation out there for it.

The solution I wrote for this uses a very famous Artificial Intelligence search algorithm. This can be solved in many ways though, albeit many of them are very inefficient. 

I hope you guys enjoy this one, and thrive on the difficulty. Knowing how to solve this efficiently is an immensely useful skill. On to the problem!

 

Problem Description:
 

A classic problem in Computer Science is to find the answer to the following question: 

Given an initial and final setup of an N-Puzzle of size CxC (where C = sqrt(N+1)), find the minimum number of steps required to get from the initial to the final setup.

 

For example, given the following initial and final set ups of a 8-Puzzle:

 

 

A minimum of 26 steps are required to reach the final setup. Your task is to find this value.

Note that there isn't a standard "final state".

 

All of the given tests are solvable.

 
Input:
 

(You can download the zip file containing all of the input files here.)

 

The first line of the input contains an integer, C (an indicative of the size of the puzzle, CxC).

The following C lines each contain C integers, representing the initial setup of the puzzle. Each integer is separated by a space.

The next C lines each contain C integers, representing the final setup of the puzzle. Each integer is separated by a space.

 

These integers are a number in the range 0-[(CxC)-1], where 0 represents the "empty" space.

 

Input example

 

3

7 2 4

5 0 6

8 3 1

0 1 2

3 4 5

6 7 8

 
Output:

The output consists of a single integer representing the minimum amount of steps required to reach the final setup, from the initial setup.

The output must end with a line break.

 

Output example

26

 

 
How to test your solution:
To submit your output solutions you need to run your code with each of the input files provided in the zip file, and place your output in the appropriate text box.
So your program's output with input from file "input1.txt" should be placed in the "Output 1" box.
 
I recommend downloading the zip file, and using command-line input redirection to send the file contents into the standard input stream of your program, and the output into the standard output stream. In Windows, Linux or Mac OS, you would do something like:
[command to run your program] < inputN.txt > outputN.txt
You can submit your output solutions through the problem solving gateway here.
 
Final notes:

• Create your account at the gateway with the same username as the one you use at the forums.
• Include your code in spoiler tags, so that the thread isn't cluttered with code.
• If you're having trouble solving the problem, ask the community for help! You may learn a lot from them.
• Don't worry too much about efficiency if you're starting out. Solve the problem first, we'll then tell you how to improve it.
• Please don't share the output solution if you've solved the problem.
• If the problem description isn't clear, please ask for further explanation!

[wolfsinner]

The gateway page for the 15-puzzle version has a specific input/output example for that particular size. You can read it here.

[gauvinic]

Are there any specific rules the steps have to follow? I've seen some problems relatively similar, but each of them had specific rules. Or maybe I'm just missing it because I'm on mobile.

 

Edit: My guess is that you can only swap the 0 element with any adjacent element in the two dimensional array.

[fizzlesticks]

Are there any specific rules the steps have to follow? I've seen some problems relatively similar, but each of them had specific rules. Or maybe I'm just missing it because I'm on mobile.

 

Edit: My guess is that you can only swap the 0 element with any adjacent element in the two dimensional array.

You can only swap the 0 with the element to the left, right, below or above it (no diagonals.)

[fizzlesticks]

@wolfsinner Just curious, how long does your solution to problem 7 take for the first input?

[MikeD]

I looked at the picture and, even before reading anything, immediately thought "Artificial Intelligence".

And sure enough that is the exact picture that appears on the book we used in that class!

 

When I have the time I'll study that again and give the problem a go.

[wolfsinner]

@wolfsinner Just curious, how long does your solution to problem 7 take for the first input?

 

The example input takes ~2.5 seconds. Input 1 takes ~7 seconds, Input 2 takes ~14 seconds, and Input 3 takes ~5 seconds.

 

It is not a perfect solution, and could be improved significantly but it did the job. I used the A* search algorithm with the following heuristic: the sum of the Manhattan Distance of each piece from its current position to its desired position. It's a typical solution to the problem. A* is a simple algorithm that is used to solve a bunch of seemingly complex problems in acceptable time.

If you guys want to read more about it, a great book is the one @MikeD mentioned. It's called Artificial Intelligence: A Modern Approach. 

 

BTW, what solution are you going for? I've noticed you solved the C <= 3 version, but missed the 15-Puzzle one. What results are you getting for the 15-Puzzle?

 

EDIT: @gauvinic, sorry, yes, it is as fizzlesticks said.

[fizzlesticks]

BTW, what solution are you going for? I've noticed you solved the C <= 3 version, but missed the 15-Puzzle one. What results are you getting for the 15-Puzzle?

I used A* with manhattan distance but added more weight if 2 tiles are in opposite positions.

My solution worked for the problem 6 input and the problem 7 sample so besides being incredibly slow I'm not sure where the problem is.

My wrong answers are

input1 = 42, input2 = 47, input3 = 41

 

But I'm currently using a linear lookup with vector compares to find already visited nodes, so once I get rid of that I'm hoping the time goes way down.

[wolfsinner]

I used A* with manhattan distance but added more weight if 2 tiles are in opposite positions.

My solution worked for the problem 6 input and the problem 7 sample so besides being incredibly slow I'm not sure where the problem is.

My wrong answers are

input1 = 42, input2 = 47, input3 = 41

 

But I'm currently using a linear lookup with vector compares to find already visited nodes, so once I get rid of that I'm hoping the time goes way down.

 

Adding weight may make the heuristic non-admissible.

To guarantee optimal solutions, your heuristic needs to be at least admissible. A few scenarios might overestimate the cost with the addition of weight, which may lead to non-optimal solutions. The original definition of the Manhattan Distance is admissible (and consistent in this case), so it's guaranteed to find an optimal solution.

Your results are very close to the correct ones though.

[gauvinic]

@fizzlesticks  @wolfsinner  Thanks. I figured it was that, but I've never seen this specific take on problems relating to permutations. I have researched A* before, because of Problem A (http://icpc.baylor.edu/download/worldfinals/problems/icpc2014.pdf). Haven't implemented it yet, but I did find that a heuristic based on Disjoint Pattern Databases can be significantly faster than the Manhattan Distance. Probably won't get to it any time soon, though, because I have to focus on my Digital System Design project (a singing Tesla Coil!!!). Hopefully will have some reasonable amount of time to spend on these next week, or maybe during the ACM meeting this week if its the same overly simple stuff again (we have alot of freshman).

[wolfsinner]

@fizzlesticks  @wolfsinner  Thanks. I figured it was that, but I've never seen this specific take on problems relating to permutations. I have researched A* before, because of Problem A (http://icpc.baylor.edu/download/worldfinals/problems/icpc2014.pdf). Haven't implemented it yet, but I did find that a heuristic based on Disjoint Pattern Databases can be significantly faster than the Manhattan Distance. Probably won't get to it any time soon, though, because I have to focus on my Digital System Design project (a singing Tesla Coil!!!). Hopefully will have some reasonable amount of time to spend on these next week, or maybe during the ACM meeting this week if its the same overly simple stuff again (we have alot of freshman).

 

Yes, there are numerous ways to solve this, and better heuristics than the Manhattan Distance. The Manhattan Distance is actually a disjoint pattern database heuristic (albeit a very trivial one). Its main advantage is how simple it is to implement.

Awesome that you're willing to spend more time looking at more efficient ways to solve the problem. Looking forward to seeing your solution.  :lol:

[fizzlesticks]

Welp I'm stumped, everything I do keeps comin up 42.

[Nuluvius]

Welp I'm stumped, everything I do keeps comin up 42.

Well at least you found the answer to The Ultimate Question of Life, The Universe, and Everything

I don't have the time to work on this yet. Too much going on with work.

[Ciccioo]

i think that my program makes use of hyperspaces or something to move the blank tile across the board, because the sample input takes only 13 moves to solve, and it seems really convinced about it

[Maximation]

Well, for starters there will be a new problem this week. I've solved it, I'm just making some nice test cases and it should be up this weekend.

 

Yeah, is this supposed to be a starters problem?

Oh well, I will try to understand it. Are there any resources about this subject you would recommend me to check out?

[wolfsinner]

Welp I'm stumped, everything I do keeps comin up 42.

 

That is odd. Have you changed the heuristic to what I've suggested (classical Manhattan Distance)?

 

 

i think that my program makes use of hyperspaces or something to move the blank tile across the board, because the sample input takes only 13 moves to solve, and it seems really convinced about it

 

Are you using A*? Can you check what solution it tells you to solve (the moves themselves)? It's impossible to solve this in 13 steps. 

 

 

Yeah, is this supposed to be a starters problem?

Oh well, I will try to understand it. Are there any resources about this subject you would recommend me to check out?

 

Hey, I actually meant "for starters" in the sense of "first". This is not a beginner problem, it is just a regular problem like the ones we've had before, and a hard one at that.

The beginner problems should only come in mid-October because I have to change the gateway first. Are you having trouble understanding what is asked? I mentioned in an earlier post the A* algorithm isn't hard to understand, and can achieve fast results for this problem. A good book is Artificial Intelligence: A Modern Approach. There's a lot of articles and info on the internet about the A* algorithm and the N-Puzzle that can start you on the right direction.

[fizzlesticks]

That is odd. Have you changed the heuristic to what I've suggested (classical Manhattan Distance)?

Yup, it comes up with the same answer.

[Maximation]

Hey, I actually meant "for starters" in the sense of "first". This is not a beginner problem, it is just a regular problem like the ones we've had before, and a hard one at that.

The beginner problems should only come in mid-October because I have to change the gateway first. Are you having trouble understanding what is asked? I mentioned in an earlier post the A* algorithm isn't hard to understand, and can achieve fast results for this problem. A good book is Artificial Intelligence: A Modern Approach. There's a lot of articles and info on the internet about the A* algorithm and the N-Puzzle that can start you on the right direction.

 

Aha, ok. I understand what the problem is, but I have no clue yet on how to solve it. I read some articles about the N-puzzle, but I have yet to read more about A*. There are a bunch of other projects I am working on at the moment though, so I can not dedicate as much time to this problem as I would like to. I will first read up more on this and then try to solve it.

"Artificial intelligence: a modern approach" was already on my list of interesting books, but it is quite expensive. Aha, I just searched for it and found a few pdf files, maybe I can print those so I can read them, because I do not like reading books on my computer. But 1000 pages are a lot of pages, that would probably take up a considerably large amount of time, and paper. Oh well, I will read as much as I can.

Thank you.

[Ciccioo]

Are you using A*? Can you check what solution it tells you to solve (the moves themselves)? It's impossible to solve this in 13 steps. 

at the beginning i truly hoped i found a brilliant incredible standing-ovation-generating 13-moves solution

but nope, i did check it last night and altough the moves are legal, it does not reach the "goal"

tonight i can go back to work on it, i think that it's some kind of naive problem in the computation of the manchester distance

in my googling i saw that there are many famous approaches to the problem, even in terms of tweaks to the manchester distance (+2 for linear conflict?), so i feel a bit guilty that we're all on the vanilla manchester train :rolleyes:

[Ciccioo]

Welp I'm stumped, everything I do keeps comin up 42.

i think i just joined the 42 club

[fizzlesticks]

i think i just joined the 42 club

Well that makes me feel a little better.

[Ciccioo]

hah! after tryharding hard and consuming the wikipedia article, i spotted the error

 

 

Well that makes me feel a little better.

i'll report here the problem i had, in case you're interested

i didn't consider that the algorithm should be able to pass multiple times over a single node, because the first time you pass through it isn't guaranteed to be via the shortest path

 

and here is my code, this time i really had a hard time with C++, at some point i almost decided to write the program in javascript just to abandon types and weird cryptic errors

#include <iostream>#include <cmath>#include <unordered_map>#include <queue>class Map{        private:                size_t C, S;                size_t manhattanDistance = 0, currentDistance = 0;                std::vector<char> map;                std::vector<char> indexOf;                static Map* goal;                Map swapWith(size_t i, size_t j){                        Map tmp (*this);                        tmp.currentDistance++;                        tmp.map[i] = tmp.map[i + j];                        tmp.map[i + j] = 0;                        return tmp;                }                static size_t computeManhattanDistance(int a, int b, int C){                        return std::abs(a / C - b / C) + std::abs(a % C - b % C);                }        public:                size_t hash() const{                        size_t value = 0;                        for(const auto& tile: map){                                value <<= 4;                                value |= tile;                        }                        return value;                }                bool operator == (const Map& rhs) const {                        return map == rhs.map;                }                bool operator < (const Map& rhs) const {                        return getManhattanDistance() + currentDistance > rhs.getManhattanDistance() + rhs.currentDistance;                }                void 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;                        }                }                void computeIndexOf(){                        indexOf.resize(S);                        for(size_t i = 0; i < S; i++)                               indexOf[map[i]] = i;                }                void computeManhattanDistance(){                        manhattanDistance = 0;                        for(size_t i = 0; i < S; i++)                                if(map[i])                                        manhattanDistance += computeManhattanDistance(i, goal -> indexOf[map[i]], C);                }                std::vector<Map> getNextMoves(){                        size_t i;                        for(i = 0; map[i]; i++);                        std::vector<Map> v;                        if(i % C != 0)  v.push_back(swapWith(i, -1));                        if(i / C != 0)  v.push_back(swapWith(i, -C));                        if(i % C != C - 1) v.push_back(swapWith(i, +1));                        if(i / C != C - 1) v.push_back(swapWith(i, +C));                        return v;                }                void setDistance(size_t d){ currentDistance = d; }                size_t getDistance() const { return currentDistance; }                size_t getManhattanDistance() const { return manhattanDistance; }                static void setGoal(Map& g){ goal = &g; }};Map* Map::goal;namespace std{        template<>        struct hash<Map>{                size_t operator () (const Map& x) const{                        return x.hash();                }        };}class Astar{        private:                Map start, goal;                std::unordered_map<Map, size_t> visitedNodes;                std::priority_queue<Map> nodesToVisit;        public:                Astar(Map& start, Map& goal): start{start}, goal{goal} {}                ssize_t execute(){                        start.computeManhattanDistance();                        nodesToVisit.push(start);                        while(!nodesToVisit.empty()){                                Map current{nodesToVisit.top()};                                nodesToVisit.pop();                                if(current == goal)                                        return current.getDistance();                                auto nextMoves = current.getNextMoves();                                for(auto& move: nextMoves){                                        auto it = visitedNodes.find(move);                                        if(it == visitedNodes.end() || it -> second > move.getDistance()){                                                visitedNodes[move] = move.getDistance();                                                move.computeManhattanDistance();                                                nodesToVisit.push(move);                                        }                                }                        }                        return -1;                }};int main(){        size_t n;        std::cin >> n;        Map start;        start.read(std::cin, n);        Map goal;        goal.read(std::cin, n);        goal.computeIndexOf();        Map::setGoal(goal);        Astar search(start, goal);        size_t result = search.execute();        std::cout << result << std::endl;}

[fizzlesticks]

hah! after tryharding hard and consuming the wikipedia article, i spotted the error

 

 

i'll report here the problem i had, in case you're interested

i didn't consider that the algorithm should be able to pass multiple times over a single node, because the first time you pass through it isn't guaranteed to be via the shortest path

Hm well that's what happens when you make assumptions I guess, thanks.

 

Ignore the bad memory management, I gave up on that after rewriting the code like 5 times.

#include <iostream>#include <vector>#include <queue>#include <unordered_set>#include <unordered_map>#include <string>#include <limits>#include "Clock.h"using namespace std;struct Board;Board* solution = NULL;int pow(int x, int p) {	if (p == 0) 	{		return 1;	}	else if (p == 1)	{		return x;	}	return x * pow(x, p - 1);}struct Board{	static int size;	Board* parent;	vector<Board*> children;	short f;	short numMoves;	string hash;	Board(int s, vector<char> sq, Board* p = NULL, bool isSolution = false)	: parent(p), f(0), numMoves(0), hash(sq.begin(),sq.end())	{		if (isSolution)		{			solution = this;		}		if(equals(solution))		{			f = 0;		}		else		{			for(int x=0;x<size;++x)			{				for(int y=0;y<size;++y)				{					int ind = y * size + x;					int n = hash[ind];					if(n==0)					{						continue;					}										int pos = solution->getPosition(n);					int col = pos % size;					int row = pos / size;					if(x < col)					{						f += col - x;					}					else					{						f += x - col;					}					if(y < row)					{						f += row - y;					}					else					{						f += y - row;					}					if (solution->hash[row * size + col] == n)					{						f += 1;					}				} 			}		}	}	~Board()	{	}	void updateChildren()	{		for(auto& c : children)		{			c->numMoves = numMoves + 1;			c->updateChildren();		}	}	int getPosition(int n)	{		for(int i=0;i<size*size;++i)		{			if (hash[i] == n)			{				return i;			}		}		return -1;	}	vector<Board*> getMoves()	{		int zero = getPosition(0);		int col = zero % size;		int row = zero / size;		if(col > 0)		{			vector<char> nsq(hash.begin(),hash.end());			int tmp = nsq[zero];			nsq[zero] = nsq[zero-1];			nsq[zero-1] = tmp;			children.push_back(new Board(size, nsq, this, false)); 		}		if (col < size - 1)		{			vector<char> nsq(hash.begin(), hash.end());			int tmp = nsq[zero];			nsq[zero] = nsq[zero + 1];			nsq[zero + 1] = tmp;			children.push_back(new Board(size, nsq, this, false));		}		if (row > 0)		{			vector<char> nsq(hash.begin(), hash.end());			int tmp = nsq[zero];			nsq[zero] = nsq[zero - size];			nsq[zero - size] = tmp;			children.push_back(new Board(size, nsq, this, false));		}		if (row < size - 1)		{			vector<char> nsq(hash.begin(), hash.end());			int tmp = nsq[zero];			nsq[zero] = nsq[zero + size];			nsq[zero + size] = tmp;			children.push_back(new Board(size, nsq, this, false));		}		return children;	}	bool equals(Board* o)	{		return hash == o->hash;	}	friend ostream& operator<<(ostream& out, const Board* b)	{		for(int x=0;x<b->size;++x)		{			for (int y = 0; y<b->size; ++y)			{				cout << (int)b->hash[x * b->size + y] << '\t';			}			cout << endl;		}		return out;	}};int Board::size = 0;struct cmpBoardGreater{	bool operator()(const Board* lhs, const Board* rhs)	{		return lhs->f > rhs->f;	}};int main(){	FE::Clock clock;	clock.update();	int size;	vector<char> iBoardV;	vector<char> sBoardV;	cin >> size;	Board::size = size;	for (int i = 0; i<size*size; ++i)	{		int s;		cin >> s;		iBoardV.push_back((char)s);	}	for (int i = 0; i<size*size; ++i)	{		int s;		cin >> s;		sBoardV.push_back((char)s);	}	Board* sBoard = new Board(size,sBoardV,NULL,true);	Board* iBoard = new Board(size,iBoardV,NULL,false);	priority_queue<Board*, vector<Board*>, cmpBoardGreater> open;	open.push(iBoard);	unordered_map<string,Board*> used = {{iBoard->hash, iBoard}};	string last = iBoard->hash;		while(!open.empty())	{		Board* cur = open.top();		open.pop();		if(cur->equals(sBoard))		{			cout << cur->numMoves << endl;			break;		}		vector<Board*> moves = cur->getMoves();		for(auto& m : moves)		{						if (last != m->hash)			{				unordered_map<string,Board*>::iterator it = used.find(m->hash);				if(it == used.end())				{					m->parent = cur;					m->numMoves = cur->numMoves + 1;					m->f += m->numMoves;					if (m->equals(solution))					{						m->f = 0;					}					open.push(m);					used[m->hash] = m;				}				else				{					Board* b = it->second;					if(cur->numMoves + 1 < b->numMoves)					{						b->parent = cur;						b->f -= b->numMoves;						b->numMoves = cur->numMoves + 1;						b->f += b->numMoves;                                                b->updateChildren();					} 					delete m;				}			}			else			{				delete m;			}		}		last = cur->hash;	}		delete sBoard;	while (!open.empty())	{		Board* b = open.top();		open.pop();		delete b;	}	cout << clock.update() << endl;	return 0;}

[wolfsinner]

Awesome, good job guys.  :lol:

 

I'd share my code, but I took it out of some code I wrote for an AI class I monitored a few years ago (don't judge me). It is very generic for any problem definition and any graph search algorithm, so for you guys to understand it I'd have to share about 12-15 files of code, which is too much.

[Ciccioo]

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