CODEWITHSUNDEEP
javamultithreadingalgorithm
themaestro
themaestro

Reputation: 14256

Multithread Solver for N-Puzzle Problem

As a homework assignment in my current CS course, we've been instructed to write a program that implements an A* algorithm for the n-puzzle problem. In order to solve, you must take in an initial nxn board configuration from StdIn. The catch is some of the boards may not be solvable. Thankfully for us, if you create a "twin" board by flipping any two non-zero squares and attempt to solve that, either the original or the twin must be solvable. Therefore, in order to implement the algorithm we are effectively trying to solve two boards at the same time, the original and the twin.

Doing this in a single-thread was quite easy and that's what the actual assignment is. Looking at this problem, it seems like this is a perfect place to utilize parallelism. I was thinking that from the main thread I would try to spawn two concurrent threads each trying to solve their own board. Is this possible to do without too much crazy code in java? For that matter, on a multicore chip would this run significantly faster than the non-multithread version? I am trying to read through the java documentation for threads but it's a little thick for somebody who has never tried this before and for that matter, I find I learn much more quickly by writing/looking at examples than reading more documentation.

Could somebody please give me some sample code that shows the type structures, class, important statements, ect. that would be necessary to do this? So far I'm thinking that I want to implement a private class the implements runnable and having the main thread throw an interrupt to which ever thread does not finish first to figure out which one is solvable plus the number of moves and sequence of boards to get there.

EDIT: TL;DR THIS IS NOT PART OF THE GRADED ASSIGNMENT. The assignment was to do a single threaded implementation. For my own enrichment and SOLELY my own enrichment I want to try and make my implementation multithreaded.

Upvotes: 2

Views: 1665

Answers (2)

Dialecticus
Dialecticus

Reputation: 16761

Forget about solving two boards, with one of them being unsolvable. I don't see how is that even useful, but ignoring that, parallelization should not stop at two processors. If system has more of those then algorithm should use them all. BTW, checking if the board is solvable is rather easy. Check out the section Solvability in Wikipedia article.

To parallelize things your implementation of A* should have some kind of priority queue that sorts items by heuristic value. Expansion of a node in search tree involves removing node from the top of the queue, and inserting several nodes back in the queue, keeping the queue sorted. When things are organized like this then adding more threads to insert and remove stuff is rather simple. Just make the access to the queue synchronized.

Upvotes: 0

Voo
Voo

Reputation: 30216

Since you don't want the implementation yourself threaded (which is arguably a lot more complex; the transposition table is the bottleneck for parallel A* implementations - but in praxis parallel IDA* algorithms are easier to implement anyhow and have the usual advantages) the problem is actually really quite simple.

Just pack your implementation in a runnable Class and use a thread. For simplicity you can just use a global volatile boolean variable that is initialized to false and set to true as soon as one thread has found the solution. You now just check the flag at apropriate situations in your code and return if the other thread has already found a solution. You could also use interrupts but keeping it simple can't harm (and in the end it's actually quite similar anyhow, you'd just check the variable a bit fancier).

Trivial example:

public class Main implements Runnable {
    private static volatile boolean finished = false;

    public static void main(String[] args) {
        new Thread(new Main()).start();
        new Main().run();
    }

    @Override
    public void run() {
        while (!finished) {
            // do stuff
            if (solutionFound) {
                finished = true;
                // save result
            }
        }
        return;
    }

}

Upvotes: 3

Related Questions