440,929 Members | 1,245 Online
Need help? Post your question and get tips & solutions from a community of 440,929 IT Pros & Developers. It's quick & easy.

# Puzzle program

 P: 3 HI I M ASHISH I WANT ALGORYTHMUS OF THIS PROBLEM Jigsaw puzzles. You would have solved many in your childhood and many people still like it in their old ages also. Now what you have got to do is to solve jigsaw puzzles using the computer. The jigsaw puzzle here is a square of dimension d (a puzzle with d^2 pieces) and the jigsaw pieces (all same dimensions) are of dimensions H x W (Which means the pieces have ‘H’ rows of ‘W’ characters. The pieces will be given as ( For eg a piece of 2 x 3 ) ABC DEF 5 0 0 -2 Where the pieces is having 2 rows of 3 characters (ABC DEF ) and the corners have directions 5 0 0 -2. These numbers (between –cons and +cons) will indicate the shape of the top, left, bottom and right edges of the puzzle piece, respectively. A value of 0 indicates a straight edge. Positive and Negative edges of same values are an interlock. The pieces can NOT be rotated and all pieces will be unique. Note : All characters can be a part of the puzzle piece. Your Job The puzzle will have one and only one solution and you have to find it. If the puzzle is not possible then return an error. Mar 7 '07 #1
5 Replies

 100+ P: 1,806 Have we started? Mar 7 '07 #2

 P: 3 Have we started? yes we can man plz answer it Mar 7 '07 #3

 Expert 2.5K+ P: 3,652 The experts on this site are more than happy to help you with your problems but they cannot do your assignment/program for you. Attempt the assignment/program yourself first and post questions regarding any difficulties you have or about a particular function of the code that you don't know how to achieve. Please read the Posting Guidelines and particularly the Coursework Posting Guidlines. Then when you are ready post a new question in this thread. MODERATOR Mar 7 '07 #4

 P: 3 when i want to calculate for d>3 i have problem for d =2 and for d=3 i first asign the position to the pieces according to thier shape indicating no.(which are top bottom left and right) and then i check whether they satisfiy the given condition of intrerlocking or not ! but for d>3 the algorithm is quite complex Mar 7 '07 #5

 100+ P: 1,806 There are many ways to approach this, but I would start by fining one of the corners. (luckily we can't rotate the pieces). Having found the corner (Let's say the top L (which I assume is 0 x y 0)) Now we search for all pieces that will link with either x or y (let's say x (0 v, w, -x)).... For each of these pieces, we repeat the problem and since there are a limited number of pieces accross this row, the answer should fall out reasonably simply. You can then try in another direction along an edge.... Once you have completed the border, you try to find the corner pieces INSIDE your new frame (a little harder, but with some thought you could generalise the staright edged algorithm) And work around again...... It might help to represent the pieces in a Graph where each node has 4 Arcs (one or two of which are NULL for edge pieces). You can also verify the datas validity, since you know how many pieces there are, and how many should be edges/corners. Mar 7 '07 #6