`
参照物
  • 浏览: 11706 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
社区版块
存档分类
最新评论

Java基础算法--数独

阅读更多

转载自IT学习社区:http://bbs.itcast.cn/thread-6273-1-1.html

作者:梁桐

 

无聊时偶尔会玩一玩益智类游戏。有一种游戏叫“数独”,满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复

shudu.jpg

突发奇想,使用Java基础编写一个自己的获得数独数据小程序。

  1. package cn.itcast;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Random;
  6.  
  7. public class SudokuTest2 {
  8.  
  9.         public static void main(String[] args) {
  10.                
  11.                 //数组
  12.                 int[][] soduku = new int[9][9];
  13.                 //生成数据
  14.                 getData(soduku);
  15. //                print(soduku);
  16.                 //修改数据
  17.                 changeData(soduku);
  18.                 //打印
  19.                 print(soduku);
  20.                
  21. //                System.out.println(getValueList());
  22.                
  23.         }
  24.  
  25.         private static int currentCount; //当前循环次数
  26.         /**
  27.          * 修改内容
  28.          * @param soduku
  29.          */
  30.         private static void changeData(int[][] soduku) {
  31.                 //获得一个数字
  32.                 for(int m = 0 ; m < soduku.length ; m ++){
  33.                         lineNumList =  getValueList(); //随机生成数据
  34.                         //获得一行数据
  35.                         currentCount = 0;
  36.                         for(int i = 0 ; i < lineNumList.size() ; i ++){
  37.                                 int num = lineNumList.get(i);
  38.                                 //查询是否已经使用,当前之前
  39.                                 if(findHasValue(soduku,m,i,num)){
  40.                                         //将当前添加到最后
  41.                                         lineNumList.add(lineNumList.remove(i));
  42.                                         i--;
  43.                                         if(currentCount > lineNumList.size()){ //数据不符合
  44.                                                 m--; //重新来
  45.                                                 break;
  46.                                         }
  47.                                         currentCount ++;
  48.                                         continue;
  49.                                 }
  50.                                 
  51.                                 //交换与之后的
  52.                                 changeValue(soduku,m,i,num);
  53.                         }
  54. //                        System.out.println(m + " ## " + lineNumList);
  55. //                        print(soduku);
  56.                 }
  57.                
  58.                
  59.                
  60.                
  61.                
  62.         }
  63.  
  64.         private static void changeValue(int[][] soduku, int currentRow, int currentCols, int num) {
  65.                 int endRow = (currentRow / 3 + 1) * 3;
  66.                 int endCols = (currentCols / 3 + 1) * 3;
  67.                 for(int i = currentRow ; i < endRow ; i ++){
  68.                         int startCols = currentCols / 3 * 3;
  69.                         if(i == currentRow){
  70.                                 startCols = currentCols;
  71.                         }
  72.                         for(int j = startCols ; j < endCols ; j ++){
  73.                                 int temp = soduku[i][j];
  74.                                 if(temp == num){
  75.                                         soduku[i][j] = soduku[currentRow][currentCols];
  76.                                         soduku[currentRow][currentCols] = temp;
  77.                                 }
  78.                         }
  79.                 }
  80.         }
  81.  
  82.         /**
  83.          * 查询当前的之前是否使用过num
  84.          * @param soduku
  85.          * @param currentRow
  86.          * @param currentCols
  87.          * @param num
  88.          * @return
  89.          */
  90.         private static boolean findHasValue(int[][] soduku, int currentRow, int currentCols, int num) {
  91.                 return findAreaValue(soduku, currentRow, currentCols, num)
  92.                         || findRowValue(soduku, currentRow, currentCols, num)
  93.                         || findColsValue(soduku, currentRow, currentCols, num);
  94.         }
  95.         
  96.         /**
  97.          * 当前行查询
  98.          * @param soduku
  99.          * @param currentRow
  100.          * @param currentCols
  101.          * @param num
  102.          * @return
  103.          */
  104.         private static boolean findRowValue(int[][] soduku, int currentRow, int currentCols, int num) {
  105.                 for(int i = 0 ; i < currentCols ; i++ ){
  106.                         int exists = soduku[currentRow][i];
  107.                         if(exists == num ){
  108.                                 return true;
  109.                         }
  110.                 }
  111.                 return false;
  112.         }
  113.         
  114.         /**
  115.          * 当前列查询
  116.          * @param soduku
  117.          * @param currentRow
  118.          * @param currentCols
  119.          * @param num
  120.          * @return
  121.          */
  122.         private static boolean findColsValue(int[][] soduku, int currentRow, int currentCols, int num) {
  123.                 for(int i = 0 ; i < currentRow ; i ++){
  124.                         int exists = soduku[i][currentCols];
  125.                         if(exists == num){
  126.                                 return true;
  127.                         }
  128.                 }
  129.                 return false;
  130.         }
  131.         
  132.         /**
  133.          * 当前区域查询
  134.          * @param soduku
  135.          * @param currentRow
  136.          * @param currentCols
  137.          * @param num
  138.          * @return
  139.          */
  140.         private static boolean findAreaValue(int[][] soduku, int currentRow, int currentCols, int num) {
  141.                 //currentRow 1  currentCols 5
  142.                 int startRow = currentRow / 3 * 3;  //3
  143.                 int startCols = currentCols / 3 * 3;
  144.                 for(int i = startRow ; i <= currentRow ; i ++ ){  // 345
  145.                         int cols = startCols + 3;
  146.                         if(i == currentRow){
  147.                                 cols = currentCols;
  148.                         }
  149.                         for(int j = startCols ; j < cols ; j ++) {
  150.                                 int exists = soduku[i][j];
  151.                                 if(exists == num){
  152.                                         return true;
  153.                                 }
  154.                         }
  155.                 }
  156.                 return false;
  157.         }
  158.         
  159.         
  160.  
  161.         /**
  162.          * 生成数据
  163.          * @param soduku
  164.          */
  165.         private static void getData(int[][] soduku) {
  166.                 for(int m = 0 ; m < 9 ; m ++){
  167.                         for(int n = 0 ; n < 9 ; n ++){
  168.                                 soduku[m][n] = (m % 3) * 3 + (n % 3) + 1 ;
  169.                         }
  170.                 }
  171.         }
  172.  
  173.         
  174.         private static List<Integer> lineNumList;
  175.         private static List<Integer> getValueList(){
  176.                 Random random = new Random();
  177.                 List<Integer> list = new ArrayList<Integer>();
  178.                 while(list.size() < 9){
  179.                         //保证行数据唯一
  180.                         int num = random.nextInt(10);
  181.                         if(!list.contains(num) && num > 0){
  182.                                 list.add(num);
  183.                         }
  184.                 }
  185.                 return list;
  186.         }
  187.  
  188.         /**
  189.          * 输出
  190.          * @param soduku
  191.          */
  192.         private static void print(int[][] soduku) {
  193.                 for(int m = 0 ; m < 9 ; m ++){
  194.                         for(int n = 0 ; n < 9 ; n ++){
  195.                                 System.out.print(soduku[m][n]);
  196.                                 if( ( (n + 1) % 3 == 0 ) && n < 8 ){
  197.                                         System.out.print(" | ");
  198.                                 }
  199.                         }
  200.                         if( ( (m + 1) % 3 == 0 ) && m < 8){
  201.                                 System.out.println();
  202.                                 for(int i = 0 ; i < 15 ; i ++){
  203.                                         System.out.print("-");
  204.                                 }
  205.                         }
  206.                         System.out.println();
  207.                 }
  208.                 System.out.println("#############");
  209.         }
  210. }
  211.  
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics