depthfirst.java

一个Java写的数独游戏

/*
 * This file is part of MUSoSu.
 *
 * MUSoSu is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, version 3 of the License.
 *
 * MUSoSu is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with MUSoSu.  If not, see <http://www.gnu.org/licenses/>.
 */

package sudokuSolver;

import java.util.Vector;

import sudoku.Sudoku;

/**
 * part of <b>MUSoSu</b>
 * <p><code>DepthFirst</code> A Brute Force - Depth First Solving method 
 * @author Visvardis Marios
 * @since version 0.8.4
 */
public class DepthFirst extends SolveMethod{
	private BFTMap record;
	public DepthFirst(Sudoku game){
		super("Depth First", SolveMethod.BRUTE_FORCE, game);
		this.record = new BFTMap();
	}
	
	public int passOnce(){
		startTimer();
		int contrib = 0, i = -1, value, index, check;
		Vector<Integer> tmpos = new Vector<Integer>();
		boolean error = false;
		
		game.setPersistantPossibles(false);
		
		while(!game.checkFull() && !error){
			i++;
			while(game.get(i) != 0)
				i++;
			if(i > 80) break;
			tmpos = game.getPossibles(i);
			if(tmpos.size() != 0){
				value = tmpos.get(0).intValue();
				game.add(value, i);
				add(i, value);
				contrib++;
				record.addRecord(i, 0);
			}else{
				check = -1;
				index = -1;
				while(check <= 0){
					game.remove(record.getLastAddPosition());
					remove(record.getLastAddPosition());
					index = record.getLastIndex();
					i = record.getLastAddPosition();
					record.stepBack();
					tmpos = game.getPossibles(i);
					check = tmpos.size() - index - 1;
				}
				if(index > -1){
					value = tmpos.get(index + 1).intValue();
					game.add(value, i);
					add(i, value);
					contrib++;
					record.addRecord(i, index + 1);
				}
			}
		}
		
		stopTimer();
		game.setPersistantPossibles(true);
		return contrib;
	}
}