Guest User

COTO Water Puzzle Solver

a guest
Dec 16th, 2014
403
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public final class Water {
  4.     static final int[] ROW_FILLS = { 4, 5, 6, 5, 6, 4, 7, 7, 4, 5, 7, 6 };
  5.     static final int[] COL_FILLS = { 4, 6, 5, 4, 8, 7, 4, 4, 6, 6, 6, 6 };
  6.  
  7.     static final Piece[] Pcs = {
  8.         new Piece( new Row[] { // 1
  9.             new Row( 3, new int[] { 2, 3 } ), new Row( 2, new int[] { 2 } ), new Row( 1, new int[] { 1, 2, 3 } )
  10.         } ),
  11.         new Piece( new Row[] { // 2
  12.             new Row( 2, new int[] { 3, 4, 5 } ), new Row( 1, new int[] { 4 } )
  13.         } ),
  14.         new Piece( new Row[] { // 3
  15.             new Row( 3, new int[] { 5, 6 } ), new Row( 2, new int[] { 6 } ), new Row( 1, new int[] { 5, 6 } )
  16.         } ),
  17.         new Piece( new Row[] { // 4
  18.             new Row( 1, new int[] { 7, 8, 9, 10} )
  19.         } ),
  20.         new Piece( new Row[] { // 5
  21.             new Row( 3, new int[] { 10 } ), new Row( 2, new int[] { 9, 10, 11 } ), new Row( 1, new int[] { 11, 12 } )
  22.         } ),
  23.         new Piece( new Row[] { // 6
  24.             new Row( 3, new int[] { 1 } ), new Row( 2, new int[] { 1 } )
  25.         }, 1 ),
  26.         new Piece( new Row[] { // 7
  27.             new Row( 4, new int[] { 6, 7 } ), new Row( 3, new int[] { 7 } ), new Row( 2, new int[] { 7, 8 } )
  28.         } ),
  29.         new Piece( new Row[] { // 8
  30.             new Row( 5, new int[] { 12 } ), new Row( 4, new int[] { 12 } ), new Row( 3, new int[] { 11, 12 } ),
  31.             new Row( 2, new int[] { 12 } )
  32.         } ),
  33.         new Piece( new Row[] { // 9
  34.             new Row( 5, new int[] { 1, 3 } ), new Row( 4, new int[] { 1, 2, 3, 4 } ), new Row( 3, new int[] { 4 } )
  35.         }, 2 ),
  36.         new Piece( new Row[] { // 10
  37.             new Row( 4, new int[] { 9, 10, 11 } ), new Row( 3, new int[] { 8, 9 } )
  38.         } ),
  39.         new Piece( new Row[] { // 11
  40.             new Row( 6, new int[] { 5 } ), new Row( 5, new int[] { 4, 5, 6, 7 } ), new Row( 4, new int[] { 5 } )
  41.         }, 3 ),
  42.         new Piece( new Row[] { // 12
  43.             new Row( 6 , new int[] { 9, 10 } ), new Row( 5, new int[] { 8, 9 } ), new Row( 4, new int[] { 8 } )
  44.         } ),
  45.         new Piece( new Row[] { // 13
  46.             new Row( 7, new int[] { 1 } ), new Row( 6, new int[] { 1, 2, 3, 4 } ), new Row( 5, new int[] { 2 } )
  47.         }, 4 ),
  48.         new Piece( new Row[] { // 14
  49.             new Row( 8, new int[] { 11 } ), new Row( 7, new int[] { 10, 11 } ), new Row( 6, new int[] { 11 } ),
  50.             new Row( 5, new int[] { 10, 11 } )
  51.         } ),
  52.         new Piece( new Row[] { // 15
  53.             new Row( 8, new int[] { 4 } ), new Row( 7, new int[] { 4, 5, 6 } ), new Row( 6, new int[] { 6 } )
  54.         }, 5 ),
  55.         new Piece( new Row[] { // 16
  56.             new Row( 9, new int[] { 8 } ), new Row( 8, new int[] { 6, 7, 8 } ), new Row( 7, new int[] { 7 } ),
  57.             new Row( 6, new int[] { 7, 8 } )
  58.         } ),
  59.         new Piece( new Row[] { // 17
  60.             new Row( 8 , new int[] { 12 } ), new Row( 7, new int[] { 12 } ), new Row( 6, new int[] { 12 } )
  61.         } ),
  62.         new Piece( new Row[] { // 18
  63.             new Row( 10, new int[] { 1, 2 } ), new Row( 9, new int[] { 2 } ), new Row( 8, new int[] { 2 } ),
  64.             new Row( 7, new int[] { 2, 3 } )
  65.         }, 6 ),
  66.         new Piece( new Row[] { // 19
  67.             new Row( 8, new int[] { 9, 10 } ), new Row( 7, new int[] { 8, 9 } )
  68.         } ),
  69.         new Piece( new Row[] { // 20
  70.             new Row( 9, new int[] { 1 } ), new Row( 8, new int[] { 1 } )
  71.         }, 7 ),
  72.         new Piece( new Row[] { // 21
  73.             new Row( 9, new int[] { 3, 4, 5 } ), new Row( 8, new int[] { 3, 5 } )
  74.         } ),
  75.         new Piece( new Row[] { // 22
  76.             new Row( 11, new int[] { 5, 6, 7 } ), new Row( 10, new int[] { 6 } ), new Row( 9, new int[] { 6 } )
  77.         }, 8 ),
  78.         new Piece( new Row[] { // 23
  79.             new Row( 12, new int[] { 8 } ), new Row( 11, new int[] { 8 } ), new Row( 10, new int[] { 7, 8 } ),
  80.             new Row( 9, new int[] { 7 } )
  81.         } ),
  82.         new Piece( new Row[] { // 24
  83.             new Row( 11, new int[] { 9 } ), new Row( 10, new int[] { 9, 10 } ), new Row( 9, new int[] { 9 } )
  84.         } ),
  85.         new Piece( new Row[] { // 25
  86.             new Row( 11, new int[] { 12 } ), new Row( 10, new int[] { 12 } ), new Row( 9, new int[] { 10, 11, 12 } )
  87.         } ),
  88.         new Piece( new Row[] { // 26
  89.             new Row( 11, new int[] { 2, 3 } ), new Row( 10, new int[] { 3, 4, 5 } )
  90.         }, 9 ),
  91.         new Piece( new Row[] { // 27
  92.             new Row( 12, new int[] { 11, 12 } ), new Row( 11, new int[] { 10, 11 } ), new Row( 10, new int[] { 11 } )
  93.         } ),
  94.         new Piece( new Row[] { // 28
  95.             new Row( 12, new int[] { 1, 2, 3 } ), new Row( 11, new int[] { 1 } )
  96.         }, 10 ),
  97.         new Piece( new Row[] { // 29
  98.             new Row( 12, new int[] { 4, 5, 6, 7 } ), new Row( 11, new int[] { 4 } )
  99.         } ),
  100.         new Piece( new Row[] { // 30
  101.             new Row( 12, new int[] { 9, 10 } )
  102.         }, 11 )
  103.     };
  104.  
  105.  
  106.     public static void main( String[] sArgs ) {
  107.         final int[] iRowSums = new int[12],
  108.             iColSums = new int[12];
  109.  
  110.         final Deque<StackElement> SEs = new LinkedList<>();
  111.  
  112.         SEs.push( new StackElement( 1 ) );
  113.  
  114.         pieceHeap: while( !SEs.isEmpty() ) {
  115.             StackElement SE = SEs.peek();
  116.  
  117.             if( !SE.isMutable() ) {
  118.                 SEs.pop();
  119.                 continue;
  120.             }
  121.             while( SE.isMutable() ) {
  122.                 boolean isOverfull = SE.fillToNextLevel( iRowSums, iColSums );
  123.                 if( !isOverfull ) {
  124.                     if( SE.iPieceIndex == 30 ) {
  125.                         if( iRowSums[11] == ROW_FILLS[11] )
  126.                             break pieceHeap;
  127.  
  128.                         continue;
  129.                     }
  130.  
  131.                     int iDeadRow = Pcs[SE.iPieceIndex + 1 - 1].iDeadRow;
  132.                     if( iDeadRow != -1 && iRowSums[iDeadRow - 1] < ROW_FILLS[iDeadRow - 1] )
  133.                         break;
  134.  
  135.                     SEs.push( new StackElement( SE.iPieceIndex + 1 ) );
  136.                     continue pieceHeap;
  137.                 }
  138.             }
  139.             SE.repeal( iRowSums, iColSums );
  140.             SEs.pop();
  141.         }
  142.         if( SEs.isEmpty() )
  143.             System.out.println( "Unable to find solution." );
  144.         else {
  145.             System.out.println( "Found solution:\n" );
  146.  
  147.             Iterator<StackElement> I_SE = SEs.descendingIterator();
  148.             while( I_SE.hasNext() )
  149.                 System.out.println( "\t" + I_SE.next().fillString() );
  150.         }
  151.     }
  152.  
  153.  
  154.     static class StackElement {
  155.         final int iPieceIndex;
  156.         final Piece Pc;
  157.         int iFillLevel;
  158.  
  159.         StackElement( int iPieceIndex ) {
  160.             this.iPieceIndex = iPieceIndex;
  161.             Pc = Pcs[iPieceIndex - 1];
  162.             iFillLevel = -1;
  163.         }
  164.  
  165.         boolean isMutable() {
  166.             return iFillLevel != 0;
  167.         }
  168.  
  169.         boolean fillToNextLevel( int[] iRowSums, int[] iColSums ) {
  170.             if( iPieceIndex == 9 ) {
  171.  
  172. /* Hack for piece 9, which doesn't obey the canonical fill rules (that I'd initially assumed). */
  173.  
  174.                 if( iFillLevel == -1 ) {
  175.                     iRowSums[2] += 1;
  176.                     iRowSums[3] += 4;
  177.                     iRowSums[4] += 2;
  178.                     iColSums[0] += 2;
  179.                     iColSums[1] += 1;
  180.                     iColSums[2] += 2;
  181.                     iColSums[3] += 2;
  182.                     iFillLevel = 5;
  183.                 } else if( iFillLevel == 5 ) {
  184.                     iRowSums[2] -= 1;
  185.                     iColSums[3] -= 1;
  186.                     iFillLevel = 4;
  187.                 } else if( iFillLevel == 4 ) {
  188.                     iRowSums[3] -= 4;
  189.                     iColSums[0] -= 1;
  190.                     iColSums[1] -= 1;
  191.                     iColSums[2] -= 1;
  192.                     iColSums[3] -= 1;
  193.                     iFillLevel = 3;
  194.                 } else if( iFillLevel == 3 ) {
  195.                     iRowSums[4] -= 1;
  196.                     iColSums[2] -= 1;
  197.                     iFillLevel = 2;
  198.                 } else if( iFillLevel == 2 ) {
  199.                     iColSums[2] += 1;
  200.                     iColSums[0] -= 1;
  201.                     iFillLevel = 1;
  202.                 } else if( iFillLevel == 1 ) {
  203.                     iColSums[2] -= 1;
  204.                     iRowSums[4] -= 1;
  205.                     iFillLevel = 0;
  206.                 }
  207.                 for( int iRow = 2; iRow <= 4; iRow++ )
  208.                     if( iRowSums[iRow] > ROW_FILLS[iRow] )
  209.                         return true;
  210.  
  211.                 for( int iCol = 0; iCol <= 3; iCol++ )
  212.                     if( iColSums[iCol] > COL_FILLS[iCol] )
  213.                         return true;
  214.  
  215.                 return false;
  216.             }
  217.  
  218.             if( iFillLevel == -1 ) {
  219.                 boolean isOverfull = false;
  220.  
  221.                 iFillLevel = Pc.Rws.length;
  222.                 for( Row Rw : Pc.Rws ) {
  223.                     iRowSums[Rw.iRow - 1] += Rw.iCols.length;
  224.                     if( iRowSums[Rw.iRow - 1] > ROW_FILLS[Rw.iRow - 1] )
  225.                         isOverfull = true;
  226.  
  227.                     for( int iCol : Rw.iCols )
  228.                         if( ++iColSums[iCol - 1] > COL_FILLS[iCol - 1] )
  229.                             isOverfull = true;
  230.                 }
  231.                 return isOverfull;
  232.             }
  233.             iFillLevel--;
  234.  
  235.             Row Rw = Pc.Rws[iFillLevel];
  236.  
  237.             iRowSums[Rw.iRow - 1] -= Rw.iCols.length;
  238.             for( int iCol : Rw.iCols )
  239.                 iColSums[iCol - 1]--;
  240.  
  241.             for( int iRow = 0; iRow < iFillLevel; iRow++ ) {
  242.                 Rw = Pc.Rws[iRow];
  243.                 if( iRowSums[Rw.iRow - 1] > ROW_FILLS[Rw.iRow - 1] )
  244.                     return true;
  245.  
  246.                 for( int iCol : Rw.iCols )
  247.                     if( iColSums[iCol - 1] > COL_FILLS[iCol - 1] )
  248.                         return true;
  249.             }
  250.             return false;
  251.         }
  252.  
  253.         void repeal( int[] iRowSums, int[] iColSums ) {
  254.             for( int iRow = 0; iRow < iFillLevel; iRow++ ) {
  255.                 Row Rw = Pc.Rws[iRow];
  256.  
  257.                 iRowSums[Rw.iRow - 1] -= Rw.iCols.length;
  258.                 for( int iCol : Rw.iCols )
  259.                     iColSums[iCol - 1]--;
  260.             }
  261.         }
  262.  
  263.         String fillString() {
  264.             return "Piece " + iPieceIndex + " filled to level " + iFillLevel + ".";
  265.         }
  266.     }
  267.  
  268.  
  269.     static class Piece {
  270.         final Row[] Rws;
  271.         final int iDeadRow;
  272.  
  273.         Piece( Row[] Rws ) {
  274.             this( Rws, -1 );
  275.         }
  276.  
  277.         Piece( Row[] Rws, int iDeadRow ) {
  278.             this.Rws = Rws;
  279.             this.iDeadRow = iDeadRow;
  280.         }
  281.     }
  282.  
  283.  
  284.     static class Row {
  285.         final int iRow;
  286.         final int[] iCols;
  287.  
  288.         Row( int iRow, int[] iCols ) {
  289.             this.iRow = iRow;
  290.             this.iCols = iCols;
  291.         }
  292.     }
  293. }
RAW Paste Data