gistfile1.java

/*
 * @date 2010/10/04
 * @author Pieter Kokx <p.a.kokx@student.tue.nl> (0747517)
 * @author Mitchel Brunings <m.d.brunings@student.tue.nl> (0746097)
 */

import java.util.*;
import java.io.*;

public class Sudoku {

    Scanner stdin;
    int grid[][];

    /**
     * Get the next integer from the file.
     */
    int getNextInteger(Scanner file) {
        String next;

        while (file.hasNext()) {
            next = file.next();

            // first check if it is a .
            if (next.equals(".")) {
                return 0;
            }

            try {
                // execute this only if we have an integer
                return Integer.parseInt(next);
            } catch (NumberFormatException e) {
                continue;
            }
        }

        // this will only happen if the input file is incorrectly formatted
        return 0;
    }

    /**
     * Read a file and parse the grid.
     */
    void readGrid(String filename) {
        grid = new int[9][9];

        try {
            // read the file and
            Scanner file = new Scanner(new File(filename));

            for (int x = 0; x < 9; x++) {
                for (int y = 0; y < 9; y++) {
                    grid[x][y] = getNextInteger(file);
                }
            }
        } catch (FileNotFoundException e) {
            System.out.println("http://www.youtube.com/watch?v=EK2tWVj6lXw");
        }
    }

    /**
     * Display the grid
     */
    void displayGrid() {
        System.out.println("-------------------------");

        // now display the grid itself
        for (int x = 0; x < 9; x++) {
            System.out.print("| ");
            for (int y = 0; y < 9; y++) {

                // display the number, or a . if it is a 0
                if (grid[x][y] > 0) {
                    System.out.print(grid[x][y] + " ");
                } else {
                    System.out.print(". ");
                }

                // show the horizontal bars
                if ((y + 1) % 3 == 0) {
                    System.out.print("| ");
                }
            }
            System.out.println("");

            // show the vertical bars
            if ((x + 1) % 3 == 0) {
                System.out.println("-------------------------");
            }
        }
    }

    boolean givesRowConflict(int x, int y, int n) {
        // false means no conflict

        for (int i = 0; i < 9; i++) {
            if (!(i == x)) {
                if (n == grid[i][y]) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean givesColConflict(int x, int y, int n) {
        // false means no conflict

        for (int i = 0; i < 9; i++) {
            if (!(i == y)) {
                if (n == grid[x][i]) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean givesBoxConflict(int x, int y, int n) {
        // false means no conflict

        int x0 = x - (x % 3);
        int y0 = y - (y % 3);

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (!((x0 + i == x) && (y0 + j == y))) {
                    if (n == grid[x0 + i][y0 + j]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    boolean givesConflict(int x, int y, int n){
        return (givesRowConflict(x, y, n) || givesColConflict(x, y, n) || givesBoxConflict(x, y, n));
    }

    int[] searchZero() {
        for (int x = 0; x < 9; x++) {
            for (int y = 0; y < 9; y++) {
                if (grid[x][y] == 0) {
                    return new int[]{x, y};
                }
            }
        }
        return new int[]{-1, -1};
    }

    boolean tryToSolve(){
        //Look for something to fill in
        int[] xy;
        xy = searchZero();
        int xempty = xy[0];
        int yempty = xy[1];
        if (xempty == -1 || yempty == -1){
            //Nothing to fill in; we're done here.
            return true;
        }

        //Try to fill in some numbers. If it works, we'll be very happy :)
        for (int n = 1; n <= 9; n++){
            if (!givesConflict(xempty, yempty, n)){
                //There was no conflict, let's fill it in!
                grid[xempty][yempty] = n;
                //Moving on to the next step, if we find a solution, we're TRUEly happy.
                if (tryToSolve()){
                    //It appears that we are happy with the number we filled in.
                    return true;
                }else{
                    //It appears that we aren't happy with the number we filled in after all.
                    //Let's remove it then!
                    grid[xempty][yempty] = 0;
                }
            }
        }
        //If all else fails:
        return false;
    }

    /**
     * Solve the sudoku.
     */
    void execute() {
        stdin = new Scanner(System.in);

        readGrid(stdin.next());
/*
grid = new int[][] {
{ 2, 6, 0, 0, 0, 1, 0, 9, 4 },
{ 3, 0, 0, 0, 0, 7, 1, 0, 0 },
{ 0, 0, 0, 0, 9, 0, 0, 0, 0 },
{ 7, 0, 6, 5, 0, 0, 2, 0, 9 },
{ 0, 3, 0, 0, 2, 0, 0, 6, 0 },
{ 9, 0, 2, 0, 0, 6, 3, 0, 1 },
{ 0, 0, 0, 0, 5, 0, 0, 0, 0 },
{ 0, 0, 7, 3, 0, 0, 0, 0, 2 },
{ 4, 1, 0, 7, 0, 0, 0, 8, 0 },
};
*/

        displayGrid();

        if (tryToSolve()){
            displayGrid();
        }else{
            System.out.println("No solution");
        }
    }

    /**
     * Main method
     */
    public static void main(String[] args) {
        new Sudoku().execute();
    }
}