pairanalysis.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.Convert;
import sudoku.Sudoku;

/**
 * part of <b>MUSoSu</b>
 * <p>
 * <code>PairAnalysis</code> is a solving/analysis method for resolving square 
 * values after dismissing some exististing candidate values.</p>
 * <p>The later is done in method <code>excludePossibles</code>, where for each
 * line, column, box(major square), for each square that has exactly two candidate 
 * values, we search for a matching square(pair) with the same two
 * candidates. The candidate values of these squares are set no longer candidates
 * of the remaining unfilled squares of the line/column/box.</p>
 * <p>With this method moderate to advanced sudokus are solved.</p>
 * @author Visvardis Marios
 * @version 0.2
 * @see <code>SolveMethod</code>
 */
public class PairAnalysis extends SolveMethod{
	public PairAnalysis(Sudoku game){
		super("Pairs Analysis", SolveMethod.MODERATE, game);
	}
	
	private int getWhere(int mode, int a, int b){
		int ret = -1;
		switch(mode){
		case 0:
			ret = Convert.kartesToIndex(a, b);
			break;
		case 1:
			ret = Convert.kartesToIndex(b, a);
			break;
		case 2:
			ret = Convert.koutiaToIndex(a, b);
			break;
		}
		return ret;
	}
	
	public int excludePossibles(){
		Vector<Pair> pairs = new Vector<Pair>();
		Vector<Integer> pos = new Vector<Integer>();
		int i, j, k, l, m, n, a, b, blanks;
		int where = 0, mode = 0;
		int found = 0;
		
		for(i = 0; i < 9; i++){
			for(mode = 0; mode < 3; mode++){
				pairs.clear();
				int th = 0;
				blanks = 0;
				for(j = 0; j < 9; j++){
					where = this.getWhere(mode, i, j);
					if(game.get(where) == 0 && !game.isFixed(where)){
						blanks++;
						pos = game.getPossibles(where);
						if(pos.size() == 2){
							Pair p = new Pair(j, pos.get(0).intValue(), pos.get(1).intValue());
							pairs.add(th, p);
							th++;
						}
					}
				}
				for(k = 0; k < (pairs.size() - 1) && blanks > 2; k++){
					for(l = k + 1; l < pairs.size(); l++){
						if(pairs.get(k).compare(pairs.get(l))){
							m = pairs.get(k).getIndex(); 
							n = pairs.get(l).getIndex();
							a = pairs.get(k).getA(); b = pairs.get(k).getB();
							for(int tmp = 0; tmp < 9; tmp++){
								if(tmp != m && tmp != n){
									where = getWhere(mode, i, tmp);
									if((!game.isFixed(where)) && game.get(where) == 0){ 
										game.setImpossible(a, where);
										game.setImpossible(b, where);
										found++;
									}
								}
							}
						}
					}
				}
			}
		}
		return found;
	}
	
	
	public int passOnce(){
		startTimer();
		int contrib = 0;
		Vector<Integer> possibles;
		solvedSquares.clear();
		game.refreshPossibleMap();
		if(excludePossibles() != 0){
			excludePossibles();
			for(int i = 0; i < 81; i++){
				if((possibles = game.getPossibles(i)).size() == 1 && game.get(i) == 0){
					add(i, possibles.get(0));
					contrib++;
				}
			}	
		}
		contribution += contrib;
		stopTimer();
		return contrib;
	}
}

class Pair{
	private int a;
	private int b;
	private int index;
	
	public Pair(int index, int a, int b){
		this.index = index;
		this.a = a;
		this.b = b;
	}
	
	public int getIndex(){return index;}
	public int getA(){return a;}
	public int getB(){return b;}
	
	public boolean compare(Pair p){
		if((a == p.getA() &&  b == p.getB()))
			return true;
		else
			return false;
	}
}