数独

java | 2016-03-05 21:00:05 | 阅读 11798 次 | 评论(0)

基本设计思想与8皇后差不多,注意2个细节

1,遍历时分数组中是否有原始数

2,在没有原始数时找k值时要用temp数组处理,主要是让temp[i][j]取不同的K值,以便递归。

package qunxingw.com;

import java.util.Scanner;

public class Soudu {

	static int[][] array = new int[9][9];

	public void show(int array[][]) {
		for (int i = 0; i < 9; i++) {

			for (int j = 0; j < 9; j++) {

				System.out.print(array[i][j] + "   ");
			}
			System.out.println("\n");
		}
		System.out.println("**************************************");
	}

	public void setarray(int array[][], int i, int j, int k) {
		array[i][j] = k;
	}

	public boolean check(int array[][], int r, int c, int k) {
		int i, j;
		// 该单元格的所在行的其他单元格是否已选K
		for (i = 0; i < 9; i++) {
			if (array[i][c] == k) {
				return false;
			}
		}
		// 该单元格的所在列的其他单元格是否已选K
		for (j = 0; j < 9; j++) {
			if (array[r][j] == k) {
				return false;
			}
		}
		// 该单元格小九宫内是否可选k
		int temp1, temp2;
		temp1 = r / 3 * 3;
		temp2 = c / 3 * 3;

		for (i = temp1; i < temp1 + 3; i++) {
			for (j = temp2; j < temp2 + 3; j++) {
				if (array[i][j] == k) {
					return false;
				}
			}
		}
		return true;
	}

	public void soudugame(int array[][], int num) {
		
		int i, j;
		int[][] temp = new int[9][9];
		for (i = 0; i < 9; i++)
			for (j = 0; j < 9; j++) {
				temp[i][j] = array[i][j];
			}

		i = num / 9;
		j = num % 9;
		// 此格有数时
		if (temp[i][j] != 0) {
			if (num == 80) {
				// count++;
				show(temp);

			} else {
				soudugame(temp, num + 1);
			}
		}
		// 0时选个不冲突的数
		else {
			for (int k = 1; k <= 9; k++) {
				if (check(temp, i, j, k)) {
					temp[i][j] = k;

					if (num == 80) {
						// count++;
						show(temp);
					} else {
						soudugame(temp, num + 1);
					}

				}
				temp[i][j] = 0;
			}

		}
	}

	public static void main(String[] args) {
		int i, j, k, n;

		Soudu soudu = new Soudu();
		Scanner scan = new Scanner(System.in);
		System.out.println("原始数独有几个数?");
		n = scan.nextInt();
		System.out.println("第一个数:行,第二个为:列;第三个数为 数独数");
		while (n > 0) {
			n--;
			i = scan.nextInt() - 1;// 行号从1--9
			j = scan.nextInt() - 1;// 列号 1--9
			k = scan.nextInt();// 此格中初始固定值
			soudu.setarray(array, i, j, k);

		}
		soudu.show(array);
		soudu.soudugame(array, 0);

	}
}

/////////////////////////////////////////

 原始数独有几个数?
17
第一个数:行,第二个为:列;第三个数为 数独数


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

**************************************
0   5   0   6   0   0   0   0   0   


0   0   0   0   0   0   7   3   0   


0   0   0   1   0   0   0   0   0   


0   0   0   0   7   0   8   0   0   


0   6   0   0   0   0   0   5   0   


1   0   0   0   0   0   0   0   0   


7   0   0   0   4   0   2   0   0   


0   0   4   0   3   0   0   0   0   


0   0   0   5   0   0   0   6   0   


*************************************

3   5   1   6   2   7   9   4   8   


2   8   6   4   5   9   7   3   1   


4   7   9   1   8   3   6   2   5   


5   4   3   2   7   1   8   9   6   


8   6   7   3   9   4   1   5   2   


1   9   2   8   6   5   3   7   4   


7   1   5   9   4   6   2   8   3   


6   2   4   7   3   8   5   1   9   


9   3   8   5   1   2   4   6   7   


文章评论,共0条
游客请输入验证码
浏览161934次
最新评论