Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie

Knight's tour

  • 24-04-2013 12:57pm
    #1
    Registered Users Posts: 11


    Hi all,
    how to implement knight's tour in parallel? this program should be organised around a family of producer/consumer worker threads. However, I am really struggling with that and cannot start with the program. Could someone give me some advises? Thank you very much!


Comments

  • Registered Users Posts: 1,922 ✭✭✭fergalr


    Hi all,
    how to implement knight's tour in parallel? this program should be organised around a family of producer/consumer worker threads. However, I am really struggling with that and cannot start with the program. Could someone give me some advises? Thank you very much!

    What do you need help with?
    The parallel bit, or the knights tour bit?
    How much can you do yourself?
    What are your current thoughts on the problem?

    You have to at least start the problem yourself.

    Have you tried implement knights tour but not in parallel? How far have you gotten with that?


  • Registered Users Posts: 11 followme_1987


    fergalr wrote: »
    What do you need help with?
    The parallel bit, or the knights tour bit?
    How much can you do yourself?
    What are your current thoughts on the problem?

    You have to at least start the problem yourself.

    Have you tried implement knights tour but not in parallel? How far have you gotten with that?

    Yes, I have implemented it in sequential. I want to implement the parallel version based on the sequential one.

    My thoughts are to create four workers threads as my laptop is four-cores and these four threads are both consumers and producers. besides i need a work queue containing the path. each iteration takes a path from this queue and generate the new paths and put them in the work queue. Does the idea make sense?

    However, my code does not work. the result is ridiculous. I do not know where the problem is.


  • Registered Users Posts: 1,922 ✭✭✭fergalr


    Yes, I have implemented it in sequential. I want to implement the parallel version based on the sequential one.

    That sounds like a good start.

    Have you tested your sequential version? Does it find tours correctly on small sized boards?

    Do you understand it fully, and have a good grasp of the main parts of the problem?
    My thoughts are to create four workers threads as my laptop is four-cores

    That sounds like a good start. I would guess that knights tour is heavily CPU bound, due to the nature of the problem, and that as such, one worker per core is a good starting point.
    and these four threads are both consumers and producers.
    besides i need a work queue containing the path.

    Ok, so you are making 4 separate worker threads, and you are going to use a queue to handle communication between these threads.
    That seems standard enough.

    You would have to be very careful, because threads share address space, that the one way you are communicating between the threads is by using the queue, in the way you intend. It could cause problems if the threads were all separately trying to modify shared state (shared variables). Are you aware of issues like that, and watching out for them?

    each iteration takes a path from this queue and generate the new paths and put them in the work queue. Does the idea make sense?
    Well, I can certainly think of a way of solving the problem that sounds a bit like that. But I'm not sure exactly what you are doing.

    How are you going to split up the problem, so that the queue can be used to share the work?

    I presume the model you are following here, for getting knights tours, is to recursively search for possible tours, backtracking when you get stuck?

    Have you got a good strategy for splitting this sequential algorithm up, so that many workers can work on it in parallel?

    Ultimately, you want a way of:
    1) taking a partial solution to the problem from the queue (e.g. a partial solution could be represented on the queue by a partial path, i.e. a partial possible tour)
    2) then doing a little bit of work towards the solution, and then
    3) putting a piece of information (e.g. the updated partial path, or partial possible tour) back onto the queue

    You will need to be sure there is some sort of ordering to how the solutions are found, so that various workers done cover the same ground; and so that when something processing partial solutions gets one from the queue, that it knows exactly what work to do next.

    Are you figured out a good way of doing that?
    Are you convinced of the correctness of your solution?
    If so, why don't you say exactly how you are doing that?
    However, my code does not work. the result is ridiculous. I do not know where the problem is.

    Do you think the issue is in your conceptualisation of the problem, or do you think you have figured out how to do it, and you have a small bug in your code?

    People would need a lot more to go on, in order to help you.
    But a good first step would be to describe your solution in more detail -- sometimes even the act of describing it can help you find bugs.


  • Registered Users Posts: 11 followme_1987


    fergalr wrote: »
    That sounds like a good start.....
    I would like to post my code and that is clearer than what i said. Thank you for your attending to this matter !!! it is a 3 X 10 board in my program.
    class KnightsTourMulThread
    {
    
    	static class KnightsTours implements Runnable
    	{
    
    		private Buffer<Path> workQ;
    
    		KnightsTours(Buffer<Path> workQ)
    		{
    			this.workQ = workQ;
    		}
    
    		@Override
    		public void run()
    		{
    			while (true)
    			{
    				Path p = workQ.take();
    
    				if (p == null)
    				{
    					return;
    				}
    
    				Position[] moves = p.pathMoves();
    
    				for (Position pos : moves)
    				{
    					if (!p.contains(pos))
    					{
    						Path newPath = new Path(pos, p);
    
    						if (newPath.pathComplete())
    						{
    							if (newPath.pathClosed())
    							{
    								newPath.putPath();
    							}
    
    							return;
    						}
    						else
    						{
    							workQ.put(newPath);
    						}
    
    					}
    				}
    			}
    		}
    	}
    
    	public static void main(String[] args)
    	{
    		int numWorkers = Runtime.getRuntime().availableProcessors();
    
    		Buffer<Path> workQ = new Buffer<Path>(numWorkers);
    
    		workQ.put(new Path(new Position(0, 0), null));
    
    		Thread[] t = new Thread[numWorkers];
    
    		for (int i = 0; i < numWorkers; i++)
    		{
    			t[i] = new Thread(new KnightsTours(workQ));
    
    			t[i].start();
    		}
    		for (int i = 0; i < numWorkers; i++)
    		{
    			try
    			{
    				t[i].join();
    			}
    			catch (InterruptedException e)
    			{
    			}
    
    		}
    
    	}
    }
    
    the following is a "work queue" class
    import java.util.*; // for LinkedList
    import java.util.concurrent.locks.*;
    
    class Buffer<E>
    {
    	// Unbounded shared buffer with termination detection for systems
    	// of a fixed number of producer/consumers
    
    	private ReentrantLock monitor = new ReentrantLock();
    	
    	private Condition notEmpty = monitor.newCondition();
    
    	private LinkedList<E> buffer = new LinkedList<E>(); // the buffer
    
    	private int numLive; // number of live producer/consumers
    
    	Buffer(int numLive)
    	{
    		this.numLive = numLive;
    	}
    
    	void put(E x)
    	{
    		monitor.lock();
    		
    		buffer.add(x);
    		
    		notEmpty.signal();
    		
    		monitor.unlock();
    	}
    
    	E take()
    	{
    		monitor.lock();
    		
    		while (buffer.size() == 0)
    		{
    			numLive--;
    			
    			if (numLive == 0)
    			{ // discover it's finished
    				notEmpty.signalAll(); // waken others to finish
    				
    				monitor.unlock();
    				
    				return null;
    			}
    			try
    			{
    				notEmpty.await();
    			}
    			catch (InterruptedException e)
    			{
    			}
    			
    			if (numLive == 0)
    			{ // am being told it's finished
    				monitor.unlock();
    				
    				return null;
    			}
    			else
    			{
    				numLive++;
    			}
    				
    		}
    		E x = buffer.removeFirst();
    		
    		monitor.unlock();
    		
    		return x;
    	}
    }
    
    the following two pieces of code are about the algorithm of knight's tour. I think that should be right
    class Path
    { 
    	// non-empty path of Position's
    
    	private Position start; // one end position in path (other is (0,0))
    	
    	private Path next; // path following start node (may be null)
    	
    	private int pathLength; // length of path
    
    	Path(Position start0, Path next0)
    	{
    		start = start0;
    		
    		next = next0;
    		
    		if (next == null)
    		{
    			pathLength = 1;
    		}
    		else
    		{
    			pathLength = 1 + next.pathLength;
    		}
    			
    	}
    
    	boolean contains(Position p)
    	{ 
    		// does p occur in this path?
    		if (start.equals(p))
    		{
    			return true;
    		}
    		else if (next == null)
    		{
    			return false;
    		}
    		else
    		{
    			return next.contains(p);
    		}
    			
    	}
    
    	Position[] pathMoves()
    	{ 
    		// new positions to extend path
    		return start.knightMoves();
    	}
    
    	boolean pathComplete()
    	{ 
    		// does the path cover the entire board?
    		int tourLength = Position.numRows * Position.numCols;
    		
    		return pathLength == tourLength;
    	}
    
    	boolean pathClosed()
    	{ 
    		// is the path (assumed complete) closed?
    		return start.equals(Position.end1) || start.equals(Position.end2);
    	}
    
    	void putPath()
    	{ 
    		// print path
    		start.putPosition();
    		
    		if (next != null)
    		{
    			System.out.print(":");
    			
    			next.putPath();
    		}
    	}
    
    }
    
    class Position
    {
    
    	static final int numRows = 3; // number of rows on board
    	
    	static final int numCols = 10; // number of columns on board
    
    	static final Position end1 = new Position(1, 2); // possible end positions
    														// (start is (0,0)
    	static final Position end2 = new Position(2, 1); // other possible end
    														// position
    	private int row; // row number, o<=i<numRows
    	
    	private int col; // column number, o<=j<numCols
    	Position(int row0, int col0)
    	{
    		row = row0;
    		
    		col = col0;
    	}
    
    	public boolean equals(Object obj)
    	{ 
    		// compare with another position
    		if (obj == null)
    		{
    			return false;
    		}
    			
    		Position p = (Position) obj;
    		
    		return (p.row == row && p.col == col);
    	}
    
    	Position[] knightMoves()
    	{ 
    		// list of knight's possible moves from here
    		Position[] temp = new Position[8];
    		
    		int count = 0; // temp[0..count-1] holds results
    		
    		int[] xStep = { 2, 2, -2, -2, 1, 1, -1, -1 }; // potential moves are
    														// (row+yStep[k],col+xStep[k])
    														// for each index k
    		int[] yStep = { 1, -1, 1, -1, 2, -2, 2, -2 };
    		
    		for (int k = 0; k < xStep.length; k++)
    		{ 
    			// check that each potential move stays on board
    			int x = row + yStep[k];
    			
    			int y = col + xStep[k];
    			
    			if (0 <= x && x < numCols && 0 <= y && y < numRows)
    			{
    				temp[count] = new Position(x, y);
    				
    				count++;
    			}
    		}
    		
    		Position[] result = new Position[count];
    		
    		for (int k = 0; k < count; k++)
    		{
    			result[k] = temp[k];
    		}
    			
    		return result;
    	}
    
    	void putPosition()
    	{ // print position
    		
    		// print position
    		System.out.print("(" + row + "," + col + ")");
    	}
    }
    


Advertisement