+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

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