Counting the number of solutions for a given sudoku puzzle?

Question 1

The answer is (probably): don't do that.

Sudoku solving is NP-complete, so it might take a while to solve one, let alone counting the number of solutions.

Even if you try to compute the count, it might be extremely large. A Sudoku board with nothing on it has 6,670,903,752,021,072,936,960 answers.

Question 2

I don't speak much Java, but here's a basic description of a recursive method:

If the board has errors (i.e., two identical numbers in the same row, column, or box), then there are zero solutions. If there are no errors and the board is full, then there is one solution. If there are no errors but the board isn't full, then pick the earliest empty cell, and sum the number of solutions for the boards which contain 1, 2, ..., 9 in that cell.

This isn't the best method, but it gets the job done, and I'm sure there are some optimizations waiting to be made once the code is actually there on your screen.

Question 3

Maybe something I saved years ago might give some idea it is below,,,in which the cell having the most candidates rather than the cell with the least being chosen seems to ensure more than one solution if the givens allows for it, then stop at count equals two. Otherwise solving puzzle as far as possible and only if there are few enough empty cells, it might be feasible to count. As it is html code I'm not sure you can see it but here it is:

    <!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>