Sudoku: Difference between revisions
Content deleted Content added
Line 1,251: | Line 1,251: | ||
=={{header|J}}== |
=={{header|J}}== |
||
See [[j:Essays/Sudoku|Solving Sudoku in J]]. |
See [[j:Essays/Sudoku|Solving Sudoku in J]]. |
||
=={{header|Java}}== |
|||
<lang java>public class SudokuSolver { |
|||
private int[] grid; |
|||
public SudokuSolver(String s) { |
|||
grid = new int[81]; |
|||
for (int i = 0; i < s.length(); i++) { |
|||
grid[i] = Character.getNumericValue(s.charAt(i)); |
|||
} |
|||
} |
|||
public void solve() { |
|||
try { |
|||
placeNumber(0); |
|||
System.out.println("Unsolvable!"); |
|||
} catch (Exception ex) { |
|||
System.out.println(ex.getMessage()); |
|||
System.out.println(this); |
|||
} |
|||
} |
|||
public void placeNumber(int pos) throws Exception { |
|||
if (pos == 81) { |
|||
throw new Exception("Finished!"); |
|||
} |
|||
if (grid[pos] > 0) { |
|||
placeNumber(pos + 1); |
|||
return; |
|||
} |
|||
for (int n = 1; n <= 9; n++) { |
|||
if (checkValidity(n, pos % 9, pos / 9)) { |
|||
grid[pos] = n; |
|||
placeNumber(pos + 1); |
|||
grid[pos] = 0; |
|||
} |
|||
} |
|||
} |
|||
public boolean checkValidity(int val, int x, int y) { |
|||
for (int i = 0; i < 9; i++) { |
|||
if (grid[y * 9 + i] == val || grid[i * 9 + x] == val) |
|||
return false; |
|||
} |
|||
int startX = (x / 3) * 3; |
|||
int startY = (y / 3) * 3; |
|||
for (int i = startY; i < startY + 3; i++) { |
|||
for (int j = startX; j < startX + 3; j++) { |
|||
if (grid[i * 9 + j] == val) |
|||
return false; |
|||
} |
|||
} |
|||
return true; |
|||
} |
|||
@Override |
|||
public String toString() { |
|||
StringBuilder sb = new StringBuilder(); |
|||
for (int i = 0; i < 9; i++) { |
|||
for (int j = 0; j < 9; j++) { |
|||
sb.append(grid[i * 9 + j] + " "); |
|||
if (j == 2 || j == 5) |
|||
sb.append("| "); |
|||
} |
|||
sb.append('\n'); |
|||
if (i == 2 || i == 5) |
|||
sb.append("------+-------+------\n"); |
|||
} |
|||
return sb.toString(); |
|||
} |
|||
public static void main(String[] args) { |
|||
new SudokuSolver("850002400" + |
|||
"720000009" + |
|||
"004000000" + |
|||
"000107002" + |
|||
"305000900" + |
|||
"040000000" + |
|||
"000080070" + |
|||
"017000000" + |
|||
"000036040").solve(); |
|||
} |
|||
}</lang> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |