solver.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><b><code>Solver</code></b> class provides hinting, solving, custom solving
 * of sudokus and other helper methods.
 * @author Visvardis Marios
 * @since MUSoSu version 0.8.2
 * @see <code>Sudoku</code> class
 */
public class Solver {
	private Sudoku gameCopy;
	private SolveMethod[] solvers;
	private Vector<SolvedSquare> solvedSquares; 
	private int[] selected;
	private boolean completed;
	private Sudoku original;
	
	public Solver(){
		solvers = new SolveMethod[7];
		solvedSquares = new Vector<SolvedSquare>();
	}
	
	public void setGame(Sudoku game){
		this.original = game;
		this.gameCopy = new Sudoku(game);
		solvers[0] = new EliminationA(gameCopy);
		solvers[1] = new EliminationB(gameCopy);
		solvers[2] = new CantBeElsewhere(gameCopy);
		solvers[3] = new PairAnalysis(gameCopy);
		solvers[4] = new HiddenPairs(gameCopy);
		solvers[5] = new DominoElimination(gameCopy);
		solvers[6] = new DepthFirst(gameCopy);
		gameCopy.setPersistantPossibles(true);
	}
	
	private void copyPossiblesToOriginal(){
		for(int i = 0; i < 81; i++){
			original.setPossibles(i, gameCopy.getPossibles(i));
		}
		original.setPersistantPossibles(true);
		gameCopy.setPersistantPossibles(true);
	}
	
	public boolean isCompleted(){return completed;}
	
	private boolean isSelected(int index){
		for(int i = 0; i < selected.length; i++)
			if(selected[i] == index)
				return true;
		return false;
	}
	
	public int getNumberOfMethods(){
		return solvers.length;
	}
	
	public String getMethodName(int index){
		return solvers[index].getName();
	}
	
	public int getMethodType(int index){
		return solvers[index].getType();
	}
	
	public int getMethodContribution(int index){
		return solvers[index].getMethodContribution();
	}
	
	/**
	 * <p>Method <b><code>void solve()</code></b> is used to automatically
	 * solve a sudoku, using all the solving methods available in solvers[] array.
	 * <br> The total time required for solving can be provided by
	 * <code>getTotalTimeSecs()</code> method.
	 * @see solveWithSelectedMethods
	 * @see getHint 
	 * @since MUSoSu version 0.8.3
	 */
	public void solve(){
		int i = 0;
		int c = 0;
		while(i < solvers.length){
			c = runMethod(solvers[i]);
			i++;
			if(c != 0) i = 0;
		}
		if(gameCopy.checkFull()){
			completed = true;
		}
	}

	public void solveWithSelectedMethods(int[] selection){
		this.selected = selection;
		int i = 0;
		while(i < solvers.length){
			if(isSelected(i)){
				if(runMethod(solvers[i]) != 0)
					i = 0;
				else
					i++;
			}else{
				i++;
			}
		}
		if(!gameCopy.checkFull()){
			completed = true;
		}
	}
	
	public double getTotalTimeSecs(){
		double time = 0;
		for(int i = 0; i < solvers.length; i++)
			time += solvers[i].getTotalTimeSecs();
		return  time;
	}
	
	public long getTotalTimeMillis(){
		long time = 0;
		for(int i = 0; i < solvers.length; i++)
			time += solvers[i].getTotalTimeMillis();
		return time;
	}
	
	public long getMethodUptimeMillis(int methodIndex){
		return solvers[methodIndex].getTotalTimeMillis();
	}
	
	public int runMethod(SolveMethod sm){
		int contrib = 0;
		Vector<SolvedSquare> sqv = null;
		if((contrib = sm.passOnce()) != 0){
			sqv = sm.getSolvedSquares();
			if(sqv == null) return 0;
			for(SolvedSquare ssq: sqv){
				addToGame(ssq.getValue(), ssq.getIndex());
				solvedSquares.add(ssq);
			}
		}
//		copyPossiblesToOriginal();
		return contrib;
	}
	
	private void addToGame(int number, int index){
		gameCopy.add(number, index);
	}
	
	public Vector<SolvedSquare> runMethodStandalone(int index){
		Vector<SolvedSquare> ssq = null;
		if(solvers[index].passOnce() != 0){
			copyPossiblesToOriginal();
			ssq = solvers[index].getSolvedSquares();
		}
		copyPossiblesToOriginal();
		return ssq;
	}
	
	public Sudoku getBoard(){
		return gameCopy;
	}
	
	public Vector<SolvedSquare> getSolvedSquares(){
		return solvedSquares;
	}
	
	public double estimateDifficulty(){
		double ret;
		int i = 0;
		int c = 0;
		int easy = 0, medium = 0, advanced = 0, evil = 0;
		while(i < solvers.length - 1){
			c = runMethod(solvers[i]);
			if(c != 0){
				switch(solvers[i].getType()){
				case SolveMethod.ELIMINATION:
					easy++; break;
				case SolveMethod.MODERATE:
					medium++; break;
				case SolveMethod.ADVANCED:
					advanced++; break;
				case SolveMethod.EVIL:
					evil++; break;
				case SolveMethod.BRUTE_FORCE:
					ret = -1; break;
				}
				i = 0;
			}
			i++;
		}
		if(gameCopy.checkFull()){
			completed = true;
			ret = ((double)(easy + 5 * medium + 20 * advanced + 40 * evil)) / 6;
			if(ret > 8 && advanced == 0 && evil == 0) ret = 8;
			if(ret > 10) ret = 10;
		}else{
			ret = 11;
		}
		return ret;
	}
	
	public SolvedSquare getHint(){
		int i = 0;
		while(i < solvers.length && !gameCopy.checkFull()){
			if(runMethod(solvers[i]) != 0){
				 return solvers[i].getSolvedSquares().get(0);
			}else{
				i++;
			}
		}
		return null;
	}
}