Jigsaw Puzzle
So in my computer programming class at the end of the semester, for extra credit, we can make program that would automatically solve the jigsaw puzzle. I've been doing alot of research but yet I'm not sure how I would want to tackle this. The pieces would be generated inside a matrix and somehow the program will figure out how to line individual pieces. Maybe it doesn't even have to be a matrix but I think this would be the best option.
Although the semester quite a ways off, I think getting a head start is never a bad idea.
Any thoughts?
Although the semester quite a ways off, I think getting a head start is never a bad idea.
Any thoughts?
Ok we are give a few pieces. The character 0 will represent a square.
Just for example purposes, I will make a puzzle.
Piece 1
000
0
000
Piece 2
000
Piece 3
00
0
00
We are allowed to rotate these pieces. So the final solution would be a 5x3 rectangle where piece 2 would go in center and piece 3 will be rotated 180 degrees and go at the end.
The final result.
00000
00000
00000
Just for example purposes, I will make a puzzle.
Piece 1
000
0
000
Piece 2
000
Piece 3
00
0
00
We are allowed to rotate these pieces. So the final solution would be a 5x3 rectangle where piece 2 would go in center and piece 3 will be rotated 180 degrees and go at the end.
The final result.
00000
00000
00000
You could always brute-force it. Trial and error. Try every single combination the pieces could possibly placed in, and when none collide, the puzzle is solved.
It won't be the most speed efficient solution, but it'll solve before you blink. :P
EDIT: that reminds me, there was a post similar to this... here: http://cplusplus.com/forum/general/28315/
Somewhat the same as solving a jigsaw puzzle.
It won't be the most speed efficient solution, but it'll solve before you blink. :P
EDIT: that reminds me, there was a post similar to this... here: http://cplusplus.com/forum/general/28315/
Somewhat the same as solving a jigsaw puzzle.
Last edited on
nice!! I haven't been coding for a while (only reading) I think I wanna do this myself.
good luck to you too!!
good luck to you too!!
@Thumper
It's exactly the same thing as the mosaic problem. I've been doing Google searches for brute-force algorithm but haven't really come up with any good responses. They way I'm planning it, lets say I set up a matrix, how would I actually compare the values (or combination) as suggested for brute-force trial and error approach.
@blackcoder41
If you have a working program, would you mind sharing the way you approached this problem and how you were finally able to work up an algorithm. I don't need the program just tips on how I can approach this.
It's exactly the same thing as the mosaic problem. I've been doing Google searches for brute-force algorithm but haven't really come up with any good responses. They way I'm planning it, lets say I set up a matrix, how would I actually compare the values (or combination) as suggested for brute-force trial and error approach.
@blackcoder41
If you have a working program, would you mind sharing the way you approached this problem and how you were finally able to work up an algorithm. I don't need the program just tips on how I can approach this.
I believe the algorithm would basically be an extension of http://en.wikipedia.org/wiki/Eight_queens_puzzle
If you understand how to solve queens, this shouldn't be a problem. You have to change the function that checks if you can place the queen on a tile or not. You would also have to add iterating through all possible shapes and angles. Unlike in 8 queens problem, using a 2d array would be a good idea.
If you understand how to solve queens, this shouldn't be a problem. You have to change the function that checks if you can place the queen on a tile or not. You would also have to add iterating through all possible shapes and angles. Unlike in 8 queens problem, using a 2d array would be a good idea.
Brute-force isn't really an algorithm, it's more of a "create an infinite loop in your program that doesn't quit until your answer is found" kind of thing, and your program just tries thousands upon thousands of combinations.
I'm not sure how you would actually go about comparing the values at this time, but i'm deffinatlely gonna give this a shot myself. I'll let you know if i have any progress.
I'm not sure how you would actually go about comparing the values at this time, but i'm deffinatlely gonna give this a shot myself. I'll let you know if i have any progress.
Again Thumper if you don't mind my pestering, I would love if you share your approach.
I have to say that I do like these kinds of challenging problem as opposed to just procedural programming because it makes you think and once you finish, the end result if very satisfying.
For example, in school, we were supposed to develop NSD for an exchange sort program and just thinking about it logically and overcoming the challenge gave me satisfaction.
I have to say that I do like these kinds of challenging problem as opposed to just procedural programming because it makes you think and once you finish, the end result if very satisfying.
For example, in school, we were supposed to develop NSD for an exchange sort program and just thinking about it logically and overcoming the challenge gave me satisfaction.
Done!
As I said, this is a slightly more complicated version of 8 queens algorithm.
I don't see a better way to describe it..
Do you want me to post the code?
As I said, this is a slightly more complicated version of 8 queens algorithm.
I don't see a better way to describe it..
Do you want me to post the code?
| thepedestrian wrote: |
|---|
| If you have a working program, would you mind sharing the way you approached this problem and how you were finally able to work up an algorithm. I don't need the program just tips on how I can approach this. |
Oh sorry, I haven't started it yet. Been spending my time socializing with friend and families, getting familiar with linux, etc..
@hamsterman
Whaaaaaaaaaaaat. That was fast!!!!!!!!!!!!!!!!!!!!! Year can you please kindly post the code.
@blackcoder41,
It's fine. I just need a starting point. hamsterman, using his leets skills has already developed an algorithm. I'm sure his posting of the code will be valuable to all of us.
Anyways I want to thank both of you guys for your support and just the mere fact that we can have a conversation about a give subject. Thanks guys.
Whaaaaaaaaaaaat. That was fast!!!!!!!!!!!!!!!!!!!!! Year can you please kindly post the code.
@blackcoder41,
It's fine. I just need a starting point. hamsterman, using his leets skills has already developed an algorithm. I'm sure his posting of the code will be valuable to all of us.
Anyways I want to thank both of you guys for your support and just the mere fact that we can have a conversation about a give subject. Thanks guys.
http://pastebin.com/Y17kvz6n
I tried to add comments..
It isn't a very beautiful solution though. There's too much copying and some other stuff I don't like..
I tried to add comments..
It isn't a very beautiful solution though. There's too much copying and some other stuff I don't like..
Thanks hamsterman. I'm currently no on my development computer but will definitely try out your code once I get home. Thank you.
Thanks hamsterman. This works perfectly. Although some of the functions are beyond my grasp right now, I probably would have a better understanding in a few more months when I deal heavily into this and learn more in school. Thanks man. I appreciate it.
The thing with me is, I can follow the code and see why you are doing something but if you ask me to recreate this from ground up, I would be completely lost and wouldn't even know where to begin. But the fact that something like this is possible gives me hope and I'm looking forward to building something of my own where I'm not plagiarizing your code although I might "plagiarize" your concepts. lol. ;)
The thing with me is, I can follow the code and see why you are doing something but if you ask me to recreate this from ground up, I would be completely lost and wouldn't even know where to begin. But the fact that something like this is possible gives me hope and I'm looking forward to building something of my own where I'm not plagiarizing your code although I might "plagiarize" your concepts. lol. ;)
Topic archived. No new replies allowed.