Let's break down this to the smallest possible problem and build up
Check if the content of each cell is correct
First of all, you want to check if the content of each cell is correct. To do that, you have to verify that the value of each cell is a number between 1 and 9. This is simple enough
function isCellContentValid(value) {
return typeof value === "number"
&& value >= 1
&& value <= 9;
}
console.log("1 => ", isCellContentValid(1));
console.log("5 => ", isCellContentValid(5));
console.log("9 => ", isCellContentValid(9));
console.log("0 => ", isCellContentValid(0));
console.log("42 => ", isCellContentValid(42));
console.log("'a' => ", isCellContentValid('a'));
Since this code is pretty simple, we can quickly verify it's correct and using Array#every() we can just check an entire row and we can be sure that the row is correct, since .every() will check if each cell conforms to the predicate:
function isCellContentValid(value) {
return typeof value === "number"
&& value >= 1
&& value <= 9;
}
function isRowContentValid(row) {
return row.every(isCellContentValid);
}
console.log(isRowContentValid([1, 2, 3, 4, 5, 6, 7, 8, 9]))
console.log(isRowContentValid(['a', 2, 3, 4, 5, 6, 7, 8, 9]))
From there, we can trivially check if the entire board has valid content in its cells by using the same idea as above - use .every() to verify each row:
function isBoardContentValid(board) {
return board.every(isRowContentValid);
}
Check if each row contains unique values
However, we also need to check if each collection of values contains unique values. It's easiest to start with rows, so let's do that.
There are many ways to check for uniqueness in an array but let's take one that is simple to read. Put the contents of the array in a Set which will only contain unique values. If the size of the set and the array are the same, that means that there were no duplicates. If there are any, then the set will not contain them and this have a different size:
function isArrayUnique(array) {
const set = new Set(array);
return set.size === array.length;
}
console.log(isArrayUnique([1, 2, 3]));
console.log(isArrayUnique([1, 2, 2]));
This could be optimised but it works for illustrative purposes, since it's simple.
Once we can make sure an array is unique...we can just go through each row again and use .every() to verify that each row contains unique values:
function areRowsUnique(board) {
return board.every(isArrayUnique);
}
Check if each column contains unique values
Cool, one down - we checked the rows. Two to go. Let's go with columns next.
Columns are really just rows but positioned vertically. If you can treat them the same way, you can re-use the same logic. This is tricky but luckily, you can simplify it by doing a matrix transposition which will essentially "rotate 90 degrees" the 2D array making a new one where the columns are now rows:
function flipBoard(board) {
//perform transposition
return board[0].map((col, i) => board.map(row => row[i]));
}
//just to show off that it works
let exampleBoard = [
["a1", "b1", "c1"],
["a2", "b2", "c2"],
["a3", "b3", "c3"],
]
console.log(flipBoard(exampleBoard));
/* result:
[
["a1", "a2", "a3"]
["b1", "b2", "b3"]
["c1", "c2", "c3"]
]
*/
Thus the entire code needed to check if all columns contain correct values is to rotate the board and check every row (that was previously a column):
function areColumnsUnique(board) {
const flipped = flipBoard(board);
return areRowsUnique(flipped);
}
Check if each square contains unique values
All in all, the rows and columns were easy. They share most of the code, so it was a matter of finding how to link them. Where it becomes harder is the 3x3 squares. If we can extract each 3x3 square into a 9 element array, and collect each of those, we can re-use the previous logic again.
To do that, it's useful to think of the board in terms of sub-sections
║ ║ ║ ║
║ ║ ║ ║
║ A ║ B ║ C ║
║ ║ ║ ║
║ ║ ║ ║
+=======+=======+=======+=======+=======+=======+=======+=======+=======+===========
║ (0,0) | (1,0) | (2,0) ║ (3,0) | (4,0) | (5,0) ║ (6,0) | (7,0) | (8,0) ║
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
║ (0,1) | (1,1) | (2,1) ║ (3,1) | (4,1) | (5,1) ║ (6,1) | (7,1) | (8,1) ║ 1
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
║ (0,2) | (1,2) | (2,2) ║ (3,2) | (4,2) | (5,2) ║ (6,2) | (7,2) | (8,2) ║
+=======+=======+=======+=======+=======+=======+=======+=======+=======+===========
║ (0,3) | (1,3) | (2,3) ║ (3,3) | (4,3) | (5,3) ║ (6,3) | (7,3) | (8,3) ║
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
║ (0,4) | (1,4) | (2,4) ║ (3,4) | (4,4) | (5,4) ║ (6,4) | (7,4) | (8,4) ║ 2
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
║ (0,5) | (1,5) | (2,5) ║ (3,5) | (4,5) | (5,5) ║ (6,5) | (7,5) | (8,5) ║
+=======+=======+=======+=======+=======+=======+=======+=======+=======+===========
║ (0,6) | (1,6) | (2,6) ║ (3,6) | (4,6) | (5,6) ║ (6,6) | (7,6) | (8,6) ║
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
║ (0,7) | (1,7) | (2,7) ║ (3,7) | (4,7) | (5,7) ║ (6,7) | (7,7) | (8,7) ║ 3
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
║ (0,8) | (1,8) | (2,8) ║ (3,8) | (4,8) | (5,8) ║ (6,8) | (7,8) | (8,8) ║
+=======+=======+=======+=======+=======+=======+=======+=======+=======+===========
This is a decent way to visualise it. The content of each cell specifies its coordinates and the double lines denote each of the 3x3 squares that need to be checked. So we need to extract each into an array To do so, we can employ some mathematics. But first, let's start with what we are trying to do - by examining the position of each cell we see that the top left with coordinates (0, 0) belongs to A1. However, (3, 3) belongs to B2, while (7, 6) in C3.
Since we want these extracted into one array each, let's re-label each square by just giving it a number
+-------+-------+-------+
| | | |
| 0 | 1 | 2 |
| | | |
+-------+-------+-------+
| | | |
| 3 | 4 | 5 |
| | | |
+-------+-------+-------+
| | | |
| 6 | 7 | 8 |
| | | |
+-------+-------+-------+
comparing the two representations that both show the squares, we can see that each coordinate falls into one of the numbered squares and we can determine which one by looking at the coordinates.
- (0, 0) => 0 (A1)
- (3, 3) => 4 (B1)
- (7, 6) => 8 (C3)
So even more general, we can derive the formula to find the index of the square a cell belongs to:(rowIndex / 3) * 3 + (columnIndex / 3). We need to round down during division (in essence, performing integer division) in order to get an integer. We can plug our previous numbers in the formula we can verify it's correct:
- (0, 0) => (0 / 3) * 3 + (0 / 3) = 0 * 3 + 0 = 0 + 0 = 0 (A1)
- (3, 3) => (3 / 3) * 3 + (3 / 3) = 1 * 3 + 1 = 3 + 1 = 4 (B1)
- (7, 6) => (7 / 3) * 3 + (6 / 3) = 2 * 3 + 2 = 6 + 2 = 8 (C3)
With all of this said, we finally know what to do - we can walk the entire board and based on the coordinates of each cell, put it in an array that corresponds to its square. This leads us to the following code:
function extractSquares(board) {
//nine arrays for each square
const squares = [
[], [], [], [], [], [], [], [], []
];
board.forEach((row, rowIndex) => {
row.forEach((cell, columnIndex) => {
const squareIndex = (Math.floor(rowIndex / 3) * 3) + Math.floor(columnIndex / 3);
squares[squareIndex].push(cell);
})
});
return squares;
}
Thus we can finally define the last check:
function areSquaresUnique(board) {
const squares = extractSquares(board);
return areRowsUnique(squares);
}
Complete solution
Putting it all together, we get the following:
function isValid(board){
if (!isBoardContentValid(board)) {
return false;
}
if (!areRowsUnique(board)) {
return false;
}
if (!areColumnsUnique(board)) {
return false;
}
if(!areSquaresUnique(board)) {
return false;
}
return true;
}
function isCellContentValid(value) {
return typeof value === "number" && value >= 1 && value <= 9;
}
function isBoardContentValid(board) {
return board.every(isRowContentValid);
}
function isRowContentValid(row) {
return row.every(isCellContentValid);
}
function isArrayUnique(array) {
const set = new Set(array);
return set.size === array.length;
}
function areRowsUnique(board) {
return board.every(isArrayUnique);
}
function flipBoard(board) {
return board[0].map((col, i) => board.map(row => row[i]))
}
function areColumnsUnique(board) {
const flipped = flipBoard(board);
return areRowsUnique(flipped);
}
function extractSquares(board) {
//nine arrays for each square
const squares = [
[], [], [], [], [], [], [], [], []
];
board.forEach((row, rowIndex) => {
row.forEach((cell, columnIndex) => {
const squareIndex = (Math.floor(rowIndex / 3) * 3) + Math.floor(columnIndex / 3);
squares[squareIndex].push(cell);
})
});
return squares;
}
function areSquaresUnique(board) {
const squares = extractSquares(board);
return areRowsUnique(squares);
}
///////////////////////////////////
const invalidBoard = [
[ 5, 3, 4, 6, 7, 9, 8, 1, 2 ],
[ 6, 7, 2, 1, 9, 5, 3, 4, 7 ],
[ 6, 9, 8, 3, 4, 2, 7, 6, 5 ],
[ 8, 5, 9, 7, 6, 1, 4, 2, 1 ],
[ 4, 2, 6, 8, 5, 3, 7, 8, 1 ],
[ 7, 1, 3, 9, 2, 4, 8, 5, 6 ],
[ 9, 6, 1, 5, 3, 7, 2, 8, 4 ],
[ 2, 8, 7, 4, 1, 9, 6, 3, 5 ],
[ 3, 4, 5, 2, 8, 6, 1, 8, 8 ],
];
const validBoard = [
[ 5, 3, 4, 6, 7, 8, 9, 1, 2 ],
[ 6, 7, 2, 1, 9, 5, 3, 4, 8 ],
[ 1, 9, 8, 3, 4, 2, 5, 6, 7 ],
[ 8, 5, 9, 7, 6, 1, 4, 2, 3 ],
[ 4, 2, 6, 8, 5, 3, 7, 9, 1 ],
[ 7, 1, 3, 9, 2, 4, 8, 5, 6 ],
[ 9, 6, 1, 5, 3, 7, 2, 8, 4 ],
[ 2, 8, 7, 4, 1, 9, 6, 3, 5 ],
[ 3, 4, 5, 2, 8, 6, 1, 7, 9 ],
];
console.log(isValid(validBoard)); // => true
console.log(isValid(invalidBoard)); // => false
