Read Me

This is a prototype of the game klotski. For more information about klotski, visit http://en.wikipedia.org/wiki/Klotski.

Contents:
	Compile and Run
	How to play the game
	Solve the game
	Customize the game
	Bugs and todos

1. Compile and Run
	You must have Java 6. 
	compile:
		javac JKlotski.java
	run:	
		java JKlotski or java JKlotski.jar
		
2. How to Play the Game
	The goal of the game is to move the biggest piece (in red color) to the exit located in the middele of the bottom. During this process, all pieces must remain in the boarder of the board and no overlapping between pieces are allowed. The board is a 5x4 rectangle. The pieces are 1x1, 1x2, 2x1, and 2x2. There are usually at least 2 1x1 places in the board that are not occupied by any piece, in order to make the game solvable.
	You can use mouse to drag and drop any piece that is movable by the rule of the game. There is no animation yet. The piece moved will studently appear in its new location when you release the mouse button. A move is defined as one piece moving one location. A consecutive move of the same piece, even in the same direction, is considered as two moves. 
	
3. Solve the Game
	You can ask the program to solve the puzzle for you by pressing the 'solve' button. It uses the current configuration of the game (shown on the left) as the start location. If there is a solution, you can use 'next' button to step through the solution. You can also use 'start' and 'stop' button to show the solution automatically.
	
4. Customize a Game
	You can create your own game by providing the shapes and layout of pieces in the board. In this initial version, it's not trival. You must provide an encoding of the configuration, type it in the text area on the right, then press the 'Reload' button. The default configuration is loaded when the game starts. Let's use this as an example.
	
		baac
		baac
		dEEf
		dghf
		i  j
	
	Encoding rules:
	a) The encoding is a string consisting of exactly 20 characters. (5x4 locations)
	b) Every piece has a unique character, different locations covered by the same piece are marked with the same character. 
	c) The locations not occupied are marked as spaces, ' '. We always use 'a' to denote the 2x2 piece.
	d) Use 'g' 'h' 'i' 'j' to denote the 1x1 pieces, 'b' 'c' 'd' 'e' 'f' the vertical 2x1 pieces, and uppercase 'B' to 'F' the horizental 1x2 pieces.
	e) No other characters should be used. 
	f) You can type the string in different lines, the newline character will be removed automatically, resulting "baacbaacdEEfdghfi  j".
	
	These rules are ugly and should be relaxed later. However, failure to follow may have unexpected result. (such as finding sub-optimal solution, or failure to find a solution.)
	
4.1 A New Method
	A simplified method of defining the board configuration is as follows:
	The big 2x2 square is denoted by four '4' characters.
	The horizontal 1x2 piece by two '2' characters.
	The vertical 2x1 piece is two '3'.
	The 1x1 is one '1'.
	The blank space is '0'.
	For example, the above configuration can be represented by this one:
		2442
		2442
		2332
		2442
		1001
		
5. Bugs and todos
	a) Quick consecutive presses of 'solve' button don't solve it.
	b) Pressing 'start' more than one time makes the animation faster. (more thread, I guess.)
	c) Improve user interface. Image instead solid color. Smooth movement. Progress bar, etc.
	d) The counting of steps are not intuitive. Some people argue that one piece moving two locations is only one move, no matter in the same direction or not. For example, 
		
		baac		baac
		baac		baac
		dEEf	==>	dEEf	is only one move
		dghf		dghf
		i##j		ij##  
		
		baac		baac
		baac		baac
		dEEf	==>	dEEf	is only one move
		dghf		dg#f
		ij##		ij#h 
		(I use '#' here to denote the 'space' clearly, but in the encoding, it should be ' ')
		
	Under this definition, the optimal solution usually has less moves. But if we decompose the combined move into two smaller moves, the total number of moves is no less than that with the original definition. (Note that althought the path might be different.) I am not sure if it's possible for the optimal solution of combined moves to decompose to sub-optimal solution in the original definition.
	
	Anyways, if a piece must be moved over two locations, doing them consecutively is intuitive. The current version doesn't guarantee that. For example, 
		bg##		b#g#		bhg#		bh#g
		bhaa		bhaa		b#aa		b#aa
		cfaa	==>	cfaa	==>	cfaa	==>	cfaa
		cfDD		cfDD		cfDD		cfDD
		EEij		EEij		EEij		EEij
		
	This may look better:
		bg##		b#g#		b##g		bh#g
		bhaa		bhaa		bhaa		b#aa
		cfaa	==>	cfaa	==>	cfaa	==>	cfaa
		cfDD		cfDD		cfDD		cfDD
		EEij		EEij		EEij		EEij