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

Computer Science

I Pressed My Words Here. Will You Read ?

 
 
 

日志

 
 

The Matrix of SUDOKU in Java.Edition 1 and Edition 2  

2010-11-30 16:28:10|  分类: My Projects |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


正文:读完数据结构的第一章(绪论)的第一节(什么是数据结构)後,花了两个小时修修改改,把曾经尝试了很久没有做成功的数独游戏的矩阵生成程序写出来了。I am not kidding.结果发现只实现了部分特定的数独。代码完善中……
在这里將代码和大家分享下:
版本1:得到的基础矩阵,满足游戏要求,但是无法生成所有的SUDOKU矩阵;

/**
 * 数独:每一行、每一列、每9个(不是任意的9个组成的,而是井字形划分出的)组成小方块的格子都不能有相同的数字。
 */
package com.wordpress.iwillaccess.classes.algorithm;

import java.util.Date;
import java.util.Random;

/**
 *
 * @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個組成的小方塊中也不重複。

        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;
                }
            }
            // 第二層循環,確保被選擇的數字每大行都有。j作爲大行參數,將3個組成的行視爲一個大行。
            for (int j = 0; j < 3; j++) {

                /*
                 * int[] tmpIndex = { 0, 1, 2 }; tmpIndex =
                 * disruptOrder(tmpIndex); for (int k = 0; k < 3; k++) { //
                 * 第三層循環,確保被选择的数字每行每列不重复。 if (lattice[j % 3][tmpIndex[k]] == 0)
                 * { lattice[j % 3][tmpIndex[k]] = 1; matrix[j][3 * ((j + i/3) %
                 * 3) + tmpIndex[k]] = nums[i]; break; }
                 *
                 * }
                 */
                // 第三層循環,確保被选择的数字每行每列不重复。
                for (int k = 0; k < 3; k++) {
                    matrix[(j * 3) + k][(i + tmpIndex[j][k]) % 9] = nums[i];
                    // 核心语句,居然就一句……
                    // 每大行j乘以3加上用於表示列的變量k來遍歷每一小行;
                    // tmpIndex[][]中沒小組包含每大行中同一數字可以選擇的列的位置組合。
                }
            }
        }
        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;
        }
        Date d = new Date();
        Random rd = new Random(d.getTime());
        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++) {
            Date date = new Date();
            Random rd = new Random(date.getTime());
            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.length; j++) {
                columnLength[j] = j;
            }
            for (int j = 0; j < nums[i].length; j++) {
                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();
            }
        }
    }
}

//檢驗随机打乱顺序方法的效果:
//2    4    9    6    7    1    3    5    8   
//
//输出SUDOKU矩阵:
//
// 7  1  3    5  8  2    4  9  6  
// 5  8  2    4  9  6    7  1  3  
// 4  9  6    7  1  3    5  8  2  
//
// 3  5  8    2  4  9    6  7  1  
// 2  4  9    6  7  1    3  5  8  
// 6  7  1    3  5  8    2  4  9  
//
// 1  3  5    8  2  4    9  6  7  
// 8  2  4    9  6  7    1  3  5  
// 9  6  7    1  3  5    8  2  4
版本2:满足游戏要求,在版本1的基础上,增加了能生成的种类,但还是不全。

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

import java.util.Date;
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, 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++) {

                /*
                 * int[] tmpIndex = { 0, 1, 2 }; tmpIndex =
                 * disruptOrder(tmpIndex); for (int k = 0; k < 3; k++) { //
                 * 第三層循環,確保被选择的数字每行每列不重复。 if (lattice[j % 3][tmpIndex[k]] == 0)
                 * { lattice[j % 3][tmpIndex[k]] = 1; matrix[j][3 * ((j + i/3) %
                 * 3) + tmpIndex[k]] = nums[i]; break; }
                 *
                 * }
                 */
                // 第三層循環,確保被选择的数字每行每列不重复。
                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[][]中沒小組包含每大行中同一數字可以選擇的列的位置組合。
                }
            }
        }
        // disrupt matrix

        for (int i = 0; i < 3; i++) {
            // three columns in one big column
            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 };
            for (int l = 0; l < 3; l++) {
                Date date = new Date();
                Random rd = new Random(date.getTime() * tmpArray0[0]);
                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);
            }
        }
        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;
        }
        Date d = new Date();
        Random rd = new Random(d.getTime() * d.getTime() - d.getTime());
        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++) {
            Date date = new Date();
            Random rd = new Random(date.getTime() * (date.getTime() * 107 + i));
            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++) {
                date = new Date();
                rd = new Random(-date.getTime() * 173 + i + j);
                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();
            }
        }
    }
}

//檢驗随机打乱顺序方法的效果:
//7    4    2    8    9    1    6    3    5   
//
//输出SUDOKU矩阵:
//
// 5  6  3    7  4  2    1  9  8  
// 2  7  4    8  9  1    5  3  6  
// 1  8  9    6  3  5    2  4  7  
//
// 8  4  2    9  1  6    7  5  3  
// 7  3  5    4  2  8    6  1  9  
// 6  9  1    3  5  7    8  2  4  
//
// 4  5  7    2  8  9    3  6  1  
// 3  1  6    5  7  4    9  8  2  
// 9  2  8    1  6  3    4  7  5
后来经过12小时的修改,完成了一个真正意义上的数独矩阵生成程序。同样在此与大家分享:
The Matrix of SUDOKU.In Java.Edition 3 http://computerscience.blog.163.com/blog/static/174962343201011111352672/
  评论这张
 
阅读(603)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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