+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
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 .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*/ 36private int [][]board ; 37 38/** 39* The size of the board 40*/ 41private int size ; 42 43/** 44* The size of the sub-squares in cells across 45*/ 46private int squareXSize ; 47 48/** 49* The size of the sub-squares in celss up and down 50*/ 51private int squareYSize ; 52 53/** 54* This interface is a marker class for the columns created for the 55* Sudoku solver. 56*/ 57protected 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*/ 67static String stringifySolution (int size ,List <List <ColumnName >>solution ) { 68int [][]picture =new int [size ][size ]; 69StringBuffer result =new StringBuffer (); 70// go through the rows selected in the model and build a picture of the 71// solution. 72for (List <ColumnName >row :solution ) { 73int x = -1 ; 74int y = -1 ; 75int num = -1 ; 76for (ColumnName item :row ) { 77if (item instanceof ColumnConstraint ) { 78x = ((ColumnConstraint )item ).column ; 79num = ((ColumnConstraint )item ).num ; 80 }else if (item instanceof RowConstraint ) { 81y = ((RowConstraint )item ).row ; 82 } 83 } 84picture [y ][x ] =num ; 85 } 86// build the string 87for (int y =0 ;y <size ; ++y ) { 88for (int x =0 ;x <size ; ++x ) { 89result .append (picture [y ][x ]); 90result .append (" " ); 91 } 92result .append ("\n" ); 93 } 94return 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*/ 101private static class SolutionPrinter 102implements DancingLinks .SolutionAcceptor <ColumnName > { 103int size ; 104 105public SolutionPrinter (int size ) { 106this .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*/ 114void rawWrite (List solution ) { 115for (Iterator itr =solution .iterator ();itr .hasNext (); ) { 116Iterator subitr = ((List )itr .next ()).iterator (); 117while (subitr .hasNext ()) { 118System .out .subitr .next ().toString () +" " ); 119 } 120System .out .println (); 121 } 122 } 123 124public void solution (List <List <ColumnName >>names ) { 125System .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*/ 137public Sudoku (InputStream stream )throws IOException { 138BufferedReader file =new BufferedReader ( 139new InputStreamReader (stream ,Charsets .UTF_8 )); 140String line =file .readLine (); 141List <int []>result =new ArrayList <int []>(); 142while (line !=null ) { 143StringTokenizer tokenizer =new StringTokenizer (line ); 144int size =tokenizer .countTokens (); 145int []col =new int [size ]; 146int y =0 ; 147while (tokenizer .hasMoreElements ()) { 148String word =tokenizer .nextToken (); 149if ("?" .equals (word )) { 150col [y ] = -1 ; 151 }else { 152col [y ] =Integer .parseInt (word ); 153 } 154y +=1 ; 155 } 156result .add (col ); 157line =file .readLine (); 158 } 159size =result .size (); 160board =result .toArray (new int [size ][]); 161squareYSize = (int )Math .sqrt (size ); 162squareXSize =size /squareYSize ; 163file .close (); 164 } 165 166/** 167* A constraint that each number can appear just once in a column. 168*/ 169static private class ColumnConstraint implements ColumnName { 170ColumnConstraint (int num ,int column ) { 171this .num =num ; 172this .column =column ; 173 } 174int num ; 175int column ; 176public String toString () { 177return num +" in column " +column ; 178 } 179 } 180 181/** 182* A constraint that each number can appear just once in a row. 183*/ 184static private class RowConstraint implements ColumnName { 185RowConstraint (int num ,int row ) { 186this .num =num ; 187this .row =row ; 188 } 189int num ; 190int row ; 191public String toString () { 192return num +" in row " +row ; 193 } 194 } 195 196/** 197* A constraint that each number can appear just once in a square. 198*/ 199static private class SquareConstraint implements ColumnName { 200SquareConstraint (int num ,int x ,int y ) { 201this .num =num ; 202this .x =x ; 203this .y =y ; 204 } 205int num ; 206int x ; 207int y ; 208public String toString () { 209return num +" in square " +x +"," +y ; 210 } 211 } 212 213/** 214* A constraint that each cell can only be used once. 215*/ 216static private class CellConstraint implements ColumnName { 217CellConstraint (int x ,int y ) { 218this .x =x ; 219this .y =y ; 220 } 221int x ; 222int y ; 223public String toString () { 224return "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*/ 236private boolean []generateRow (boolean []rowValues ,int x ,int y ,int num ) { 237// clear the scratch array 238for (int i =0 ;i <rowValues .length ; ++i ) { 239rowValues [i ] =false ; 240 } 241// find the square coordinates 242int xBox =x /squareXSize ; 243int yBox =y /squareYSize ; 244// mark the column 245rowValues [x *size +num -1 ] =true ; 246// mark the row 247rowValues [size *size +y *size +num -1 ] =true ; 248// mark the square 249rowValues [2 *size *size + (xBox *squareXSize +yBox )*size +num -1 ] =true ; 250// mark the cell 251rowValues [3 *size *size +size *x +y ] =true ; 252return rowValues ; 253 } 254 255private DancingLinks <ColumnName >makeModel () { 256DancingLinks <ColumnName >model =new DancingLinks <ColumnName >(); 257// create all of the columns constraints 258for (int x =0 ;x <size ; ++x ) { 259for (int num =1 ;num <=size ; ++num ) { 260model .addColumn (new ColumnConstraint (num ,x )); 261 } 262 } 263// create all of the row constraints 264for (int y =0 ;y <size ; ++y ) { 265for (int num =1 ;num <=size ; ++num ) { 266model .addColumn (new RowConstraint (num ,y )); 267 } 268 } 269// create the square constraints 270for (int x =0 ;x <squareYSize ; ++x ) { 271for (int y =0 ;y <squareXSize ; ++y ) { 272for (int num =1 ;num <=size ; ++num ) { 273model .addColumn (new SquareConstraint (num ,x ,y )); 274 } 275 } 276 } 277// create the cell constraints 278for (int x =0 ;x <size ; ++x ) { 279for (int y =0 ;y <size ; ++y ) { 280model .addColumn (new CellConstraint (x ,y )); 281 } 282 } 283boolean []rowValues =new boolean [size *size *4 ]; 284for (int x =0 ;x <size ; ++x ) { 285for (int y =0 ;y <size ; ++y ) { 286if (board [y ][x ] == -1 ) { 287// try each possible value in the cell 288for (int num =1 ;num <=size ; ++num ) { 289model .addRow (generateRow (rowValues ,x ,y ,num )); 290 } 291 }else { 292// put the given cell in place 293model .addRow (generateRow (rowValues ,x ,y ,board [y ][x ])); 294 } 295 } 296 } 297return model ; 298 } 299 300public void solve () { 301DancingLinks <ColumnName >model =makeModel (); 302int results =model .solve (new SolutionPrinter (size )); 303System .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*/ 310public static void main (String []args )throws IOException { 311if (args .length ==0 ) { 312System .out .println ("Include a puzzle on the command line." ); 313 } 314for (int i =0 ;i <args .length ; ++i ) { 315Sudoku problem =new Sudoku (new FileInputStream (args [i ])); 316System .out .println ("Solving " +args [i ]); 317problem .solve (); 318 } 319 } 320 321}