UTS Programming Competition 2016 Problem 7

From ProgSoc Wiki

(Difference between revisions)
Jump to: navigation, search
(Created page with "__NOTOC__ = 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,...")
(Solutions)
 
(One intermediate revision not shown)
Line 1: Line 1:
__NOTOC__
__NOTOC__
 +
This is a part of the [[UTS Programming Competition 2016 Problem Set]].
= Problem 7: Sudoku =
= Problem 7: Sudoku =
''Run time limit: 2 seconds''
''Run time limit: 2 seconds''
Line 50: Line 51:
Put your solutions here!
Put your solutions here!
 +
 +
== 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) {
 +
        int i, mask = 0;
 +
        for (i = 0; i < DIMSQR; ++i)
 +
            if (g[i][y] != 0) {
 +
                if ((mask & 1 << g[i][y]) != 0)
 +
                    return false;
 +
                mask |= 1 << g[i][y];
 +
            }
 +
        return true;
 +
    }
 +
 +
    private boolean isColValid(int[][] g, int x) {
 +
        int i, mask = 0;
 +
        for (i = 0; i < DIMSQR; ++i)
 +
            if (g[x][i] != 0) {
 +
                if ((mask & 1 << g[x][i]) != 0)
 +
                    return false;
 +
                mask |= 1 << g[x][i];
 +
            }
 +
        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;
 +
                    mask |= 1 << g[xx][yy];
 +
                }
 +
        return true;
 +
    }
 +
}
[[Category: Programming Competitions]]
[[Category: Programming Competitions]]

Latest revision as of 20:41, 6 April 2016

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

Solutions

Put your solutions here!

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) {
       int i, mask = 0;
       for (i = 0; i < DIMSQR; ++i)
           if (g[i][y] != 0) {
               if ((mask & 1 << g[i][y]) != 0)
                   return false;
               mask |= 1 << g[i][y];
           }
       return true;
   }

   private boolean isColValid(int[][] g, int x) {
       int i, mask = 0;
       for (i = 0; i < DIMSQR; ++i)
           if (g[x][i] != 0) {
               if ((mask & 1 << g[x][i]) != 0)
                   return false;
               mask |= 1 << g[x][i];
           }
       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;
                   mask |= 1 << g[xx][yy];
               }
       return true;
   }
}
Personal tools