+/EE422C

software design

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

Joseph RyanAdd the rest of the files7e47727

master
6.2 KiB213 linesraw
1import java.io.File;
2import java.io.FileNotFoundException;
3import java.util.Arrays;
4import java.util.Scanner;
5
6/**
7 * This is a Sudoku Solver that solves a partial Sudoku Board using
8 * recursion.  The Sudoku solver fills a N×N (N=9 by default) grid
9 * with digits so that each column, each row, and each of the Size
10 * ×Size (N=Size × Size while Size =3 by default) subgrids contains
11 * all of the digits from 1 to 9.
12 * <p>
13 * You need to implement the solve(SudokuBoard b, int current) method
14 * using recursion.  Everything else is given to you.
15 * </p>
16 * <p>
17 * Don't change other given methods/fields. You can add some private
18 * helper methods but you may not add new public methods or fields.
19 * </p>
20 */
21public class Sudoku {
22
23    public static int noSolves = 0;
24    public static int size;
25
26    @SuppressWarnings("resource")
27    public static void main(String[] args)
28            throws FileNotFoundException {
29        // Initialize board
30        Scanner sc = new Scanner(new File("sudoku.in"));
31
32        boolean more = true;
33        while (more) {
34            int n = sc.nextInt();
35            size = n * n;
36            int[][] initial = new int[size][size];
37
38            for (int cell = 0; cell < size * size; cell++) {
39                initial[cell / size][cell % size] = sc.nextInt();
40            }
41            System.out.println(initial.length);
42            solve(initial);
43            more = sc.hasNextInt();
44            if (more) {
45                System.out.println(); // Print blank line between test cases
46            }
47        }
48    }
49
50    public static void solve(int[][] initial) {
51        if (size == 1) {
52            System.out.println(1);
53            return;
54        }
55        SudokuBoardSoln brd = new SudokuBoardSoln(size, initial);
56        if (solve(brd, brd.nextEmpty(-1))) {
57            brd.print();
58        } else {
59            System.out.println("NO SOLUTION");
60        }
61    }
62
63    public static boolean solve(SudokuBoardSoln b, int current) {
64        noSolves++; // For debug
65        // current increases from 0 to size^2 - 1 -- first along a
66        // row, then downwards.
67
68        // IF the current placement is at square size^2, we are done.
69        // ELSE
70        //     LOOP try out all 'size' numbers in the current square.
71        //         IF any number is safe to place there
72        //             Place it.
73        //             Call solve with the next square without an initial value.
74        //             IF above returns TRUE
75        //                 RETURN TRUE.
76        //             ELSE
77        //                 Remove the placement, (and try the next possible digit)
78        //     END LOOP
79        // RETURN false (if we fall out of the LOOP without returning true, we have exhausted 1 - size)
80        if(current == size * size) {
81            return true;
82        }
83        for(int i=1; i < size + 1; ++i) {
84            // System.out.println("Checking: " + i + " at " + current%size + " " + current/size);
85            if(b.isSafe(i, current)){
86                b.set(i, current);
87                if(solve(b, b.nextEmpty(current))) {
88                    return true;
89                }
90                b.remove(i, current);
91            }
92        }
93        return false;
94    }
95}
96
97class SudokuBoardSoln {
98
99    int[][] board;
100    boolean[][] initial;
101    int size;
102    int N;
103
104    public SudokuBoardSoln(int size) {
105        this.size = size;
106        N = (int) (Math.sqrt(size) + 1e-3);
107        board = new int[size][size];
108    }
109
110    public SudokuBoardSoln(int size, int[][] starting) {
111        this(size);
112        initial = new boolean[size][size]; // Is a square is
113        // initialized?  Iff not,
114        // program may change its
115        // value.
116        for (int r = 0; r < size; r++) {
117            for (int c = 0; c < size; c++) {
118                if (starting[r][c] != 0) {
119                    initial[r][c] = true;
120                }
121            }
122        }
123
124        for (int r = 0; r < size; r++) {
125            board[r] = Arrays.copyOf(starting[r], size);
126        }
127    }
128
129    public void set(int a, int n) {
130        board[n / size][n % size] = a;
131    }
132
133    public void remove(int a, int n) {
134        set(0, n);
135    }
136
137    /*
138     * Given a square, find the next one that was not initialized.
139     */
140    public int nextEmpty(int n) {
141        n++;
142        if (n == size * size) {
143            return n;
144        }
145        int row = n / size;
146        int col = n % size;
147        while (initial[row][col]) {
148            n++;
149            if (n == size * size) {
150                return n;
151            }
152            row = n / size;
153            col = n % size;
154        }
155        return n;
156    }
157
158    /*
159     * Whether safe to place number 'a' in space 'n'.
160     */
161    public boolean isSafe(int a, int n) {
162        int row = n / size;
163        int col = n % size;
164        // If putting 'a' at location 'n' causes duplicate
165        // number at its row, return false
166        for (int i = 0; i < size; ++i) {
167            if (board[row][i] == a) {
168                return false;
169            }
170        }
171
172        // If putting 'a' at location 'n' causes duplicate
173        // number at its column, return false
174        for (int i = 0; i < size; ++i) {
175            if (board[i][col] == a) {
176                return false;
177            }
178        }
179
180        // If putting 'a' at location 'n' causes duplicate
181        // number at its inner 3*3 (any N by N) square, return false
182        int r = row / N;
183        int c = col / N;
184        for (int i = 0; i < N; ++i) {
185            for (int j = 0; j < N; ++j) {
186                if (board[r*N + i][c*N + j] == a) {
187                    return false;
188                }
189            }
190        }
191
192        // Hint: If there is a duplicate number, it means that one
193        // number is missing (e.g. If we have two 1s in range of
194        // [1..9], it means one of the other numbers is missing as we
195        // can have at most 9 empty cells).
196        return true;
197    }
198
199    public void print() {
200        for (int r = 0; r < size; r++) {
201            String blank = "";
202            for (int c = 0; c < size; c++) {
203                if (board[r][c] == 0) {
204                    System.out.print(blank + "*");
205                } else {
206                    System.out.print(blank + board[r][c]);
207                }
208                blank = " ";
209            }
210            System.out.println();
211        }
212    }
213}