java数独计算器升级版(包含出题器)

  • S5_947360
    了解作者
  • 35.1KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-05 09:54
    上传日期
第一部分:纯java实现的数独计算器,使用回溯法递归求解。同时实现了唯一候选值法、隐性唯一候选值法、区块删减法等最优求解法。 第二部分:java数独出题器,运用回溯算法实现自定义出题,绝对的随机出题,可以自定义难度,所出题目有唯一解。后续将实现更多删减法出题,使得所出题型更加科学。
ALGORITHM.rar
内容介绍
package com.shudu.algorithm.impl; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; import com.shudu.algorithm.Algorithm; import com.shudu.model.Cell; import com.shudu.model.Group; import com.shudu.model.Palace; /** * 区块删减法 * @author CBB */ public class BlockDeleteAlgorithm implements Algorithm{ /** * 数独宫格 */ private Palace palace; /** * 行区块二维数组 */ private RowBlock[][] rowBlocks; /** * 列区块二维数组 */ private ColumnBlock[][] columnBlocks; @Override public boolean execute(Palace palace) { //如果不是同一个数独宫格,则进行初始化 if(this.palace!=palace){ this.init(palace); } //行区块删减法 for(int i=0;i<9;i++){ for(int j=0;j<3;j++){ RowBlock rowBlock = rowBlocks[i][j]; Set<Integer> testingNum = rowBlock.getTestingNum(); if(testingNum!=null){ RowBlock[] rowOtherBlocks = rowBlock.getRowOtherBlocks();//获取其他行区块 RowBlock[] latticeOtherBlocks = rowBlock.getLatticeOtherBlocks();//获取其他九宫格区块 for(Integer num:testingNum){//针对每个检测数 //这里调用区块删减法核心,如果删减成功返回true if(blockDelete(num,rowOtherBlocks,latticeOtherBlocks)){ return true; } } } } } //列区块删减法 for(int i=0;i<3;i++){ for(int j=0;j<9;j++){ ColumnBlock columnBlock = columnBlocks[i][j]; Set<Integer> testingNum = columnBlock.getTestingNum(); if(testingNum!=null){ ColumnBlock[] columnOtherBlocks = columnBlock.getColumnOtherBlocks();//获取其他行区块 ColumnBlock[] latticeOtherBlocks = columnBlock.getLatticeOtherBlocks();//获取其他九宫格区块 for(Integer num:testingNum){//针对每个检测数 //这里调用区块删减法核心,如果删减成功返回true if(blockDelete(num,columnOtherBlocks,latticeOtherBlocks)){ return true; } } } } } return false; } @Override public String getName() { return "区块删减法"; } public void init(Palace palace){ this.palace=palace; this.rowBlocks=new RowBlock[9][3]; for(int i=0;i<9;i++){ for(int j=0;j<3;j++){ RowBlock rowBlock = new RowBlock(i,j); this.rowBlocks[i][j] = rowBlock; for(int z=0;z<3;z++){ rowBlock.cells[z]=this.palace.getCell(i, j*3+z); } rowBlock.r = this.palace.getRows()[i]; rowBlock.l = this.palace.getLattices()[(i/3)*3+j]; } } this.columnBlocks=new ColumnBlock[3][9]; for(int i=0;i<3;i++){ for(int j=0;j<9;j++){ ColumnBlock columnBlock = new ColumnBlock(i,j); this.columnBlocks[i][j] = columnBlock; for(int z=0;z<3;z++){ columnBlock.cells[z]=this.palace.getCell(i*3+z, j); } columnBlock.c = this.palace.getColumns()[j]; columnBlock.l = this.palace.getLattices()[i*3+j/3]; } } } /** * 区块删减法核心 * @param num 检测数 * @param firstBlocks 其他区块1 * @param secondBlocks 其他区块2 * @return 检测成功-true,失败-false */ private boolean blockDelete(Integer num,Block[] firstBlocks,Block[] secondBlocks){ boolean firstExists = false;//检测数在第一组区块中是否存在 boolean secondExists = false;//检测数在第二组区块中是否存在 for(int z=0;z<3;z++){ if(firstBlocks[0].cells[z].getV()==null &&firstBlocks[0].cells[z].getCandidateValue().contains(num)){ firstExists = true; break; } if(firstBlocks[1].cells[z].getV()==null &&firstBlocks[1].cells[z].getCandidateValue().contains(num)){ firstExists = true; break; } } for(int z=0;z<3;z++){ if(secondBlocks[0].cells[z].getV()==null &&secondBlocks[0].cells[z].getCandidateValue().contains(num)){ secondExists = true; break; } if(secondBlocks[1].cells[z].getV()==null &&secondBlocks[1].cells[z].getCandidateValue().contains(num)){ secondExists = true; break; } } /** * 如果检测数在区块组一和区块组二,一方存在另一方不存在, * 则算法生效,清除存在方的检测数 */ if(firstExists&&!secondExists){ for(int z=0;z<3;z++){ if(firstBlocks[0].cells[z].getV()==null &&firstBlocks[0].cells[z].getCandidateValue().contains(num)){ firstBlocks[0].cells[z].getCandidateValue().remove(num); } if(firstBlocks[1].cells[z].getV()==null &&firstBlocks[1].cells[z].getCandidateValue().contains(num)){ firstBlocks[1].cells[z].getCandidateValue().remove(num); } } return true; } if(!firstExists&&secondExists){ for(int z=0;z<3;z++){ if(secondBlocks[0].cells[z].getV()==null &&secondBlocks[0].cells[z].getCandidateValue().contains(num)){ secondBlocks[0].cells[z].getCandidateValue().remove(num); } if(secondBlocks[1].cells[z].getV()==null &&secondBlocks[1].cells[z].getCandidateValue().contains(num)){ secondBlocks[1].cells[z].getCandidateValue().remove(num); } } return true; } return false; } /** * 内部抽象类---区块 * @author CBB */ public abstract class Block{ int i;//行坐标 int j;//列坐标 Cell[] cells;//区块包含单元格 public Block(int i,int j) { this.i=i; this.j=j; this.cells=new Cell[3]; } /** * 获取该区块检测数集合,不需要被检测返回null */ public Set<Integer> getTestingNum(){ //先获取候选值数大于2的单元格列表 List<Cell> list = new ArrayList<Cell>(); for(int z=0;z<3;z++){ if(cells[z].getV()==null&&cells[z].getCandidateValue().size()>=2){ list.add(cells[z]); } } //如果单元格数不足2则返回null if(list.size()<2){ return null; } //构建检测数集合 Set<Integer> result = new HashSet<Integer>(9); //如果在列表中存在重复的候选值,则将该候选值放进检测数集合 for(int a=0;a<list.size();a++){ Cell temp = list.get(a); for(Integer candidate:temp.getCandidateValue()){ for(int b=a+1;b<list.size();b++){ if(list.get(b).getCandidateValue().contains(candidate)){ result.add(candidate); } } } } if(result.size()==0){ return null; } return result; } } /** * 内部类---行区块 * @author CBB */ public class RowBlock extends Block{ Group r;//对应行 Group l;//对应九宫格 public RowBlock(int i,int j) { super(i, j); } /** * 获取该行其他行区块 */ public RowBlock[] getRowOtherBlocks(){ return new RowBlock[]{rowBlocks[i][(j+1)%3],rowBlocks[i][(j+2)%3]}; } /** * 获取该九宫格其他行区块 */ public RowBlock[] getLatticeOtherBlocks(){ return new RowBlock[]{rowBlocks[(i/3)*3+(i+1)%3][j],rowBlocks[(i/3)*3+(i+2)%3][j]}; } } /** * 内部类---列区块 * @author CBB */ public class ColumnBlock extends Block{ Group c;//对应列 Group l;//对应九宫格 public ColumnBlock(int i,int j) { super(i, j); } /** * 获取该列其他列区块 */ public ColumnBlock[] getColumnOtherBlocks(){ return new ColumnBlock[]{columnBlocks[(i+1)%3][j],columnBlocks[(i+2)%3][j]}; } /** * 获取该九宫格其他列区块 */ public ColumnBlock[] getLatticeOtherBlocks(){ return new ColumnBlock[]{columnBlocks[i][(j/3)*3+(j+1)%3],columnBlocks[i][(j/3)*3+(j+2)%3]}; } } }
评论
    相关推荐
    • SVM 算法 java 实现
      SVM 算法 java 实现了调用接口,只要传入数据即可,调用了encog这个开源包的SVM算法,也是官方libsvm的。
    • 经典算法Java实现
      包括JAVA的经典算法和实现,用于JAVA的学习和研究
    • 遗传算法java工程
      工程利用遗传算法解决多路复用器的模拟状态,里面有充分的技术文档(英语)以及代码注释,自己写的,用不到了以后。贡献出来给大家。
    • LRU算法 java实现
      LRU算法java实现
    • 国密算法java实现
      国家商用密码管理局公布的标准国密算法SM4的算法实现哦
    • 遗传算法java实现
      本代码为Java实现的遗传算法,压缩包中有详细的说明,希望对各位有帮助
    • SVM 算法 java版本
      SVM 算法 java 实现了调用接口,只要传入数据即可,调用了encog这个开源包的SVM算法,也是官方libsvm的。
    • AHP算法java实现
      java实现AHP算法,包括文档说明,算法介绍等ppt文档 欢迎使用
    • DES算法Java实现
      DES算法Java代码实现,适用于学生交作业
    • tomasulo算法java实现
      自己用java实现的一个简单的tomasulo算法的实现对,并且做了界面,有助于对tomasulo算法有一个更好的了解