Tetravex solving algorithm_问答_开发者_运维开发者技术经验分享

Well, i was thinking of mak开发者_如何转开发ing a Tetravex solving program in order to practice my code writing skills (language will propably be Visual Basic) and I need help finding an algorithm for solving it. For those that don't know what tetravex is see this http://en.wikipedia.org/wiki/TetraVex . The only algorithm I can come up with is the brute force way, place a tile randomly in one corner and try every possible tile next to it and continue the same process, if it reaches a dead end revert to a previous state and place a different tile. So can anyone come up with a better algorithm? Thank you for your time.

here some ideas.

A vanilla brute force algorithm would try to fill out the grid recursively by enumerating the grid positions in a fixed order (e.g. row major) and always trying to fit every possible piece in the current position and then recursing. This is what you mentioned and it is very inefficient.

An improvement is to always count for every free position the number of pieces that fit there, and then recurse on the position that has least fits; if one has zero fitting pieces, backtrack immediately; if there is one where only one piece fits fill that and continue (no branch created); otherwise select the one that has least fitting pieces (≥ 2) and continue from there.

Once you have this algorithm in place, the next question is how you can prune the search space more. If have, say, A pieces with "1" on the top position and B pieces with "1" on the bottom position, and A > B, then you know that at least A - B of the "1 at top position" pieces must be actually placed on the top row, so you can exclude them from any other position. This helps to reduce the branching factor and to spot dead-ends earlier.

You should also check at every recursion step that every piece has at least one spot where it fits (do this check after verifying that there is no piece that fits in only one place for speed). If there is a piece that doesn't fit anywhere you need to backtrack immediately. You can extend this to checking that every pair of pieces fits for a potentially better earlier dead-lock checking capability.

There is a also a strategy called "non-chronological backtracking" or "backjumping" which originates from research into SAT solving. This helps you to backtrack more than one level at a time when you reach a dead-end; if you want, you can google for these terms to find more, but you need to do some mental work to map the concept into your problem space.

A first improvement would be counting how many matching pairs of numbers there are, and if, say, there are 5 "1"'s on the top of squares, but only 4 on the bottom, then there must be a "1" pointing off the top of the grid.

At any given partly solved board I would

look for a place where none of the remaining tiles could be played. If found, the board must be unwound to the last place a tile was played randomly.
Look for a place where only 1 of the remaining tiles can legally be played. If found, place that tile.
Place a tile randomly at the spot on the board where the fewest number of remaining tiles can legally be played. Remember this board layout before I lay the tile, I may want to unwind back to this board and play a different tile.

In pseudocode it would be

top:
  evaluate # of tiles that match at each empty square
  if any square has 0 matches, unwind to <prev>
  if any square has 1 match, lay tile, goto top
  save current board as <prev>
  play randomly at square with minimum number of matches, goto top

As an optimization, you can ignore evaluating squares that don't touch any squares that have tiles, since they will always allow all remaining tiles.

It looks like Tetravex is a Constraint Satisfaction Problem, so you want to limit your options as quickly as possible. It should be possible to do better than random placement. How about?:

Create links between all tile faces with their possible matches.
Any tile with an unlinked face must be an edge tile.
Any tile with two adjacent unlinked faces must be a corner tile.
Center tiles must have four active links.
Now, place a tile in a valid location and invalidate links that are used. If any un-placed tile contains three unlinked faces or unlinked faces on opposite sides, the move is invalid and you can backtrack.
You should be able to use tile face links to look for the next possible tile versus searching through all tiles. If there isn't one, backtrack.

I wrote a solver for Tetravex and used a different approach and it seems very efficient. I built up possible valid relationships increasing the size. So each iteration gives me larger puzzle pieces to work with while reducing the number of puzzle of pieces, so to speak.

I start by creating a list of all possible connections between tiles from bottom to top and a list of all possible connections between tiles from right to left.

From these two lists, I build a list of all possible valid 2x2 combinations.

Using the 2x2 list, I build a list of all possible valid 3x3 combinations.

From there I can go 4x4 by using the 2x2 and 3x3 lists, or do 5x5 by just using the 3x3 list.

Right now my code does each iteration separately, but should be able to be cleaned up to handle each iteration with the same code which would allow for larger grid sizes.

This also seems like a great situation for using a neural net, and I might give that a try next.