class SudokuSolver {
// check for string being sudoku
validate(puzzleString) {
const puzzleArr = puzzleString.split("")
const digitCheck = puzzleArr.every( val => val.match(/[1-9]/) || val.match(/\./))
const lengthCheck = puzzleArr.length == 81? true: false;
const checkString = this.checkString(puzzleString)
if(digitCheck && lengthCheck && checkString){
return "valid"
}
if(!lengthCheck){
return "Expected puzzle to be 81 characters long"
}
if(!digitCheck){
return "Invalid characters in puzzle"
}
if(!checkString){
return "Invalid puzzle string"
}
}
// check for string by digit.
checkString(puzzleString){
const puzzleArr = puzzleString.split("")
const check = puzzleArr.every((val, index) => {
let {row, column} = this.getRowColumn(index);
if(val.match(/\./)){
return true
}
if(val.match(/[1-9]/)){
column = ""
val = val;
const rowCheck = this.checkRowPlacement(puzzleString, row, column, val)
const colCheck = this.checkColPlacement(puzzleString, row, column, val)
const sqrCheck = this.checkSquareRegionPlacement(puzzleString, row, column, val)
if(rowCheck && colCheck && sqrCheck){
return true
}
}
return false;
})
return check;
}
// check by place in array of string and returns row and column.
getRowColumn(place){
const value = place
place = ""
let obj = {};
place.match(/\b(9|1[0-7])\b/)? obj = {row: 'B', column: value - 8}
: place.match(/1[8-9]|2[0-6]/)? obj = {row: 'C', column: value - 17}
: place.match(/2[7-9]|3[0-5]/)? obj = {row: 'D', column: value - 26}
: place.match(/3[6-9]|4[0-4]/)? obj = {row: 'E', column: value - 35}
: place.match(/4[5-9]|5[0-3]/)? obj = {row: 'F', column: value - 44}
: place.match(/5[4-9]|6[0-2]/)? obj = {row: 'G', column: value - 53}
: place.match(/6[3-9]|7[0-1]/)? obj = {row: 'H', column: value - 62}
: place.match(/7[2-9]|80/)? obj = {row: 'I', column: place - 71}
: obj = {row: 'A', column: value 1};
return obj;
}
// check for valid inputs.
checkValues(row, column, value){
value = ""
column = ""
if(!value.match(/[1-9]/)){
return "Invalid value"
}
if(!row.match(/[A-I]/) || !column.match(/[1-9]/)){
return "Invalid coordinate"
}
return "fine"
}
// check for row(character) and return min and max value for that row.
rowAdd(row){
let arr;
switch(row){
case "A":
arr = [0, 9];
break;
case "B":
arr = [9, 18];
break;
case "C":
arr = [18, 27];
break;
case "D":
arr = [27, 36];
break;
case "E":
arr = [36, 45];
break;
case "F":
arr = [45, 54];
break;
case "G":
arr = [54, 63];
break;
case "H":
arr = [63, 72];
break;
case "I":
arr = [72, 81];
break;
}
return arr;
}
//check placement by row
checkRowPlacement(puzzleString, row, column, value) {
const [min, max] = this.rowAdd(row)
const index = min parseInt(column) - 1
const puzzleArr = puzzleString.split("")
for(let i = min; i < max; i ){
if(puzzleArr[i] == value){
if(i == index){
continue
}
return false
}
}
return true;
}
//check placement by col
checkColPlacement(puzzleString, row, column, value) {
const puzzleArr = puzzleString.split("")
const startIndex = parseInt(column) - 1;
const index = this.rowAdd(row)[0] parseInt(column) - 1;
for(let i = startIndex; i < 81; i = 9){
if(puzzleArr[i] == value){
if(index == i){
continue
}
return false;
}
}
return true
}
// check for which square does the value belongs
checkSquareRegion(row, column){
column = column;
switch(row){
case "A": case "B": case "C":
if(column < 4){
return "0"
}
if(column < 7){
return "1"
}
if(column < 10){
return "2"
}
;
case "D": case "E": case "F":
if(column < 4){
return "3"
}
if(column < 7){
return "4"
}
if(column < 10){
return "5"
}
;
case "G": case "H": case "I":
if(column < 4){
return "6"
}
if(column < 7){
return "7"
}
if(column < 10){
return "8"
}
;
default:
return undefined
}
}
// for square check of different values. return true if value does differ then others.
checkSquareRegionPlacement(puzzleString, row, column, value) {
const puzzleArr = puzzleString.split("")
const square = this.checkSquareRegion(row,column)
const check = this.checkValues(row, column, value)
const index = this.rowAdd(row)[0] parseInt(column) - 1;
if(check == "fine"){
let startIndex = (square * 3)
let flag = true;
for(let i = 0; i < 3; i ){
for(let j = startIndex; j < (startIndex 3); j ){
if((parseInt(puzzleArr[j]) == value)){
if(puzzleArr[j] == puzzleArr[index]){
continue;
} else{
flag = false
}
} else{
continue;
}
}
if(flag == false){
break;
}
startIndex = 9;
}
if(flag){
return true
}
return false;
}else {
return check;
}
}
// solve whole puzzle
solve(puzzleString) {
const validate = this.validate(puzzleString)
if(validate == "valid"){
puzzleString = this.fillSoduko(puzzleString)
} else {
return {error: validate};
}
return puzzleString;
}
// fill soduko.
fillSoduko(puzzleString) {
const puzzleArr = puzzleString.split("")
var _this = this;
fill(puzzleArr.indexOf(val => !val.match(/[1-9]/)))
function fill(index){
console.log(index)
while (index < 81 && puzzleArr[index].match(/[1-9]/)) index; // skip non-empty cells
if (index == 81) return true; // we filled'em all, success!
let moves = getChoices(index);
for (let m of moves) {
puzzleArr[index] = m; // try one choice
if (fill(index 1)) // if we can solve for the next cell
return true; // then return true, success!
}
puzzleArr[index] = "."; // no move worked; we failed, clear the cell
return false;
} // and backtrack
function getChoices(index) {
const {row, column} = _this.getRowColumn(index)
let choices = [];
for (let value = 1; value <= 9; value) {
if (_this.checkPlaceAndValue(puzzleString, row, column, value) == true) {
choices.push(value);
}
}
return choices;
}
return puzzleArr.join("")
}
// check for place and value of the value inserted.
checkPlaceAndValue(puzzleString, row, column, value){
value = value;
const validate = this.validate(puzzleString);
const check = this.checkValues(row, column, value);
if((check == "fine") && (validate == "valid")){
const rowCheck = this.checkRowPlacement(puzzleString, row, column, value)
const colCheck = this.checkColPlacement(puzzleString, row, column, value)
const sqrCheck = this.checkSquareRegionPlacement(puzzleString, row, column, value)
if(rowCheck && colCheck && sqrCheck){
return true
} else{
let obj = {};
!rowCheck ? obj = {conflict: "row"}:
!colCheck ? obj = {conflict: "column"}:
obj = {conflict: "region"};
return obj;
}
} else{
let obj = {}
validate != "valid"? obj = {error: validate}:
obj = { error: check};
return obj;
}
}
}
module.exports = SudokuSolver;
所以我上面有部分代碼需要永遠處理。我必須使用遞回，因為沒有其他選擇。如果我做錯了什么，請通知我。
后端對這個類方法的想法是它需要拼圖字串并自動填充它。它檢查字串中的空（“。”）值，然后檢查是否有任何（1-9）對其有效。當然，有很多單元格是空的，所以我們選擇的不是 1，而是太多的數字。然后，我們會檢查每個選擇是否完成并驗證板。
uj5u.com熱心網友回復：
我注意到的第一件事是：
fill(puzzleArr.indexOf(val => !val.match(/[1-9]/)))
應該：
fill(puzzleArr.findIndex(val => !val.match(/[1-9]/)))
這是一個容易犯的錯誤。 indexOf是在提供的值的陣列中找到第一個索引。 findIndex是找到提供的謂詞函式回傳的陣列中的第一個索引true。
在修復它時，我能夠發現checkSquareRegionPlacement. 我沒有深入研究它，但是使用一個完全解決的難題并簡單地洗掉最終值，我嘗試測驗一個非常簡單的案例：
const complete = "172396845549287316368514297634975182927831564851462973215749638793658421486123759"
const puzzle = "17239684554928731636851429763497518292783156485146297321574963879365842148612375."
當我們進入checkSquareRegionPlacement時，我們應該測驗指數60。61, 62, 69, 70, 71, 78, 79, 80. 但是flag = false當索引j為時（通過設定）失敗了25。我還沒有深入了解這段代碼中的失敗之處，但這至少可以為您指明正確的方向。
總的來說，我建議您解決更大的問題：
拼圖線不斷斷裂。您需要一個更有用的拼圖內部格式。假設這個用數字 (
1-9) 或點 (.) 填充的 81 個字符的字串是您需要的輸入格式，那么我建議您在輸入初始函式時將其更改為更有用的格式，或者包含 81 個字符的單個陣列/數字或它們的 9 x 9 陣列。如果您最后需要轉換回字串格式，那很好。在您的初始呼叫開始和回傳之間，將所有內容保持在更有用的格式中。您反復執行將普通陣列索引轉換為邏輯網格模型并回傳的作業。您可以使用如下代碼預先執行此操作：
const _09 = [0, 1, 2, 3, 4, 5, 6, 7, 8]; const _03 = [0, 1, 2]; const rows = _09 .map ((i) => _09 .map ((j) => 9 * i j)) const cols = _09 .map ((i) => _09 .map ((j) => i 9 * j)) const squares = _03 .flatMap ((i) => _03 .map ((j) => _03 .flatMap ( (k) => _03 .map (l => 27 * i 3 * j 9 * k l) ))) const groups = Array .from ({length: 80}, (_, i) => [ rows .find (row => row .includes (i)), cols .find (col => col .includes (i)), squares .find (square => square .includes (i)) ])然后使用那些存盤的值。例如，“我可以
7在索引處放置一個80嗎？” 變成類似groups [80] .every (g => ! g .includes (7))（未經測驗！）。這將停止對行和列的大部分擺弄。這是
class沒有明顯原因的。您的方法正在它們之間傳遞相關資料，因此似乎沒有內部狀態。在我看來，這作為一個模塊會更好。
還有其他問題。但總的來說，問題似乎是你作業太努力了。我認為強烈的簡化應該真的有幫助。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/470048.html
標籤：javascript 递归