完整的九宫格算法程序 (2).doc

package ninegrid;import java.util.ArrayList;import java.util.List;/* * 功能说明：九宫格功能实现bean * * author ClarkJia * */public class NineGrid protected Integer nineGrid = new Integer99; /九宫格阵列图 protected Boolean existsGrid = new Boolean99;/九宫每个位置是否已经存在值 protected int x = 0; /当前填空点位x坐标 protected int y = 0; /当前填空点位y坐标 protected int times = 0;/计算次数统计 / 初始构造九宫格 public NineGrid(Integer initData) /ArrayUtils.cloneArray(nineGrid, initData);/复制原始九宫格 for (int i = 0; i 9; i+) for (int j = 0; j 0) existsGridij = true; else existsGridij = false; public NineGrid() /* * 查找可填充的合法的x,y值集 * return */ public Integer getValidData() /空格中数字已经存在，则返回null if (existsGridxy) return null; List tempList = new ArrayList(); / 找到x轴剩余的数字 for (int i = 1; i 10; i+) boolean hasValue = false; for (int k = 0; k 9; k+) if (nineGridxk = i) hasValue = true; break; / 在x轴中没有找到 if (!hasValue) tempList.add(i); / 找xy轴都没有的数字 for (int i = 0; i tempList.size(); i+) Integer t = (Integer) tempList.get(i); boolean hasValue = false; for (int k = 0; k 9; k+) if (nineGridky = Value() hasValue = true; break; / y轴中找到x的数字则删除它 if (hasValue) tempList.remove(i); i-; for (int i = 0; i tempList.size(); i+) Integer t = (Integer) tempList.get(i); / 检查这个是否能满足小三宫格 int starti = (x / 3) * 3; int startj = (y / 3) * 3; boolean hasEqual = false;/ 表示是否已经存在，若存在则删除 for (int m = starti; m starti + 3; m+) for (int n = startj; n startj + 3; n+) if (nineGridmn != null & t.equals(nineGridmn) hasEqual = true; break; if (hasEqual) tempList.remove(i); i-; Integer returnInts = new IntegertempList.size(); for (int i = 0; i tempList.size(); i+) Integer t = (Integer) tempList.get(i); returnIntsi = Value(); return returnInts; /* * 查找横行或竖列中空格最少的那个点位置 * return */ public String getLeastLocation() int xLeast = 10; / x 轴中空缺数最少个数 int xI = 10; / 索引 int yLeast = 100; int yI = 10; for (int i = 0; i 9; i+) int temp = 0; for (int j = 0; j 0 & temp xLeast) xLeast = temp; xI = i; / 如果x只剩下一个空位，则填写空位 if (xLeast = 1) return x + xI; else for (int i = 0; i 9; i+) int temp = 0; for (int j = 0; j 0 & temp xLeast) yLeast = temp; yI = i; if (xLeast yLeast) return x + xI; else if (yLeast = xLeast) return y + yI; else return null; /* * 打印结果 * * return */ public void doPrint() System.out.println( -); for (int i = 0; i 9; i+) for (int j = 0; j 9; j+) System.out.print( | + nineGridij); System.out.println( |); System.out.println( -); /* * 检查是否生成成功 * * return */ public boolean checkResult() for (int i = 0; i 9; i+) for (int j = 0; j 9; j+) if (nineGValue() = 0) / 若仍存在0位置点，则求解失败 return false; return true; public Integer get_nine() return nineGrid; public void set_nine(Integer _nine) this.nineGrid = _nine; public Boolean get_bool() return existsGrid; public void set_bool(Boolean _bool) this.existsGrid = _bool; public int getX() return x; public void setX(int x) this.x = x; public int getY() return y; public void setY(int y) this.y = y; public void setValue(int value) nineGridxy = value; existsGridxy = true; public int getValue() return nineGridxy; public int getTimes() return times; public void setTimes(int times) this.times = times; package ninegrid;import java.util.ArrayList;import java.util.List;/* * 功能说明：九宫格堆栈模拟 * * author ClarkJia * */public class NineGridList private List nineGridList = new ArrayList();/模拟九宫格list堆栈 /压栈 public void push(NineGrid jiuGong) nineGridList.add(jiuGong); /弹栈 public NineGrid pop() if (nineGridList.size() 0) NineGrid jiuGong = newJiuGong(NineGrid) nineGridList.remove(nineGridList.size() - 1); return jiuGong; else / System.out.println(题目给定九宫格无解); return null; /复制九宫格 public NineGrid newJiuGong(final NineGrid jiuGong) NineGrid temp = new NineGrid(); Integer d = new Integer99; Boolean b = new Boolean99; for (int i = 0; i 9; i+) for (int j = 0; j 9; j+) int aa = jiuGong.get_nine()ij; boolean bb = jiuGong.get_bool()ij; dij = aa; bij = bb; temp.set_bool(b); temp.set_nine(d); return temp; package ninegrid;/* * 功能说明：九宫格计算 * * author ClarkJia * */public class NineGridTest /* * 九宫格功能实现核心算法 * return */ public NineGrid genGridResult(NineGrid nineGrid) NineGridList stack = new NineGridList(); int times = 0;/计算次数 while (nineGrid != null & !nineGrid.checkResult() times+; String least = nineGrid.getLeastLocation(); if (least = null) System.out.println(此题无解, 请检查题目给定九宫格是否错误! ); break; else char t = least.charAt(0);/取出x、y坐标标志 int location = Integer.parseInt(least.substring(1, 2); for (int j = 0; j 0)/ 找到可填充数据 for (int k = 0; k 1 & k temp.length - 1)/ 如果有多个可填写值，则把多余数字组合成临时表，并压入堆栈 NineGrid tJiuGong = stack.newJiuGong(nineGrid); stack.push(tJiuGong); else / 未找到可填充数字，则弹出栈顶元素 nineGrid = stack.pop();/ 取出堆栈中暂存的栈顶未检查九宫数据表格，开始下一轮计算 break; if(null != nineGrid)nineGrid.setTimes(times); return nineGrid; public static void main(String agrs) / 九宫格初始数据阵列图 Integer initGrid = 7, 8, 0, 2, 3, 0, 1, 0, 5, 6, 0, 1, 0, 0, 0, 7, 0, 0, 9, 5, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 1, 6, 5, 0, 0, 2, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 6, 8, 7, 0, 3, 2, 0, 0, 0, 0, 0, 6, 0, 9, 0, 8, 0, 4, 0, 0, 0, 0, 0, 7, 6; long startTime = System.currentTimeMillis(); NineGridTest nineTest = new NineGridTest(); NineGrid nineGrid = nineTest.genGridResult(new NineGrid(initGrid);