Tetravex solving algorithm

Question

Well, i was thinking of making 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.

Answer 1

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.

Answer 2

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.

Answer 3

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.