Nano Hash - криптовалюты, майнинг, программирование

Подсчет количества решений для данной головоломки судоку?

Я разрабатываю веб-игру судоку, которая позволяет пользователю создавать свою собственную доску судоку. Мне нужен способ сообщить пользователю количество возможных решений, которые имеет собранная им плата. Минимальное количество записей для судоку, чтобы иметь уникальное решение, равно 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 и пытаюсь решить игру для каждого числа. В случае успеха увеличьте количество решений. Но это не дает мне количество всех возможных комбинаций, а сумму количества чисел для каждой ячейки, которая может быть подключена.

Есть ли способ, которым я могу рассчитать это?

java algorithm math puzzle sudoku
19.05.2013

Ответы:


1

Ответ (вероятно): не делайте этого.

Решение судоку NP-complete, поэтому может потребоваться пока решать одно, не говоря уже о подсчете количества решений.

Даже если вы попытаетесь вычислить количество, оно может быть очень большим. Доска судоку, на которой ничего нет, содержит 6 670 903 752 021 072 936 960 ответов.

19.05.2013
  • Решение судоку является NP-полным, но имеет ОЧЕНЬ маленькое n (9), поэтому решатели судоку могут работать и работают за миллисекунды. 20.05.2013
  • @Patashu Тем не менее, для недоопределенных сеток количество возможных решений быстро растет, поэтому не делайте этого - это хороший совет. 20.05.2013
  • @DanielFischer Представьте себе решение, которое возвращает 0, 1, 2, 3, 4, 5 или «слишком много». Это легко написать и то, что хочет сделать ОП. 20.05.2013
  • @Patashu Да, все в порядке. Вероятно, это то, что нужно ОП, но не то, о чем он просил. 20.05.2013

    • 2

    Я не очень хорошо говорю на Java, но вот базовое описание рекурсивного метода:

    Если на доске есть ошибки (т. е. два одинаковых числа в одной строке, столбце или поле), то решений нет. Если ошибок нет и доска заполнена, то решение одно. Если ошибок нет, но доска не заполнена, то выберите самую раннюю пустую ячейку и просуммируйте количество решений для досок, содержащих 1, 2, ..., 9 в этой ячейке.

    Это не лучший метод, но он выполняет свою работу, и я уверен, что есть некоторые оптимизации, ожидающие выполнения, как только код появится на вашем экране.

    19.05.2013

    3

    Может быть, что-то, что я сохранил много лет назад, может дать некоторое представление о том, что ниже, в котором ячейка с наибольшим количеством кандидатов, а не ячейка с наименьшим выбором, кажется, обеспечивает более одного решения, если данные позволяют это, затем остановитесь на число равно двум. В противном случае, решив головоломку, насколько это возможно, и только если пустых ячеек достаточно, можно будет посчитать. Поскольку это 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>
    18.04.2016
  • Вопрос был о Java...? 18.04.2016
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..