Pentomino.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:14k
源码类别:

网格计算

开发平台:

Java

  1. /**
  2.  * Licensed to the Apache Software Foundation (ASF) under one
  3.  * or more contributor license agreements.  See the NOTICE file
  4.  * distributed with this work for additional information
  5.  * regarding copyright ownership.  The ASF licenses this file
  6.  * to you under the Apache License, Version 2.0 (the
  7.  * "License"); you may not use this file except in compliance
  8.  * with the License.  You may obtain a copy of the License at
  9.  *
  10.  *     http://www.apache.org/licenses/LICENSE-2.0
  11.  *
  12.  * Unless required by applicable law or agreed to in writing, software
  13.  * distributed under the License is distributed on an "AS IS" BASIS,
  14.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15.  * See the License for the specific language governing permissions and
  16.  * limitations under the License.
  17.  */
  18. package org.apache.hadoop.examples.dancing;
  19. import java.util.*;
  20. public class Pentomino {
  21.   /**
  22.    * This interface just is a marker for what types I expect to get back
  23.    * as column names.
  24.    */
  25.   protected static interface ColumnName {
  26.     // NOTHING
  27.   }
  28.   /**
  29.    * Maintain information about a puzzle piece.
  30.    */
  31.   protected static class Piece implements ColumnName {
  32.     private String name;
  33.     private boolean [][] shape;
  34.     private int[] rotations;
  35.     private boolean flippable;
  36.     
  37.     public Piece(String name, String shape, 
  38.                  boolean flippable, int[] rotations) {
  39.       this.name = name;
  40.       this.rotations = rotations;
  41.       this.flippable = flippable;
  42.       StringTokenizer parser = new StringTokenizer(shape, "/");
  43.       List<boolean[]> lines = new ArrayList<boolean[]>();
  44.       while (parser.hasMoreTokens()) {
  45.         String token = parser.nextToken();
  46.         boolean[] line = new boolean[token.length()];
  47.         for(int i=0; i < line.length; ++i) {
  48.           line[i] = token.charAt(i) == 'x';
  49.         }
  50.         lines.add(line);
  51.       }
  52.       this.shape = new boolean[lines.size()][];
  53.       for(int i=0 ; i < lines.size(); i++) {
  54.         this.shape[i] = (boolean[]) lines.get(i);
  55.       }
  56.     }
  57.     
  58.     public String getName() {
  59.       return name;
  60.     }
  61.     
  62.     public int[] getRotations() {
  63.       return rotations;
  64.     }
  65.     
  66.     public boolean getFlippable() {
  67.       return flippable;
  68.     }
  69.     
  70.     private int doFlip(boolean flip, int x, int max) {
  71.       if (flip) {
  72.         return max - x - 1;
  73.       } else {
  74.         return x;
  75.       }
  76.     }
  77.     
  78.     public boolean[][] getShape(boolean flip, int rotate) {
  79.       boolean [][] result;
  80.       if (rotate % 2 == 0) {
  81.         int height = shape.length;
  82.         int width = shape[0].length;
  83.         result = new boolean[height][];
  84.         boolean flipX = rotate == 2;
  85.         boolean flipY = flip ^ (rotate == 2);
  86.         for (int y = 0; y < height; ++y) {
  87.           result[y] = new boolean[width];
  88.           for (int x=0; x < width; ++x) {
  89.             result[y][x] = shape[doFlip(flipY, y, height)]
  90.                                  [doFlip(flipX, x, width)];
  91.           }
  92.         }
  93.       } else {
  94.         int height = shape[0].length;
  95.         int width = shape.length;
  96.         result = new boolean[height][];
  97.         boolean flipX = rotate == 3;
  98.         boolean flipY = flip ^ (rotate == 1);
  99.         for (int y = 0; y < height; ++y) {
  100.           result[y] = new boolean[width];
  101.           for (int x=0; x < width; ++x) {
  102.             result[y][x] = shape[doFlip(flipX, x, width)]
  103.                                  [doFlip(flipY, y, height)];
  104.           }
  105.         }        
  106.       }
  107.       return result;
  108.     }
  109.   }
  110.   /**
  111.    * A point in the puzzle board. This represents a placement of a piece into
  112.    * a given point on the board.
  113.    */
  114.   static class Point implements ColumnName {
  115.     int x;
  116.     int y;
  117.     Point(int x, int y) {
  118.       this.x = x;
  119.       this.y = y;
  120.     }
  121.   }
  122.   
  123.   /**
  124.    * Convert a solution to the puzzle returned by the model into a string
  125.    * that represents the placement of the pieces onto the board.
  126.    * @param width the width of the puzzle board
  127.    * @param height the height of the puzzle board
  128.    * @param solution the list of column names that were selected in the model
  129.    * @return a string representation of completed puzzle board
  130.    */
  131.   public static String stringifySolution(int width, int height, 
  132.                                          List<List<ColumnName>> solution) {
  133.     String[][] picture = new String[height][width];
  134.     StringBuffer result = new StringBuffer();
  135.     // for each piece placement...
  136.     for(List<ColumnName> row: solution) {
  137.       // go through to find which piece was placed
  138.       Piece piece = null;
  139.       for(ColumnName item: row) {
  140.         if (item instanceof Piece) {
  141.           piece = (Piece) item;
  142.           break;
  143.         }
  144.       }
  145.       // for each point where the piece was placed, mark it with the piece name
  146.       for(ColumnName item: row) {
  147.         if (item instanceof Point) {
  148.           Point p = (Point) item;
  149.           picture[p.y][p.x] = piece.getName();
  150.         }
  151.       }
  152.     }
  153.     // put the string together
  154.     for(int y=0; y < picture.length; ++y) {
  155.       for (int x=0; x < picture[y].length; ++x) {
  156.         result.append(picture[y][x]);
  157.       }
  158.       result.append("n");
  159.     }
  160.     return result.toString();
  161.   }
  162.   
  163.   public enum SolutionCategory {UPPER_LEFT, MID_X, MID_Y, CENTER}
  164.   
  165.   /**
  166.    * Find whether the solution has the x in the upper left quadrant, the
  167.    * x-midline, the y-midline or in the center.
  168.    * @param names the solution to check
  169.    * @return the catagory of the solution
  170.    */
  171.   public SolutionCategory getCategory(List<List<ColumnName>> names) {
  172.     Piece xPiece = null;
  173.     // find the "x" piece
  174.     for(Piece p: pieces) {
  175.       if ("x".equals(p.name)) {
  176.         xPiece = p;
  177.         break;
  178.       }
  179.     }
  180.     // find the row containing the "x"
  181.     for(List<ColumnName> row: names) {
  182.       if (row.contains(xPiece)) {
  183.         // figure out where the "x" is located
  184.         int low_x = width;
  185.         int high_x = 0;
  186.         int low_y = height;
  187.         int high_y = 0;
  188.         for(ColumnName col: row) {
  189.           if (col instanceof Point) {
  190.             int x = ((Point) col).x;
  191.             int y = ((Point) col).y;
  192.             if (x < low_x) {
  193.               low_x = x;
  194.             }
  195.             if (x > high_x) {
  196.               high_x = x;
  197.             }
  198.             if (y < low_y) {
  199.               low_y = y;
  200.             }
  201.             if (y > high_y) {
  202.               high_y = y;
  203.             }
  204.           }
  205.         }
  206.         boolean mid_x = (low_x + high_x == width - 1);
  207.         boolean mid_y = (low_y + high_y == height - 1);
  208.         if (mid_x && mid_y) {
  209.           return SolutionCategory.CENTER;
  210.         } else if (mid_x) {
  211.           return SolutionCategory.MID_X;
  212.         } else if (mid_y) {
  213.           return SolutionCategory.MID_Y;
  214.         }
  215.         break;
  216.       }
  217.     }
  218.     return SolutionCategory.UPPER_LEFT;
  219.   }
  220.   
  221.   /**
  222.    * A solution printer that just writes the solution to stdout.
  223.    */
  224.   private static class SolutionPrinter 
  225.                        implements DancingLinks.SolutionAcceptor<ColumnName> {
  226.     int width;
  227.     int height;
  228.     
  229.     public SolutionPrinter(int width, int height) {
  230.       this.width = width;
  231.       this.height = height;
  232.     }
  233.     
  234.     public void solution(List<List<ColumnName>> names) {
  235.       System.out.println(stringifySolution(width, height, names));
  236.     }
  237.   }
  238.   
  239.   protected int width;
  240.   protected int height;
  241.   protected List<Piece> pieces = new ArrayList<Piece>();
  242.   
  243.   /**
  244.    * Is the piece fixed under rotation?
  245.    */
  246.   protected static final int [] oneRotation = new int[]{0};
  247.   
  248.   /**
  249.    * Is the piece identical if rotated 180 degrees?
  250.    */
  251.   protected static final int [] twoRotations = new int[]{0,1};
  252.   
  253.   /**
  254.    * Are all 4 rotations unique?
  255.    */
  256.   protected static final int [] fourRotations = new int[]{0,1,2,3};
  257.   
  258.   /**
  259.    * Fill in the pieces list.
  260.    */
  261.   protected void initializePieces() {
  262.     pieces.add(new Piece("x", " x /xxx/ x ", false, oneRotation));
  263.     pieces.add(new Piece("v", "x  /x  /xxx", false, fourRotations));
  264.     pieces.add(new Piece("t", "xxx/ x / x ", false, fourRotations));
  265.     pieces.add(new Piece("w", "  x/ xx/xx ", false, fourRotations));
  266.     pieces.add(new Piece("u", "x x/xxx", false, fourRotations));
  267.     pieces.add(new Piece("i", "xxxxx", false, twoRotations));
  268.     pieces.add(new Piece("f", " xx/xx / x ", true, fourRotations));
  269.     pieces.add(new Piece("p", "xx/xx/x ", true, fourRotations));
  270.     pieces.add(new Piece("z", "xx / x / xx", true, twoRotations));
  271.     pieces.add(new Piece("n", "xx  / xxx", true, fourRotations));
  272.     pieces.add(new Piece("y", "  x /xxxx", true, fourRotations));
  273.     pieces.add(new Piece("l", "   x/xxxx", true, fourRotations));
  274.   }
  275.   
  276.   /**
  277.    * Is the middle of piece on the upper/left side of the board with 
  278.    * a given offset and size of the piece? This only checks in one
  279.    * dimension.
  280.    * @param offset the offset of the piece
  281.    * @param shapeSize the size of the piece
  282.    * @param board the size of the board
  283.    * @return is it in the upper/left?
  284.    */
  285.   private static boolean isSide(int offset, int shapeSize, int board) {
  286.     return 2*offset + shapeSize <= board;
  287.   }
  288.   
  289.   /**
  290.    * For a given piece, generate all of the potential placements and add them 
  291.    * as rows to the model.
  292.    * @param dancer the problem model
  293.    * @param piece the piece we are trying to place
  294.    * @param width the width of the board
  295.    * @param height the height of the board
  296.    * @param flip is the piece flipped over?
  297.    * @param row a workspace the length of the each row in the table
  298.    * @param upperLeft is the piece constrained to the upper left of the board?
  299.    *        this is used on a single piece to eliminate most of the trivial
  300.    *        roations of the solution.
  301.    */
  302.   private static void generateRows(DancingLinks dancer,
  303.                                    Piece piece,
  304.                                    int width,
  305.                                    int height,
  306.                                    boolean flip,
  307.                                    boolean[] row,
  308.                                    boolean upperLeft) {
  309.     // for each rotation
  310.     int[] rotations = piece.getRotations();
  311.     for(int rotIndex = 0; rotIndex < rotations.length; ++rotIndex) {
  312.       // get the shape
  313.       boolean[][] shape = piece.getShape(flip, rotations[rotIndex]);
  314.       // find all of the valid offsets
  315.       for(int x=0; x < width; ++x) {
  316.         for(int y=0; y < height; ++y) {
  317.           if (y + shape.length <= height && x + shape[0].length <= width &&
  318.               (!upperLeft || 
  319.                   (isSide(x, shape[0].length, width) && 
  320.                    isSide(y, shape.length, height)))) {
  321.             // clear the columns related to the points on the board
  322.             for(int idx=0; idx < width * height; ++idx) {
  323.               row[idx] = false;
  324.             }
  325.             // mark the shape
  326.             for(int subY=0; subY < shape.length; ++subY) {
  327.               for(int subX=0; subX < shape[0].length; ++subX) {
  328.                 row[(y + subY) * width + x + subX] = shape[subY][subX];
  329.               }
  330.             }
  331.             dancer.addRow(row);
  332.           }         
  333.         }
  334.       }
  335.     }
  336.   }
  337.   
  338.   private DancingLinks<ColumnName> dancer = new DancingLinks<ColumnName>();
  339.   private DancingLinks.SolutionAcceptor<ColumnName> printer;
  340.   
  341.   {
  342.     initializePieces();
  343.   }
  344.   /**
  345.    * Create the model for a given pentomino set of pieces and board size.
  346.    * @param width the width of the board in squares
  347.    * @param height the height of the board in squares
  348.    */
  349.   public Pentomino(int width, int height) {
  350.     initialize(width, height);
  351.   }
  352.   /**
  353.    * Create the object without initialization.
  354.    */
  355.   public Pentomino() {
  356.   }
  357.   void initialize(int width, int height) {
  358.     this.width = width;
  359.     this.height = height;
  360.     for(int y=0; y < height; ++y) {
  361.       for(int x=0; x < width; ++x) {
  362.         dancer.addColumn(new Point(x,y));
  363.       }
  364.     }
  365.     int pieceBase = dancer.getNumberColumns();
  366.     for(Piece p: pieces) {
  367.       dancer.addColumn(p);
  368.     }
  369.     boolean[] row = new boolean[dancer.getNumberColumns()];
  370.     for(int idx = 0; idx < pieces.size(); ++idx) {
  371.       Piece piece = (Piece) pieces.get(idx);
  372.       row[idx + pieceBase] = true;
  373.       generateRows(dancer, piece, width, height, false, row, idx == 0);
  374.       if (piece.getFlippable()) {
  375.         generateRows(dancer, piece, width, height, true, row, idx == 0);
  376.       }
  377.       row[idx + pieceBase] = false;
  378.     }
  379.     printer = new SolutionPrinter(width, height);
  380.   }
  381.   
  382.   /**
  383.    * Generate a list of prefixes to a given depth
  384.    * @param depth the length of each prefix
  385.    * @return a list of arrays of ints, which are potential prefixes
  386.    */
  387.   public List<int[]> getSplits(int depth) {
  388.     return dancer.split(depth);
  389.   }
  390.   
  391.   /**
  392.    * Find all of the solutions that start with the given prefix. The printer
  393.    * is given each solution as it is found.
  394.    * @param split a list of row indexes that should be choosen for each row
  395.    *        in order
  396.    * @return the number of solutions found
  397.    */
  398.   public int solve(int[] split) {
  399.     return dancer.solve(split, printer);
  400.   }
  401.   
  402.   /**
  403.    * Find all of the solutions to the puzzle.
  404.    * @return the number of solutions found
  405.    */
  406.   public int solve() {
  407.     return dancer.solve(printer);
  408.   }
  409.   
  410.   /**
  411.    * Set the printer for the puzzle.
  412.    * @param printer A call-back object that is given each solution as it is 
  413.    * found.
  414.    */
  415.   public void setPrinter(DancingLinks.SolutionAcceptor<ColumnName> printer) {
  416.     this.printer = printer;
  417.   }
  418.   
  419.   /**
  420.    * Solve the 6x10 pentomino puzzle.
  421.    */
  422.   public static void main(String[] args) {
  423.     int width = 6;
  424.     int height = 10;
  425.     Pentomino model = new Pentomino(width, height);
  426.     List splits = model.getSplits(2);
  427.     for(Iterator splitItr=splits.iterator(); splitItr.hasNext(); ) {
  428.       int[] choices = (int[]) splitItr.next();
  429.       System.out.print("split:");
  430.       for(int i=0; i < choices.length; ++i) {
  431.         System.out.print(" " + choices[i]);
  432.       }
  433.       System.out.println();
  434.       
  435.       System.out.println(model.solve(choices) + " solutions found.");
  436.     }
  437.   }
  438. }