SHARE
TWEET

COTO Water Puzzle Solver

a guest Dec 16th, 2014 247 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top