Last active
February 14, 2019 02:20
-
-
Save brayvasq/536934bc12a08d38aece33a57ddbd24f to your computer and use it in GitHub Desktop.
Backtracking solution to problem that locate the numbers from 1 to (n*n) in a board, Checking that the sum of all the rows, all the columns and the main diagonals are the same.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* @author brayan vasquez <brayvasq@gmail.com> | |
* @version 0.1 | |
* @date 13/02/2019 | |
*/ | |
/** | |
* Size of matrix n*n | |
*/ | |
const n = 3 | |
/** | |
* Magic constant | |
*/ | |
let sum = n * ((n**2 + 1) / 2); | |
/** | |
* board where the numbers will be located | |
*/ | |
let matrix = [ | |
[0,0,0], | |
[0,0,0], | |
[0,0,0] | |
] | |
/** | |
* Method that call the checks functions and compares them | |
* @param {*} matrix board with all the numbers located | |
* @param {*} verified tell if a board is a solution | |
*/ | |
function verify(matrix,verified=false){ | |
return verify_row_colums(matrix,false,verified) && | |
verify_row_colums(matrix,true,verified) && | |
verify_diagonal(matrix,0,1,verified) && | |
verify_diagonal(matrix,n-1,2,verified) | |
} | |
/** | |
* Method that check for the columns or the rows if the sum is equal to the magic constant | |
* @param {*} matrix board with all the numbers located | |
* @param {*} rows tell if is a verification for rows or columns | |
* @param {*} verified tell if a board is a solution | |
*/ | |
function verify_row_colums(matrix,rows=false,verified){ | |
let new_sum = 0; | |
let message = ""; | |
for(let i = 0; i < n;i++){ // Iterate the rows of the matrix | |
for(let j=0; j < n; j++){ // Iterate the columns of the matrix | |
if(rows){ | |
message = "SUM ROW" | |
new_sum += matrix[i][j] // ROWS --- | |
}else{ | |
message = "SUM COLUM" | |
new_sum += matrix[j][i] // COLUMS | | |
} | |
} | |
let resp = sum === new_sum? true: false; | |
if(!resp) return false | |
if(verified) console.log(message,i,new_sum) | |
new_sum = 0; | |
} | |
return true | |
} | |
/** | |
* Method that check for a diagonals if the sum is equal to the magic constant | |
* @param {*} matrix board with all the numbers located | |
* @param {*} m tell the horizontal position to start | |
* @param {*} num_diagonal tell the diagonal to check | |
* @param {*} verified tell if a board is a solution | |
*/ | |
function verify_diagonal(matrix,m,diagonal,verified){ | |
let k = 0; // vertical position | |
let new_sum = 0; | |
if(diagonal===1){ | |
// FIRST DIAGONAL \ | |
/** | |
* x 0 0 | |
* 0 x 0 x -> represent the positions to check | |
* 0 0 x | |
*/ | |
while(k < n && m < n){ | |
new_sum += matrix[k][m]; | |
k++; | |
m++; | |
} | |
}else{ | |
// SECOND DIAGONAL / | |
/** | |
* 0 0 x | |
* 0 x 0 x -> represent the positions to check | |
* x 0 0 | |
*/ | |
while(k < n && m >= 0){ | |
new_sum += matrix[k][m]; | |
k++; | |
m--; | |
} | |
} | |
if(verified) console.log("SUM DIAGONAL "+diagonal,new_sum) | |
return new_sum === sum? true:false; | |
} | |
/** | |
* Method that use backtracking to find a solution | |
* @param {*} matrix board where the numbers will be located | |
* @param {*} index node number on the recursion tree | |
* @param {*} num number to locate | |
*/ | |
function sum_matrix(matrix,index,num){ | |
let resp = 0; | |
// If all the board was iterated | |
if(index >= n*n){ | |
//console.log() | |
//matrix.map(i=> console.log(i)) | |
// Verify if the board is a solution of the problem | |
if(verify(matrix)){ | |
/** | |
* print the solution | |
*/ | |
console.log(matrix); | |
console.log(verify(matrix,true)) | |
return true | |
} | |
}else{ | |
for(let i=0; i < n; i++){ // Iterate the rows of the matrix | |
for(let j=0; j < n; j++){ // Iterate the columns of the matrix | |
if(matrix[i][j] === 0){ // locate a number just if the position is empty | |
matrix[i][j] = num; // change the state of the matrix | |
resp = sum_matrix(matrix,index+1,num+1) // call the method for the new matrix | |
// and the next number to locate | |
if(resp) break; // If a solution exist, just break the loops | |
matrix[i][j] = 0; // remove the last change in the matrix | |
} | |
} | |
} | |
} | |
return resp; | |
} | |
//console.log(verify(matrix)) | |
sum_matrix(matrix,0,1) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment