1
\$\begingroup\$

Problem explanation

I've written a function to validate sudoku. Given a two-dimensional 9×9 array of numbers:

  • Each row should have each of the numbers 1–9 exactly once.
  • Each column should have each of the numbers 1–9 exactly once.
  • Each square should have each of the numbers 1–9 exactly once.
 · · · | · · · | · · · 
 · · · | · · · | · · · 
 · · · | · · · | · · · 
-------+-------+-------
 · · · | · · · | · · · 
 · · · | · · · | · · · 
 · · · | · · · | · · · 
-------+-------+-------
 · · · | · · · | · · · 
 · · · | · · · | · · · 
 · · · | · · · | · · · 

Queries

  • Is there a better way to approach the problem than creating arrays for columns and squares and validating those individually?
  • Is there a better way of creating the column arrays than running a neste loop and using the loop indices as co-ordinates?
  • Is there a better way of creating the square arrays than using the squareAnchors and running a nested loop, using the indices as offsets?

If they are more succinct/readable, functional approaches are also welcome.

Code

function isValidSudoku(sudoku: sudoku): boolean {
    const rows = sudoku;
    const columns = [];
    const squares = [];

    for (let r = 0; r < 9; r++) {
        const column = [];

        for (let c = 0; c < 9; c++) {
            column.push(rows[c][r]);
        }

        columns.push(column);
    }

    // Co-ordinates of top-left elements of squares
    const squareAnchors = [
        [0, 0], [3, 0], [6, 0],
        [0, 3], [3, 3], [6, 3],
        [0, 6], [3, 6], [6, 6]
    ];

    for (const anchor of squareAnchors) {
        const square = [];
        const [x, y] = anchor;

        for (let offsetX = 0; offsetX < 3; offsetX++) {
            for (let offsetY = 0; offsetY < 3; offsetY++) {
                square.push(rows[x + offsetX][y + offsetY]);
            }
        }

        squares.push(square);
    }

    const rowsValid = rows.every(isArrayValid);
    const columnsValid = columns.every(isArrayValid);
    const squaresValid = squares.every(isArrayValid);

    if (rowsValid && columnsValid && squaresValid) {
        return true;
    }

    return false;
}

isArrayValid:

function isArrayValid(array: row): boolean {
    const oneThroughNine = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    array = array.sort();

    for (let i = 0; i < 9; i++) {
        if (array[i] !== oneThroughNine[i]) return false;
    }

    return true;
}

types/sudoku.ts:

import row from './row';

type sudoku = [
    row, row, row, row, row, row, row, row, row
];

export default sudoku;

types/row.ts:

type row = [number, number, number, number, number, number, number, number, number];

export default row;

Examples

const validSudoku: sudoku = [
    [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]
];
const invalidSudoku: sudoku = [
    [5, 3, 4,  6, 7, 8,  9, 1, 2],
    [6, 7, 2,  1, 9, 0,  3, 4, 9],
    [1, 0, 0,  3, 4, 2,  5, 6, 0],

    [8, 5, 9,  7, 6, 1,  0, 2, 0],
    [4, 2, 6,  8, 5, 3,  7, 9, 1],
    [7, 1, 3,  9, 2, 4,  8, 5, 6],

    [9, 0, 1,  5, 3, 7,  2, 1, 4],
    [2, 8, 7,  4, 1, 9,  6, 3, 5],
    [3, 0, 0,  4, 8, 1,  1, 7, 9]
];
\$\endgroup\$
2
\$\begingroup\$

Inefficient

Your code has two major inefficiencies due to poor logic order and design

Unneeded sort

The sort in isArrayValid will be rather slow and not needed if you write to the oneThroughNine to mark numbers found. Before you mark the number found check if its been marked, if so then the game is invalid.

function isArrayValid(array: row): boolean {
    const mustInclude = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; // except for 0

    for (const val of array) {
        if (!mustInclude[val]) { return false }
        mustInclude[val] = 0; // mark the position as found
    }
    return true;    
}

Processing when the result is known

At the bottom of the main function you check rows, columns, and squares. The problem is that if one of the rows is invalid you will still end up checking the columns and squares even though you know that the game is invalid.

If you place the rows, columns, and squares in an array and test it with Array.every you can exit on the first bad set.

return [rows, columns, squares].every(set => set.every(isArrayValid));

However...

Don't create data before you need it,

You create and hold the columns and square before you check rows, they may not be needed as rows may find an invalid game.

Nor do you need to keep each column and square. Check them as you create them, no point creating 9 columns if the first of them is invalid. Same with the squares

I also changed the name of isArrayValid to isInvalid to avoid having to use ! each time the set is tested

function isValidSudoku(sudoku: sudoku): boolean {
    if (sudoku.some(isInvalid)) { return false }

    for (let r = 0; r < 9; r++) {
        const column = [];
        for (let c = 0; c < 9; c++) { column.push(sudoku[c][r]) }
        if (isInvalid(column)) { return false }

    }
    const squareAnchors = [[0, 0], [3, 0], [6, 0], [0, 3], [3, 3], [6, 3], [0, 6], [3, 6], [6, 6]];

    for (const [x, y] of squareAnchors) {
        const square = [];
        for (let ix = 0; ix < 3; ix++) {
            const row = sudoku[x + ix];
            for (let iy = 0; iy < 3; iy++) { square.push(row[y + iy]) }
        }
        if (isInvalid(square)) { return false }
    }
    return true;
}
function isInvalid(set: row): boolean {
    const mustInclude = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; // except for 0

    for (const val of set) {
        if (!mustInclude[val]) { return true }
        mustInclude[val] = 0; // mark the position as found
    }
    return false;    
}   

There are many other things that could be done to improve the code like

  • Checking each value as you create the column and square arrays.
  • Using a bitfield rather than an array to mark of included values.
  • Have the input array as a single dimension (flat) so you don`t have to do all the double indexing and nested loops.

But you would only do that if you had millions of games to check and needed every ounce of performance. The further optimizations are only going to give you a few percentage point improvement.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.