UTS Programming Competition 2016 Problem 7

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

This is a part of the UTS Programming Competition 2016 Problem Set.

Problem 7: Sudoku

Run time limit: 2 seconds

Problem Description

A 9x9 sudoku puzzle has 9 rows, 9 columns, and 9 blocks (3x3 subgrids), each of 9 cells, where each cell can contain a digit in the range [1, 9]. Each row, column and block should have a cell with each digit once only. Write a program to solve any Sudoku puzzle.

Note that Sudoku puzzles can often have multiple solutions for a given input. These test cases will all have enough cells completed such that there will be only one possible solution to the puzzle.

Data Specification

Input

Input consists of a single test case containing the initial puzzle state.

Known cells are given as digits 1-9, and unknown cells are given as 0. Each digit on a line is separated by a single SPACE.

There are nine lines in total.

Output

Output consists of the solution to the given puzzle, ie. with all the zeroes filled in with digits 1-9, digits separated by a single SPACE, nine lines in total.

Sample Input

```4 0 0 3 5 7 9 6 0
0 0 5 2 0 6 3 0 4
0 0 9 0 0 0 0 2 5
5 2 0 9 0 8 1 4 7
0 0 6 0 7 0 2 0 0
1 9 7 5 0 2 0 3 8
6 5 0 0 0 0 8 0 0
9 0 8 6 0 5 4 0 0
0 7 1 8 3 4 0 0 6
```

Sample Output

```4 8 2 3 5 7 9 6 1
7 1 5 2 9 6 3 8 4
3 6 9 4 8 1 7 2 5
5 2 3 9 6 8 1 4 7
8 4 6 1 7 3 2 5 9
1 9 7 5 4 2 6 3 8
6 5 4 7 2 9 8 1 3
9 3 8 6 1 5 4 7 2
2 7 1 8 3 4 5 9 6
```

Luke's Java solution

```import java.util.Scanner;
class Sudoku {

public static void main(String[] args) throws Exception {
(new Sudoku()).solve();
}

private int DIM = 3;
private int DIMSQR = DIM * DIM;

private void solve() throws Exception {
int[][] g = new int[DIMSQR][DIMSQR];
Scanner in = new Scanner(
System.in);

int x, y;
for (y = 0; y < DIMSQR; ++y)
for (x = 0; x < DIMSQR; ++x)
g[x][y] = in.nextInt();
// print(g);
if (backtrack(g))
print(g);
}

private void print(int[][] g) {
int x, y;
for (y = 0; y < DIMSQR; ++y) {
for (x = 0; x < DIMSQR; ++x) {
if (g[x][y] == 0)
System.out.print(".");
else
System.out.print(g[x][y]);
if (x < DIMSQR - 1)
System.out.print(" ");
}
System.out.println();
}
// System.out.println();
}

private boolean backtrack(int[][] g) {
int x, y, i;
if (!isValid(g))
return false;
if (isComplete(g)) {
print(g);
return false;
}
for (y = 0; y < DIMSQR; ++y)
for (x = 0; x < DIMSQR; ++x)
if (g[x][y] == 0) {
int[] a = getRandom();
for (i = 0; i < DIMSQR; ++i) {
g[x][y] = a[i];
if (backtrack(g))
return true;
}
g[x][y] = 0;
return false;
}
return false;
}

private int[] getRandom() {
int i, j;
int[] a = new int[DIMSQR];
for (i = 0; i < DIMSQR; ++i) {
a[i] = i + 1;
}
java.util.Random r = new java.util.Random();
for (i = a.length - 1; i > 0; i--)
{
j = r.nextInt(i + 1);
if (j != i)
{
a[j] ^= a[i];
a[i] ^= a[j];
a[j] ^= a[i];
}
}
return a;
}

private boolean isValid(int[][] g) {
int x, y;
for (y = 0; y < DIMSQR; ++y)
if (!isRowValid(g, y))
return false;
for (x = 0; x < DIMSQR; ++x)
if (!isColValid(g, x))
return false;
for (y = 0; y < DIM; ++y)
for (x = 0; x < DIM; ++x)
if (!isBlockValid(g, x, y))
return false;
return true;
}

private boolean isComplete(int[][] g) {
int x, y;
for (y = 0; y < DIMSQR; ++y)
for (x = 0; x < DIMSQR; ++x)
if (g[x][y] == 0)
return false;
return true;
}

private boolean isRowValid(int[][] g, int y) {
for (i = 0; i < DIMSQR; ++i)
if (g[i][y] != 0) {
if ((mask & 1 << g[i][y]) != 0)
return false;
}
return true;
}

private boolean isColValid(int[][] g, int x) {
for (i = 0; i < DIMSQR; ++i)
if (g[x][i] != 0) {
if ((mask & 1 << g[x][i]) != 0)
return false;
}
return true;
}

private boolean isBlockValid(int[][] g, int x, int y) {
int xx, yy, mask = 0;
for (xx = x * DIM; xx < (x + 1) * DIM; ++xx)
for (yy = y * DIM; yy < (y + 1) * DIM; ++yy)
if (g[xx][yy] != 0) {
if ((mask & 1 << g[xx][yy]) != 0)
return false;