/** Dominoes 
    by Jeffrey K. Brown
    
    A friend who is a mathematician and I came across a problem that
    went like this:
    
    If you had an 8 x 8 chessboard, you can lay 32 dominoes on the board
    in such a way that each domino occupies two squares.  Suppose you
    cut off two diagonally opposing corners.  Can 31 dominoes be arranged
    on the board?

    We weren't sure of the answer, and decided to take a crack at it.  I
    wanted to solve it with a program, he wanted to figure it out mathematically.
    
    I wrote this program and set it in motion for a smaller set, a 4x4
    board.  It didn't take long to write.  Shortly after we set it in
    motion, my friend and I discovered that you could not do it, because
    each domino must take up one black and one white square.  Opposing
    corners on a chessboard are the same color, so it couldn't be done.
    
    I also ran across a library called Apache POI (for Poor Obfuscation 
    Implementation), which allows a Java program to write to Excel spreadsheets.
    I decided to try out the POI library on my Dominoes program and have the
    combinations printed to Excel.
     
    Unfortunately, we ran out of memory before we printed all of the combinations,
    but I did figure out how POI worked as a result.  I have plenty of memory if
    I do a smaller chessboard and the Excel printing works just fine.  It's an 
    interesting program although its no longer needed since I have the answer.
*/

import java.util.*;
import java.io.*;
import org.apache.poi.hssf.usermodel.*;

/** Dominoes
This program will simulate the dominoes on a chessboard problem.
*/
public class Dominoes {
    // Blocks Per Side
    static final int block=4;
    
    // We build the board based on Blocks Per Side
    int board[][] = new int[block][block];

    // Here, we set up the Excel Variables
    FileOutputStream excel=null;
    HSSFWorkbook wb=null;
    HSSFSheet sheet=null;
    HSSFRow row = null;
    
    boolean reporting=false;
    long rownum=0;
           
    /** Constructor.  Simply clear out the Board */
    public Dominoes() {
        int i=0;
        int j=0;
        for (i=0; i<block; ++i) {
            for (j=0; j<block; ++j) {
                board[i][j] = 0;
            }
        }
    }
    
    /** checkwin() checks through the chessboard to see if all squares are covered.
      @return boolean indicating true if it is a winner, false if it is a loser. 
      */
    public boolean checkwin() {
        int i=0;
        int j=0;
        for (i=0; i<block; ++i) {
            for (j=0; j<block; ++j) {
                if (board[i][j] == 0) return false;
            }
        }
        return true;
    }
    
    /** Main function starts things in motion */    
    public static void main (String[] args) {
        Dominoes d = new Dominoes();
	
	// This is the hard-coded move that will plug the
	// two corners of the chessboard.
	String movestr = "0-0-"+(block-1)+"-"+(block-1);
	
	// Uncomment this line if you want to print to Excel.
	//d.setReporting();
	
	// I start the recursion here.	
	d.recurse ("",movestr);

	// If you set reporting to get Excel Report, you must close
	// the excel file at the end.  Uncomment if you want reports.	
	//d.finish();
    }   
    
    /** setReporting() sets up the Excel file to print the Dominoes 
      attempts.  Basically, we'll fill up an Excel file with moves
      that won't solve the problem.
      */    
    void setReporting() {
    	try {
    		wb = new HSSFWorkbook();
		excel = new FileOutputStream("dominoes.xls");
		sheet = wb.createSheet("Dominoes");
		
		row = sheet.createRow((short) rownum);
		row.createCell((short)0).setCellValue("Jkb's Dominoes Simulation Results");
		rownum+=2;
		
		reporting=true;
	}
	catch (Exception e) {
		System.out.println("Exception Opening Excel File!");
		e.printStackTrace();
		System.out.println("Continuing without reporting!");
		reporting = false;
	}
    }
    
    /** Finish() will close the Excel File so it can be read by Microsoft Applications */
    void finish() {
    	try {
		wb.write(excel);
		excel.close();    
	}
	catch (Exception e) {
		System.out.println("Error Writing and Closing Excel File");
		e.printStackTrace();
		System.exit(1);
	}
    }
    
    /** getMoves() produces the set of available moves given the current board/domino
      positions in board.
      @return String containing the moves available
      */    
    String getMoves() {
        String allmoves="";
        boolean above,below,left,right;
        String a = "";
        String b = "";
        String l = "";
        String r = "";
        int totalmoves = 0;
        int moves = 0;
        
        int i=0;
        int j=0;
        
        for (i=0; i<block; ++i) {
            for (j=0; j<block; ++j) {
                moves = 0;
                above = false;
                below = false;
                left  = false;
                right = false;
                a = "";
                b = "";
                l = "";
                r = "";
                
                if (board[i][j] != 0) continue;
                
		// I commented this section out, because I found that an "above" move from the
		// current block to one above it is the same as a "below" move for this block.
		// Cutting this out will cut out half of the vertical moves.
		
                //try {
                //    if (board[i-1][j]==0) {
                //        above=true;
                //        a = ""+i+"-"+j+"-"+(i-1)+"-"+j;
                //        moves++;
                //    }
                //}
                //catch (Exception e) { above=false; }

                try {
                    if (board[i+1][j]==0) {
                        below=true;
                        b = ""+i+"-"+j+"-"+(i+1)+"-"+j;
                        moves++;
                    }
                }
                catch (Exception e) { below=false; }

		// This is also commented out when I found a "left" move from the current
		// block was the same as a "right" move from the block next to it.  Again,
		// this cuts out half of the horizontal moves.
		
                //try {
                //    if (board[i][j-1]==0) {
                //        left=true;
                //        l = ""+i+"-"+j+"-"+i+"-"+(j-1);
                //        moves ++;
                //    }
                // }
                //catch (Exception e) { left=false; }

                try {
                    if (board[i][j+1]==0) {
                        right=true;
                        r = ""+i+"-"+j+"-"+i+"-"+(j+1);
                        moves ++;
                    }
                }
                catch (Exception e) { right=false; }

        
                allmoves = allmoves +" "+a+" "+b+" "+l+" "+r;
                totalmoves += moves;
                
            }  // J-Loop
        }  // I-Loop

        if (totalmoves==0) {
		return "None";
        }
        
        return allmoves;
    }
    
    /** Move accepts a specially formatted string to indicate
      a move.  The position on the board identified by that 
      move is set to Occupied.
      @param movecode specially formatted String containing the move.
    */
    void move (String movecode) {
        
        int x1=0, y1=0;
        int x2=0, y2=0;
        
        StringTokenizer st = new StringTokenizer(movecode,"-");
        try {
            
            x1 = new Integer(st.nextToken()).intValue();
            y1 = new Integer(st.nextToken()).intValue();
            x2 = new Integer(st.nextToken()).intValue();
            y2 = new Integer(st.nextToken()).intValue();

            board[x1][y1] = 1;
            board[x2][y2] = 1;            
        }
        
        catch (Exception e) {
            System.out.println("Illegal Move: '"+movecode+"'");
            e.printStackTrace();
        }
    }
    
    /** Unmove accepts another move and "Un-Moves" it by 
      setting the defined board positions to unoccupied.
      @param movecode specially formatted String containing the move.
    */
    void unmove (String movecode) {
        
        int x1=0, y1=0;
        int x2=0, y2=0;
        
        StringTokenizer st = new StringTokenizer(movecode,"-");
        
        try {
            
            x1 = new Integer(st.nextToken()).intValue();
            y1 = new Integer(st.nextToken()).intValue();
            x2 = new Integer(st.nextToken()).intValue();
            y2 = new Integer(st.nextToken()).intValue();

            board[x1][y1] = 0;
            board[x2][y2] = 0;            
        }
        
        catch (Exception e) {
            System.out.println("Illegal Move: '"+movecode+"'");
            e.printStackTrace();
        }
        
    }

    /** Recurse makes the move it was passed and creates the set of moves available given 
      this board position and then recurses with the next move from that new set.  The recursed
      instance then makes the next move given its available set of moves.  When a dead-end
      is reached, the moves are "Un-moved" and the instance makes the next move at that
      set, in a depth-first exhaustive search.
      @param inmoves - String containing the set of moves already moved.
      @param newmove - String containing the next move to make
      */
    void recurse(String inmoves, String newmove) {
    	String nextmove = "";	           
	String nextset = "";
    	String moves = inmoves + " " + newmove;
	
	// Here we move.
	move (newmove);
	
	// Get the set of Next Moves
	nextset = getMoves();
	
	if (nextset.equals("None")) {
		if (checkwin()==true) {
			System.out.println("Winner!");
			System.out.println(moves);		
			
			// Report if we've opted to report.
			if (reporting) {
				rownum++;
				row = sheet.createRow((short) rownum);
				row.createCell((short)0).setCellValue("Winner!");
				rownum++;
			
				StringTokenizer str = new StringTokenizer(moves);
				row = sheet.createRow((short) rownum);
				int colnum=0;
			
				while (str.hasMoreTokens()) {
					row.createCell((short)colnum).setCellValue(str.nextToken());
					colnum++;
				}
			
				
				finish();
			}
			
			System.exit(0);			
		}
	}
	else {
        
		StringTokenizer st = new StringTokenizer(nextset);
        	while (st.hasMoreTokens()) {
        		nextmove = st.nextToken();
        		System.out.println(moves + " " + nextmove);
		
			// Report if we've opted to report.
			if (reporting) {	
				StringTokenizer str = new StringTokenizer(moves+" "+nextmove);
				row = sheet.createRow((short) rownum);
				int colnum=0;
				//str.nextToken();  // Skip First One
				while (str.hasMoreTokens()) {
					row.createCell((short)colnum).setCellValue(str.nextToken());
					colnum++;
				}
				
				rownum++;
			}
			
			// recurse the set of moves and the next move to make.
			recurse(moves, nextmove);
		}           
        }
		
	// Now, we unmove the last move.
	unmove(newmove);
	
    }
    
}