游戲規則：

1、每行都是 1~9

2、沒列都是 1~9

3、每塊都是 1~9

?

解答思路：

從坐標 [0][0] 開始，算出其允許填入的數字集合（每行允許數字集合、每列允許數字集合 和 每塊允許數字集合 的交集）。

從左到右，從上到下依次嘗試（即，遞歸），當無法向 [下一步] 進行時候，則回溯（恢復狀態，再嘗試另一個值）。

這樣直到最后解答完成。

?

源代碼：

package com.gq.algorithm;import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set;public class NumberOnly {public static Set<Integer> NUMBER = new HashSet<Integer>();static{for( int i=1 ; i<=9 ; i++ ){NUMBER.add(i);}}/*** 記錄每行還未輸入的數字*/private List<Set<Integer>> rowMissNumber = new ArrayList<Set<Integer>>();/*** 記錄每列還未輸入的數字*/private List<Set<Integer>> colMissNumber = new ArrayList<Set<Integer>>();/*** 記錄每方塊還未輸入的數字*/private List<Set<Integer>> squareMissNumber = new ArrayList<Set<Integer>>();{for( int i=0 ; i<9 ; i++ ){rowMissNumber.add( null );colMissNumber.add( null );squareMissNumber.add( null );}}/*** 解答是否完成*/private boolean gameOver = false;public static void main(String[] args) {int[][] numbers = {{0, 9, 3, 0, 0, 1, 5, 0, 6},{0, 8, 0, 4, 3, 5, 1, 0, 0},{0, 0, 7, 9, 0, 2, 0, 8, 4},{0, 2, 0, 0, 7, 4, 8, 6, 0},{3, 7, 0, 5, 9, 0, 2, 0, 0},{9, 0, 4, 1, 0, 8, 7, 5, 0},{0, 0, 0, 0, 5, 3, 6, 0, 2},{8, 1, 0, 0, 0, 0, 0, 3, 5},{6, 0, 0, 0, 1, 9, 0, 0, 8},};NumberOnly obj = new NumberOnly();obj.init(numbers);obj.solution(0, 0, numbers);}/*** 遞歸破解* @param x* @param y* @param numbers*/void solution( int x, int y, int[][] numbers){if( numbers[x][y] == 0 ){Set<Integer> allowNums = possiableNumber(x, y);for( Integer num : allowNums ){numbers[x][y] = num;// 移除設定的值rowMissNumber.get(x).remove( num );colMissNumber.get(y).remove( num );squareRemove( x,y,num );// 結束if( x == 8 && y == 8 ){gameOver = true;print( numbers );return;}// 下一步int x1=x, y1=0;if( y == 8 ){x1 = (x+1)%9;}y1 = (y+1)%9;solution( x1, y1, numbers);//如果已經計算完成就不需要再回溯，直接返回if( gameOver ){return;}// 恢復numbers[x][y] = 0;rowMissNumber.get(x).add( num );colMissNumber.get(y).add( num );squareAdd( x, y, num );}}else{// 結束if( x == 8 && y == 8 ){gameOver = true;print( numbers );return;}// 下一步int x1=x, y1=0;if( y == 8 ){x1 = (x+1)%9;}y1 = (y+1)%9;solution( x1, y1, numbers);}}/*** 打印結果* @param numbers*/void print( int[][] numbers ){if( check(numbers) ){System.out.println( "計算數獨成功。" );}else {System.out.println( "計算數獨失敗。" );}for( int i=0 ; i<9 ; i++ ){for( int j=0 ; j<9 ; j++ ){System.out.print( numbers[i][j] + ", ");}System.out.println( );}}/*** 檢查結果是否正確* @param numbers* @return*/boolean check( int[][] numbers ){// 驗證每行for( int i=0 ; i<9 ; i++ ){int sum = 0;for( int j=0 ; j<9 ; j++ ){sum += numbers[i][j];if( j==8 && sum != 45 ){return false;}}}// 驗證每列for( int i=0 ; i<9 ; i++ ){int sum = 0;for( int j=0 ; j<9 ; j++ ){sum += numbers[j][i];if( j==8 && sum != 45 ){return false;}}}// 驗證每塊if( !checkSquare(0, 3, 0, 3, numbers)){return false;}if( !checkSquare(0, 3, 3, 6, numbers)){return false;}if( !checkSquare(0, 3, 6, 9, numbers)){return false;}if( !checkSquare(3, 6, 0, 3, numbers)){return false;}if( !checkSquare(3, 6, 3, 6, numbers)){return false;}if( !checkSquare(3, 6, 6, 9, numbers)){return false;}if( !checkSquare(6, 9, 0, 3, numbers)){return false;}if( !checkSquare(6, 9, 3, 6, numbers)){return false;}if( !checkSquare(6, 9, 6, 9, numbers)){return false;}return true;}/*** 驗證塊* @param x1* @param x2* @param y1* @param y2* @param numbers* @return*/boolean checkSquare( int x1, int x2, int y1, int y2, int[][] numbers ){int sum =0;for( int i=x1 ; i<x2 ; i++ ){for( int j=y1 ; j<y2 ; j++ ){sum += numbers[i][j];}}if( sum != 45 ){return false;}return true;}void squareRemove( int x, int y, int num ){if( 0<=x && x <=2 ){if( 0<=y && y<=2 ){squareMissNumber.get(0).remove( num );}if( 3<=y && y<=5 ){squareMissNumber.get(1).remove( num );}if( 6<=y && y<=8 ){squareMissNumber.get(2).remove( num );}}if( 3<=x && x <=5 ){if( 0<=y && y<=2 ){squareMissNumber.get(3).remove( num );}if( 3<=y && y<=5 ){squareMissNumber.get(4).remove( num );}if( 6<=y && y<=8 ){squareMissNumber.get(5).remove( num );}}if( 6<=x && x <=8 ){if( 0<=y && y<=2 ){squareMissNumber.get(6).remove( num );}if( 3<=y && y<=5 ){squareMissNumber.get(7).remove( num );}if( 6<=y && y<=8 ){squareMissNumber.get(8).remove( num );}}}void squareAdd( int x, int y, int num ){if( 0<=x && x <=2 ){if( 0<=y && y<=2 ){squareMissNumber.get(0).add( num );}if( 3<=y && y<=5 ){squareMissNumber.get(1).add( num );}if( 6<=y && y<=8 ){squareMissNumber.get(2).add( num );}}if( 3<=x && x <=5 ){if( 0<=y && y<=2 ){squareMissNumber.get(3).add( num );}if( 3<=y && y<=5 ){squareMissNumber.get(4).add( num );}if( 6<=y && y<=8 ){squareMissNumber.get(5).add( num );}}if( 6<=x && x <=8 ){if( 0<=y && y<=2 ){squareMissNumber.get(6).add( num );}if( 3<=y && y<=5 ){squareMissNumber.get(7).add( num );}if( 6<=y && y<=8 ){squareMissNumber.get(8).add( num );}}}/*** 計算出指定坐標可能輸入的數字* @return*/Set<Integer> possiableNumber( int x, int y ){Set<Integer> result = buildAllNumber();result.retainAll( rowMissNumber.get(x) );result.retainAll( colMissNumber.get(y) );if( 0<=x && x <=2 ){if( 0<=y && y<=2 ){result.retainAll( squareMissNumber.get(0) );}if( 3<=y && y<=5 ){result.retainAll( squareMissNumber.get(1) );}if( 6<=y && y<=8 ){result.retainAll( squareMissNumber.get(2) );}}if( 3<=x && x <=5 ){if( 0<=y && y<=2 ){result.retainAll( squareMissNumber.get(3) );}if( 3<=y && y<=5 ){result.retainAll( squareMissNumber.get(4) );}if( 6<=y && y<=8 ){result.retainAll( squareMissNumber.get(5) );}}if( 6<=x && x <=8 ){if( 0<=y && y<=2 ){result.retainAll( squareMissNumber.get(6) );}if( 3<=y && y<=5 ){result.retainAll( squareMissNumber.get(7) );}if( 6<=y && y<=8 ){result.retainAll( squareMissNumber.get(8) );}}return result;}/*** 初始化* @param numbers*/void init( int[][] numbers ){for( int i=0 ; i<9 ; i++ ){for( int j=0 ; j<9 ; j++ ){// 初始化行if( rowMissNumber.get(i) == null ){rowMissNumber.set(i, buildAllNumber());}if( numbers[i][j] != 0 ){rowMissNumber.get(i).remove( numbers[i][j] );}// 初始化列if( colMissNumber.get(j) == null ){colMissNumber.set(j, buildAllNumber());}if( numbers[i][j] != 0 ){colMissNumber.get(j).remove( numbers[i][j] );}// 初始化方塊//[0][0] ~ [2][2]if( 0<=i && i <=2 ){if( 0<=j && j<=2 ){if( squareMissNumber.get(0) == null ){squareMissNumber.set(0, buildAllNumber());}if( numbers[i][j] != 0 ){squareMissNumber.get(0).remove( numbers[i][j] );}}if( 3<=j && j<=5 ){if( squareMissNumber.get(1) == null ){squareMissNumber.set(1, buildAllNumber());}if( numbers[i][j] != 0 ){squareMissNumber.get(1).remove( numbers[i][j] );}}if( 6<=j && j<=8 ){if( squareMissNumber.get(2) == null ){squareMissNumber.set(2, buildAllNumber());}if( numbers[i][j] != 0 ){squareMissNumber.get(2).remove( numbers[i][j] );}}}if( 3<=i && i <=5 ){if( 0<=j && j<=2 ){if( squareMissNumber.get(3) == null ){squareMissNumber.set(3, buildAllNumber());}if( numbers[i][j] != 0 ){squareMissNumber.get(3).remove( numbers[i][j] );}}if( 3<=j && j<=5 ){if( squareMissNumber.get(4) == null ){squareMissNumber.set(4, buildAllNumber());}if( numbers[i][j] != 0 ){squareMissNumber.get(4).remove( numbers[i][j] );}}if( 6<=j && j<=8 ){if( squareMissNumber.get(5) == null ){squareMissNumber.set(5, buildAllNumber());}if( numbers[i][j] != 0 ){squareMissNumber.get(5).remove( numbers[i][j] );}}}if( 6<=i && i <=8 ){if( 0<=j && j<=2 ){if( squareMissNumber.get(6) == null ){squareMissNumber.set(6, buildAllNumber());}if( numbers[i][j] != 0 ){squareMissNumber.get(6).remove( numbers[i][j] );}}if( 3<=j && j<=5 ){if( squareMissNumber.get(7) == null ){squareMissNumber.set(7, buildAllNumber());}if( numbers[i][j] != 0 ){squareMissNumber.get(7).remove( numbers[i][j] );}}if( 6<=j && j<=8 ){if( squareMissNumber.get(8) == null ){squareMissNumber.set(8, buildAllNumber());}if( numbers[i][j] != 0 ){squareMissNumber.get(8).remove( numbers[i][j] );}}}}}}/*** 構造一個集合，包含1~9* @return*/Set<Integer> buildAllNumber(){Set<Integer> set = new HashSet<Integer>();for( int i=1 ; i<=9 ; i++ ){set.add(i);}return set;} } ?

??int[][] numbers = {{5, 0, 6,? 0, 0, 0,? 0, 8, 0},{0, 4, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 5,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 6, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 1,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 3, 0, 0},{0, 0, 0,? 0, 0, 0,? 9, 0, 8}};

??int[][] numbers = {{4, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 1,? 0, 0, 0,? 0, 0, 0},{0, 5, 0,? 0, 0, 0,? 0, 7, 0},{0, 8, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 1, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 6,? 0, 1, 0},{0, 6, 0,? 0, 0, 0,? 0, 5, 0}};

??int[][] numbers = {{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},{0, 0, 0,? 0, 0, 0,? 0, 0, 0},};

總結

以上是生活随笔為你收集整理的数独游戏破解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。