dominoelimination.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>DominoElimination</code> method is an advanced solving method
 * which removes candidate values from a row or a column, if we know that 
 * a specific number in a major square(in MUSoSu usually is called box) is
 * certainly in a row or column, but we don't know in which square exactly<br />
 * After removing candidate values with the procedure described above, the 
 * method uses the "can't be elsewhere" routine to submit the revealed values.</p>
 * 
 * @author Visvardis Marios
 * @since version 0.8.5
 * @see <code>SolveMethod</code>, the parent class of all solving methods in sudoku_solver package.
 *
 */
public class DominoElimination extends SolveMethod{
	public DominoElimination(Sudoku game){
		super("Domino Elimination", SolveMethod.ADVANCED, game);
	}
	
	public int passOnce(){
		int contrib = 0;
		int[] r, c;
		int[] r1p, r2p, r3p, c1p, c2p, c3p;
		int box;
		
		solvedSquares.clear();
		
		for(box = 0; box < 9; box++){
			r = Convert.getRowsOnBox(box);
			c = Convert.getColumnsOnBox(box);
			r1p = getPossiblesInRow(r[0], c[0]);
			r2p = getPossiblesInRow(r[1], c[0]);
			r3p = getPossiblesInRow(r[2], c[0]);
			c1p = getPossiblesInCol(r[0], c[0]);
			c2p = getPossiblesInCol(r[0], c[1]);
			c3p = getPossiblesInCol(r[0], c[2]);
			
			for(int i = 0; i < 9; i++){
				if(r1p[i] == 1 && r2p[i] == 0 && r3p[i] == 0){
					removePossibleInRow(i + 1, r[0], c[0]);
				}else if(r2p[i] == 1 && r1p[i] == 0 && r3p[i] == 0){
					removePossibleInRow(i + 1, r[1], c[0]);
				}else if(r3p[i] == 1 && r1p[i] == 0 && r2p[i] == 0){
					removePossibleInRow(i + 1, r[2], c[0]);
				}
			}
			
			for(int i = 0; i < 9; i++){
				if(c1p[i] == 1 && c2p[i] == 0 && c3p[i] == 0)
					removePossibleInCol(i + 1, r[0], c[0]);
				else if(c2p[i] == 1 && c1p[i] == 0 && c3p[i] == 0)
					removePossibleInCol(i + 1, r[0], c[1]);
				else if(c3p[i] == 1 && c1p[i] == 0 && c2p[i] == 0)
					removePossibleInCol(i + 1, r[0], c[2]);
			}
		}
		
		// "Cannot be alsewhere" routine
		// repeatation does not cost too much...
		game.refreshPossibleMap();
		int mode, index, count, position = -1;
		for(int i = 0; i < 9; i++){
			for(mode = 0; mode < 3; mode++){
				for(int num = 1; num < 10; num++){
					count = 0;
					for(int j = 0; j < 9; j++){
						index = Convert.translateToIndex(mode, i, j);
						if(game.getPossibles(index).contains(num)){
							count++;
							position = index;
						}
					}
					if(count == 1){
						add(position, num);
						contrib++;
					}
				}
			}
		}	
		//--
		
		contribution += contrib;
		return contrib;
	}
	
	private void removePossibleInRow(int num, int row, int startCol){
		for(int i = 0; i < 9; i++){
			if(i < startCol || i > startCol + 2)
				game.setImpossible(num, Convert.kartesToIndex(row, i));
		}
	}
	
	private void removePossibleInCol(int num, int startRow, int col){
		for(int i = 0; i < 9; i ++)
			if(i < startRow || i > startRow + 2)
				game.setImpossible(num, Convert.kartesToIndex(i, col));
	}
	
	/**
	 * Provides the possible values for a row in a major square
	 * @param row the row that we examin.
	 * @param col the starting column.
	 * @return an array int[9] with 0 for values (index + 1) that are not
	 * possible in this row(inside a box) and 1 for the ones that are.
	 */
	private int[] getPossiblesInRow(int row, int col){
		int[] candidates = new int[9];
		int count;
		Vector<Integer> pos = null;
		for(int i = 0; i < 9; i++) 
			candidates[i] = 0;
		count = 0;
		while(count < 3){
			pos = game.getPossibles(Convert.kartesToIndex(row, col + count));
			if(pos != null)
				for(Integer val:pos)
					if(candidates[val.intValue() - 1] == 0)
						candidates[val.intValue() - 1] = 1;
			count++;
		}
		return candidates;
	}
	
	/**
	 * Provides the possible values for a column in a major square
	 * @param row the starting row.
	 * @param col the column that we examin.
	 * @return an array int[9] with 0 for values (index + 1) that are not
	 * possible in this column(inside a box) and 1 for the ones that are.
	 */
	private int[] getPossiblesInCol(int row, int col){
		int[] candidates = new int[9];
		int count;
		Vector<Integer> pos = null;
		for(int i = 0; i < 9; i++)
			candidates[i] = 0;
		count = 0;
		while(count < 3){
			pos = game.getPossibles(Convert.kartesToIndex(row + count, col));
			if(pos != null)
				for(Integer val:pos)
					if(candidates[val.intValue() - 1] == 0)
						candidates[val.intValue() - 1] = 1;
			count++;
		}
		return candidates;
	}
	
}