scala - Solve n-queens puzzle with akka -

i relatively new programming scala , akka , tried write solution n-queens problem using akka actors. unfortunately idea didn't work well: took way longer compute solutions compared sequential method , program never terminates. right solutions printed console. here's code:

  case class work(list: list[point])   case class reply(list: list[point])    class queenworker(val master: actorref) extends actor {         override def prestart() = {       println("new worker")     }     def receive = {       case work(list) =>         val len = list.length         if (len < size) {           val actors = (             <- 0 until size if (!list.exists(_.y == i))           ) yield (context.actorof(props(new queenworker(master))), i)           actors.foreach { case (actor, pos) => actor ! work(list :+ (new point(len, pos))) }     } else {           if (check(list)) { //check() checks whether solution valid             master ! reply(list)             println("solution found!")           }           //else sender ! reply(list[list[point]]())         }          //context.stop(self) //when have use it?          //println("worker stopped - len "+len)     }   }    class queenmaster extends actor {     override def prestart() = {       println("prestart")       context.actorof(props(new queenworker(self))) ! work(list[point]())     }        def receive = {//print solution console       case reply(list) =>         (x <- 0 until size) {           (y <- 0 until size) {             if (list.exists(p => p.x == x && p.y == y)) print("x ") else print("o ")           }           println()         }         println()     }   }   def runparallel {     val system = actorsystem("queensystem")     val queenmaster = system.actorof(props[queenmaster])   } 

my intention create new actor every new backtracking iteration. if actor has found valid solution send master prints console.

• the program never terminates. however, if remove comments around //context.stop(self) no solutions found @ all. how can fix issue?
• my whole approach seems wrong. better one?
• would possible find parallel solution using futures instead of actors?

thanks in advance!

after bit of tweaking managed run program , obtain results size=8. debugging purposes add these 2 lines in runparallel:

readline() system.shutdown() 

when program finishes - press enter - cause shutdown method invoked , program exit.

i'm running on 8-core i7 2.2ghz machine - results may vary.

regarding performance, pretty inefficient solution , here why: @ each step in backtracking process - each tried partial solution - creating , actor , doing simple loop creates more actors next proposed solutions.

now, creating actor in akka pretty fast dare in case overhead of creating actor bigger (probably order of magnitude, even) actual work doing - haven't tested this, it's likely.

the number of analysed partial solutions here exponential in size of board. creating exponential number of actors - lot of overhead , lose advantage gained computing solutions in parallel.

how can make better ? well, one, can create few less actors.

lets create fixed pool of queenworker actors (the same number number of cores have in computer), , place them behind smallesmailboxrouter.

when workers check current solution in processed work message instead of creating new actors send new proposed solutions router, , router dispatch these new work messages routees, in uniform fashion.

a worker actor process lot more partial solutions , not one, did until now. that's better actual_work/akka_housekeeping ratio before.

can better ? think can, if model problem bit differently. in queens problem, , in general, in backtracking exploring tree of partial solutions. @ each step in algorithm when generate more partial solutions existing ones branching tree. problem approach when branching in algorithm branching in concurrency flow - i'm referring here fact sending new work message processed actor. fine, if add numbers you'll see lot of overhead won't gain time advantage.

that because granularity of work tasks small. doing little work between sending messages - , affects performance. can make workers explore larger chunk of partial solutions before generating new work messages.

for example, if have 8-core cpu, , problem has size=8 better of creating 8 workers , giving worker k task compute solutions have queen sitting on column k in first line. each worker executes 1 work task represents 1/8 of total work - give better results.

regarding solution futures - can think program time same actor solution fixed pool of actors. encourage try since might wrong.