当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

生成数独矩阵--《编程之美》1.15节

发表于: 2014-08-18   作者:cherishLC   来源:转载   浏览次数:
摘要: 生成数独矩阵,定义参见《编程之美》第1.15节. 程序可以直接运行 import java.util.ArrayList; import java.util.List; import java.util.Set; import java.util.TreeSet; /** * 生成数独矩阵,定义参见《编程之美》第1.15节. * * @author LC */
生成数独矩阵,定义参见《编程之美》第1.15节.
程序可以直接运行
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * 生成数独矩阵,定义参见《编程之美》第1.15节.
 * 
 * @author LC
 */
public class Sudoku {
	Cell g[][] = new Cell[9][9];

	public Sudoku() {
		for (int i = 0; i < g.length; i++) {
			for (int j = 0; j < g[i].length; j++) {
				g[i][j] = new Cell();
			}
		}
	}

	//检查整个矩阵是否满足数独的条件,不允许有空格
	boolean check() {
		//检查每行是否数字不重复
		Set<Integer> s = new TreeSet<>();

		//检查每个小块是否数字不重复
		for (int r = 0; r < 3; r++) {
			for (int c = 0; c < 3; c++) {
				int rShift = r * 3;
				int cShift = c * 3;
				s.clear();

				for (int i = 0; i < 3; i++) {
					for (int j = 0; j < 3; j++) {
						Cell cell = g[rShift + i][cShift + j];
						if (!cell.isValid() || s.contains(cell.number)) {
							System.out.println("error in block (" + r + ", "
									+ c + ") with duplicated " + cell.number);

							return false;
						} else
							s.add(cell.number);

					}
				}

			}
		}

		for (int i = 0; i < g.length; i++) {
			s.clear();
			for (int j = 0; j < g[i].length; j++) {
				Cell cell = g[i][j];
				if (!cell.isValid() || s.contains(cell.number)) {
					System.out.println("error in row " + i
							+ " with duplicated " + cell.number);
					return false;
				} else
					s.add(cell.number);

			}

		}

		//检查每列是否数字不重复
		for (int j = 0; j < g[0].length; j++) {
			s.clear();
			for (int i = 0; i < g.length; i++) {
				Cell cell = g[i][j];
				if (!cell.isValid() || s.contains(cell.number)) {
					System.out.println("error in column " + j
							+ " with duplicated " + cell.number);
					return false;
				} else
					s.add(cell.number);
			}

		}

		return true;

	}

	//检查整个矩阵是否满足数独的条件,允许有空格;该方法可以用于游戏中检测选手的输入是否有误
	boolean checkCurrent() {
		//检查每行是否数字不重复
		Set<Integer> s = new TreeSet<>();

		//检查每个小块是否数字不重复
		for (int r = 0; r < 3; r++) {
			for (int c = 0; c < 3; c++) {
				int rShift = r * 3;
				int cShift = c * 3;
				s.clear();

				for (int i = 0; i < 3; i++) {
					for (int j = 0; j < 3; j++) {
						Cell cell = g[rShift + i][cShift + j];
						if (!cell.isValid())
							continue;

						if (s.contains(cell.number)) {
							System.out.println("error in block (" + r + ", "
									+ c + ") with duplicated " + cell.number);

							return false;
						} else
							s.add(cell.number);

					}
				}

			}
		}

		for (int i = 0; i < g.length; i++) {
			s.clear();
			for (int j = 0; j < g[i].length; j++) {
				Cell cell = g[i][j];
				if (!cell.isValid())
					continue;

				if (s.contains(cell.number)) {
					System.out.println("error in row " + i
							+ " with duplicated " + cell.number);
					return false;
				} else
					s.add(cell.number);

			}

		}

		//检查每列是否数字不重复
		for (int j = 0; j < g[0].length; j++) {
			s.clear();
			for (int i = 0; i < g.length; i++) {
				Cell cell = g[i][j];
				if (!cell.isValid())
					continue;

				if (s.contains(cell.number)) {
					System.out.println("error in column " + j
							+ " with duplicated " + cell.number);
					return false;
				} else
					s.add(cell.number);
			}

		}

		return true;

	}

	//生成合法的数独矩阵,尝试性的生成,选取数字用了随机化方法
	boolean generateValidMatrix() {
		int rollBackCount = 0;

		int i = 0;
		int j = 0;
		//生成数独矩阵,每个单元逐次生成,顺序为从左到右,从上到下
		while (i < g.length) {
			int rShift = i / 3 * 3;
			int cShift = j / 3 * 3;

			Cell cell = g[i][j];

			//剔除该列已有的数字
			for (int r = 0; r < i; r++) {
				cell.alternativeNumbers.remove((Integer) g[r][j].number);
			}

			//剔除该行已有的数字
			for (int c = 0; c < j; c++) {
				cell.alternativeNumbers.remove((Integer) g[i][c].number);
			}

			//剔除该块已有的数字
			for (int r = rShift; r <= i; r++) {
				for (int c = cShift; c < cShift + 3; c++) {
					cell.alternativeNumbers.remove((Integer) g[r][c].number);
				}
			}
			if (cell.hasAlternativeNumber()) {
				cell.pickAnAlternativeNumberRandomlyAndRemoveIt();//这一步中已经将当选的数字从可选数字列表中删除了
				//转到下一个要处理的cell
				j++;
				if (j == g[0].length) {
					j = 0;
					i++;
				}
			} else {//回退
				rollBackCount++;
				cell.init();
				//找到上一个cell
				if (j > 0) {
					--j;
				} else {
					--i;
					j = g[0].length - 1;
				}

				Cell lastCell = g[i][j];//没这一步也行
				lastCell.number = 0;

			}
		}

		System.out.println("生成该数独矩阵时回退了" + rollBackCount + "步");
		return true;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < g.length; i++) {
			for (int j = 0; j < g[i].length; j++) {
				sb.append(g[i][j].toString());
				if (j % 3 == 2)
					sb.append(' ');
			}
			sb.append('\n');
			if (i % 3 == 2 && i != g.length - 1)
				sb.append('\n');
		}

		return sb.toString();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Sudoku s = new Sudoku();
		s.generateValidMatrix();
		System.out.println(s);
		boolean b = s.check();

		System.out.println("生成的数独矩阵是否通过了检测?  " + b);
	}
}

//数独的一个单元格
class Cell {
	int number = 0;//该单元中的数字,为0表示为空, 有效数字为1~9
	List<Integer> alternativeNumbers;//当前可选的数字, 生成数独矩阵时使用

	void init() {
		number = 0;
		alternativeNumbers = new ArrayList<>();//当前可选的数字
		for (int i = 1; i <= 9; i++) {
			alternativeNumbers.add(i);

		}
	}

	public Cell() {
		init();
	}

	/**
	 * @return 该单元 是否还有满足数独规则的数字可用
	 */
	boolean hasAlternativeNumber() {
		return alternativeNumbers.size() > 0;
	}

	/**
	 * 随机选取一个满足数独规则的数字作为该单元的数字,并将其从可选数字集合中剔除
	 */
	void pickAnAlternativeNumberRandomlyAndRemoveIt() {
		int idx = (int) (Math.random() * alternativeNumbers.size());
		number = alternativeNumbers.get(idx);
		alternativeNumbers.remove(idx);
	}

	@Override
	public String toString() {
		//		System.out.println(number);
		return number <= 0 ? " " : String.valueOf(number);
	}

	/**
	 * @return 当前单元中是否有有效的数字
	 */
	boolean isValid() {
		return number > 0 && number < 10;
	}
}

生成数独矩阵--《编程之美》1.15节

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
《编程之美》读书笔记(七):数独游戏解析 前言:说实话,所有游戏都是有一定规律可循的,只要掌握游
  其实一直都很想写个数独的游戏,最近刚好看了《编程之美》,得到了一些启发。   好,这时第一
今天开始看编程之美 。第一个问题是CPU的使用率控制,微软的问题果然高大上,我一看就傻了,啥也不
3、题目:能否快速找出一个数组(简单起见,数组中元素值各不一样)中的两个数字,让这两个数字之和
环境:PowerDesigner 15.1 问题:生成数据库报表文件 解决: 当设计出数据库以后,有一份正规的DOC
题目: 有一个无序、元素个数为2n的正整数数组,要求:如何能吧这个数组分割为元素个数为n的两个数
编程之美:平面最近点对 一.概念引入 最接近点对问题的提法是:给定平面上n个点,找其中的一对点,使
编程之美电子书下载 24点游戏大家都知道:4张牌,可以进行+ - * / 四种运算,可以使用括号,每个牌
题目: 有一个无序、元素个数为2n的正整数数组,要求:如何能吧这个数组分割为元素个数为n的两个数
第一章 软件架构是什么 软件架构应该... asoftware architect that the system should be friendly
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号