20
2021
01

比特币上的数独游戏合约的实现代码

我们在 Bitcoin SV 上实现了一个数独游戏智能合约,利用之前介绍过的一种合约范式可以将游戏中寻找解题方案的过程外包上链。因为求解数独问题的计算工作量会随着其行列数快速增长,实际上它也是一个 NP-完全 问题。不过我们可以借由比特币智能合约巧妙地寻求答案,只需要验证答案提供者所给出的解答是否满足要求即可,这样即可以将复杂的求解计算过程实现链下外包。

20210119161651103.png

典型的数独游戏


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);

 }

}

« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。