CodeForge QQ客服 CodeForge 400电话 客服电话 4006316121
首页 » 源代码 » 一块拼图 » Puzzle.java

Puzzle.java ( 文件浏览 )

文件源自:一块拼图
  • 发布于2016-05-18
  • 浏览次数:0
  • 下载次数:0
  • 下载需 1 积分
  • 侵权举报
			package com.tamal.tiles;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;

public class Puzzle {


	private Board board;
	private Tile[] tiles;

	private boolean allSameSizeTiles;
	private int singleTileSize;
	private int totalTileSquare;

	private Tile[] participants;

	private HashSet<IMonitor> monitors = new HashSet<IMonitor>();

	public void addMonitor(IMonitor monitor) {

		if (monitor != null)
			monitors.add(monitor);
	
}

	public void removeMonitor(IMonitor monitor) {

		if (monitor != null)
			monitors.remove(monitor);
	
}

	protected void OnProgress(int event) {

		for (IMonitor monitor : monitors) {

			monitor.update(event);
		
}
	
}

	public Tile[] getTiles() {

		return tiles;
	
}

	public Board getBoard() {

		return board;
	
}

	public ArrayList<Solution> getSolutions() {

		return sols;
	
}

	public int getSolutionCount() {

		return sols.size();
	
}

	public void parse(String path) throws IOException {

		parse(new FileInputStream(new File(path)));
	
}

	public void parse(InputStream inStream) throws IOException {

		ArrayList<char[]> fullInput = new ArrayList<char[]>();

		BufferedReader in = new BufferedReader(new InputStreamReader(inStream));
		try {

			String line = null;
			while ((line = in.readLine()) != null) {

				fullInput.add(line.toCharArray());
			
}
		
} finally {

			in.close();
		
}

		MergedBoard merged = new MergedBoard(fullInput, false);
		merged.parse();
		ArrayList<RawPiece> rawPieces = merged.getRawPieces();
		rawPieces.remove(merged.getMaxPiece());
		board = new Board(0, merged.getMaxPiece());
		tiles = new Tile[rawPieces.size()];

		singleTileSize = rawPieces.get(0).size();
		allSameSizeTiles = true;
		int i = 0;
		totalTileSquare = 0;
		for (RawPiece rawPiece : rawPieces) {

			tiles[i] = new Tile(i + 1, rawPiece);
			totalTileSquare += tiles[i].size();
			if (singleTileSize != tiles[i].size())
				allSameSizeTiles = false;
			i++;
		
}
	
}

	long totalTime = 0;
	long deadEndTime = 0;

	public long getTotalTime() {

		return totalTime;
	
}

	private int[] order;
	private int[] orientation;

	private ArrayList<Solution> sols = new ArrayList<Solution>();
	private boolean singleSolution;

	public void solve(boolean singleSolution, boolean useRotation,
			boolean useReflection) {

		sols.clear();
		totalTime = 0;
		this.singleSolution = singleSolution;

		setOrientationMode(useRotation, useReflection);
		for (int index = 0; index < tiles.length; index++) {

			tiles[index].process(orientation);
		
}

		if (board.size() == totalTileSquare) {


			participants = new Tile[tiles.length];
			for (int index = 0; index < tiles.length; index++) {

				participants[index] = tiles[index];
			
}
			solveThis();
		
} else if (board.size() < totalTileSquare) {


			selectParticipants(new BitSet(tiles.length), 0, board.size());
		
} else {


			totalTime = 0;
		
}
	
}

	private void selectParticipants(BitSet pbits, int index, int unfilled) {

		int newUnFilled;
		for (int i = 2; i-- > 0;) {

			if (i == 1) {

				pbits.set(index);
				newUnFilled = unfilled - tiles[index].size();
			
} else {

				pbits.clear(index);
				newUnFilled = unfilled;
			
}

			if (newUnFilled > 0) {

				if (index + 1 < tiles.length)
					selectParticipants(pbits, index + 1, newUnFilled);
			
} else if (newUnFilled == 0) {

				participants = new Tile[pbits.cardinality()];
				int k = 0;
				for (int j = 0; j <= index; j++) {

					if (pbits.get(j))
						participants[k++] = tiles[j];
				
}
				solveThis();
			
} else
				return;

			if (singleSolution && sols.size() == 1) {

				return;
			
}
		
}
	
}

	private void solveThis() {

		orderTiles();

		int startRow = 0;
		int startCol = 0;
		while (board.squareId[startRow][startCol] != board.id) {

			startCol++;
			if (startCol == board.width()) {

				startCol = 0;
				startRow++;
			
}
		
}

		this.deadEndTime = 0;
		this.board.addtime = 0;
		this.board.removetime = 0;
		long startTime = System.currentTimeMillis();

		play(startRow, startCol);

		totalTime = System.currentTimeMillis() - startTime;
		System.err.println(String.format(
				"addtime = %s ms removetime = %s ms, deadEndTime = %s ms",
				board.addtime, board.removetime, this.deadEndTime));
	
}

	private void orderTiles() {

		// unchanged order
		order = new int[participants.length];
		for (int i = 0; i < participants.length; i++)
			order[i] = i;

		// // modify order based on # of possible placement positions
		// IntPair[] posCount = new IntPair[tiles.length];
		// int index, count;
		// Tile tile;
		// for (index = 0; index < tiles.length; index++) {

		// count = 0;
		// tile = tiles[index];
		// for (int o = 0; o < orientation.length; o++) {

		// if (tile.distinctOrientation(orientation[o])) {

		// tile.setOrientation(orientation[o]);
		// for (int j = 0; j < board.height(); j++) {

		// for (int i = 0; i < board.width(); i++) {

		// tile.setPos(i, j);
		// if (board.add(tiles[index])) {

		// count++;
		// board.remove(tile);
		// 
}
		// 
}
		// 
}
		// 
}
		// 
}
		// posCount[index] = new IntPair(index, count);
		// tile.setOrientation(Piece.ROTATE_0);
		// 
}
		// Arrays.sort(posCount, new Comparator<IntPair>() {

		// @Override
		// public int compare(IntPair p1, IntPair p2) {

		// return p1.getB() - p2.getB();
		// 
}
		// 
});
		// order = new int[tiles.length];
		// for (index = 0; index < tiles.length; index++) {

		// order[index] = posCount[index].getA();
		// 
}

		// // modify order based on symmetryCount
		// IntPair[] posCount = new IntPair[tiles.length];
		// for (int index = 0; index < tiles.length; index++) {

		// posCount[index] = new IntPair(index, tiles[index]
		// .getSymmetryCount());
		// 
}
		// Arrays.sort(posCount, new Comparator<IntPair>() {

		// @Override
		// public int compare(IntPair p1, IntPair p2) {

		// return p1.getB() - p2.getB();
		// 
}
		// 
});
		// order = new int[tiles.length];
		// for (int index = 0; index < tiles.length; index++) {

		// order[index] = posCount[index].getA();
		// 
}

		// // REVERSE order based on symmetryCount
		// IntPair[] posCount = new IntPair[tiles.length];
		// for (int index = 0; index < tiles.length; index++) {

		// posCount[index] = new IntPair(index, tiles[index]
		// .getSymmetryCount());
		// 
}
		// Arrays.sort(posCount, new Comparator<IntPair>() {

		// @Override
		// public int compare(IntPair p1, IntPair p2) {

		// return p2.getB() - p1.getB();
		// 
}
		// 
});
		// order = new int[tiles.length];
		// for (int index = 0; index < tiles.length; index++) {

		// order[index] = posCount[index].getA();
		// 
}
	
}

	private void setOrientationMode(boolean useRotation, boolean useReflection) {

		if (useRotation && useReflection) {

			orientation = new int[] {
 Piece.ROTATE_0, Piece.ROTATE_90,
					Piece.ROTATE_180, Piece.ROTATE_270, Piece.FLIP_ROTATE_0,
					Piece.FLIP_ROTATE_90, Piece.FLIP_ROTATE_180,
					Piece.FLIP_ROTATE_270 
};
		
} else if (useRotation && !useReflection) {

			orientation = new int[] {
 Piece.ROTATE_0, Piece.ROTATE_90,
					Piece.ROTATE_180, Piece.ROTATE_270 
};
		
} else if (!useRotation && useReflection) {

			orientation = new int[] {
 Piece.ROTATE_0, Piece.ROTATE_180,
					Piece.FLIP_ROTATE_0, Piece.FLIP_ROTATE_180 
};
		
} else {

			orientation = new int[] {
 Piece.ROTATE_0 
};
		
}
	
}

	private void play(int row, int col) {

		for (int index = 0; index < participants.length; index++) {

			if (order[index] < 0)
				continue; // tile already used

			Tile tile = participants[order[index]];
			for (tile.curO = 0; tile.curO < tile.oCount; tile.curO++) {

				if (!board.putPiece(tile, row, col))
					continue;
				order[index] -= order.length;

				if (board.isFull()) {

					Solution sol = board.getSolution();
					// if (!foundSymmetry(sol)) {

					sols.add(sol);
					OnProgress(IMonitor.NEW_SOL);
					// 
}
				
} else if (!deadendReached()) {

					// find next empty space, going
					// left-to-right then top-to-bottom
					int nextRow = row;
					int nextCol = col;
					while (board.squareId[nextRow][nextCol] != board.id) {

						nextCol++;
						if (nextCol == board.width()) {

							nextCol = 0;
							nextRow++;
						
}
					
}
					play(nextRow, nextCol); // and try to
...
...
(完整源码请下载查看)
			
...
展开> <收缩

下载源码到电脑,阅读使用更方便

1 积分

快速下载
还剩0行未阅读,继续阅读
云测速

源码文件列表

温馨提示: 点击源码文件名可预览文件内容哦 ^_^
...
名称 大小 修改日期
Puzzle0.00 B2010-05-09|20:37
Puzzle516.00 B2008-04-14|03:27
Puzzle252.00 B2008-04-18|23:36
Puzzle268.00 B2008-04-18|23:36
Puzzle392.00 B2008-04-14|18:24
Puzzle304.00 B2008-04-14|22:08
Puzzle309.00 B2008-04-19|01:56
Puzzle340.00 B2008-04-19|02:32
Puzzle316.00 B2008-04-19|02:32
Puzzle322.00 B2008-04-23|23:33
Puzzle429.00 B2008-04-23|23:33
Puzzle431.00 B2008-04-23|23:33
Puzzle429.00 B2008-04-23|23:34
Puzzle428.00 B2008-04-23|23:34
Puzzle427.00 B2008-04-23|23:34
Puzzle428.00 B2008-04-23|23:34
Puzzle322.00 B2008-04-23|23:34
Puzzle321.00 B2008-04-23|23:34
Puzzle323.00 B2008-04-23|23:34
Puzzle337.00 B2008-04-14|18:30
Puzzle56.00 B2008-04-13|22:31
LICENSE-2.0.txt11.09 kB2010-05-11|11:33
readme.txt521.00 B2010-05-11|11:32
01.96 kB
.classpath2.14 kB2010-05-06|13:08
.project385.00 B2010-05-06|13:06
01.96 kB
org.eclipse.jdt.core.prefs629.00 B2010-05-06|13:06
01.96 kB
application_view_tile.png465.00 B2006-03-12|21:48
readme.txt626.00 B2006-03-12|22:19
logging.properties1.29 kB2010-04-19|01:37
01.96 kB
01.96 kB
01.96 kB
01.96 kB
Board.java3.20 kB2010-05-09|22:26
IMonitor.java137.00 B2010-05-06|13:09
IntChPair.java676.00 B2010-05-06|13:09
IntPair.java662.00 B2010-05-06|13:09
MergedBoard.java2.89 kB2010-05-06|13:45
Piece.java3.13 kB2010-05-07|14:42
Point.java652.00 B2010-05-06|13:09
Program.java6.29 kB2010-05-11|03:07
Puzzle.java12.63 kB2010-05-10|03:05
RawPiece.java1.94 kB2010-05-06|14:49
Solution.java1.31 kB2010-05-10|02:56
Square.java661.00 B2010-05-06|13:23
Tile.java3.99 kB2010-05-07|13:43
01.96 kB
ImageUtil.java1.54 kB2010-05-06|13:10
MainDialog.java12.50 kB2010-05-07|14:32
PieceComposite.java1.80 kB2010-05-06|16:19
云测速

Puzzle.java (29.94 kB)

需要 1 积分
您持有 积分

CodeForge积分(原CF币)全新升级,功能更强大,使用更便捷,不仅可以用来下载海量源代码马上还可兑换精美小礼品了 了解更多

您的积分不足

支付宝优惠套餐快速获取 30 积分

订单支付完成后,积分将自动加入到您的账号。以下是优惠期的人民币价格,优惠期过后将恢复美元价格。

更多付款方式:网银PayPal

上传代码,免费获取

您本次下载所消耗的积分将转交上传作者。

同一源码,30天内重复下载,只扣除一次积分。

登录 CodeForge

还没有CodeForge账号? 立即注册
关注微博
联系客服

Switch to the English version?

Yes
CodeForge 英文版
No
CodeForge 中文版

完善个人资料,获价值¥30元积分奖励!

^_^"呃 ...

Sorry!这位大神很神秘,未开通博客呢,请浏览一下其他的吧
好的