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

网格计算

开发平台:

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.io.*;
  20. import java.util.*;
  21. /**
  22.  * This class uses the dancing links algorithm from Knuth to solve sudoku
  23.  * puzzles. It has solved 42x42 puzzles in 1.02 seconds.
  24.  */
  25. public class Sudoku {
  26.   /**
  27.    * The preset values in the board
  28.    * board[y][x] is the value at x,y with -1 = any
  29.    */ 
  30.   private int[][] board;
  31.   
  32.   /**
  33.    * The size of the board
  34.    */
  35.   private int size;
  36.   
  37.   /**
  38.    * The size of the sub-squares in cells across
  39.    */
  40.   private int squareXSize;
  41.   
  42.   /**
  43.    * The size of the sub-squares in celss up and down
  44.    */
  45.   private int squareYSize;
  46.   
  47.   /**
  48.    * This interface is a marker class for the columns created for the
  49.    * Sudoku solver.
  50.    */
  51.   protected static interface ColumnName {
  52.     // NOTHING
  53.   }
  54.   /**
  55.    * A string containing a representation of the solution.
  56.    * @param size the size of the board
  57.    * @param solution a list of list of column names
  58.    * @return a string of the solution matrix
  59.    */
  60.   static String stringifySolution(int size, List<List<ColumnName>> solution) {
  61.     int[][] picture = new int[size][size];
  62.     StringBuffer result = new StringBuffer();
  63.     // go through the rows selected in the model and build a picture of the
  64.     // solution.
  65.     for(List<ColumnName> row: solution) {
  66.       int x = -1;
  67.       int y = -1;
  68.       int num = -1;
  69.       for(ColumnName item: row) {
  70.         if (item instanceof ColumnConstraint) {
  71.           x = ((ColumnConstraint) item).column;
  72.           num = ((ColumnConstraint) item).num;
  73.         } else if (item instanceof RowConstraint) {
  74.           y = ((RowConstraint) item).row;
  75.         }
  76.       }
  77.       picture[y][x] = num;
  78.     }
  79.     // build the string
  80.     for(int y=0; y < size; ++y) {
  81.       for (int x=0; x < size; ++x) {
  82.         result.append(picture[y][x]);
  83.         result.append(" ");
  84.       }
  85.       result.append("n");
  86.     }
  87.     return result.toString();
  88.   }
  89.   /**
  90.    * An acceptor to get the solutions to the puzzle as they are generated and
  91.    * print them to the console.
  92.    */
  93.   private static class SolutionPrinter 
  94.   implements DancingLinks.SolutionAcceptor<ColumnName> {
  95.     int size;
  96.     public SolutionPrinter(int size) {
  97.       this.size = size;
  98.     }
  99.     /**
  100.      * A debugging aid that just prints the raw information about the 
  101.      * dancing link columns that were selected for each row.
  102.      * @param solution a list of list of column names
  103.      */
  104.     void rawWrite(List solution) {
  105.       for (Iterator itr=solution.iterator(); itr.hasNext(); ) {
  106.         Iterator subitr = ((List) itr.next()).iterator();
  107.         while (subitr.hasNext()) {
  108.           System.out.print(subitr.next().toString() + " ");
  109.         }
  110.         System.out.println();
  111.       }      
  112.     }
  113.     
  114.     public void solution(List<List<ColumnName>> names) {
  115.       System.out.println(stringifySolution(size, names));
  116.     }
  117.   }
  118.   /**
  119.    * Set up a puzzle board to the given size.
  120.    * Boards may be asymmetric, but the squares will always be divided to be
  121.    * more cells wide than they are tall. For example, a 6x6 puzzle will make 
  122.    * sub-squares that are 3x2 (3 cells wide, 2 cells tall). Clearly that means
  123.    * the board is made up of 2x3 sub-squares.
  124.    * @param stream The input stream to read the data from
  125.    */
  126.   public Sudoku(InputStream stream) throws IOException {
  127.     BufferedReader file = new BufferedReader(new InputStreamReader(stream));
  128.     String line = file.readLine();
  129.     List<int[]> result = new ArrayList<int[]>();
  130.     while (line != null) {
  131.       StringTokenizer tokenizer = new StringTokenizer(line);
  132.       int size = tokenizer.countTokens();
  133.       int[] col = new int[size];
  134.       int y = 0;
  135.       while(tokenizer.hasMoreElements()) {
  136.         String word = tokenizer.nextToken();
  137.         if ("?".equals(word)) {
  138.           col[y] = - 1;
  139.         } else {
  140.           col[y] = Integer.parseInt(word);
  141.         }
  142.         y += 1;
  143.       }
  144.       result.add(col);
  145.       line = file.readLine();
  146.     }
  147.     size = result.size();
  148.     board = (int[][]) result.toArray(new int [size][]);
  149.     squareYSize = (int) Math.sqrt(size);
  150.     squareXSize = size / squareYSize;
  151.     file.close();
  152.   }
  153.   
  154.   /**
  155.    * A constraint that each number can appear just once in a column.
  156.    */
  157.   static private class ColumnConstraint implements ColumnName {
  158.     ColumnConstraint(int num, int column) {
  159.       this.num = num;
  160.       this.column = column;
  161.     }
  162.     int num;
  163.     int column;
  164.     public String toString() {
  165.       return num + " in column " + column;
  166.     }
  167.   }
  168.   
  169.   /**
  170.    * A constraint that each number can appear just once in a row.
  171.    */
  172.   static private class RowConstraint implements ColumnName {
  173.     RowConstraint(int num, int row) {
  174.       this.num = num;
  175.       this.row = row;
  176.     }
  177.     int num;
  178.     int row;
  179.     public String toString() {
  180.       return num + " in row " + row;
  181.     }
  182.   }
  183.   /**
  184.    * A constraint that each number can appear just once in a square.
  185.    */
  186.   static private class SquareConstraint implements ColumnName {
  187.     SquareConstraint(int num, int x, int y) {
  188.       this.num = num;
  189.       this.x = x;
  190.       this.y = y;
  191.     }
  192.     int num;
  193.     int x;
  194.     int y;
  195.     public String toString() {
  196.       return num + " in square " + x + "," + y;
  197.     }
  198.   }
  199.   /**
  200.    * A constraint that each cell can only be used once.
  201.    */
  202.   static private class CellConstraint implements ColumnName {
  203.     CellConstraint(int x, int y) {
  204.       this.x = x;
  205.       this.y = y;
  206.     }
  207.     int x;
  208.     int y;
  209.     public String toString() {
  210.       return "cell " + x + "," + y;
  211.     }
  212.   }
  213.   
  214.   /**
  215.    * Create a row that places num in cell x, y.
  216.    * @param rowValues a scratch pad to mark the bits needed
  217.    * @param x the horizontal offset of the cell
  218.    * @param y the vertical offset of the cell
  219.    * @param num the number to place
  220.    * @return a bitvector of the columns selected
  221.    */
  222.   private boolean[] generateRow(boolean[] rowValues, int x, int y, int num) {
  223.     // clear the scratch array
  224.     for(int i=0; i < rowValues.length; ++i) {
  225.       rowValues[i] = false;
  226.     }
  227.     // find the square coordinates
  228.     int xBox = (int) x / squareXSize;
  229.     int yBox = (int) y / squareYSize;
  230.     // mark the column
  231.     rowValues[x*size + num - 1] = true;
  232.     // mark the row
  233.     rowValues[size*size + y*size + num - 1] = true;
  234.     // mark the square
  235.     rowValues[2*size*size + (xBox*squareXSize + yBox)*size + num - 1] = true;
  236.     // mark the cell
  237.     rowValues[3*size*size + size*x + y] = true;
  238.     return rowValues;
  239.   }
  240.   
  241.   private DancingLinks<ColumnName> makeModel() {
  242.     DancingLinks<ColumnName> model = new DancingLinks<ColumnName>();
  243.     // create all of the columns constraints
  244.     for(int x=0; x < size; ++x) {
  245.       for(int num=1; num <= size; ++num) {
  246.         model.addColumn(new ColumnConstraint(num, x));
  247.       }
  248.     }
  249.     // create all of the row constraints
  250.     for(int y=0; y < size; ++y) {
  251.       for(int num=1; num <= size; ++num) {
  252.         model.addColumn(new RowConstraint(num, y));
  253.       }
  254.     }
  255.     // create the square constraints
  256.     for(int x=0; x < squareYSize; ++x) {
  257.       for(int y=0; y < squareXSize; ++y) {
  258.         for(int num=1; num <= size; ++num) {
  259.           model.addColumn(new SquareConstraint(num, x, y));
  260.         }
  261.       }
  262.     }
  263.     // create the cell constraints
  264.     for(int x=0; x < size; ++x) {
  265.       for(int y=0; y < size; ++y) {
  266.         model.addColumn(new CellConstraint(x, y));
  267.       }
  268.     }
  269.     boolean[] rowValues = new boolean[size*size*4]; 
  270.     for(int x=0; x < size; ++x) {
  271.       for(int y=0; y < size; ++y) {
  272.         if (board[y][x] == -1) {
  273.           // try each possible value in the cell
  274.           for(int num=1; num <= size; ++num) {
  275.             model.addRow(generateRow(rowValues, x, y, num));
  276.           }
  277.         } else {
  278.           // put the given cell in place
  279.           model.addRow(generateRow(rowValues, x, y, board[y][x]));
  280.         }
  281.       }
  282.     }
  283.     return model;
  284.   }
  285.   
  286.   public void solve() {
  287.     DancingLinks<ColumnName> model = makeModel();
  288.     int results = model.solve(new SolutionPrinter(size));
  289.     System.out.println("Found " + results + " solutions");
  290.   }
  291.   
  292.   /**
  293.    * Solves a set of sudoku puzzles.
  294.    * @param args a list of puzzle filenames to solve
  295.    */
  296.   public static void main(String[] args) throws IOException {
  297.     if (args.length == 0) {
  298.       System.out.println("Include a puzzle on the command line.");
  299.     }
  300.     for(int i=0; i < args.length; ++i) {
  301.       Sudoku problem = new Sudoku(new FileInputStream(args[i]));
  302.       System.out.println("Solving " + args[i]);
  303.       problem.solve();
  304.     }
  305.   }
  306. }