CS420 Project: TeTravex

Liwen Huang liwen.huang@yale.edu

April 29, 2001

My final project of Functional Programming is about the Game TeTravax. It consistes following parts:

1. For Tetravex Puzzle, write a Haskell program to find a solution.

2. In the algorithm, using depth-first search, back track and some herusitic, and discuss the difference.

3. Use SOEGraphics to show the solution.

1 Tetravex Puzzle

The Tetravex Puzzle is a game you can find under Linux Game. You are given N^{2} Tiles, and each edge of the tile have a number attached to it. You are asked to put those tiles in an n ∗ n big square, such that all the connected edges share the same number.

In order to use search algorithm to solve the puzzle. We need to represent this puzzle as a Search problem. Basicly we want to define the following concepts:

1. Initial State:

The Initial State is all those tiles you have and an empty Board. A tile is represented as a tuple of integers(number of each side).

type Tile = (Side, Side, Side,Side)
type Side = Int

The Board is a List of Tiles put in correspond Position of the board. It is defined as below:

type Board=[(Tile,Position)]

type Position=(Int,Int) The Board is a List of Tiles put in correspond Position of the board.

2. Moves:

A move is to fetch a tile from the tile list, put it to an unoccupied Position on Board.

3. State space:

This is all the possible states we can reach from the Initial State.

4. Goal test: The goal state is your tile list is empty, the Board is full, and there is no conflicts on the board(No two attached edges have different number). We introduce a function to do this conflicts check:

nonconflict ::  Tile -> Board -> Bool, is to check whether the tile

has conflict with the tiles that beside it.

Before running the search algorithm, I do some bound check, to make sure it’s a legal start state.

2 Algorithm and Search Sequence

• Backtracking Alogrithm The basic depth first research will only use the goal test to test the success of the solution. This means that it will check whether or not the board is a success solution or not only when the board is full. But we can see that it wastes time to search when the tiles in the board have already violated the constrains. So I modified the algorithm to insert a test every time we add a new tile to the broad to check whether the new added tile cause conflict. If has conflict, try to find another, if can not find such one, we do backtrack. This is called ”Backtracking search”.

• Search Sequence Initially I start the search from the Position(1,1) and search line by line from left to right. I found this is not a good search sequence. Becasue if we put a wrong Tile in the early steps, for example to the Position (1,1), it can not find a proper tile assign to (2,1) because of it. But accouding to this search sequence, it will consider (1,1)–(1,n) then try to assign (2,1), when it found conflicts it will backtrack. It will not consider to replace tile (1,1) unless all possible assignment of tile from (1,2)-(1,n) didn’t work out. The best way to solve this problem is to use Forward checking. Here I tried another search sequence. I first search for Position (1,1), then for Position(1,2),(2,2),(2,1) thus they compose a puzzle of n = 2, then I search for subpuzzle n = 3 based on it. Until n = k(Given argument). To see the difference, I trace the algorithm. I have try both two for n = 4, in my example, the later one only search 237 steps to get the result, while the first one use 613 steps.

3 Result Demonstration

The Board contains what we need to show the final result. Once the solution is found, we use SOEGraphics to show the result. It is implemented as the render function.

Inside rugs, after loading the program Travex.hs, you can type in start2 n tn to activate the game show window. The window is a squareWindow named “TeTravex”. There are n ∗ n squares in the window. Each small square is a tile, with 4 numbers. After the result is fully demonstrated, you can press any key to close the window.

For each tile, we compute the real position of it’s four corners, draw a square, and then draw two cross lines on it, at last we show the number of each side on the proper position in square.