~eda-qa/dhlib/main

/* <license>
 * This file is part of the dis-Emi-A HaXe Library. Copyright © edA-qa mort-ora-y
 * For full copyright and license information please refer to doc/license.txt.
 * </license> 
 */
package sudoku;

import mathx.Matrix;
import mathx.MatPoint;

/**
 * The board is the logical construct of the grid and all
 * the numbers which it contains
 */
class Board extends Matrix<Int>
{
	/**
	 * Creates a new board, either from the provided data, or completely
	 * empty.
	 */
	public function new( ?fromData : Matrix<Int> )
	{
		if( fromData == null )
		{
			fromData = Matrix.create( GConst.boardSize, GConst.boardSize, GConst.cellUnset );
		}
		else
		{
			Assert.isTrue( fromData.size.x == GConst.boardSize );
			Assert.isTrue( fromData.size.y == GConst.boardSize );
		}
		super( fromData );		
			
	}

	/**
	 * Determines if all values have been filled in
	 */
	public function isComplete() : Bool
	{
		for( x in 0...GConst.boardSize )
			for( y in 0...GConst.boardSize )
				if( get( x, y ) == GConst.cellUnset )
					return false;
		return true;
	}
	
	/**
	 * Determines whether the board so far is part of a valid solution,
	 * that is, are all the values currently in place in order.  Empty cells
	 * are just skipped, use isComplete to determine if the board is 
	 * complete.
	 */
	public function isValid() : Bool
	{
		//NOTE: There are quicker ways to check for validity other than
		//generating the matrix, but we don't need that optimization now
		var m = getValidityMatrix();
		for( mp in m.xOrderIter() )
			if( !m.get(mp.x,mp.y) )
				return false;
		return true;
	}
	
	/**
	 * Creates a matrix showing the validity of every cell (based on simple
	 * calculations of the duplication of numbers.
	 * In the returned matrix true indicates valid, or empty, false indicates
	 * invalid (and it will always come in a pair)
	 */
	public function getValidityMatrix() : Matrix<Bool>
	{
		var ret = Matrix.create( GConst.boardSize, GConst.boardSize, true );
		
		//do the rows/columns
		for( row in [true, false] )
		{
			for( i in 0...GConst.boardSize )
			{
				var line = row ? extractRow( i ) : extractCol( i );
				var count = ArrayUtil.countElementsInt( line );
				
				//mark as invalid
				for( j in 0...GConst.boardSize )
				{
					var c = get( row ? j : i, row ? i : j );
					if( c == GConst.cellUnset )
						continue;
					if( c < GConst.cellLow || c > GConst.cellHigh 	
						|| count.get(c) > 1 )
						ret.set( row ? j : i, row ? i : j, false );
				}
			}
		}
		
		//do the groups
		for( gx in 0...GConst.numGroups )
			for( gy in 0...GConst.numGroups )
			{
				//count
				var line = new Array<Int>();
				for( mp in 
					subIter( 
						MatPoint.at( gx * GConst.groupSize, gy * GConst.groupSize ),
						MatPoint.at( GConst.groupSize, GConst.groupSize )
						)
					)
					line.push( get( mp.x, mp.y ) );
				var count = ArrayUtil.countElementsInt( line );
				
				//mark as invalid
				for( mp in 
					subIter( 
						MatPoint.at( gx * GConst.groupSize, gy * GConst.groupSize ),
						MatPoint.at( GConst.groupSize, GConst.groupSize )
						)
					)
				{
					var c = get( mp.x, mp.y );
					if( c == GConst.cellUnset )
						continue;
					if( c < GConst.cellLow || c > GConst.cellHigh 	
						|| count.get(c) > 1 )
						ret.set( mp.x, mp.y, false );
				}
			}
		
		return ret;
	}
	
	/**
	 * Creates a random filled Sudoku board.  All existing data will
	 * be lost.
	 *
	 * This works by creating a short random diagonal seed, then
	 * combining those seeds to fill in the remaining spots.  Only the
	 * first two diagonals are set since if more are set there is a possibility
	 * that the board is unsolvable.
	 * In theory we don't even need a seed, the solve algorithm could 
	 * simply randomly order it's available values and then a solution
	 * of an empty board would be okay.  The seed here is thus to break
	 * any pattern which may occur in the solver logic.
	 */
	public function fillRandom() : Int
	{
		var seed = [createRandomGroup(),createRandomGroup()];
		
		//fill in first two diagonals, the seed of the board
		replace( Matrix.create( GConst.boardSize, GConst.boardSize, 0 ) );
		for( i in 0...2 )
			paste( 
				i * GConst.groupSize, 
				i * GConst.groupSize,
				seed[i]
				);
		var at = findSolution();
		Assert.isFalse( at == -1 );
		return at;
	}
	
	/**
	 * Attempts to find a solution for the current Board state.
	 *
	 * NOTE: This is not a great solver, in that it can't actually solve many
	 * boards (though it seems to always be able to solve our fillRandom
	 * scenario, which is all we needed it for).  Sudoku is just a graph-coloring
	 * problem, so a proper solution would really just be a special coloring
	 * algorithm.  I do however suspect with a bit of back-tracking code
	 * here (rather than random retesting) this might also work reasonably
	 * well (though whether it always works would be in question)
	 *
	 * @return	[out] the count of how many iterations were tested before
	 *		a solution was found, -1 if not solution was found (which doesn't
	 *		necessarily mean none exists, just that the current algorithm can't
	 *		find it)
	 */
	public function findSolution() : Int
	{
		//make backup
		var backup = clone();
		
		//loop since we still have an ordering problem in the solver, which
		//occassionally doesn't choose the right items first -- randomizing
		//the order of those items helps, and in a loop of 10K creations
		//no invalid boards were created, thus I suspect there must be some
		//simple change to the ordering to make it work...
		
		/* No such ordering has yet been found, and counting the number
		 * of choices made there looks to be a staggering number of 
		 * possible options for even a 2-diagonal seed. TODO: check
		 * existing literature for solution, or demonstration of NP-completness
		 * Since a loop of 10 works, I'm guessing most choices are irrelevant
		 * and only in a few cases does it make the board unsolvable -- which
		 * would be then like Minesweeper: usually simple games, other
		 * times virtually impossible (though rare)
		 */
		 
		/* Further interesting, the SolveStep is usually zero, and virtually
		 * never higher than one, which would strengthen the claim that
		 * in most choice situations the choice made is irrelevant
		 * By 10K: [9606, 383, 10, 1, 0, 0, 0, 0, 0, 0] (from zero seed)
		 */
		for( i in 0...10 )
		{
			if( solve() )
				return i;
				
			replace( backup );
		}
		
		return -1;
	}
	
	private var solveRemain : Int;
	private function solve() : Bool
	{
		//setup a grid of allowed values first
		var baseSet = ArrayUtil.incList( GConst.cellLow, GConst.cellHigh );
		var solveAllow = Matrix.create( GConst.boardSize, GConst.boardSize, baseSet );
		for( mp in solveAllow.xOrderIter() )
			solveAllow.set( mp.x, mp.y, baseSet.copy() );
			
		//setup total possibility counts (number of cells on Board where a number could still appear)
		solveRemain = GConst.boardSize * GConst.boardSize;
		var poss = new Array<Int>();
		var iPoss = GConst.boardSize * GConst.boardSize;
		for( i in GConst.cellLow...(GConst.cellHigh+1) )
			poss[i] = iPoss;
			
		//setup group possibility number counts (number of cells in a group where a number could still appear)
		var basePoss = new Array<Int>();
		var igPoss = GConst.cellRange;
		for( i in GConst.cellLow...(GConst.cellHigh+1) )
			basePoss[i] = igPoss;
		var possInGroup = Matrix.create( GConst.numGroups, GConst.numGroups, basePoss );
		for( mp in possInGroup.xOrderIter() )
			possInGroup.set( mp.x, mp.y, basePoss.copy() );
		
		//setup remaining cells per group
		var remainInGroup = Matrix.create( GConst.numGroups, GConst.numGroups, GConst.cellRange );
		
		//remove existing elements in line/column
		for( y in 0...GConst.boardSize )
			for( x in 0...GConst.boardSize )
				solvePlace( get( x, y ), x, y, solveAllow, poss, remainInGroup, possInGroup );
			
		var remain = solveRemain;	//afterwards count in solvePlace may be wrong
		
		//now, loop over the group allow numbers, and work on the target
		//with the lowest count next always.
		var totalChoiceCount = 0;
		for( i in 0...remain )
		{
			//get smallest group
			var gc = GConst.cellRange+1;
			var ggc = GConst.cellRange+1;	//TODO: actually only 10 is needed
			var at = null;
			for( mp in solveAllow.xOrderIter() )
			{
				var l = solveAllow.get(mp.x,mp.y);
				var gx = Math.floor( mp.x / GConst.groupSize );
				var gy = Math.floor( mp.y / GConst.groupSize );
				if( l.length > 0 && ( l.length < gc 
					//|| (l.length == gc && mathx.Random.s_nextBool()) ) //add random order to those of equal length
					|| (l.length == gc
					&& remainInGroup.get( gx, gy ) < ggc ) )
					)
				{
					gc = solveAllow.get(mp.x,mp.y).length;
					ggc = remainInGroup.get( gx, gy );
					at = mp.clone();
				}
			}
			if( at == null )
			{
				//trace( solveAllow );
				//dump();
				return false;
			}
			
			var gx = Math.floor( at.x / GConst.groupSize );
			var gy = Math.floor( at.y / GConst.groupSize );
				
			//identify lowest
			var low = iPoss+1;
			var glow = igPoss+1;
			var which = GConst.cellUnset;
			var avail = solveAllow.get( at.x, at.y );
			var choiceCount = 0;
			for( i in avail )
			{
				if( poss[i] == 0 )
					continue;
					
				if( poss[i] > low )
					continue;
					
				if( poss[i] == low )
				{
					choiceCount = 1;
					if( mathx.Random.s_nextBool() )
						continue;
						
					//interestingly they always have the same counts...
					//trace( which + ":" + low + "/" + glow + " => " 
					//	+ i +":" +poss[i] + "/" + possInGroup.get( gx, gy )[i] );
				}
				else
					choiceCount = 0;
						
				low = poss[i];
				glow = possInGroup.get( gx, gy )[i];
				which = i;
			}
			totalChoiceCount += choiceCount;
					
			solvePlace( which, at.x, at.y, solveAllow, poss, remainInGroup, possInGroup );
		}
		
		//between 20 and 30 choices usually (from 2 diagonal seeds)
		//from ~28 to 35 with 1 diagonal seed
		//!37 to 42 with no seeds (an empty board)
		//trace( "Choices: " + totalChoiceCount );
		return true;
	}
	
	private function solvePlace( value : Int, x : Int, y : Int, 
		solveAllow : Matrix<Array<Int>>, poss, remainInGroup,
		possInGroup )
	{
		if( value == GConst.cellUnset )
			return;
			
		solveRemain--;
		set( x, y, value );
			
		var gx = Math.floor( x / GConst.groupSize );
		var gy = Math.floor( y / GConst.groupSize );
		
		//remove from all in that row/col
		for( i in 0...GConst.boardSize )
		{
			var gi = Math.floor( i / GConst.groupSize );
			if( solveAllow.get( i, y ).remove( value ) )
			{
				poss[value]--;
				possInGroup.get( gi, gy )[value]--;
			}
			if( solveAllow.get( x, i ).remove( value ) )
			{
				poss[value]--;
				possInGroup.get( gx, gi )[value]--;
			}
		}
		
		//remove from the group
		for( i in 0...GConst.groupSize )
			for( j in 0...GConst.groupSize )
				if( solveAllow.get( i + gx * GConst.groupSize, j + gy * GConst.groupSize ).remove( value ) )
				{
					poss[value]--;
					possInGroup.get( gx, gy )[value]--;
				}
		remainInGroup.set( gx, gy, remainInGroup.get(gx,gy)-1 );
				
		//adjust counts (remove remaining items from the allowed set for this cell)
		var avail = solveAllow.get( x, y );
		for( i in avail )
		{
			poss[i]--;
			possInGroup.get( gx, gy )[i]--;
		}
		solveAllow.set(x,y,new Array<Int>());	//empty out this one
	}
	
	/** 
	 * Creates a random block the size of a group, with the properties
	 * of a group.
	 */
	private function createRandomGroup() : Matrix<Int>
	{
		var seedList = ArrayUtil.shuffle( ArrayUtil.incList( GConst.cellLow, GConst.cellRange ) );
		return Matrix.fromArrayFlat( GConst.groupSize, seedList );
	}
	
	/**
	 * Removes random cells (unsets) from the Board.
	 */
	public function removeCount( num : Int )
	{
		Assert.isTrue( num <= maxLinearIndex() );
		var all = ArrayUtil.incList( 0, maxLinearIndex() );
		var rand = ArrayUtil.shuffle( all );
		for( i in 0...num )
		{
			var mp = fromLinearIndex( rand[i] );
			set( mp.x, mp.y, GConst.cellUnset );
		}
	}
	
	public function dump()
	{
		for( y in 0...GConst.boardSize )
		{
			if( y % GConst.groupSize == 0 )
				trace( "" );
			var line = "";
			for( x in 0...GConst.boardSize )
			{
				if( x % GConst.groupSize == 0 )
					line = line + " ";
				line = line + get( x, y );
			}
			trace( line );
		}
	}
}