UGH! (for 15 puzzle)

After two whole weeks of working on the script and tweaking it, using a random-puzzle generator to see whether it can work with any puzzle thrown at it, there's constantly a little hang up with one part of it, which when I would fix it, it would break for another puzzle. All that work and all that trial-and-error, and now I can't enter.

Good luck to all those who got a script to work properly for this contest.

:[
me too, you are not alone

I think we may organize an "off"-contest for all those who, like us, have not finished their dev. yet

Moreover, since we'll have the winner code, it'll be easier for us to get the perfect one :p

It took me a while, but I got one to handle random puzzles... It was relatively fast too...

My only downside was # of moves - I simply could not get less than 95 moves on the one that everyone else insisted they could do in 81...

I guess I was using the wrong approach with my alogorithm

It is vital to understand the problem before attempting to solve it.

I spent three days in research and thinking.
Then two hours coding and two hours commenting, refining and testing.

If you mean this puzzle:
3 11 7 2 14 1 6 9 5 10 4 15 13 12 x 8
... I solved it with 71 moves.

I see that sample puzzle.txt file is now different than before ...
There were 2 sample puzzles, now there are 6 of them.
It's a pitty that such a test puzzle file was not there before ...

Folks,

If you're going to compare puzzle solutions, please don't pick one or two puzzles, and compare how you do on those. That doesn't really tell you much at all about how your approach handles all possible puzzles, it just tells you how it handles those particular puzzles. A puzzle solver can do well in a few cases, and bad generally, or well generally but bad in specific cases. It's virtually impossible to tell which applies from the results for a single puzzle.

For example, my approach did better in one of the cases people discussed, and worse in the other case (and not just 1 or 2 moves better & worse either!). So, this doesn't really tell you a lot, other than that there's more than one way to skin a cat! And to the person who took 95 moves, you should have entered. Really. Mine took 99 moves on that, and 112 moves on the "x 15 14 13... etc" one. In a previous version it took 71 moves on that, and 144 on the "x 15 14 13... etc" one.

If you actually want to be scientific about it though, then I'd suggest running your puzzle solver overnight with a large number of truly random puzzles (e.g. I used 3000). Then compare the results for that (e.g. number of puzzles solved, average number of moves, worst case moves, best case moves, average time taken, worst case time, best case time, the kind of machine used, and so forth), and then you're closer to comparing apples with apples. Below is a command-line script that generates random puzzles that is useful for this.

Only after doing this was it possible for me to tell which approach I considered better.

Cheers,
Nick.

=================================================

#!/usr/bin/php -q
<?php

/* generates puzzles for testing
* 3000 puzzles is a good number to generate to leave running overnight
*/

// report any errors at all
error_reporting (E_ALL | E_NOTICE);

// shuffle an array, required because inbuilt PHP shuffles aren't statistically random at all.
function my_shuffle(&$array) {
$array = array_values($array); // strip out the indeces
mt_srand((double)microtime()*1000000);
for ($j=count($array)-1; $j>0; $j--) {
if (($i = mt_rand(0,$j))<$j) {
$swp=$array[$i];
$array[$i]=$array[$j];
$array[$j]=$swp;
}
}
}

// determine whether something is a valid integer
function valid_int($id) {
if (strval(intval($id)) === $id) return true;
else return false;
}

// -- Global code starts here --

// check we have the right # of args
if ($argc != 2) {
print "Incorrect number of arguments - need to specifiy a number of puzzles to generaten";
print "Usage: ./generate-puzzles.php 200 > puzzle.txtn";
exit();
}


// check the num_puzzles is valid
if (!valid_int($argv[1])) {
print "passed arg "$argv[1]" was not a numbern";
exit();
}

// passed these args on the command line
$num_puzzles = $argv[1];

if ($num_puzzles < 1 || $num_puzzles > 10000) {
print "number of puzzles must be between 1 and 10000 inclusiven";
exit();

}

// pieces in the 4 x 4 puzzle
$pieces = array(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,'x');

for ($i=0;$i<$num_puzzles;$i++) {
my_shuffle($pieces);
$first = true;
foreach($pieces as $piece) {
if ($first) {
$first = false;
}
else {
print " ";
}
print $piece;
}
print "n";
}

?>

Good idea. How about we all use the same 3000 puzzles. That way we can actually compare...

I've created a file using the script posted above. Grab it at www.phazer.dk/puzzle.txt and post summary here.

- Solveable puzzles
- Total number of moves
- Total time consumption

I'll post my results as soon as I have them.

My results of the above:

Solveable puzzles: 1,503
Total number of moves: 113,636
Total time consumption: 43 secs

PS: I did the 15 14 13.... in 104 moves.

My results for the above:

# proccessed 3000
# solved 1503
moves to solve (1503 puzzles) 113606
Total time spent proccessing boards 30.572 sec
Time spent solving (1503 puzzles) 15.322 sec
Time spent rejecting 1497 boards 15.25 sec


Mind you it's harder to compare time as it depends on what you run the script on, and exactly how you time the script.
The above results were from a Sun Netra X1 (400Mhz UltraSparcII). The timings were generated with the following code:
$time_start = microtime();
// ************ SOLVE THE PUZZLE *************
$ans = Solve($board);
// *******************************************
$time_stop = microtime();

so parsing the file, printing the answer or rendering HTML was not counted.

Zilvester

PS, it shows how subtle differences in algorithms can be (and how hard Matt's job will be in deciding a winner). Looking at Annucas results, there is only (an average of) 0.02 moves per puzzle difference between us.

I used a similar method of calculating time spent. Tested on a Dual P2-400 running linux.

My results:

Running code took 2857 sec.
MOVES: sum=120676, max=115, min=28, avg=80.29
No of puzzless: solved=1503, can not solve=0 unsolvable=1497

It seems your average is 75 moves
per puzzle. I'am interested in methods you
were using...
to solve puzzle in 0.01 sec with 75 moves in average is impressive.
Does your program use any db file?
OK... I will wait for Matt
to see it in the FTP.

I used dba database files. I could have gotten better results by increasing my solution from 1.3 Mb to 10 Mb, but I didn't.

Check it out here: www.phazer.dk/15.tar.bz2

That was me, and I did enter I just thought there was no way could I win. Who knows...

Here is my entry:
http://www.bearca.com/linux/puzzle15/

And here are the results using the 3000 for those who care... (Run on a Celeron 600 running Windows)

Using fast algorithm:
Parsed puzzle file in 5.3669699430466 seconds.
Solved with an average of 0.08609469250838 seconds and 132.07833333333 moves per puzzle.
Overall time 266.10979092121 seconds
Number of unsolvable puzzles: 1497
Number of solvable puzzles: 1503

Using least moves algorithm:
Still running... (will post)