solver.java

Sudoku游戏的原代码,以aop方式进行修改

/**
* Copyright 2005 Victor Ferrer
* 
* This file is part of FreeSudoku.
* 
* FreeSudoku 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; either version 2 of the License, or
* (at your option) any later version.
* 
* FreeSudoku 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 FreeSudoku; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA*
*/
package org.gos.freesudoku;

import java.util.*;

/**
 * @author gos
 *
 */
public class Solver
{

	private int[][] 	matriu 			= null;
	private int 		filled 			= 0;
	protected ArrayList solutions       = null;
    protected String    strategiesUsed  = null;
    protected int       difficulty      = 0;
    private static Hashtable cache    = null;

    /**
     * Comment for <code>posVals</code>
     * For each i,j position in board
	 * contains an array of posible values:
	 * posVals[i][j][0] -> number of posible values
	 * posvals[i][j][n] -> 1 if n is a posible value
	 *		where 1 <= n <= 9
     */
    private int[][][]	posVals			= null;
    
    /**
     * Comment for <code>groups</code>
     * There are 27 groups of 9 cells; 9 rows + 9 columns + 9 3x3_blocks 
     * For each group we can apply the different strategies.
     * Each position is just a pointer to a posVals element. 
     */
    private int[][][]   groups          = null;
    
	

	public Solver()
	{
		matriu            = new int[9][9];
		solutions         = new ArrayList();
		posVals       	  = new int[9][9][10];
        if( cache == null) cache = new Hashtable();
	}
    
    protected void setMatriu(int[][] pMatriu)
    {
        strategiesUsed    = "";
        difficulty = 0;
    	filled = 0;
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                matriu[i][j] = pMatriu[i][j];
                if( matriu[i][j] != 0) filled++;
            }
        }
        fillPosVals();
        setGroups();
//        CONSTS.log( " *** Matriu initializated:\n" + matriuToString( matriu));
    }
	
    private void setGroups()
    {
        groups = new int[27][9][];
        int cont = 0;

        for (int n = 0; n < 9; n++)
        {
            // add rows
            for (int m = 0; m < 9; m++)
            {
                groups[cont][m] = posVals[n][m];
            }
            cont++;

            // add cols
            for (int m = 0; m < 9; m++)
            {
                groups[cont][m] = posVals[m][n];
            }
            cont++;
        }
        
        // add boxes
        for (int i = 0; i < 9; i+=3)
        {
            for (int j = 0; j < 9; j+=3)
            {
                groups[cont][0] = posVals[i][j];               
                groups[cont][1] = posVals[i][j+1];             
                groups[cont][2] = posVals[i][j+2];             
                groups[cont][3] = posVals[i+1][j];             
                groups[cont][4] = posVals[i+1][j+1];               
                groups[cont][5] = posVals[i+1][j+2];               
                groups[cont][6] = posVals[i+2][j];             
                groups[cont][7] = posVals[i+2][j+1];               
                groups[cont][8] = posVals[i+2][j+2];
                cont++;
            }
        }
        
    }
    
    protected int getAllSols()
    {
        int sols = 0;
        if( filled == 81) 
        { 
            CONSTS.log( "************* SOLUCIO ********************\n" + matriuToString( matriu));
        	solutions.add( dupArray( matriu));
            return 1;
        }
        CONSTS.log(" ++++  Filled: " + filled);
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if( matriu[i][j] == 0)
                {
                    ArrayList arrayPos = Game.getCorrectValsForArray( i, j, matriu);
                    if( arrayPos.isEmpty()) 
                    {
                        CONSTS.log(" ------ 0   No posible number! " + i + " " + j);
                        return 0;
                    }
                }
            }
        }

        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if( matriu[i][j] == 0)
                {
                    CONSTS.log( matriuToString( matriu));
                    ArrayList arrayPos = Game.getCorrectValsForArray( i, j, matriu);

                    filled++;
                    for (int n = 0; n < arrayPos.size(); n++)
                    {
                        matriu[i][j] = ((Integer )arrayPos.get( n)).intValue();
//                        CONSTS.log("Checking " + i + " " + j + " " + matriu[i][j] + " Filled: " + filled);
                        sols += getAllSols();
                    }
                    matriu[i][j] = 0;
                    filled--;
//                    CONSTS.log(" ----- Checked " + i + " " + j + " sols: " + sols);
                    return sols;
                }
            }
        }
//        CONSTS.log(" ------ End check matriu: sols" + sols + "\n" + matriuToString( matriu));
        return sols;
    }

    
    protected static int[][] dupArray(int[][] pArray)
	{
    	int[][] res = new int[9][9];
    	for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
            	res[i][j] = pArray[i][j];
            }
        }
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		int[][] aux = 
		{

//				 2 9 7 4 1 8 6 3 5
//				 5 8 1 9 3 6 7 4 2
//				 6 4 3 2 5 7 8 1 9
//				 9 5 8 7 2 3 1 6 4
//				 3 1 4 5 6 9 2 7 8
//				 7 2 6 1 8 4 5 9 3
//				 4 7 5 6 9 2 3 8 1
//				 1 3 9 8 7 5 4 2 6
//				 8 6 2 3 4 1 9 5 7

                {0,0,0,0,0,0,1,0,7},
                {0,7,0,0,0,6,0,3,0},
                {2,0,0,7,0,0,5,0,0},
                {0,0,4,1,2,0,6,5,0},
                {3,0,0,0,0,0,0,0,1},
                {0,5,7,0,3,8,4,0,0},
                {0,0,1,0,0,3,0,0,5},
                {0,6,0,8,0,0,0,4,0},
                {5,0,9,0,0,0,0,0,0}
        };
        
//        matriuFromKey(  "010900000" +
//                        "820706010" +
//                        "075000200" +
//                        "060800000" +
//                        "109000507" +
//                        "000001040" +
//                        "006000870" +
//                        "040508029" +
//                        "000007060");
				
		
		Solver solver = new Solver();
        solver.setMatriu( aux);
        solver.resetCache();
        CONSTS.log( solver.posibleValsToString());
        boolean changed = false;
        solver.loopAllStg();
        CONSTS.log( solver.toString());
        CONSTS.log( "Filled: " + solver.filled);
        CONSTS.log( solver.strategiesUsed);
        CONSTS.log( "Diff: " + solver.difficulty);
	}

    public static String matriuToString( int[][] pArray)
    {
        StringBuffer res = new StringBuffer();
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                res.append( " " + pArray[i][j]);
            }
            res.append("\n");
        }
        return res.toString();
    }
    
    protected static String matriuToKey( int[][] pArray)
    {
        StringBuffer res = new StringBuffer();
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                res.append( pArray[i][j]);
            }
        }
        return res.toString();
    }
    
    protected static int[][] matriuFromKey( String key)
    {
        int[][] res = new int[9][9]; 
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                res[i][j] = Integer.parseInt( String.valueOf( key.charAt( i*9 + j)));
            }
        }
        return res;
    }
    
	private boolean applyStrategy_2()
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (matriu[i][j] != 0) continue;
                if (posVals[i][j][0] == 1)
                {
                	for (int k = 1; k <= 9; k++)
					{
						if( posVals[i][j][k] == 1) 
						{
							setVal( i, j, k);
                            logStrategy(2);
                            return true;
						}
					}
                }
            }
        }
//        CONSTS.log( this.toString());
        return false;
    }
    protected void setVal(int i, int j, int val)
	{
    	if( matriu[i][j] != 0 || val<=0) 
    		throw new RuntimeException("Cant setVal " + val);
    	matriu[i][j] = val;
  	  	filled++;
//    	CONSTS.log("setVal " + i + " " + j + " -> " + val + " filled: " + filled);
  	  	checkPosibleValsFor( i, j, val);
	}

	private void checkPosibleValsFor(int i, int j, int val)
	{
    	Arrays.fill( posVals[i][j], 0);	// remove all posible vals
		posVals[i][j][0] = -val;  		
		removeNumFromRow( val, i, -1);  // remove from all 3 boxes
		removeNumFromCol( val, j, -1);  // remove from all 3 boxes
		removeNumFromBox( val, i, j, -1, -1);
	}

	private boolean applyStrategy_1()
	{
		// TODO: recode to check per blocks and call subrutine...
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				if (matriu[i][j] != 0) continue;
				for (int n = 1; n <= 9; n++)
				{
					if(posVals[i][j][n] != 1) continue;
					boolean found;

					// check block
					found = false;
					for (int x = i - i%3; x < i - i%3 + 3; x++)
					{
						for (int y = j - j%3; y < j - j%3 + 3; y++)
						{
							if ((x == i && y == j) || matriu[x][y] != 0)
								continue;
							if ( posVals[x][y][n] == 1)
							{
								found = true;
								break;
							} 
						}
						if( found) break;
					}
					if (!found)
					{
						setVal( i, j, n);
                        logStrategy(1);
						return true;
					}

					// check row
					found = false;
					for (int x = 0; x < 9; x++)
					{
						if (x == j || matriu[i][x] != 0)
							continue;
						if ( posVals[i][x][n] == 1 )
						{
							found = true;
							break;
						}
					}
					if (!found)
					{
						setVal( i, j, n);
                        logStrategy(1);
                        return true;
					}

					// check column
					found = false;
					for (int x = 0; x < 9; x++)
					{
						if (x == i || matriu[x][j] != 0)
							continue;
						if ( posVals[x][j][n] == 1)
						{
							found = true;
							break;
						}
					}
					if (!found)
					{
						setVal( i, j, n);
                        logStrategy(1);