import std.stdio;
import std.file;
import std.string;
import std.math;
import std.ctype;
import std.conv;
import std.bitarray;

int main(char[][] args)
{
  uint correct, total, failed,errors;
  foreach(char[] filename; args[1..$])
    {
      try
	{
	  char[][] unsolvedGrids = splitlines(cast(char[])read(filename));
	  
	  foreach( uint gridNum, char[] unsolved; unsolvedGrids)
	    {
	      total++;
	      try {
		
		Board curBoard = new Board(unsolved);
		bool isCorrect = curBoard.Solve();
		char[] solved = curBoard.GetAscii();

		version(OUTPUT)
		  {
		    writef("%s-%.05d:\n\n",filename, gridNum+1);
		    
		    uint inc = cast(uint)sqrt(cast(float)unsolved.length);
		    for( uint i = 0; i < curBoard.BoardSize(); i+=sqrt(cast(float)unsolved.length) )
		      {
			writefln( "%s\t%s", unsolved[i..i+inc], solved[i..i+inc] );
		      }
		  }
		if( isCorrect )
		  {
		    correct++;
		    version(OUTPUT)
		      {
			writef("Correct!\n\n");
		      }
		  }
		else
		  {
		    failed++;

		    version(OUTPUT)
		      {
			writef("Incorrect!\n\n");
		      }
		  }
	      }
	      catch( SudokuException e ) {
		writefln("Error %s", e.toString());
		errors++;
	      }
	    }
	}
      catch(FileException e) {
	writefln("Error reading file %s", e.toString());
      }
    }

  writef("\n");
  writefln("Statistics: %d total, %d correct, %d errors, %d failed", total, correct, errors, failed);
  
  return 0;
}
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
class SudokuException : Exception {
  this(char[] msg)
  {
    super(msg);
  }
}
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
class Board
{
  Cell[] Cells;
  uint sideSize, squareSize, boardSize;
  Board outer;
  
  uint BoardSize()
  {
    return boardSize;
  }

  private this(uint numCells)
  {
    outer = this;

    squareSize = cast(uint)rint( sqrt( sqrt( cast(float)numCells ) ) );
    sideSize = cast(uint)pow( cast(real)squareSize, 2);
    boardSize = cast(uint)pow(cast(real)squareSize, 4);
    
    //Init the Cells
    Cells.length = boardSize;
    for( uint i=0; i<Cells.length; i++ )
      {
	Cell curCell = Cells[i]= new Cell();
	CellSet[3] CellFriends;
	CellFriends[Cell.Row] = new Row(i);
	CellFriends[Cell.Column] = new Column(i);
	CellFriends[Cell.Square] = new Square(i);
	curCell.Friends = CellFriends;
      }
  }
  
  this(in char[] boardAscii) {
    //Only use the board size

    this(boardAscii.length);
    
    foreach( int i, char c; boardAscii )
      {
	if(i >= Cells.length) break;
	
	if( isdigit( c ) && c != '0')
	  {
	    Cells[i].Value = c - '0';
	  }
	else if ( isalpha( c ) )
	  {
	    Cells[i].Value = std.ctype.toupper(c) - 'A' + 9;
	  }
      }
  }
  
  bool Solve()
  {
    bool changed = true; //Ensure an initial run
    
    int count = 0;

    ubyte[] arrStorage = new ubyte[cast(uint)ceil(sideSize/8)];
    BitArray possible;
    possible.init(arrStorage, sideSize);
    CellSet relCells = new CellSet();

    //Keep trying until we can't figure out any possibilities to eliminate
    while( changed )
      {
	changed = false;
	++count;
	
RestartCheck:
	foreach( uint idx, Cell curCell; Cells )
	{ 
	    if( ! curCell.Value )
	      {
		possible ^= possible;
		
		//If something isn't possible in any of the units this idx belongs to, it has to be here.
		foreach( CellSet set; curCell.Friends )
		  {
		    possible ^= possible;
		    foreach( uint i; set )
		      {
			if ( i != idx ) possible |= Cells[i].Possible;
		      }
		    changed = curCell.PossibleElsewhere( possible );
		  }

		if(changed) break RestartCheck;
		
		//If something can't be in the other rows, or columns, of the current square
		//Then it can't be in this row or column of other squares
		CellSet square = curCell.Friends[Cell.Square];
		foreach( CellSet set; curCell.Friends[0..3] )
		  {
		    relCells.clear();
		    possible ^= possible;
		  
		    relCells.or( set ); // Column
		    relCells.not(); //Everything Else 
		    relCells.and( square ); //What's in the square of everything else;
		  
		    foreach( uint i; relCells )
		      {
			possible |= Cells[i].Possible;
		      }
		  
		    //What's not possible elsewhere has to be in this row of this square!
		    //We can eliminate them from possibilities elsewhere!
		    relCells.clear();
		    relCells.or( square ); //The Square
		    relCells.not(); //Whats not in the square
		    relCells.and( set ); // What's not in the square AND is in the column;
		  
		    //Get the possibilities of that fraction of the square
		    foreach( uint i; relCells )
		      {
			changed |= Cells[i].LimitPossible( possible );
		      }
		    if(changed) break RestartCheck;
		  }
	      }
	  }
      }
    
    return CheckGrid();
  }

  bool CheckGrid()
  {
    ubyte[] zeroStorage = new ubyte[cast(uint)ceil(sideSize/8)];
    //Add for simplicity, can this sometimes not work though?
    //Can an invalid grid add to the correct number in every square, col, and row?
    uint[] rows = new uint[sideSize];
    uint[] cols = new uint[sideSize];
    uint[] sqrs = new uint[sideSize];

    uint row,col,sqr;
    foreach( int i, Cell cur; Cells )
      {
	row = i/sideSize;
	col = i%sideSize;
	sqr = row/squareSize * squareSize + col/squareSize; // Yay for integers!

	rows[row] += cur.Value;
	cols[col] += cur.Value;
	sqrs[sqr] += cur.Value;
      }

    uint expect = (sideSize * (sideSize + 1 )) / 2;
    
    for( int i = 0; i < sideSize; i++ )
      if ( rows[i] != expect || cols[i] != expect || sqrs[i] != expect )
      {
	return false;
      }
    
    return true;
  }

  char[] GetAscii()
  {
    char[] ascii;
    ascii.length = Cells.length;
    
    foreach( int i, Cell cur; Cells )
      {
	ascii[i] = cur.Value ? ( cur.Value > 9 ? cur.Value + 'A' : cur.Value + '0') : '-';
      }
    return ascii;
  }

  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  class Cell
  {
    enum {
      Row,
      Column,
      Square
    }
    CellSet[3] _Friends;
    BitArray _Possible;
    uint _Value = 0;
    
    this()
    {
      ubyte[] arrStorage;      
      arrStorage = new ubyte[cast(uint)ceil(sideSize/8.0)];
      _Possible.init( arrStorage, sideSize );
      _Possible = ~_Possible;
    }

    void Friends(CellSet[3] friendSets)
    {
      foreach(uint i, CellSet friendSet; friendSets )
	{
	  _Friends[i] = friendSet;
	}
    }

    CellSet[] Friends()
    {
      return _Friends;
    }
  
    BitArray Possible()
    {
      return _Possible;
    }

    bool PossibleElsewhere(inout BitArray someWhere)
    {
      BitArray notPossible = ~someWhere;
      int val;
    
      val = ArrayValue( notPossible, false );
      if(val > 0) Value = val;
    
      return _Value > 0;
    }

    bool LimitPossible(inout BitArray limiter)
    {
      BitArray temp = _Possible.dup;
      _Possible &= limiter;
      
      if( temp != _Possible)
	{
	  IsSet();
	  return true;
	} else {
	  return false;
	}
    }
  
    uint Value(ushort value)
    {
      if( ! value ) return value;
      
      _Possible ^= _Possible;
      _Possible[value-1] = true;
      _Value = value;

      TellFriends();
      
      return _Value;
    }

    void TellFriends()
    //When potentials are eliminated isSet checks to see if we have a value.
    //If we do then Value is called to set the _Value property.
    //That then calls this, and we update our friends as to our status.
    in
    {
      assert( _Value, "Why am I being called when no value is set?");
    }
    body
    {
      CellSet relCells = outer.new CellSet();
      relCells.clear();
      
      foreach( CellSet set; _Friends)
	{
	  relCells.or( set );
	}
      
      //Eliminate set values from possibilities from Friends!.
      foreach( uint i; relCells)
	{
	  Cells[i].EliminateValue( _Value );
	}
    }

    uint Value()
    {    
      return _Value;
    }

    uint ArrayValue( inout BitArray arr, bool ensurePossible = true)
    {
      uint val = 0;
    
      foreach( uint i, bool x; arr )
	{
	  if( val && x )
	    return 0;
	  else if ( x )
	    {
	      val = i+1;
	    }
	}
    
      if( ensurePossible ) if( !val ) throw new SudokuException( "Something went wrong, bad grid? Solution Impossible" );
	
      return val;
    }

  
    bool IsSet()
    {
      if( _Value ) return true; //Short curcuit this expensive check.   

      Value = ArrayValue(_Possible);
    
      return _Value > 0;
    }
  
    //Returns true if eliminating this possiblity set the value
    bool EliminateValue(int value)
    {
      if( value && ! Value && _Possible[value-1] )
	{
	  _Possible[value-1] = 0;
	  IsSet(); //Make sure to set the value if we got it!
	  return true;
	}
    
      return false;    
    }
  }
  
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  class CellSet
  {
    ubyte[]    arrStorage;
    BitArray   cellSet;
    
    this( )
    {
      arrStorage = new ubyte[cast(uint)ceil(boardSize/8.0)];
      cellSet.init( arrStorage, boardSize);
    }

    void not()
    {
      cellSet = ~cellSet;
      return this;
    }

    void and( CellSet a2 )
    {
      cellSet &= a2.cellSet;
    }

    void or( CellSet a2 )
    {
      cellSet |= a2.cellSet;
    }
    
    void xor( CellSet a2 )
    {
      cellSet ^= a2.cellSet;
    }

    void clear()
    {
      cellSet ^= cellSet;
    }

    int opApply( int delegate (inout uint) dg)
    {
      int ret;
      foreach( uint i, bit x; cellSet )
	{
	  if( x ) if( (ret = dg( i )) != 0 ) break;
	}
      return ret;
    }
  }
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  class Row : CellSet
  {
    this(uint idx)
    {
      super();
      
      uint initRow = (idx / sideSize) * sideSize; //Yay for integers!
      
      for( uint i = initRow; i < initRow + sideSize; i++ )
	{
	  cellSet[i] = true;
	}
    }
  }
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  class Column : CellSet
  {
    this(uint idx)
    {
      super();
      
      uint col = (idx % sideSize); //Yay for integers!

      for( uint j = col; j < Cells.length; j += sideSize )
	{
	  cellSet[j] = true;
	}
    }
  }
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////
  class Square : CellSet
  {
    this(uint idx)
    {
      super();
      
      uint startIdx = idx;
      startIdx = (((startIdx / sideSize )  /* Number of rows */
		   / squareSize )           /* integral squares */
		  * sideSize * squareSize ); /*Multiply it back up to the first cell in the row of the square */
      
      startIdx += ((idx % sideSize) / squareSize) * squareSize; /* Add the base column back to the idx */
      
      for( uint i = 0; i < squareSize; i++)
	{
	  for( uint j = 0; j < squareSize; j++ )
	    {
	      cellSet[ startIdx + (i * sideSize) + j ] = true;
	    }
	}
    }
  }
}