jjzjj

javascript - 确定数独是否可在 JavaScript 中求解

coder 2024-07-20 原文

这是 Pramp 的问题。我需要确定数独是否可解(不像 LEETcode 问题，我只需要查看一个板是否有效)。

下面是我的 JavaScript 代码，使用递归。我遵循 Pramp 上建议的逻辑，即创建一个辅助函数 getCandidates() 来查找所有可以进入空白区域的候选数字。然后在实际的 sudokuSolve() 函数中，找到候选集最少的空白空间，将这些候选输入到空白空间中，然后尝试使用递归求解棋盘。如果可行，则董事会是可以解决的。

我的代码每次都返回 true，但我找不到问题所在。我研究了互联网上提出的其他类似问题，但大多数问题都是为了找到数独板的确切解决方案或生成数独板。我只需要看看董事会是否可以解决。如果您能告诉我我的代码哪里有问题，我将不胜感激。

无论测试用例如何，我现在每次都得到“真”...对于提供的这个测试用例，答案应该为假。

const test02 = [
  ['.', '8', '9', '.', '4', '.', '6', '.', '5'],
  ['.', '7', '.', '.', '.', '8', '.', '4', '1'],
  ['5', '6', '.', '9', '.', '.', '.', '.', '8'],
  ['.', '.', '.', '7', '.', '5', '.', '9', '.'],
  ['.', '9', '.', '4', '.', '1', '.', '5', '.'],
  ['.', '3', '.', '9', '.', '6', '.', '1', '.'],
  ['8', '.', '.', '.', '.', '.', '.', '.', '7'],
  ['.', '2', '.', '8', '.', '.', '.', '6', '.'],
  ['.', '.', '6', '.', '7', '.', '.', '8', '.']
];

function getCandidates(board, row, col) {
  const candidates = [];

  for (let chr = 1; chr <= 9; chr++) {
    let collision = false;
    for (let i = 0; i < 9; i++) {
      if (
        board[row][i] == chr ||
        board[i][col] == chr ||
        board[row - (row % 3) + Math.floor(i / 3)][
          col - (col % 3) + Math.floor(i / 3)
        ] == chr
      ) {
        collision = true;
        break;
      }
    }

    if (!collision) {
      candidates.push(chr);
    }
  }
  return candidates;
}

function sudokuSolve(board) {
  let row = -1;
  let col = -1;
  let candidates = [];

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] === '.') {
        newCandidates = getCandidates(board, r, c);
        if (
          candidates.length === 0 ||
          newCandidates.length < candidates.length
        ) {
          candidates = newCandidates;
          row = r;
          col = c;
        }
      }
    }
  }
  if (candidates.length === 0) {
    return true;
  } else {
    let solvable = false;
    candidates.forEach(val => {
      board[row][col] = val;
      if (sudokuSolve(board)) {
        solvable = true;
      } else {
        board[row][col] = '.';
      }
    });
    return solvable;
  }
}
console.log(
  sudokuSolve(test02)
);

最佳答案

问题出在你的行上:

if (candidates.length === 0) {
    return true;

您没有区分候选人为空的两种情况 - 可能是:

a) 谜题已经完全解开，没有未知的“.”。剩余方 block (在这种情况下，是的，返回 true)

b) 谜题变得无解，剩下的“.”方 block 没有任何有效值

由于您对这两个都返回“true”，所以看起来一切都已解决。

尝试添加一个 bool 值来检测是否有“.”方 block 仍然存在，并在您的“if”条件中使用它:

let allSquaresFilled = true;
for (let r = 0; r < 9; r++) {
  for (let c = 0; c < 9; c++) {
    if (board[r][c] === '.') {
        allSquaresFilled = false;


if (allSquaresFilled) {
    return true;

关于javascript - 确定数独是否可在 JavaScript 中求解，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56249817/

定数求解39sectioncandidatesjavascriptsudoku

有关javascript - 确定数独是否可在 JavaScript 中求解的更多相关文章

  1. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  2. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  3. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  4. ruby-on-rails - Ruby 检查日期时间是否为 iso8601 并保存 - 2

    我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby​​是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查

  5. ruby - 检查日期是否在过去 7 天内 - 2

    我的日期格式如下:"%d-%m-%Y"(例如，今天的日期为07-09-2015)，我想看看是不是在过去的七天内。谁能推荐一种方法？ 最佳答案 你可以这样做:require"date"Date.today-7 关于ruby-检查日期是否在过去7天内，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/32438063/

  6. ruby - 如何验证 IO.copy_stream 是否成功 - 2

    这里有一个很好的答案解释了如何在Ruby中下载文件而不将其加载到内存中:https://stackoverflow.com/a/29743394/4852737require'open-uri'download=open('http://example.com/image.png')IO.copy_stream(download,'~/image.png')我如何验证下载文件的IO.copy_stream调用是否真的成功——这意味着下载的文件与我打算下载的文件完全相同，而不是下载一半的损坏文件？documentation说IO.copy_stream返回它复制的字节数，但是当我还没有下

  7. ruby - 是否可以覆盖 gemfile 进行本地开发？ - 2

    我们的git存储库中目前有一个Gemfile。但是，有一个gem我只在我的环境中本地使用(我的团队不使用它)。为了使用它，我必须将它添加到我们的Gemfile中，但每次我checkout到我们的master/dev主分支时，由于与跟踪的gemfile冲突，我必须删除它。我想要的是类似Gemfile.local的东西，它将继承从Gemfile导入的gems，但也允许在那里导入新的gems以供使用只有我的机器。此文件将在.gitignore中被忽略。这可能吗？ 最佳答案 设置BUNDLE_GEMFILE环境变量:BUNDLE_GEMFI

  8. ruby - 在 Windows 机器上使用 Ruby 进行开发是否会适得其反？ - 2

    这似乎非常适得其反，因为太多的gem会在window上破裂。我一直在处理很多mysql和ruby​​-mysqlgem问题(gem本身发生段错误，一个名为UnixSocket的类显然在Windows机器上不能正常工作，等等)。我只是在浪费时间吗？我应该转向不同的脚本语言吗？ 最佳答案 我在Windows上使用Ruby的经验很少，但是当我开始使用Ruby时，我是在Windows上，我的总体印象是它不是Windows原生系统。因此，在主要使用Windows多年之后，开始使用Ruby促使我切换回原来的系统Unix，这次是Linux。Rub

  9. ruby-on-rails - Cucumber 是否只是 rspec 的包装器以帮助将测试组织成功能？ - 2

    只是想确保我理解了事情。据我目前收集到的信息，Cucumber只是一个“包装器”，或者是一种通过将事物分类为功能和步骤来组织测试的好方法，其中实际的单元测试处于步骤阶段。它允许您根据事物的工作方式组织您的测试。对吗？ 最佳答案 有点。它是一种组织测试的方式，但不仅如此。它的行为就像最初的Rails集成测试一样，但更易于使用。这里最大的好处是您的session在整个Scenario中保持透明。关于Cucumber的另一件事是您(应该)从使用您的代码的浏览器或客户端的角度进行测试。如果您愿意，您可以使用步骤来构建对象和设置状态，但通常您

  10. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

随机推荐