1

我正在开发一个基于网络的数独游戏，允许用户定制自己的数独板。我需要一种方法来告诉用户他组装的电路板有多少可能的解决方案。数独具有唯一解决方案的最小条目数是 17。我需要找到条目数小于 17 的解决方案数。

这是我的方法：

public long numberOfSolutions (Board myBoard) {
    this.board = myBoard;
    this.tempBoard = new Board();
    long num = 0;

    tempBoard.copy(board);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board.getCell(i,j).equals(0)) {
                for(int k=1;k<10;k++){
                    board.setCell(i, j, k, true);
                    if(isCorrect() && solvable()){
                        num++;
                    }
                    board.copy(tempBoard);
                }
            }
        }
    }
    return num;
}

所以基本上对于每个空单元格，我都会插入 1-9 的数字，并尝试为每个数字解决游戏。如果成功增加解决方案的数量。但这并没有让我知道所有可能组合的数量，而是可以插入的每个单元格的数字总和。

有没有办法可以计算这个？

4

3 回答 3

3

答案是（可能）：不要那样做。

数独求解是NP-complete，因此可能需要一段时间才能求解，更不用说计算解决方案的数量了。

即使您尝试计算计数，它也可能非常大。一个没有任何东西的数独板有6,670,903,752,021,072,936,960 个答案。

于 2013-05-19T20:51:49.900 回答
2

我不会说太多Java，但这里是递归方法的基本描述：

如果棋盘有错误（即在同一行、同一列或同一框中有两个相同的数字），则解决方案为零。如果没有错误并且电路板已满，则有一种解决方案。如果没有错误但棋盘未满，则选择最早的空单元格，并将该单元格中包含 1、2、...、9 的棋盘的解数相加。

这不是最好的方法，但它可以完成工作，而且我敢肯定，一旦代码实际出现在屏幕上，就会有一些优化等待进行。

于 2013-05-19T21:49:10.097 回答
0

也许我几年前保存的一些东西可能会在下面给出一些想法，其中具有最多候选者的单元格而不是选择最少的单元格似乎可以确保在给定允许的情况下提供多个解决方案，然后停在计数等于二。否则尽可能解谜，只有在空单元数足够少的情况下，才可能进行计数。由于它是 html 代码，我不确定您是否可以看到它，但它是：

    <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
    <HTML>
    <HEAD>
    <TITLE>Sudoku Solver</TITLE>
    <META name="Keywords" content="Sudoku, Simple, javascript, puzzle">
    <META name="Description" content="Simple Sudoku Solver, written in JavaScript">
    <script type="text/javascript">
    function Board() {
     this.cells=new Array();
     for (var i=0; i<81; ++i)
      this.cells[i]=0;
    }

    function CopyBoard(dest, src) {
     for (var i=0; i<81; ++i)
      dest.cells[i]=src.cells[i];
    }
    function CountConstraints(val) {
     var cc=0;
     for (var i=1; i<=9; ++i)
      if (((1<<i) & val)!=0) ++cc;
     return cc;
    }
    function MostConstrained() {
     var max=-1, maxp=-1;
     for (var i=0; i<81; ++i) {
      if ((this.cells[i] & 1)==0) {
       v=CountConstraints(this.cells[i]);
       if (v>=max) {
        max=v;
        maxp=i;
       }
      }
     }
     return maxp;
    }

    Board.prototype.mostConstrained=MostConstrained;

    function AllOptions(val) {
     var cc=new Array;
     var n=0;
     for (var i=1; i<=9; ++i)
      if (((1<<i) & val)==0) cc[n++]=i;
     return cc;
    }

    function SetValue(pos, val) {
      var x=pos%9;
      var y=Math.floor(pos/9);
      var x0=Math.floor(x/3)*3;
      var y0=Math.floor(y/3)*3;
      var add=(1<<val);
      for (var k=0; k<9; ++k) {
        this.cells[x+k*9]|=add;
        this.cells[k+y*9]|=add;      
        this.cells[x0+(k%3)+9*(y0+Math.floor(k/3))]|=add;}
      this.cells[pos]=1023-(1<<val);
    }
    Board.prototype.setValue=SetValue;

    function CellText(d) {
     if (d&1) {
      for (var i=1; i<=9; ++i)
       if ((d | (1<<i))==1023) return ""+i;
      return "_";
     }
     else {
      return "?"+AllOptions(d);
     }
    }
    function AsHTML() {
     var ans="";
     for (var y=0; y<9; ++y) {
      ans=ans+"<tr>"
      for (var x=0; x<9; ++x) {
       ans=ans+"<td class=sol>"+CellText(this.cells[x+y*9])+"<\/td>";
      }
      ans=ans+"<\/tr>";
     }
     return "<table border=1>"+ans+"<\/table>"
    }
    Board.prototype.asHTML=AsHTML; 

    function IsOK() {
     for (var i=0; i<81; ++i) {
      if ((this.cells[i] & 1022)==1022) {
        return false;
      }
     }
     return true;
    }  

    function IsSolved() {
     for (var i=0; i<81; ++i) {
      if ((this.cells[i] & 1)==0) return false;
     }
     return true;
    }

    Board.prototype.isSolved=IsSolved;
    Board.prototype.isOK=IsOK;

    var theOne=new Board();
    var numSol;

    function SearchSolutions() {
        while (this.isOK()) {
            if (this.isSolved()) {
                if (1<++numSol) return this;
                CopyBoard(theOne,this);return null;}
            var p=this.mostConstrained();
            if (p<0) return null;
            var l=AllOptions(this.cells[p]);
            if (l.length<1) return null;
            for (var i=1; i<l.length; ++i) {
                var nb=new Board();
                CopyBoard(nb, this);
                nb.setValue(p, l[i]);
                nb=nb.searchSolutions();
                if (nb) return nb;}
            this.setValue(p, l[0]);}
        return null;
    }
    Board.prototype.searchSolutions=SearchSolutions;

    function DrawInput() {
     var ans="";
     for (var y=0; y<9; ++y) {
      ans=ans+"<tr>"
      for (var x=0; x<9; ++x) {
       ans=ans+"<td class=sol><input size=1 type=text id='C"+(x+y*9)+"'><\/td>";
      }
      ans=ans+"<\/tr>"
     }
     document.write("<table border=1>"+ans+"<\/table>");
    }
    function solve_click() {
        var theSec=new Board();
        numSol=0;
        for (var i=0; i<81; ++i) {
        var v=document.getElementById("C"+i).value
        if (v>="1" && v<="9") theSec.setValue(i, parseInt(v));}
        var rsp=theSec.searchSolutions();
        var ans="<p>No solution<\/p>";
        if (numSol==1) ans="<p>Valid Sudoku - One and only one solution !<\/p>"+theOne.asHTML();
        if (numSol==2) ans="<p>Invalid Sudoku - More than one solution !<\/p>"+theOne.asHTML()+"<p><\/p>"+rsp.asHTML();
        document.getElementById("answer").innerHTML=ans;
    }

    </SCRIPT>

    <STYLE type=text/css>
    .sol {
        WIDTH: 1em; HEIGHT: 1em
    }
    </STYLE>
    </HEAD>
    <BODY>
    <h1>Sudoku Solver</h1>
    <a href="solverabout.html"><span style="font-size: smaller">(about)</span></a>

    <div>
    <script type="text/javascript">
     DrawInput();
    </script>
    <input type="button" value="Solve" onclick="solve_click();">
    </div>
    <div id="answer"></div>
    </BODY>
    </HTML>
于 2016-04-18T05:11:48.110 回答