注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Computer Science

I Pressed My Words Here. Will You Read ?

 
 
 

日志

 
 

The Matrix of SUDOKU. In Java.Editon 4  

2010-12-02 17:14:07|  分类: My Projects |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
正文:读完数据结构的第一章(绪论)的第一节(什么是数据结构)後,花了两个小时修修改改,把曾经尝试了很久没有做成功的数独游戏的矩阵生成程序写出来了。I am not kidding.结果发现只实现了部分特定的数独。进过一晚上加以上午的纠结完善,最终实现了能生成绝大部分可能形式数独矩阵的程序,即近乎真正意义上的数独矩阵程序。今天再加上了一个对大列中的小行进行乱序的循环的方法:disruptRowTeamOFBigColumnInMatrix(matrix),变化更多,但是还是离生成所有任意数独矩阵有段距离。在研究了下ubuntu下的SUDOKU游戏後,发现了一些规律。以后有空再专门写下来。
在这里將代码和输出结果(输出结果中记录了数独矩阵从基础矩阵的生成到最终矩阵的得到的演化过程)和大家分享下:

/**
 *
 */
package com.wordpress.iwillaccess.classes.algorithm;

import java.util.Calendar;
import java.util.Random;

/**
 * 数独:每一行、每一列、每9个(不是任意的9个组成的,而是井字形划分出的)组成小方块的格子都不能有相同的数字。
 *
 * @author knowyourself1010
 *
 */
public class ConsoleSUDOKU {

    /**
     *
     */
    public ConsoleSUDOKU() {
        // TODO Auto-generated constructor stub
    }

    /**
     * the main process used to create the SUDOKU matrix
     */
    public int[][] control() {
        // 創建數組存放1~9
        int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int[][] matrix = new int[9][9];// 用於存放結果矩陣的二維數組
        int[][] lattice = new int[3][3];// 用於模擬9個大格子的二維數組

        // System.out.println("matrix: " + matrix[0][0]);//检验二维数组初始值

        // 打乱nums数组中数字顺序
        nums = disruptOrder(nums);
        System.out.print("檢驗随机打乱顺序方法的效果:\n");
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + "\t");// 输出打乱後的结果用于检验随机打乱方法。
        }

        // 以每個數字爲對象,確保他們每行沒列都不重複的情況下,每9個組成的小方塊中也不重複。

        // create the tmpIndex, put each three indexes, which can't hold a same
        // number in the middle lattice, together as a member of tmpInder to
        // initialise tmpIndexMembers.
        // int[][] tmpIndex = { { 0, 4, 8 }, { 3, 7, 2 }, { 6, 1, 5 } };
        int[][] tmpIndex = { { 0, 3, 6 }, { 1, 4, 7 }, { 2, 5, 8 } };
        // tmpIndex[][]中每小組包含每大行中同一數字可以選擇的列的位置組合。
        // tmpIndex = disruptOrder(tmpIndex);//
        // 將tmpIndex的順序隨機打亂,並將各個小組中的成員順序隨機打亂。//为了方便大列中行互换有效无误,故不对此序列乱序。
        // 第一層循環,確保每個數字都被採用過。
        for (int i = 0; i < 9; i++) {
            // 初始化用於區分是否在同一個小方塊的數組
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    lattice[j][k] = 0;
                    // if (i < 3)
                    // System.out.println("tmpIndex:" + tmpIndex[j][k]);
                }
                // System.out.println();
            }
            // 第二層循環,確保被選擇的數字每大行都有。j作爲大行參數,將3個組成的行視爲一個大行。
            for (int j = 0; j < 3; j++) {
                // 第三層循環,確保被选择的数字每行每列不重复。
                for (int k = 0; k < 3; k++) {
                    matrix[(j * 3) + k][(i + tmpIndex[j][k]) % 9] = nums[i];
                    // System.out.print(" " + tmpIndex[j][k] + " ");
                    // 基础矩阵核心语句
                    // 每大行j乘以3加上用於表示列的變量k來遍歷每一小行;
                    // tmpIndex[][]中每小組包含每大行中同一數字可以選擇的列的位置組合。
                }
            }
        }
        System.out.println("\n初步完成数独基础矩阵\n输出SUDOKU矩阵:\n");
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(" " + matrix[i][j] + " ");
                if (j % 3 == 2) {
                    System.out.print("  ");
                }
            }
            System.out.println();
            if (i % 3 == 2) {
                System.out.println();
            }
        }
        // 选择是否进一步打乱顺序
        Calendar calendar = Calendar.getInstance();
        Random rd = new Random(calendar.getTimeInMillis());
        if (776 != rd.nextInt(777)) {
            System.out.println("\n进行对大行中的同元素列组互换操作:");
            // disrupt matrix
            // 是否进行分组乱序
            rd = new Random(calendar.getTimeInMillis());
            if (768 != rd.nextInt(769)) {
                // 通过提取大列中元素相同行,分别存放进数组,再随机打乱顺序按条件取出,实现乱序。
                matrix = disruptRowTeamOFBigColumnInMatrix(matrix);
                // 通过提取大行中元素相同列,分别存放进数组,再随机打乱顺序按条件取出,实现乱序。
                for (int i = 0; i < 3; i++) {
                    // 循环大行
                    // 随机选择是否对本大行中的组进行交换
                    calendar = Calendar.getInstance();
                    rd = new Random(calendar.getTimeInMillis() * (i + 1));
                    System.out.println("\n对当前大行" + i + "中的组进行交换:");
                    int[][][] tmpArray0 = new int[3][3][3];

                    rd = new Random(calendar.getTimeInMillis() * (i + 3));
                    int[] tmpArray = { 0, 1, 2, 3 };
                    tmpArray = disruptOrder(tmpArray);
                    int jMax = tmpArray[rd.nextInt(4)];// jMax等于0时
                    // 等同于本轮中不进行交换处理,等于3时等同于进行无效交换处理,1、2时进行有效交换乱序处理。
                    for (int j = 0; j < jMax; j++) {
                        // 遍历大行中不同类的列组
                        for (int k = 0; k < 3; k++) {
                            // 遍历大行中相同列组
                            for (int l = 0; l < 3; l++) {// 遍历相同列中各列的行
                                tmpArray0[j][k][l] = matrix[i * 3 + l][k * 3
                                        + j];
                            }
                            // i*3可以根据所选大列,水平平移行的位置。
                            // k*3可以根据垂直平移到相同列的位置,这是根据核心语句得到的矩阵的规则定的。
                        }
                    }
                    // 随机从tmpArray0中取值给matrix
                    for (int j = 0; j < jMax; j++) {// 对三个含有相同元素的类型列分别进行交互。
                        rd = new Random(calendar.getTimeInMillis()
                                * (j + 1 + i));
                        tmpArray = new int[3];
                        for (int k = 0; k < 3; k++) {
                            tmpArray[k] = k;
                        }
                        tmpArray = cutUsedItemInArray(tmpArray, rd.nextInt(3));
                        for (int k = 0; k < 2; k++) {// 交互三个相同的元素组成的列中的两个。如果交换3个將得到已經能夠得到的矩陣。
                            for (int l = 0; l < 3; l++) {
                                matrix[i * 3 + l][tmpArray[1 - k] * 3 + j] = tmpArray0[j][tmpArray[k]][l];
                            }
                        }
                    }
                    System.out.println("\n完成第" + i + "轮列小组交换处理\n输出SUDOKU矩阵:\n");
                    for (int ijk = 0; ijk < 9; ijk++) {
                        for (int jki = 0; jki < 9; jki++) {
                            System.out.print(" " + matrix[ijk][jki] + " ");
                            if (jki % 3 == 2) {
                                System.out.print("  ");
                            }
                        }
                        System.out.println();
                        if (ijk % 3 == 2) {
                            System.out.println();
                        }
                    }
                }
            } else {
                // do not change teams with same number members.
            }

            System.out.println("\n各大行中,分小組列亂序完成\n输出SUDOKU矩阵:\n");
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(" " + matrix[i][j] + " ");
                    if (j % 3 == 2) {
                        System.out.print("  ");
                    }
                }
                System.out.println();
                if (i % 3 == 2) {
                    System.out.println();
                }
            }

            // 随机是否用交换大列中的小列打乱顺序
            rd = new Random(calendar.getTimeInMillis());
            if (46 != rd.nextInt(47)) {
                System.out.print("\n进行交换大的列中的小列:\n");
                // 通过随意交换大的列中的小列,打乱顺序。
                for (int i = 0; i < 3; i++) {
                    // three columns in one big column
                    // 三个数组分别 存放3个小列的值
                    int[] tmpArray0 = new int[9];
                    int[] tmpArray1 = new int[9];
                    int[] tmpArray2 = new int[9];
                    for (int j = 0; j < 3; j++) {
                        for (int k = 0; k < 9; k++) {
                            if (j == 0) {
                                tmpArray0[k] = matrix[k][3 * i + j];
                            } else if (j == 1) {
                                tmpArray1[k] = matrix[k][3 * i + j];
                            } else if (j == 2) {
                                tmpArray2[k] = matrix[k][3 * i + j];
                            }
                        }
                    }

                    // disrupt orders of three columns.
                    int[] tmpNum = { 0, 1, 2 };// tmpNum存放小列的索引值,用于随机选择小列进行交换。
                    for (int l = 0; l < 3; l++) {
                        rd = new Random(calendar.getTimeInMillis()
                                * (l + 1 + i));
                        tmpNum = disruptOrder(tmpNum);
                        int j = rd.nextInt(tmpNum.length);
                        for (int k = 0; k < 9; k++) {
                            if ((tmpNum.length - 1) == 0) {
                                matrix[k][3 * i + tmpNum[j]] = tmpArray0[k];
                            } else if ((tmpNum.length - 1) == 1) {
                                matrix[k][3 * i + tmpNum[j]] = tmpArray1[k];
                            } else if ((tmpNum.length - 1) == 2) {
                                matrix[k][3 * i + tmpNum[j]] = tmpArray2[k];
                            }
                        }
                        tmpNum = cutUsedItemInArray(tmpNum, j);// 删掉已经赋值的小列,以免重复。
                    }
                }
            } else {
                // do not change the order of columns in a big column.
            }
        } else {// do not disrupt anymore.

        }
        return matrix;
    }

    private int[][] disruptRowTeamOFBigColumnInMatrix(int[][] matrix) {
        // 对第一大列中每大行中1、2小行互换。
        // 对第二大列中每大行中2、3小行互换。
        // 对第三大列中每大行3、1小行户黄。
        int[][] smallRowIndex = { { 0, 1 }, { 1, 2 }, { 2, 0 } };// 用于存放交换小行设置的数组。
        int[] tmpIndex = { 0, 1, 2 };// 随机数用于确定哪些大行在大列中的元素行需要互换。
        Calendar c = Calendar.getInstance();
        Random rd = new Random(c.getTimeInMillis());
        tmpIndex = disruptOrder(tmpIndex);
        for (int i = 0; i < rd.nextInt(3); i++) {
            tmpIndex = cutUsedItemInArray(tmpIndex, i);
        }
        System.out.println("tmpIndex Length: " + tmpIndex.length);
        for (int i = 0; i < 3; i++) {
            // 选择大列
            for (int j = 0; j < tmpIndex.length; j++) {
                // 选择大列中大行
                int[] tmpArray = new int[3];
                for (int k = 0; k < 2; k++) {
                    // 选择大行中小行
                    for (int l = 0; l < 3; l++) {
                        // 每小行中3个元素分别依次存入临时数组。

                        if (k == 0) {
                            // 將第一个小行存入临时数组。
                            tmpArray[l] = matrix[tmpIndex[j] * 3
                                    + smallRowIndex[i][k]][i * 3 + l];
                        } else if (k == 1) {
                            // 將第二个小行赋予第一个小行
                            matrix[tmpIndex[j] * 3 + smallRowIndex[i][k - 1]][i
                                    * 3 + l] = matrix[tmpIndex[j] * 3
                                    + smallRowIndex[i][k]][i * 3 + l];
                            // 將临时数组赋予第二个小行
                            matrix[tmpIndex[j] * 3 + smallRowIndex[i][k]][i * 3
                                    + l] = tmpArray[l];
                        } else {
                            System.out
                                    .println("strange! this place is not supposed to be access.");
                        }
                    }
                }
            }
        }

        System.out.println("\n各大列中,分小組行亂序完成\n输出SUDOKU矩阵:\n");
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(" " + matrix[i][j] + " ");
                if (j % 3 == 2) {
                    System.out.print("  ");
                }
            }
            System.out.println();
            if (i % 3 == 2) {
                System.out.println();
            }
        }

        return matrix;
    }

    /**
     * 用于随机打乱一维数组的成员顺序
     *
     * @param nums
     *            需要被随机打乱成员顺序的一维数组
     * @return 返回随机打乱顺序的一维数组
     */
    public int[] disruptOrder(int[] nums) {
        int[] result = new int[nums.length];// 这里不推荐用int[] result=nums;
        int[] index = new int[nums.length];// 这里不能用int[] index=nums;
        // 创建顺序索引
        for (int i = 0; i < nums.length; i++) {
            index[i] = i;
        }
        Calendar calendar = Calendar.getInstance();
        Random rd = new Random(calendar.getTimeInMillis());
        for (int i = 0; i < nums.length; i++) {
            // 用tmpIndex中随机一个数设定result的索引位子,为其赋值。
            int j = rd.nextInt(index.length);
            result[index[j]] = nums[i];
            // 删除用过的tmpIdex成员
            if (j != (index.length - 1)) {
                // 当j不是最后一个时,后面数前移
                for (int k = j; k < index.length - 1; k++) {
                    index[k] = index[k + 1];
                }
            } else {
                // 如果是最后一个就没有需要前移的了。
            }
            // 删去最后一个数
            int[] tmpIndex = new int[index.length - 1];
            for (int k = 0; k < tmpIndex.length; k++) {
                tmpIndex[k] = index[k];
            }
            index = tmpIndex;
        }
        return result;
    }

    /**
     * 用於隨機打亂int[][]的成員順序,以及成員的子成員順序,(成員索引在第一個[]內存放,子成員的索引在第二個[]內存放)
     *
     * @param nums
     *            需要随机大量顺序的int型二维数组
     * @return 返回打乱顺序後的二维数组
     */
    public int[][] disruptOrder(int[][] nums) {
        int[][] result = nums;
        int[][] tmpIndex = new int[nums.length][nums[0].length];
        int[] rowLength = new int[nums.length];// 存放尚未使用的行的數值
        // 初始化rowLength
        for (int i = 0; i < nums.length; i++) {
            rowLength[i] = i;
        }
        // disrupt the order of nums[][]
        for (int i = 0; i < nums.length; i++) {
            Calendar calendar = Calendar.getInstance();
            Random rd = new Random(calendar.getTimeInMillis());
            int rowIndex = rd.nextInt(rowLength.length);// 获得随机行值在rowLength中的索引值
            int row = rowLength[rowIndex];// row 作为随机行
            rowLength = cutUsedItemInArray(rowLength, rowIndex);// 确保row作为随机行不重复

            int[] columnLength = new int[nums[0].length];
            // 初始化columnLength
            for (int j = 0; j < nums[i].length; j++) {
                columnLength[j] = j;
            }
            for (int j = 0; j < nums[i].length; j++) {
                rd = new Random(calendar.getTimeInMillis());
                int columnIndex = rd.nextInt(columnLength.length);// 獲得隨機列的值在columnLength中的索引值
                int column = columnLength[columnIndex];// column作爲隨機列
                columnLength = cutUsedItemInArray(columnLength, columnIndex);// 確保隨機列不重複,剪掉用過的
                tmpIndex[i][j] = nums[row][column];// 將随机出的未调用过的点的值赋值给按顺序循環接收值的临时二维数组
            }
        }
        result = tmpIndex;
        return result;
    }

    /**
     * 用於裁剪掉一維數組中需要去掉的成員,並將其後面的成員位置遷移。
     *
     * @param nums
     *            the array with item need to cut off
     * @param j
     *            the index of the item which will be cut off and be taken
     *            place;
     * @return
     */
    public int[] cutUsedItemInArray(int[] nums, int j) {
        // 删除用过的nums成员
        if (j != (nums.length - 1)) {
            // 当j不是最后一个时,后面数前移
            for (int k = j; k < nums.length - 1; k++) {
                nums[k] = nums[k + 1];
            }
        } else {
            // 如果是最后一个就没有需要前移的了。
        }
        // 删去最后一个数
        int[] tmpIndex = new int[nums.length - 1];
        for (int k = 0; k < tmpIndex.length; k++) {
            tmpIndex[k] = nums[k];
        }
        return tmpIndex;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ConsoleSUDOKU cSUDOKU = new ConsoleSUDOKU();
        int[][] matrix = cSUDOKU.control();

        // 输出矩阵
        System.out.println("\n\n输出SUDOKU矩阵:\n");
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(" " + matrix[i][j] + " ");
                if (j % 3 == 2) {
                    System.out.print("  ");
                }
            }
            System.out.println();
            if (i % 3 == 2) {
                System.out.println();
            }
        }
    }
}


檢驗随机打乱顺序方法的效果:
8    5    4    7    2    6    9    1    3    
初步完成数独基础矩阵
输出SUDOKU矩阵:

 8  5  4    7  2  6    9  1  3   
 9  1  3    8  5  4    7  2  6   
 7  2  6    9  1  3    8  5  4   

 3  8  5    4  7  2    6  9  1   
 6  9  1    3  8  5    4  7  2   
 4  7  2    6  9  1    3  8  5   

 1  3  8    5  4  7    2  6  9   
 2  6  9    1  3  8    5  4  7   
 5  4  7    2  6  9    1  3  8   


进行对大行中的同元素列组互换操作:
tmpIndex Length: 2

各大列中,分小組行亂序完成
输出SUDOKU矩阵:

 9  1  3    7  2  6    8  5  4   
 8  5  4    9  1  3    7  2  6   
 7  2  6    8  5  4    9  1  3   

 6  9  1    4  7  2    3  8  5   
 3  8  5    6  9  1    4  7  2   
 4  7  2    3  8  5    6  9  1   

 1  3  8    5  4  7    2  6  9   
 2  6  9    1  3  8    5  4  7   
 5  4  7    2  6  9    1  3  8   


对当前大行0中的组进行交换:

完成第0轮列小组交换处理
输出SUDOKU矩阵:

 9  1  3    7  2  6    8  5  4   
 8  5  4    9  1  3    7  2  6   
 7  2  6    8  5  4    9  1  3   

 6  9  1    4  7  2    3  8  5   
 3  8  5    6  9  1    4  7  2   
 4  7  2    3  8  5    6  9  1   

 1  3  8    5  4  7    2  6  9   
 2  6  9    1  3  8    5  4  7   
 5  4  7    2  6  9    1  3  8   


对当前大行1中的组进行交换:

完成第1轮列小组交换处理
输出SUDOKU矩阵:

 9  1  3    7  2  6    8  5  4   
 8  5  4    9  1  3    7  2  6   
 7  2  6    8  5  4    9  1  3   

 4  9  1    6  7  2    3  8  5   
 6  8  5    3  9  1    4  7  2   
 3  7  2    4  8  5    6  9  1   

 1  3  8    5  4  7    2  6  9   
 2  6  9    1  3  8    5  4  7   
 5  4  7    2  6  9    1  3  8   


对当前大行2中的组进行交换:

完成第2轮列小组交换处理
输出SUDOKU矩阵:

 9  1  3    7  2  6    8  5  4   
 8  5  4    9  1  3    7  2  6   
 7  2  6    8  5  4    9  1  3   

 4  9  1    6  7  2    3  8  5   
 6  8  5    3  9  1    4  7  2   
 3  7  2    4  8  5    6  9  1   

 1  3  8    5  4  7    2  6  9   
 2  6  9    1  3  8    5  4  7   
 5  4  7    2  6  9    1  3  8   


各大行中,分小組列亂序完成
输出SUDOKU矩阵:

 9  1  3    7  2  6    8  5  4   
 8  5  4    9  1  3    7  2  6   
 7  2  6    8  5  4    9  1  3   

 4  9  1    6  7  2    3  8  5   
 6  8  5    3  9  1    4  7  2   
 3  7  2    4  8  5    6  9  1   

 1  3  8    5  4  7    2  6  9   
 2  6  9    1  3  8    5  4  7   
 5  4  7    2  6  9    1  3  8   


进行交换大的列中的小列:


输出SUDOKU矩阵:

 3  1  9    7  6  2    5  8  4   
 4  5  8    9  3  1    2  7  6   
 6  2  7    8  4  5    1  9  3   

 1  9  4    6  2  7    8  3  5   
 5  8  6    3  1  9    7  4  2   
 2  7  3    4  5  8    9  6  1   

 8  3  1    5  7  4    6  2  9   
 9  6  2    1  8  3    4  5  7   
 7  4  5    2  9  6    3  1  8   


偶然读到别人写的一篇《Java版数独算法实现http://fulong258.blog.163.com/blog/static/178950442010075444790/ 感觉其实现过程思路清晰,特别推荐。不过经过实验,此文中的算法在执行时,偶尔会因为反复退回而耗时很多,有时一直无法得出结果。个人觉得需要在算法技巧上改良。
  评论这张
 
阅读(736)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017