程序员经验分享-hwhale

JS 中的数独求解器

2023-12-19

我正在尝试编写一种可以解决数独的算法。目前，我的代码可以正常工作，直到 SupplyGrid 的数量耗尽为止。当这种情况发生时，它应该返回并尝试另一个号码，对吧？老实说，我不知道如何实现这一目标。

var grid = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
],
    supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9],
    row = 0,
    col = 0,
    value = 0,
    index = 0;


var solveSudoku = function (grid, row, col) {
    if (col > 8) {
        row++;
        col = 0;
        if (row > 8 && col > 8) {
            console.log(grid);
            return;
        }
    }
    if (grid[row][col] === 0) { //
        index = Math.floor(Math.random() * supplyGrid.length);
        value = supplyGrid[index];
        if (isValid(row, col, value)) {
            grid[row][col] = value;
            col++;
            supplyGrid = [1, 2, 3, 4, 5, 6, 7, 8, 9];
            solveSudoku(grid, row, col);
        } else {
            supplyGrid.splice(index, 1);
            console.log(supplyGrid);
            if (supplyGrid.length < 1) { 
                //backtrack();
                console.log('Out of numbers');
                return;
            }
            solveSudoku(grid, row, col);
        }
    } else { //row = 3, col = 5
        solveSudoku(grid, row, ++col);
    }
    return this;
}

function isValid(row, col, value) {
    if ((validateColumn(row, col, value)) || (validateRow(row, col, value)) || (validateBox(row, col, value))) {
        return false;
    } else {
        return true;
    }
}

function validateBox(row, col, value) {
    row = Math.floor(row / 3) * 3;
    col = Math.floor(col / 3) * 3;
    var isFound = false;
    for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
            if (grid[row + i][col + j] == value) isFound = true;
        }
    }
    return isFound;
}

function validateRow(row, col, value) { 
    var isFound = false;
    for (var i = 0; i < 9; i++) {
        if (grid[row][i] === value) isFound = true;
    }
    return isFound;
}

function validateColumn(row, col, value) { 
    var isFound = false;
    for (var i = 0; i < 9; i++) {
        if (grid[i][col] === value) isFound = true;
    }
    return isFound;
}

我用回溯算法解决了这个问题：

const _board = [
    ['.', '9', '.', '.', '4', '2', '1', '3', '6'],
    ['.', '.', '.', '9', '6', '.', '4', '8', '5'],
    ['.', '.', '.', '5', '8', '1', '.', '.', '.'],
    ['.', '.', '4', '.', '.', '.', '.', '.', '.'],
    ['5', '1', '7', '2', '.', '.', '9', '.', '.'],
    ['6', '.', '2', '.', '.', '.', '3', '7', '.'],
    ['1', '.', '.', '8', '.', '4', '.', '2', '.'],
    ['7', '.', '6', '.', '.', '.', '8', '1', '.'],
    ['3', '.', '.', '.', '9', '.', '.', '.', '.'],
];
sodokoSolver(_board);
console.log(_board);

function isValid(board, row, col, k) {
    for (let i = 0; i < 9; i++) {
        const m = 3 * Math.floor(row / 3) + Math.floor(i / 3);
        const n = 3 * Math.floor(col / 3) + i % 3;
        if (board[row][i] == k || board[i][col] == k || board[m][n] == k) {
          return false;
        }
    }
    return true;
}


function sodokoSolver(data) {
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (data[i][j] == '.') {
        for (let k = 1; k <= 9; k++) {
          if (isValid(data, i, j, k)) {
            data[i][j] = `${k}`;
          if (sodokoSolver(data)) {
           return true;
          } else {
           data[i][j] = '.';
          }
         }
       }
       return false;
     }
   }
 }
 return true;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

javascript

solver

Sudoku

JS 中的数独求解器 的相关文章

随机推荐

  • C# 中修饰符的顺序有约定吗？

    如果我要使用多个修饰符关键字 我应该按什么顺序使用 例如 public private protected virtual abstract override new static internal sealed 以及我忘记的任何其他人 我

  • 为什么 OpenXML 读取行两次

    我计算两个工作表中的行数 如下所示 foreach WorksheetPart worksheetPart in workbookPart WorksheetParts OpenXmlPartReader reader new OpenXm

  • 当 selectedItem 为 null 时，在 Combobox 中显示“选择一项”

    我有一个绑定到 viewModel 对象列表的 WPF 组合框 最初 SelectedItem 为空 因此组合框显示为空白 当所选项目为空时 我希望组合框显示 选择项目 以引导用户从组合框中选择某些内容 有点像这样 一些文本框包含灰色文本

  • Flexbox 中的行换行中心对齐

    目前 我正在尝试使用 Flexbox 将列居中 但当我调整浏览器大小时 它会粘在左侧 我尝试过调整内容中心和对齐项目中心 但我可能没有将它们放在正确的位置 如果有人知道如何解决这个问题 将不胜感激 谢谢你 wrap display flex

  • 无法完成交付

    我在尝试完成已发布的交付时收到以下错误 我可以从目标网站做些什么吗 cleartool Error Unable to check out vobs amit sumit lost found pcs i ltf odfc set sftp

  • 如何使用 javaparser 获取类级别变量声明？

    我只想获取类级别的变量声明 如何使用 javaparser 获取声明 public class Login private Keyword browser private String pageTitle Login 使用javaparse

  • 为 GridView 添加捏缩放功能

    我需要为该 gridview 添加捏缩放 我没有找到任何有关在 gridview 中添加捏缩放的示例 到目前为止 我的布局如下所示 我需要向该 gridview 添加捏缩放 活动 main xml

  • 张量流中的CUDA_ERROR_OUT_OF_MEMORY

    当我开始训练一些神经网络时 它满足了CUDA ERROR OUT OF MEMORY但训练可以继续进行 不会出现错误 因为我想根据实际需要使用GPU内存 所以我设置了gpu options allow growth True 日志如下 I

  • 如何超链接到 .ppt 文件的特定幻灯片？

    我想链接到在线 PowerPoint 文件中的特定幻灯片 例如http www example com hello ppt 但我想要的是 当人们点击我的链接时 它会直接转到第 n 张幻灯片 这可能吗 Link to http www wha

  • html2canvas 不渲染 CDN 图像

    我正在尝试使用 html2canvas 获取屏幕截图 它对于文本工作正常 但它不渲染 CDN 图像 如果我在服务器中托管图像 它工作正常 但如果尝试从 CDN 链接加载图像 则这些图像不会渲染 我的代码是 索引 php div img sr

  • 从 Android 应用程序共享图像

    我正在尝试分享我的 Android 应用程序中的图像 我正在尝试将其作为电子邮件附件以及 WhatsApp 上的照片发送 代码是 String imageUrl Path to image eg sdcard pictures image1

  • 在 Django 数据库中存储整数数组

    在 django 数据库中存储整数数组的最佳方法是什么 我正在使用数组字段 https docs djangoproject com en 2 1 ref contrib postgres fields querying arrayfiel

  • Python，argparse：如何使 nargs=2 与 type=str 和 type=int

    我花了一些时间在 argparse 文档上 但我仍然在为我的程序中的一个选项使用这个模块而苦苦挣扎 parser add argument r rmsd dest rmsd nargs 2 help extract the poses th

  • Vagrant 配置错误 - “必须指定一个框。”

    盒子工作得很好 然后我停止了其中一个 当时唯一一个正在运行的 现在我无法让它们中的任何一个恢复 Running vagrant up name 给我以下错误 无论我选择哪个或是否将其保留在vagrant up让他们俩都出现 There ar

  • 头文件中的 Lambda 错误

    在我的一堂课上 我尝试使用std priority queue与指定的 lambda 进行比较 pragma once include

  • 将变量注入回调函数作用域

    是否可以将变量添加到回调范围 我想要实现的是 Foo prototype bar function fn var baz baz fn call this Foo bar function console log baz gives baz

  • 如何异步使用“WinHttp.WinHttpRequest.5.1”？

    代码 var WinHttpReq OleVariant procedure TForm1 Button1Click Sender TObject begin WinHttpReq CreateOleObject WinHttp WinHt

  • 在wxPython中查找文本大小的正确方法

    我正在使用 wxPython 开发一个应用程序 该应用程序的一部分在网格中创建大量 TextCtrl 以便为任意大的人员列表输入一周中的每一天的四字母代码 我已经设法让它发挥作用 但我不得不做一些笨拙的事情 具体来说 我还没有找到一种好的方

  • 网络音频 api 以不同的速率播放嘟嘟声、嘟嘟声、...嘟嘟声

    我试图根据浏览器窗口内的一些传感器读数以不同的速率播放 嘟嘟 声 这个想法是当传感器读数高时更快地 嘟嘟 嘟嘟 嘟 嘟 当传感器读数低时更慢地 嘟 嘟 所有这些都是实时的 传感器读数通过 socket io 输入浏览器 我已经可以控制进度条

  • JS 中的数独求解器

    我正在尝试编写一种可以解决数独的算法 目前 我的代码可以正常工作 直到 SupplyGrid 的数量耗尽为止 当这种情况发生时 它应该返回并尝试另一个号码 对吧 老实说 我不知道如何实现这一目标 var grid 0 0 0 0 0 0 0

热门标签