typescript - 试图用打字稿和回溯解决数独的错误
问题描述
我正在编码算法,为了测试回溯,我决定在打字稿中实现数独求解器。
我正在使用一个简单的回溯实现,没什么特别的,但它不起作用:
export type SudokuBoard = Array<Array<number>>;
export type Location = [number, number];
const UNASSIGNED = 0;
// Functions
export const range = (start: number, end: number): Array<number> =>
Array.from({ length: end - start + 1 }, (_, i) => start + i);
function findEmptyLocation(board: SudokuBoard): Location {
for (const row of range(0, 8))
for (const col of range(0, 8))
if (board[row][col] === UNASSIGNED) {
return [row, col];
}
return null;
}
function usedInRow(board: SudokuBoard, row: number, value: number): boolean {
for (const i of range(0, 8))
if (board[row][i] === value)
return true;
return false;
}
function usedInCol(board: SudokuBoard, col: number, value: number): boolean {
for (const i of range(0, 8))
if(board[i][col] === value)
return true;
return false;
}
function usedInBox(board: SudokuBoard, row: number, col: number, value: number): boolean {
for (const i of range(0, 2))
for (const j of range(0, 2))
if (board[i + row][j + col] === value)
return true;
return false;
}
const checkIsSafeLocation = (board: SudokuBoard, row: number, col: number, value: number) =>
!usedInRow(board, row, value) && !usedInCol(board, col, value) && !usedInBox(board, row, col, value);
export function solveSudoku(board: SudokuBoard): boolean {
const emptyLocation = findEmptyLocation(board);
if (!emptyLocation)
return true; // sudoku is solved!!
const [row, column] = emptyLocation;
for (const value of range(1, 9)) {
// if looks promising (empty position)
if (checkIsSafeLocation(board, row, column, value)) {
console.log(`Position: (${row}, ${column}) accepts value: ${value}`);
board[row][column] = value;
if (solveSudoku(board)) // if is solved returns!!!
return true;
// not solved, reset location and try again
board[row][column] = UNASSIGNED;
}
}
return false;
}
// EXECUTION
console.clear();
console.log(solveSudoku([
[0, 1, 6, 5, 7, 8, 4, 9, 2],
[5, 2, 9, 1, 3, 4, 7, 6, 8],
[4, 8, 7, 6, 2, 9, 5, 3, 1],
[2, 6, 3, 4, 1, 5, 9, 8, 7],
[9, 7, 4, 8, 6, 3, 1, 0, 5],
[8, 5, 1, 7, 9, 2, 6, 4, 3],
[1, 3, 8, 9, 4, 7, 2, 5, 6],
[6, 9, 0, 3, 5, 1, 8, 7, 4],
[7, 4, 5, 2, 8, 6, 3, 1, 0],
]));
你可以在这里查看:stackblitz
我的代码中有问题,因为这不起作用,但我没有找出问题所在。
你能帮助我吗?
解决方案
我发现了问题。
方框计算错误。
谢谢你。
推荐阅读
- php - 致命错误:未捕获错误:语法错误,意外 '"](?P
.+?)['"' (T_CONSTANT_ENCAPSED_STRING), 在 PHP 中期望 ')' - java - 在 Java 客户端中使用 UpdateByQueryRequest
- javascript - 如何等待在NodeJS中使用嵌套循环将数据存储在数据库中
- flutter - 颤抖很多//忽略:我的代码中的不必要_null_comparison
- javascript - nodejs服务器重新启动并在调用appendfile时发送相同的请求
- angular11 - 当主题更改为ngx-admin angular中的深色主题时如何更改p表背景颜色
- python - 如何在 cx_Oracle 的 callproc 函数中将路径作为参数
- python - 将分钟数据转换为每小时数据
- github - 将项目从默认分支推送到其他分支
- git - 当 master 还没有准备好发布时,如何部署 bug 修复?