주어진 스도쿠 퍼즐에 대한 솔루션 수를 계산 하시겠습니까?

저는 사용자가 자신의 스도쿠 보드를 만들 수있는 웹 기반 스도쿠 게임을 개발 중입니다. 사용자가 보드를 조립할 때 가능한 해결책의 수를 알려주는 방법이 필요합니다. 그래서 기본적으로 대한주어진 스도쿠 퍼즐에 대한 솔루션 수를 계산 하시겠습니까?

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

: 고유의 솔루션을 가지고 스도쿠에 대한 항목의 최소 수는 내가 여기

17 이하의 항목 수에 대한 솔루션의 수를 찾을 필요 17. 내 방법 것입니다 각각의 빈 셀은 1-9의 숫자를 삽입하고 각 숫자에 대한 게임을 풀려고합니다. 성공한 경우 솔루션 수를 늘립니다. 그러나 이것은 모든 가능한 조합의 수를 얻지는 않습니다. 플러그 할 수있는 각 셀의 수의 합계가 아닙니다.

계산 방법은 있습니까?

출처

2013-05-19 Srđan Miljević

대답은 (아마도)입니다. 그러지 마세요.

스도쿠 해결은 NP-complete이므로 해결책 수를 세지 않고 한 해결하는 데 시간이 걸릴 수 있습니다.

카운트를 계산하려고해도 매우 클 수 있습니다. 그것에 아무것도없는 스도쿠 보드는 6,670,903,752,021,072,936,960 답이 있습니다.

출처

2013-05-19 20:51:49

스도쿠 해결이 NP-완료,하지만 아주 작은 N이있다 (9) 그래서 스도쿠 솔버 및 밀리 초 단위로 실행 할 수 있습니다 . – Patashu

@Patashu 여전히 미확인 격자의 경우 가능한 해결책의 수가 빠르게 폭발하므로 "하지 마라"는 좋은 충고입니다. –

@DanielFischer 0, 1, 2, 3, 4, 5 또는 'too many'를 반환하는 솔루션을 상상해보십시오. 그것은 쉽게 쓸 수 있으며 OP가 원하는 것입니다. – Patashu

내가 여기에 많은 자바 말을하지 않지만 재귀 방법의 기본적인 설명입니다 :

보드 오류 (즉, 동일한 행, 열 또는 상자에 두 개의 동일한 번호), 다음이있는 경우 제로 솔루션입니다. 오류가없고 보드가 가득차면 한 가지 해결 방법이 있습니다. 오류가 없지만 보드가 가득 차 있지 않은 경우 가장 오래된 빈 셀을 선택하고 해당 셀에 1, 2, ..., 9가 들어있는 보드에 대한 솔루션 수를 합합니다.

이것은 가장 좋은 방법은 아니지만 작업이 완료되고 코드가 실제로 화면에 나타나면 대기중인 일부 최적화가 완료됩니다.

출처

2013-05-19 21:49:10 MegaWidget

아마도 내가 몇 년 전에 구한 것은 그것이 아래에 있다는 아이디어를 줄 수도 있습니다. 선택되지 않은 세포보다 가장 많은 후보 세포를 가진 세포가 주어진다면 하나 이상의 해결책을 확보하는 것처럼 보입니다. , 그 다음 카운트가 2와 같으면 중단하십시오. 그렇지 않으면 퍼즐을 가능한 한 멀리 풀고 빈 셀이 충분하지 않은 경우에만 계산할 수 있습니다. 이 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-18 05:11:48 Lesroy

질문은 자바에 관한 것이 었습니다 ...? –

주어진 스도쿠 퍼즐에 대한 솔루션 수를 계산 하시겠습니까?

답변

관련 문제