Recently, I saw a friend posted a similar article to develop a so-called sudoku with VUE. I remembered that I had done a similar one a few months ago when I learned Vue. The idea was somewhat different from the one in the previous article, so I was inspired to share it with Github

Preface:

Some time ago, when LEARNING the VUE framework, I saw such a chestnut in the official website example

How w is not very cool, see this immediately can not bear a programmer’s heart, and then spent 2, 3 nights to write about it.

How does it feel (not at all) to grasp the essence of…

Well, we may be ugly but the basic functionality is there, and there’s something to think about in terms of data generation.

The rules

Before analyzing the code, let’s clarify the rules of Sudoku:

Sudoku is a math game that originated in 18th century Switzerland. Is a logic game using paper and pen. Based on the known numbers on the 9×9 plate, the player needs to deduce the numbers of all remaining Spaces, and satisfy that the numbers in each line, column, and thick line (3 × 3) all contain 1-9, and do not repeat.

Train of thought

To implement this game, my idea is to create a complete array of rules and then hide some of the values. Compare the entered value with the hidden value during validation. If they are the same, it is correct. If they are different, it is checked again according to the rule (considering the possibility of multiple solutions).

Implementation steps

  1. The data structure

    So if you do this 9 by 9 grid, you’re going to do the same thing, you’re going to have a two-dimensional array for each grid. Each data contains attributes that indicate specific states (correct, wrong, etc.) that can be viewed in the class file

    initGridList() { this.gridList = []; // Generate a general layoutfor (let i = 0; i < this.ROWS; i++) {
        let rowList = [];
        for (let j = 0; j < this.COLS; j++) {
            let data = new Grid();
            rowList.push(data);
        }
        this.gridList.push(rowList);
    }

    return this.gridList;

};
Copy the code

  2. Interpolate into this two-dimensional array (important)

    There are three sudoku rules to consider as we fill in the values in this two-dimensional array:

    1. Line is not repeated
    2. Column is not repeated
    3. Each minor 9 house is not repeated

    We can use these three requirements to generate three arrays that meet the corresponding requirements namely

    letunUseRowList = this.getNoRepeatData(row, col, 1); //1. Line cannot be repeatedletunUseColList = this.getNoRepeatData(row, col, 2); //2. Columns cannot be repeatedletunUseGroupList = this.getNoRepeatData(row, col, 3); //3.9 The palace can not be repeatedCopy the code

    And then you take the intersection of these three arrays, which is an array of values that can be inserted, and you just insert a random value from that array.

    Code for generating arrays:

    getNoRepeatData(row, col, type) {

    letbaseDataList = this.baseDataList; //1. Each row cannot be repeated //2. Each column cannot be repeated //3if (type=== 1) {// Filter out objects with values // debuggerlet exitDataList = this.gridList[row].filter((item, i) => {
            if(item && i ! == col)return item["text"];
        });

        return this.getUnUseDataList(exitDataList, baseDataList);
    } else if (type= = = 2) {let colDataList = this.gridList.map(item => {
            return (item.filter((subItem, index) => {
                returnindex === col; [0]}}))); // Filter out objects with valueslet exitDataList = colDataList.filter((item, i) => {
            if(item && i ! == row)return item["text"];
        });

        return this.getUnUseDataList(exitDataList, baseDataList);
    } else if (type= = = 3) {let rowRange = [(row / 3 | 0) * 3, (row / 3 | 0) * 3 + 3];
        let colRange = [(col / 3 | 0) * 3, (col / 3 | 0) * 3 + 3];
        // console.log(rowRange, colRange);

        let exitDataList = [];

        for (let i = rowRange[0]; i < rowRange[1]; i++) {
            for (let j = colRange[0]; j < colRange[1]; j++) {
                let item = this.gridList[i][j];
                if(item && (i ! == row || j ! == col))exitDataList.push(item);
            }
        }
        // console.log(exitDataList);

        return this.getUnUseDataList(exitDataList, baseDataList); }};Copy the code

    Ok and then we can try to generate standard answers.

    . loading…

    DuangDuangDuang what only generates two lines of data and is finished. Try again, it’s 3 lines, try again, it’s 2 lines.

    Careful study found that after a certain amount of data is generated, there will indeed be no data to generate the situation. Such as:

    Well, I’m going to try a different generation order: 9 cells to see if I can improve the success rate

    Well, the number is a bit too much. I tried the loop 100 times and succeeded 1 time, 1% of the time. (In the middle, I also tried to generate from the 9 grids on the four corners and in the middle, and regenerate into other grids. Although the number generated will be a little more, the success rate is still about the same.)

    It seems that the problem must be solved at the root.

    Recall that we generated values by inserting one of several alternatives, which dwindled down until there were none left. So when we have no value to take, we can consider doing a fallback, go back to the previous step to choose another value, then the optional value of our step may increase. (Kind of like the Butterfly effect)

    addCacheData(i, j, validData) {
    this.beforeGridDataList.unshift({row: i, col: j, validData});
    if (this.beforeGridDataList.length > this.cacheLength) {
        this.beforeGridDataList.length = this.cacheLength;

    }
    // console.log("this.beforeGridDataList", JSON.parse(JSON.stringify(this.beforeGridDataList)))

};

rollBack() {

    if (this.beforeGridDataList.length > 0) {
        // console.warn("rollBack"Parse (json.stringify (this.beforeGridDatalist))) // Take one of the optional values from the previous steplet beforeGridData = this.beforeGridDataList.shift();

        let beforeValidList = beforeGridData.validData.list;

        if (beforeValidList.length > 0) {
            let data = beforeValidList[common.getRandom(beforeValidList.length)];
            beforeValidList.splice(beforeValidList.indexOf(data), 1);
            return {
                row: beforeGridData.row,
                col: beforeGridData.col,
                validData: {data, list: beforeValidList}
            }

        } else {
            returnthis.rollBack(); }}else {
        returnnull; }};Copy the code

    This code creates a cache array to store the last optional values. If there are no more values to generate, go to the previous step, and go up until there are no more values, and start generating from that step again.

    If we set the size of the cache array to 3, let’s test the success rate

    Test 10 times remove the highest and lowest values, generating a map 20.75 times on average

    If I set it to 6

    Um 6.125 times on average, which is already an acceptable value (if the value is set up, it is found that the influence is not great, and the influence on performance may be far greater than the improvement of success rate, so the length is set to 6 by default).

    So far, the generated data is almost enough, but considering that there may be some special cases where more than 20 times will be generated, I have saved several successful generated data in advance, and I will directly fetch these data when the number of failures is more than 20 times.

  3. Hide some data

    This step is relatively easy to paste the code directly

    _hideSomeGridData() {for (let i = 0; i < 9; i++) {
        let rowList = [];
        lethideCount = common.getRandom(... this.level.hideGridRange);for (let j = 0; j < hideCount; j++) {
            let unAvailableList = this.gridList[i].filter((item, index) => {
                return! item.isAvailable; }); unAvailableList[common.getRandom(unAvailableList.length)].isAvailable =true; } this.gridList.push(rowList); }},Copy the code

Features to be added later

The e first point, of course, is to change the UI (wry smile), after all, I want to say who can know that I was like according to the motion effect to do. In other words, we will consider adding some difficulty levels, which are already available, but we haven’t added data testing yet, so we may want to do something different.

Like using pictures to make 9 grids…

conclusion

En routine a wave: my technical level is limited, time is also relatively hasty, write bad place welcome to point out. The code has been uploaded to Github: there is a need to star!