位元幣上的數獨游戲合約-有解無憂

我們在 Bitcoin SV 上實作了一個數獨游戲智能合約，利用之前介紹過的一種合約范式可以將游戲中尋找解題方案的程序外包上鏈，因為求解數獨問題的計算作業量會隨著其行列數快速增長，實際上它也是一個 NP-完全問題，不過我們可以借由位元幣智能合約巧妙地尋求答案，只需要驗證答案提供者所給出的解答是否滿足要求即可，這樣即可以將復雜的求解計算程序實作鏈下外包，

典型的數獨游戲

sCrypt 合約代碼如下：

import "util.scrypt";
import "array.scrypt";

contract Sudoku {

    bytes board;

    static const int N = 9;
    static bytes EMPTY = b'00';

    constructor(bytes board) {
        this.board = board;
    }

    function merge(bytes solution) : bytes {
        bytes newBoard = this.board;
        int i = 0;
        loop (N) {
            int j = 0;
            loop (N) {

                int value = this.readValue(newBoard, i, j);
                int inputValue = this.readValue(solution, i, j);
                if (value == 0) {
                    require(inputValue <= 9);
                    newBoard = this.setValue(newBoard, i, j, inputValue);
                } else {
                    require(value == inputValue);
                }
                j++;
            }

            i++;
        }
        return newBoard;
    }

    public function solve(bytes solution) {

        require(len(solution) == Sudoku.N * Sudoku.N);

        bytes newBord = this.merge(solution);

        Array rowArray = new Array();
        Array colArray = new Array();
        Array squareArray = new Array();

        int i = 0;
        loop (N) {
            int j = 0;

            loop (N) {
                // check for duplicate

                // in a row
                int rowElem = this.readValue(newBord, i, j);
                require(rowArray.indexOf(rowElem) == -1);
                rowArray.push(rowElem);

                // in a column
                int colElem = this.readValue(newBord, j, i);
                require(colArray.indexOf(colElem) == -1);
                colArray.push(colElem);

                // in a subgrid
                int squareElem = this.readSquareValue(newBord, i, j);
                require(squareArray.indexOf(squareElem) == -1);
                squareArray.push(squareElem);

                j++;
            }

            rowArray.clear();
            colArray.clear();
            squareArray.clear();

            i++;
        }

        require(true);
    }

    static function readValue(bytes board, int i, int j): int {
        return Util.fromLEUnsigned(Util.getElemAt(board, Sudoku.index(i, j)));
    }

    static function setValue(bytes board, int i, int j, int value): bytes {
        return Util.setElemAt(board, this.index(i, j), Util.toLEUnsigned(value, 1));
    }

    static function readSquareValue(bytes board, int i, int j): int {
        return Util.fromLEUnsigned(Util.getElemAt(board, Sudoku.indexSquare(i, j)));
    }


    static function index(int row, int col) : int {
        return row * Sudoku.N + col;
    }

    static function indexSquare(int i, int j) : int {
        int row = i / 3 * 3 + j / 3;
        int col = i % 3 * 3 + j % 3;
        return Sudoku.index(row, col);
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250130.html

標籤：其他

上一篇：h5貪吃蛇

下一篇：防抖節流工具型方法的封裝