gamedata.java

sudoku j2me手机游戏主要有游戏主类和闪屏类菜单类和模型类等

			else
			{	//System.out.println("B:"+val);
				dos.writeShort((short)val);
			}
			//System.out.println( val+" "+(start%gridSz)+","+(start/gridSz)+" "+(i%gridSz)+","+(i/gridSz) );
		}
	}
	private static int _findRepeat_16(short[][] arr,int start)
	{	int gridSz=arr.length;
		int end=start;
		int val=arr[start%gridSz][start/gridSz];
		while
		(	end<gridSz*gridSz && 			// Smaller than grid?
			end<=0x7fff &&					// Smaller than max repeat token size
			arr[end%gridSz][end/gridSz]==val // Same value?
		)  end++;
		return end;
	}
	private static void _writeBools(boolean[][] arr,DataOutputStream dos) throws IOException
	{	int gridSz=arr.length;
		int l=gridSz*gridSz;
		short[] buff = new short[((l%8)==0) ? l/8 : l/8+1];
		// -----Pack booleans into byte array, using bit twiddling
		for(int i=0;i<l;i++)
		{	if(arr[i%gridSz][i/gridSz])
				buff[i/8] |= (1 << (7-(i%8)));
		}
		// -----Write out byte array
		for(int i=0;i<buff.length;i++)
			dos.writeByte((byte)(buff[i]&0xff));
	}
	private static void _writeASCIIString(String s,int sz,DataOutputStream dos) throws IOException
	{	// -----Chop string to max length if necessary
		if(s.length()>sz)  s=s.substring(0,sz);
		// -----Write bytes
		for(int i=0;i<s.length();i++)
			dos.writeByte(s.charAt(i) & 0x7f);
		// -----If smaller than max size, zero terminate
		if(s.length()<sz)  dos.writeByte(0);
	}


	// -----------------------------------------------------------------
	// Update/set the collision boolean array, which shows duplicate
	// values on the grid.
	// -----------------------------------------------------------------
	void updateCollisions(int x,int y)
	{	for(int a1=0;a1<gridSz;a1++)
			for(int a2=0;a2<gridSz;a2++)  collisions[a1][a2]=false;
		_findCollisions(x,y);
	}

	boolean findAllCollisions() {	
        boolean collision_found=false;
        
        for(int y=0;y<gridSz;y++) {
			for(int x=0;x<gridSz;x++)  {
                if (_findCollisions(x,y)) {
                    collision_found=true;
                }
            }
        }
        return collision_found;
	}

    // return true if collisions have been found (empty cells count as true)
	private boolean _findCollisions(int x,int y) {	
        boolean retval=false;
        int val=grid[x][y];

		if(val==0)  return true;					// Don't do empty cells
		int sox=x-(x%setW) , soy=y-(y%setH); // Set subgrid offset
		for(int a=0;a<gridSz;a++)
		{	// -----Vertical
			if(grid[x][a]==val && a!=y)  {
                collisions[x][a]=true;
                retval=true;
            }
			// -----Horizontal
			if(grid[a][y]==val && a!=x)  {
                collisions[a][y]=true;
                retval=true;
            }
			// -----Set
			int sx=a%setW , sy=a/setW;		// Position in set subgrid
			sx+=sox;  sy+=soy;
			if(grid[sx][sy]==val && sx!=x && sy!=y)  {
                collisions[sx][sy]=true;
                retval=true;
            }
		}
        return retval;
	}

    // ============================================================ working calculations ======================================
    // toggles the i'th bot of the working array
    // bits 0 ... gridSz-1 are used to represent possible values
	void toggleWorking(int x,int y,int i) {	
        working[x][y] ^= (1<<i);
	}

    // fills in the working array - for any unfilled cells, the working array is filled 
    // The concept is to form bit-masks which are then and-ed together to complete the working array
    void createWorking() {
        createWorking(grid, working);
    }
    // Provide a version which uses custom inputs and outputs - useful in a solver
    void createWorking(byte [][] inGrid, short[][] outWorking) {
        short initValue = (short)((1 << gridSz) - 1); // corresponds to a working where everything is selected
        short rowmask,colmask,blockmask;    //masks for row/col/block
        int numBlockX=gridSz/setW;
        // fill outWorking with inital values (1's or 0's depending on whether the cell is filled
        for(int y=0;y<gridSz;y++) {
			for(int x=0;x<gridSz;x++)  {
                if (inGrid[x][y]>0) {
                    // cell is already filled
                    outWorking[x][y] = 0;
                } else {
                    outWorking[x][y] = initValue;
                }
            }
        }


        // next step cycle over row/col/blocks, creating masks and then applying them to all cells
        for (int i=0; i < gridSz; i++) {
            int j;
            // Create masks
            rowmask = colmask = blockmask = initValue;
			int sox=(i%numBlockX)*setW , soy=(i/numBlockX)*setH;		// Position in set subgrid
            for (j = 0; j < gridSz; j++) {
                if(inGrid[i][j] > 0)  rowmask &= ~(1 << (inGrid[i][j] - 1));
                if(inGrid[j][i] > 0)  colmask &= ~(1 << (inGrid[j][i] - 1));
                if(inGrid[sox+(j%setW)][soy+(j/setW)] > 0)  blockmask &= ~(1 << (inGrid[sox+(j%setW)][soy+(j/setW)] - 1));
            }

            // apply masks to cells
            for (j = 0; j < gridSz; j++) {
                outWorking[i][j] &= rowmask;
                outWorking[j][i] &= colmask;
                outWorking[sox+(j%setW)][soy+(j/setW)] &= blockmask;
            }
		}
    }

    // given a correct working grid, set a new value in the Grid, and update the working
    // newVal has range 1 .. gridSz
    void updateWorking(int newVal, int x, int y) {
        updateWorking(newVal,x,y,grid,working);
    }

    void updateWorking(int newVal, int x, int y, byte[][] inGrid, short[][] outWorking) {
        byte oldVal = inGrid[x][y];
        if ((byte)newVal == oldVal) {
            return;
        }
        inGrid[x][y] = (byte) newVal;
        if (oldVal != 0) {
            // simply re-create the Working. recalculating just the affected cells would still need a scan of the whole
            // array.  Although slightly fewer calculations would be needed, it doesnt seem worth the effort
            createWorking(inGrid, outWorking);
        } else if (newVal > 0) {
            outWorking[x][y] = 0;
            short mask=(short) ~(1 << (newVal-1));
            int sox=x-(x%setW) , soy=y-(y%setH); // Set subgrid offset

            for(int a=0;a<gridSz;a++) {	
                outWorking[x][a] &= mask;
                outWorking[a][y] &= mask;
                outWorking[sox+(a%setW)][soy+(a/setW)] &= mask;
            }
        }
    }

    // update the working value for this one cell
    // Note - this should not be used to update more than gridSz cells at once - for that it is more effective to
    // recreate the whole working array
    void updateWorkingCell(int x, int y) {
        int myWorking = 0; 
        int sox=x-(x%setW);
        int soy=y-(y%setH); // Set subgrid offset
        for (int i=0; i < gridSz; i++) { 
            myWorking |= (1 << grid[i][y]);
            myWorking |= (1 << grid[x][i]);
            myWorking |= (1 << grid[sox+(i%setW)][soy+(i/setW)]);
        }
        myWorking >>= 1; // compensate that the grid is 1 ... gridSz but working is 0 ... (gridSz-1)
        working[x][y] = (short) ((~myWorking) & ((1 << (gridSz+1))-1));
    }


    // ======================================================= solving ======================================
    int solve() {
        return solve(grid);
    }

    // returns the number of solutions found if a solution is found, the grid is updated with the first solution found.
    // solver works on a depth-first search mechanism
    // First calculate the working of this grid
    // search all cells for the cell with the lowest (non-zero) number of 1's in the working (binary) (gives x,y)
    //     (if during search you find a working with zero 1's and the grid at that x,y is not set, pop from the stack
    //     and try the next working.  If the stack is empty, return false)
    //     (if during the search you find out all cells are completed, return true)
    // if only 1 '1' exists, set this cell to the corresponding value, update the working and repeat
    // otherwise pick a valid value for x,y. remove this value from the working and push this on the
    //     stack. set x,y to this value, update working and repeat.

    class SolutionStack {
        byte grid[][];
        short working[][];
        int x,y,numWorking;
        SolutionStack next;
    
        void push(byte inGrid[][], short inWorking[][], int inX, int inY, int inNumWorking) {
            SolutionStack newElem=new SolutionStack();
            newElem.grid = new byte[gridSz][gridSz];
            newElem.working = new short[gridSz][gridSz];
            for (int x=0;x<gridSz; x++) {
                for (int y=0;y<gridSz;y++) {
                    newElem.grid[x][y] = inGrid[x][y];
                    newElem.working[x][y] = inWorking[x][y];
                }
            }
            newElem.x=inX;
            newElem.y=inY;
            newElem.numWorking=inNumWorking;
            newElem.next=head;
            head=newElem;
        }
    
        boolean hasMoreElements() {
            return (head.grid != null);
        }

        SolutionStack pop() {
            SolutionStack retVal;
            retVal = head;
            if (hasMoreElements()) {
                head = head.next;
                retVal.next = null;
            } 
            return retVal;
        }
    } 

    private SolutionStack head;

    int solve(byte inGrid[][]) {
        return solve(inGrid, DEFAULT_MAX_SOLUTIONS);
    }

    int solve(byte inGrid[][], int maxSolutions) {
        short curWorking[][] = new short[gridSz][gridSz];
        byte curGrid[][] = inGrid;
        int x,y,numWorking;                    // stores current position of scan
        int bestX,bestY,bestNumWorking; // stores position of cell with fewest working options
        boolean solved;                 // tracks if the grid is solved
        int newVal;
        int numSolutions=0;
        //int iterationCount=0;
        head = new SolutionStack();

        head.next = null;
        head.grid = null;
        head.working = null;

        createWorking(curGrid, curWorking);
        while (true) {
            // find cell with fewest workings
            solved = true;   // this is true until we find an uncompleted cell
            bestX = bestY = -1;
            bestNumWorking = gridSz+1;

            // if (SudokuME.debug) System.out.println("solve: starting iteration " + iterationCount++);
            /* Print out the solving grid each iteration
            for (y=0;y<gridSz; y++) {
                for (x=0;x<gridSz;x++) {
                    if (curGrid[x][y] > 0) {
                        System.out.print(curGrid[x][y]);
                    } else {
                        System.out.print(".");
                    }
                }
                System.out.println();
            }
            */
thisIteration:
            for (x=0;x<gridSz; x++) {