I'm trying to build an A* solver for a 15-square puzzle.
alt text http://i49.tinypic.com/343r8ki.jpg
The goal is to re-arrange the tiles so that they appear in their natural positions. You can only slide one tile at a time. Each possible state of the puzzle is a node in the search graph.
For the h(x) function, I am using an aggregate sum, across all tiles, of the tile's dislocation from the goal state. In the above image, the 5 is at location 0,0, and it belongs at location 1,0, therefore it contributes 1 to the h(x) function. The next tile is the 11, located at 0,1, and belongs at 2,2, therefore it contributes 3 to h(x). And so on. EDIT: I now understand this is what they call "Manhattan distance", or "taxicab distance".
I have been using a step count for g(x). In my implementation, for any node in the state graph, g is just +1 from the prior node's g.
To find successive nodes, I just examine where I can possibly move the "hole" in the puzzle. There are 3 neighbors for the puzzle state (aka node) that is displayed: the hole can move north, west, or east.
My A* search sometimes converges to a solution in 20s, sometimes 180s, and sometimes doesn't converge at all (waited 10 mins or more). I think h is reasonable. I'm wondering if I've modeled g properly. In other words, is it possible that my A* function is reaching a node in the graph via a path that is not the shortest path?
Maybe have I not waited long enough? Maybe 10 minutes is not long enough?
For a fully random arrangement, (assuming no parity problems), What is the average number of permutations an A* solution will examine? (please show the math)
I'm going to look for logic errors in my code, but in the meantime,
Any tips?
(ps: it's done in Javascript).
Also, no, this isn't CompSci homework. It's just a personal exploration thing. I'm just trying to learn Javascript.
EDIT: I've found that the run-time is highly depend upon the heuristic. I saw the 10x factor applied to the heuristic from the article someone mentioned, and it made me wonder - why 10x? Why linear? Because this is done in javascript, I could modify the code to dynamically update an html table with the node currently being considered. This allowd me to peek at the algorithm as it was progressing. With a regular taxicab distance heuristic, I watched as it failed to converge.
There were 5's and 12's in the top row, and they kept hanging around. I'd see 1,2,3,4 creep into the top row, but then they'd drop out, and other numbers would move up there. What I was hoping to see was 1,2,3,4 sort of creeping up to the top, and then staying there.
I thought to myself - this is not the way I solve this personally. Doing this manually, I solve the top row, then the 2ne row, then the 3rd and 4th rows sort of concurrently.
So I tweaked the h(x) function to more heavily weight the higher rows and the "lefter" columns. The result was that the A* converged much more quickly. It now runs in 3 minutes instead of "indefinitely". With the "peek" I talked about, I can see the smaller numbers creep up to the higher rows and stay there. Not only does this seem like the right thing, it runs much faster.
I'm in the process of trying a bunch of variations. It seems pretty clear that A* runtime is very sensitive to the heuristic. Currently the best heuristic I've found uses the summation of dislocation * ((4-i) + (4-j)) where i and j are the row and column, and dislocation is the taxicab distance.
One interesting part of the result I got: with a particular heuristic I find a path very quickly, but it is obviously not the shortest path. I think this is because I am weighting the heuristic. In one case I got a path of 178 steps in 10s. My own manual effort produce a solution in 87 moves. (much more than 10s). More investigation warranted.
So the result is I am seeing it converge must faster, and the path is definitely not the shortest. I have to think about this more.
Code:
var stop = false;
function Astar(start, goal, callback) {
// start and goal are nodes in the graph, represented by
// an array of 16 ints. The goal is: [1,2,3,...14,15,0]
// Zero represents the hole.
// callback is a method to call when finished. This runs a long time,
// therefore we need to use setTimeout() to break it up, to avoid
// the browser warning like "Stop running this script?"
// g is the actual distance traveled from initial node to current node.
// h is the heuristic estimate of distance from current to goal.
stop = false;
start.g = start.dontgo = 0;
// calcHeuristic inserts an .h member into the array
calcHeuristicDistance(start);
// start the stack with one element
var closed = []; // set of nodes already evaluated.
var open = [ start ]; // set of nodes to evaluate (start with initial node)
var iteration = function() {
if (open.length==0) {
// no more nodes. Fail.
callback(null);
return;
}
var current = open.shift(); // get highest priority node
// update the browser with a table representation of the
// node being evaluated
$("#solution").html(stateToString(current));
// check solution returns true if current == goal
if (checkSolution(current,goal)) {
// reconstructPath just records the position of the hole
// through each node
var path= reconstructPath(start,current);
callback(path);
return;
}
closed.push(current);
// get the set of neighbors. This is 3 or fewer nodes.
// (nextStates is optimized to NOT turn directly back on itself)
var neighbors = nextStates(current, goal);
for (var i=0; i<neighbors.length; i++) {
var n = neighbors[i];
// skip this one if we've already visited it
if (closed.containsNode(n)) continue;
// .g, .h, and .previous get assigned implicitly when
// calculating neighbors. n.g is nothing more than
// current.g+1 ;
// add to the open list
if (!open.containsNode(n)) {
// slot into the list, in priority order (minimum f first)
open.priorityPush(n);
n.previous = current;
}
}
if (stop) {
callback(null);
return;
}
setTimeout(iteration, 1);
};
// kick off the first iteration
iteration();
return null;
}
An A-star search will find the optimal solution by proving that all paths that have not yet been solved are incapable of being solved with fewer moves than the current solution. You aren't looking for the best solution, but the fastest solution. Therefore, you can optimize your algorithm by returning the first solution, by weighting the number of moves lower than your heuristic function, and the heuristic can return an over-estimate.
The heuristic function itself is typically best modeled by the Manhattan distance and linear conflict. Manhattan distance is well explained in other answers and in the Wikipedia article, and you seem to have a handle on it. Linear conflict adds two to the manhattan distance for each pair of blocks that would have to be swapped to reach a solution. For example, if a row contains "3 2 1 4", then the one and the three have to be swapped, and one would have to be moved to another row to do so.
Using a pattern database is an option and could help your search avoid certain dead-ends, and the memory usage of doing so for a 15-puzzle should be manageable.
Use IDA* instead of A*. You need much less memory. As a heuristics, the "Walking distance" developed by Ken'ichiro Takahashi is much more effective, though using only 25 kB of memory.
Here and here is English translation.
Yes, that's how I've heard of this problem being done. g(x) is the number of tile slides that have taken place, and h(x) is the total distance that all tiles are from their required squares. I hadn't seen anything used but this approach (the Manhattan heuristic) before today, but just found this so-called diagonal shortcut -- you might want to check it out.
What are you using for test data? If it's random, you will not be able to solve the puzzle about half the time. It is not possible to switch two tiles while keeping the rest in the same position, and so if you reach what is almost the end position but has two tiles interchanged, you can't possibly get it into the desired position, and no search algorithm can possibly terminate successfully.
In the 19th Century, American puzzlemaster Sam Loyd sold these toys with the 15 and 14 reversed, and offered a big prize for anybody who could demonstrate a solution switching the tiles (presumably other than the one I've got, a small screwdriver). In today's legal climate, I don't know if he'd have dared.
One possibility would be to try to get it into either the correct configuration or the 15-14 configuration.
I have programmed such an algorithm once (windowsApp) and I have the following experience
1) it is most fun to see the robot in action if it uses an (near) optimal solution. (For the human observer it is impossible to understand how the robot "thinks" and the transaction from chaos to order is sudden)
2) if you like to find the optimal solution your h() function must underestimate true distance. If you overestimate it you will not find the optimum.
3) The potential state-space is huge, 15!/2 (10^12). If you use a bad heuristic function your data sets will grow far beyond the size of your main-memory and every data access will require multiple disc-accesses. If this happens the execution time will be "infinite".
Maybe it will converge quicker if you shoot for intermediate goals first. For instance, only score the top and right rows. It shouldn't take very long to get those rows in place, then you can solve the remaining 3x3.
check this
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.lang.Object;
class Puzzle extends JPanel implements ActionListener
{
JButton[] b = new JButton[16];
Puzzle()
{
b[0] = new JButton("4");
b[1] = new JButton("11");
b[2] = new JButton("5");
b[3] = new JButton("9");
b[4] = new JButton("1");
b[5] = new JButton("10");
b[6] = new JButton("12");
b[7] = new JButton("13");
b[8] = new JButton("15");
b[9] = new JButton("14");
b[10] = new JButton("3");
b[11] = new JButton("2");
b[12] = new JButton("7");
b[13] = new JButton("8");
b[14] = new JButton("6");
b[15] = new JButton("");
GridLayout grid = new GridLayout(4,4);
setLayout(grid);
for(int i=0;i<16;i++)
add(b[i]);
for(int i=0;i<16;i++)
b[i].addActionListener(this);
}
public void actionPerformed(ActionEvent e)
{
/*if(e.getSource()==b[11])
{
if(b[15].getText()=="")
{
b[15].setText("");
}
}
else if(e.getSource()==b[3])
{
if(b[2].getText()=="")
{
b[2].setText("");
}
}*/
for(int i=0;i<16;i++)
{
System.out.println(e.getSource());
if(e.getSource()==b[i])
{
if(i==5 || i==6 || i==9 || i==10)
{
if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
else if(i==4 || i==8)
{
if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
else if(i==7 || i==11)
{
if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==0)
{
if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==3)
{
if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==15)
{
if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==12)
{
if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==1 || i==2)
{
if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==13 || i==14)
{
if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
}
}
}
//System.out.println(e.getActionCommand());
}
public static void main(String[] args)
{
JFrame frame = new JFrame("15-Puzzle");
//frame.setContentPane(panel);
JComponent newContentPane = new Puzzle();
//newContentPane.setOpaque(true); //content panes must be opaque
frame.setContentPane(newContentPane);
//panel.add(button);
frame.setSize(400,400);
frame.setVisible(true);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
}
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://img.manongdao.com/sparkler-677774__340.jpg', '推荐 爷、活的狠高调 的文章《questions regarding the use of A* with the 15-squa》','https://www.manongdao.com/article-583947.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}