sudoku.java

可算sudoku的语法 规则很简单, 9*9 的格子中

/*
 * Created on 2005/6/2
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
import java.io.*;

/**
 * 
 */
public class sudoku {

	static void SolvePuzzle() {
		/*
		 * write your algorithm here
		 */
		ReadPuzzle("answer.txt");
	}
	
	public static void main(String[] args) {
		String datafile = "sudoku.txt";
		if (args.length > 1)
			datafile = args[0];
		System.out.println("Read puzzle file:" + datafile);
		ReadPuzzle(datafile);
		PrintPuzzle();
		// Solve the puzzle
		long starttime = System.currentTimeMillis();
		SolvePuzzle();
		long endtime = System.currentTimeMillis();		
		System.out.println("\nSolve puzzle in " + (endtime-starttime) + " microseconds.");
		PrintPuzzle();		
		boolean success = CheckRule();
		if (success) 
			System.out.println("Good Job!");
		else
			System.out.println("Oops! test failed, try again.");
	}
	
	static void ReadPuzzle(String file) {
		try {
			BufferedReader in = new BufferedReader(new FileReader(file));
			String str;
			for (int r=0; r<9; r++) {
				try {
					str = in.readLine();
				} catch (IOException e1) {
					str = "";
				}
				for (int c=0; c<9; c++) {
					puzzle[r][c] = 0;						
					if (str.length() > c) {
						puzzle[r][c] = (byte) (str.charAt(c)-'0');
					}
				}
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
			return;
		}		
	}
	
	static void PrintPuzzle() {
		int row,col;
		System.out.println(" |123456789");
		System.out.println("-+---------");		
		for (row=0; row<9; row++) {
			System.out.print(row+1);
			System.out.print("|");			
			for (col=0;col<9; col++) {
				byte b = puzzle[row][col];
				if (b<1 || b>9)
					System.out.print('-');
				else
					System.out.print(puzzle[row][col]);
			}
			System.out.println("");
		}		
		System.out.println("-+---------");		
	}
	
	static boolean CheckRule() {
		int[] row_score = {0,0,0,0,0,0,0,0,0};
		int[] col_score = {0,0,0,0,0,0,0,0,0};
		int[] box_score = {0,0,0,0,0,0,0,0,0};
		int r,c, box_r, box_c;
		int score=0;
		for (r=0; r<9; r++) {
			for (c=0; c<9; c++) {
				// check row
				byte b = puzzle[r][c];
				if (b<1 || b>9) {
					System.out.println("(" + (r+1) + "," + (c+1) + ") unknown data.");
					return false;
				}
				b--;
				if (row_score[b]!=score) {
					System.out.println("Row " + (r+1) + " test failed.");
					return false;
				}
				else {
					row_score[b]++;
				}
				// check column
				b = puzzle[c][r];
				if (b<1 || b>9) {
					System.out.println("(" + (r+1) + "," + (c+1) + ") unknown data.");
					return false;
				}
				b--;
				if (col_score[b]!=score) {
					System.out.println("Column " + (r+1) + " test failed.");
					return false;
				}
				else {
					col_score[b]++;
				}
				// check 3*3 box
				box_r = (r/3)*3 + (c/3);
				box_c = (r%3)*3 + (c%3);
				b = puzzle[box_r][box_c];
				if (b<1 || b>9) {
					System.out.println("(" + (box_r+1) + "," + (box_c+1) + ") unknown data.");
					return false;
				}
				b--;
				if (box_score[b]!=score) {
					System.out.println("Box test failed at (" + (box_r+1) + "," + (box_c+1)+ ").");
					return false;
				}
				else {
					box_score[b]++;
				}				
			}
			score++;
		}
		return true;
	}
	
	static byte[][] puzzle = {
			{ 1,2,3,4,5,6,7,8,9 },
			{ 1,2,3,4,5,6,7,8,9 },
			{ 1,2,3,4,5,6,7,8,9 },
			{ 1,2,3,4,5,6,7,8,9 },
			{ 1,2,3,4,5,6,7,8,9 },
			{ 1,2,3,4,5,6,7,8,9 },
			{ 1,2,3,4,5,6,7,8,9 },
			{ 1,2,3,4,5,6,7,8,9 },
			{ 1,2,3,4,5,6,7,8,9 }};
}