BeginIndexRangeVO.java:
import java.io.Serializable;
public class BeginIndexRangeVO implements Serializable {
public BeginIndexRangeVO(int beginRowNum, int beginColNum) {
this.beginRowNum = beginRowNum;
this.beginColNum = beginColNum;
PointVO.java:
import java.io.Serializable;
public class PointVO implements Serializable {
private String tryNumber;
private List possibleNumbers;
private List impossibleNumbers;
private List possibleNumbers_bak;
public PointVO(String number, int rowNum, int colNum) {
this.code = this.rowNum + "-" + this.colNum;
}else if( this.colNum <= 6 ){
}else if( this.rowNum <= 6 ){
}else if( this.colNum <= 6 ){
}else if( this.colNum <= 6 ){
RowColVO.java:
import java.io.Serializable;
public class RowColVO implements Serializable {
public RowColVO(int rowNum, int colNum) {
ShuduSolver_backtracking.java:
public class ShuduSolver_backtracking {
private static final Map map_gongNum_beginIndexRange = new HashMap<>();
private static final Map> map_gongNum_numbers = new HashMap<>();
private static final Map> map_rowNum_numbers = new HashMap<>();
private static final Map> map_colNum_numbers = new HashMap<>();
private static Map map_code_point;
private static int deep_recursion = 0;
private static int count_filled = 0;
map_gongNum_beginIndexRange.put(1, new BeginIndexRangeVO(1, 1));
map_gongNum_beginIndexRange.put(2, new BeginIndexRangeVO(1, 4));
map_gongNum_beginIndexRange.put(3, new BeginIndexRangeVO(1, 7));
map_gongNum_beginIndexRange.put(4, new BeginIndexRangeVO(4, 1));
map_gongNum_beginIndexRange.put(5, new BeginIndexRangeVO(4, 4));
map_gongNum_beginIndexRange.put(6, new BeginIndexRangeVO(4, 7));
map_gongNum_beginIndexRange.put(7, new BeginIndexRangeVO(7, 1));
map_gongNum_beginIndexRange.put(8, new BeginIndexRangeVO(7, 4));
map_gongNum_beginIndexRange.put(9, new BeginIndexRangeVO(7, 7));
public static void main(String[] args) {
List
points = initChuPan( chupan ); map_code_point = points2CodeAndPointMap(points);
init_map_xxxNum_numbers( );
System.out.println("count_filled = " + count_filled);
calculatePossibleNumbers();
backtrackingAndCauseError();
System.out.println("aaaaaaaaaaaaaaaaaaaaaaaaaaa");
System.out.println( "递归深度 = " + deep_recursion );
private static boolean backtrackingAndCauseError() {
PointVO point = searchFirstBlankPoint();
System.out.println( "222222222222222222222222222222222222" );
System.out.println( "222222222222222222222222222222222222" );
System.out.println( "222222222222222222222222222222222222" );
System.out.println( "222222222222222222222222222222222222" );
int rowNum = point.getRowNum();
int colNum = point.getColNum();
String pointName = getPointName(rowNum, colNum);
List possibleNumbers = getPossibleNumbers( rowNum,colNum );
if( possibleNumbers.size() == 0 ){
possibleNumbers = deepCopyList( possibleNumbers );
int count_possible = possibleNumbers.size();
for( String possibleNumber:possibleNumbers ){
fillNumber( rowNum,colNum,possibleNumber );
boolean causeError = backtrackingAndCauseError();
clearNumber( rowNum,colNum,null );
if( count_error == count_possible ){
return backtrackingAndCauseError();
private static PointVO searchFirstBlankPoint() {
Set codes = map_code_point.keySet();
for( String code:codes ){
PointVO point = map_code_point.get(code);
if( point.getNumber() == null ){
private static void clearNumber(int rowNum, int colNum, String number) {
String code = getCode(rowNum, colNum);
PointVO point = map_code_point.get(code);
List impossibleNumbers = point.getImpossibleNumbers();
if( impossibleNumbers ==null ){
impossibleNumbers = new ArrayList<>();
point.setImpossibleNumbers( impossibleNumbers );
impossibleNumbers.add( number );
init_map_xxxNum_numbers( rowNum,colNum );
private static boolean gameSuccess(){
return count_filled == 81;
private static String getPointName(int rowNum, int colNum) {
return rowNum + "行" + colNum + "列";
private static void init_map_xxxNum_numbers( int targetRowNum,int targetColNum ){
Set numbers_currRow = map_rowNum_numbers.get(targetRowNum);
for (int colNum = 1; colNum <=9 ; colNum++) {
String code = getCode(targetRowNum, colNum);
PointVO point = map_code_point.get(code);
if( point.getNumber() == null ){
numbers_currRow.add( point.getNumber() );
Set numbers_currCol = map_colNum_numbers.get(targetColNum);
for (int rowNum = 1; rowNum <=9 ; rowNum++) {
String code = getCode(rowNum, targetColNum);
PointVO point = map_code_point.get(code);
if( point.getNumber() == null ){
numbers_currCol.add( point.getNumber() );
int gongNum = getGongNum(targetRowNum, targetColNum);
Set numbers_currGong = map_gongNum_numbers.get(gongNum);
numbers_currGong.clear();
BeginIndexRangeVO beginIndexRange = map_gongNum_beginIndexRange.get(gongNum);
int beginRowNum = beginIndexRange.getBeginRowNum();
int endRowNum = beginRowNum + 2;
int beginColNum = beginIndexRange.getBeginColNum();
int endColNum = beginColNum + 2;
for (int rowNum = beginRowNum; rowNum <=endRowNum ; rowNum++) {
for (int colNum = beginColNum; colNum <=endColNum ; colNum++) {
String code = getCode(rowNum, colNum);
PointVO point = map_code_point.get(code);
if( point.getNumber() == null ){
numbers_currGong.add( point.getNumber() );
private static void init_map_xxxNum_numbers( ) {
for (int rowNum = 1; rowNum <=9 ; rowNum++) {
Set numbers_row = map_rowNum_numbers.get(rowNum);
if( numbers_row == null ){
numbers_row = new HashSet<>();
map_rowNum_numbers.put( rowNum,numbers_row );
for (int colNum = 1; colNum <=9 ; colNum++) {
String code = getCode(rowNum, colNum);
PointVO point = map_code_point.get(code);
if( point.getNumber() == null ){
numbers_row.add( point.getNumber() );
for (int colNum = 1; colNum <=9 ; colNum++) {
Set numbers_col = map_colNum_numbers.get(colNum);
if( numbers_col == null ){
numbers_col = new HashSet<>();
map_colNum_numbers.put( colNum,numbers_col );
for (int rowNum = 1; rowNum <=9 ; rowNum++) {
String code = getCode(rowNum, colNum);
PointVO point = map_code_point.get(code);
if( point.getNumber() == null ){
numbers_col.add( point.getNumber() );
for (int gongNum = 1; gongNum <=9 ; gongNum++) {
Set numbers_gong = map_gongNum_numbers.get(gongNum);
if( numbers_gong == null ){
numbers_gong = new HashSet<>();
map_gongNum_numbers.put( gongNum,numbers_gong );
BeginIndexRangeVO beginIndexRange = map_gongNum_beginIndexRange.get(gongNum);
int beginRowNum = beginIndexRange.getBeginRowNum();
int endRowNum = beginRowNum + 2;
int beginColNum = beginIndexRange.getBeginColNum();
int endColNum = beginColNum + 2;
for (int rowNum = beginRowNum; rowNum <=endRowNum ; rowNum++) {
for (int colNum = beginColNum; colNum <=endColNum ; colNum++) {
String code = getCode(rowNum, colNum);
PointVO point = map_code_point.get(code);
if( point.getNumber() == null ){
numbers_gong.add( point.getNumber() );
private static List deepCopyList(List list) {
List list_copy = new ArrayList<>();
private static void calculatePossibleNumbers( ) {
for (int rowNum = 1; rowNum <=9 ; rowNum++) {
for (int colNum = 1; colNum <=9 ; colNum++) {
calculatePossibleNumberForTargetRowAndCol( rowNum,colNum );
private static List getPossibleNumbers( int rowNum,int colNum ){
String code = getCode(rowNum, colNum);
PointVO point = map_code_point.get(code);
Set numbers_canNotFill = new HashSet<>();
numbers_canNotFill.addAll( map_rowNum_numbers.get( rowNum ) );
numbers_canNotFill.addAll( map_colNum_numbers.get( colNum ) );
int gongNum = getGongNum( rowNum, colNum );
numbers_canNotFill.addAll( map_gongNum_numbers.get(gongNum) );
List possibleNumbers = new ArrayList<>();
for (int i = 1; i <=9 ; i++) {
possibleNumbers.add( String.valueOf( i ) );
possibleNumbers.removeAll( numbers_canNotFill );
if( point.getImpossibleNumbers() != null ){
possibleNumbers.removeAll( point.getImpossibleNumbers() );
private static void calculatePossibleNumberForTargetRowAndCol(int targetRowNum, int targetColNum) {
String code = getCode(targetRowNum, targetColNum);
PointVO point = map_code_point.get(code);
if( point.getNumber() != null ){
Set numbers_canNotFill = new HashSet<>();
numbers_canNotFill.addAll( map_rowNum_numbers.get(targetRowNum) );
numbers_canNotFill.addAll( map_colNum_numbers.get(targetColNum) );
int gongNum = getGongNum(targetRowNum, targetColNum);
numbers_canNotFill.addAll( map_gongNum_numbers.get(gongNum) );
List numbers_possible = new ArrayList<>();
for (int i = 1; i <=9 ; i++) {
numbers_possible.add( String.valueOf( i ) );
numbers_possible.removeAll( numbers_canNotFill );
if( point.getImpossibleNumbers() != null ){
numbers_possible.removeAll( point.getImpossibleNumbers() );
point.setPossibleNumbers( numbers_possible );
point.setPossibleNumbers_bak( deepCopyList( numbers_possible ) );
point.setTryNumber( null );
private static String getSingleMissingNumber(Set numbers) {
if( numbers == null || numbers.size() != 8 ){
for( String number:numbers ){
sum += Integer.valueOf( number );
return String.valueOf( 45 - sum );
private static void addNumber2_map_xxxNum_numbers(int rowNum, int colNum, String number) {
int gongNum = getGongNum(rowNum, colNum);
map_gongNum_numbers.get( gongNum ).add( number );
map_rowNum_numbers.get( rowNum ).add( number );
map_colNum_numbers.get( colNum ).add( number );
private static void deleteNumberFrom_map_xxxNum_numbers(int rowNum, int colNum, String number) {
init_map_xxxNum_numbers();
int gongNum = getGongNum(rowNum, colNum);
map_gongNum_numbers.get( gongNum ).remove( number );
map_rowNum_numbers.get( rowNum ).remove( number );
map_colNum_numbers.get( colNum ).remove( number );
private static void fillNumber(int rowNum, int colNum, String number) {
System.out.println( "deep_recursion = " + deep_recursion );
String code = getCode(rowNum, colNum);
PointVO point = map_code_point.get(code);
point.setNumber( number );
init_map_xxxNum_numbers( rowNum,colNum );
private static int getGongNum(int rowNum, int colNum) {
private static String getCode(int rowNum, int colNum) {
return rowNum + "-" + colNum;
public static Map
points2CodeAndPointMap( List points ){ Map map_code_point = new HashMap<>();
for( PointVO point:points ){
map_code_point.put( point.getCode(),point );
public static void print( ){
System.out.println( "--------------------------------------------------------------------------------------" );
for (int rowNum = 1; rowNum <=9 ; rowNum++) {
for (int colNum = 1; colNum <=9 ; colNum++) {
String code = getCode( rowNum,colNum );
PointVO point = map_code_point.get(code);
if( point.getNumber() == null ){
System.out.print( "-" + " ");
System.out.print( point.getNumber() + " ");
public static void printPossibles( ){
System.out.println( "--------------------------------------------------------------------------------------" );
Map map_colNum_maxLen = new HashMap<>();
for (int colNum = 1; colNum <=9; colNum++) {
for (int rowNum = 1; rowNum <=9 ; rowNum++) {
String code = getCode(rowNum, colNum);
PointVO point = map_code_point.get(code);
if( point.getNumber() != null ){
List possibleNumbers = point.getPossibleNumbers();
if( possibleNumbers.size() > maxLen ){
maxLen = possibleNumbers.size();
map_colNum_maxLen.put( colNum,maxLen );
for (int rowNum = 1; rowNum <=9 ; rowNum++) {
for (int colNum = 1; colNum <=9 ; colNum++) {
String code = getCode( rowNum,colNum );
PointVO point = map_code_point.get(code);
if( point.getNumber() == null ){
value = "[" + getStickTogetherFormat( point.getPossibleNumbers() ) + "]";
value = point.getNumber();
int maxLen = map_colNum_maxLen.get( colNum );
if( value.length() < maxLen ){
value += getBlank( maxLen - value.length() );
System.out.print( value + " ");
private static String getBlank(int count) {
for (int i = 0; i < count; i++) {
private static String getStickTogetherFormat(List list) {
if( list == null || list.size() == 0 ){
public static List
initChuPan(int[][] chupan) { List
points = new ArrayList<>(); for (int rowNum = 0; rowNum < 9; rowNum++) {
int[] row = chupan[rowNum];
for (int colNum = 0; colNum <9 ; colNum++) {
int number = row[colNum];
String number_str = null;
if( number > 0 && number < 10 ){
number_str = String.valueOf( number );
points.add( new PointVO(number_str,rowNum+1,colNum+1 ) );