java数独计算器

  • b9_339377
    了解作者
  • 29.7KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-04 06:27
    上传日期
纯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]}; } } }
评论
    相关推荐
    • Java
      Java 对于Java练习
    • java
      Java Java基础
    • Java
      Java 我创建的Java项目
    • JAVA教程
      一本非常不错的清华大学java教程,讲解非常详细,看了就知道。
    • Java Cipher
      Java Cipher 加密和解密工具 附带源码 Java Cipher 加密和解密工具 附带源码 Java Cipher 加密和解密工具 附带源码 Java Cipher 加密和解密工具 附带源码
    • javabank
      Java银行 Java com的模拟操作将在bancárias上发布! 要求:Java 8。
    • java 李兴华
      java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java 李兴华 java ...
    • JAVA教程
      详细介绍了JAVA语言程序设计,对JAVA的基础知识运用实例的方式来讲解,使初学者能够非常轻松的掌握。
    • java程序
      java程序-吃点点java程序-吃点点java程序-吃点点java程序-吃点点java程序-吃点点java程序-吃点点
    • Java
      Java 2021/02/19 .java Main.java 学生.java Bmi.java 。班级 Bmi类 主类 MyBmi.class 学生班 学生样本类 2021/02/20 .java DeleteFile.java WriteFile.java MyDataPrint.java 。班级 DeleteFile.class ...