Start a new topic
Add Reply
hello geeks,
I'm in my 2nd year in computer science major right now and i have implemented a game of Tetravex..anyway i was thinking of writing a program that will solve any tetravex puzzle and i just wanted to know your thoughts about this, is it doable in an efficient way?? or would it be a waste of time to try to implement such a program??.. thanks for reading
Tetravex Solver
Page 1 of 1
Tetravex Solver Tetravex puzzle solver algorithm
#1
mostyfriedman
- Striving Student
-
- Group: Expert w/DIC++
- Posts: 3,504
- Joined: 24-October 08
Dream Kudos: 600
Expert In: Learning
Posted 20 March 2009 - 09:36 AM
Was This Post Helpful?
0
MultiQuote
#2
mostyfriedman
- Striving Student
-
- Group: Expert w/DIC++
- Posts: 3,504
- Joined: 24-October 08
Dream Kudos: 600
Expert In: Learning
Posted 20 March 2009 - 04:26 PM
i think i should have posted this in the game programming forum, can a mod/admin move this please
Was This Post Helpful?
0
#3
Gloin
- Expert Schmexpert...
-
- Group: Mentors
- Posts: 4,130
- Joined: 04-August 08
Dream Kudos: 75
Posted 21 March 2009 - 02:55 AM
I don't know any short-cut polynomial algorithm for this problem and the immediate thought is that you would have to try an exponential number of combinations to find the solution.
However, considering there are likely more than one solution to many of these puzzles and that you can branch quite heavily, there's likely a pretty good chance of finding a solution fast anyways.
What's the largest puzzle that you allow? Is there a limit or do you intend to have a solver for the n by n case?
However, considering there are likely more than one solution to many of these puzzles and that you can branch quite heavily, there's likely a pretty good chance of finding a solution fast anyways.
What's the largest puzzle that you allow? Is there a limit or do you intend to have a solver for the n by n case?
Was This Post Helpful?
0
#4
baavgai
- Dreaming Coder
-
- Group: Expert w/DIC++
- Posts: 4,722
- Joined: 16-October 07
Dream Kudos: 575
Expert In: C, C++, Java, C#, ASP.NET, PHP, Perl, Python, Oracle, SQL Server, MySql, HTML, JavaScript, Lua, Cheese
Posted 21 March 2009 - 03:32 AM
mostyfriedman, on 20 Mar, 2009 - 11:36 AM, said:
is it doable in an efficient way?
Depends on how you judge efficient.
Every piece matches to a minimum of two other pieces. Doing an initial compare pass to find the piece that has the least matches would be a good place to start. It would also be a simple validation, since a having piece that can't even match two in a corner means your puzzle can't be done. If you're lucky enough to find a piece that must be a corner, then your search became significantly more efficient.
Sounds like fun. Good luck.
Was This Post Helpful?
0
#5
mostyfriedman
- Striving Student
-
- Group: Expert w/DIC++
- Posts: 3,504
- Joined: 24-October 08
Dream Kudos: 600
Expert In: Learning
Posted 21 March 2009 - 08:48 AM
Gloin, on 21 Mar, 2009 - 02:55 AM, said:
I don't know any short-cut polynomial algorithm for this problem and the immediate thought is that you would have to try an exponential number of combinations to find the solution.
However, considering there are likely more than one solution to many of these puzzles and that you can branch quite heavily, there's likely a pretty good chance of finding a solution fast anyways.
What's the largest puzzle that you allow? Is there a limit or do you intend to have a solver for the n by n case?
However, considering there are likely more than one solution to many of these puzzles and that you can branch quite heavily, there's likely a pretty good chance of finding a solution fast anyways.
What's the largest puzzle that you allow? Is there a limit or do you intend to have a solver for the n by n case?
the largest puzzle that i allow is 6*6 and the smallest is 2*2, i actually i thought of it and i drew a diagram for all the possibilities on paper, i thought of using recursion for it, i don't know if this is a good idea though...
btw i already have the solution, because what my program does, is that it generates the solution first and then it shuffles the puzzle(to ensure that the puzzle is solvable) so if the user gives up and wants to see the solution the solution will be displayed, what i was thinking of doing is to write a generic algorithm to solve any puzzle...
Was This Post Helpful?
0
#6
Gloin
- Expert Schmexpert...
-
- Group: Mentors
- Posts: 4,130
- Joined: 04-August 08
Dream Kudos: 75
Posted 24 March 2009 - 02:48 PM
That was my first thought actually, taking a solution and shuffle it but I figured you wanted a solver.
For a maximum of 6x6 I would go with brute force with some simple branching rule. Doesn't matter that the number of possible combinations grow exponentially since it will never grow too big to handle for a standard computer.
Recursion is good for this problem.
For a maximum of 6x6 I would go with brute force with some simple branching rule. Doesn't matter that the number of possible combinations grow exponentially since it will never grow too big to handle for a standard computer.
Recursion is good for this problem.
Was This Post Helpful?
0
#7
mostyfriedman
- Striving Student
-
- Group: Expert w/DIC++
- Posts: 3,504
- Joined: 24-October 08
Dream Kudos: 600
Expert In: Learning
Posted 24 March 2009 - 05:30 PM
Gloin, on 24 Mar, 2009 - 02:48 PM, said:
That was my first thought actually, taking a solution and shuffle it but I figured you wanted a solver.
For a maximum of 6x6 I would go with brute force with some simple branching rule. Doesn't matter that the number of possible combinations grow exponentially since it will never grow too big to handle for a standard computer.
Recursion is good for this problem.
For a maximum of 6x6 I would go with brute force with some simple branching rule. Doesn't matter that the number of possible combinations grow exponentially since it will never grow too big to handle for a standard computer.
Recursion is good for this problem.
thanks for the reply, i was actually thinking of a brute force approach, since there is no other straight forward way to do this.. i thought of either generating all the possible permutations of the puzzle, or doing like some kinda search and bound algorithm where each time i eliminate solutions that won't work..
Was This Post Helpful?
0
Page 1 of 1
| 
