sudoku2.js

Sudoku is a number-placement puzzle. The objective is to fill a 9 × 9 grid with numbers in such a way that each column, each row, and each of the nine 3 × 3sub-grids that compose the grid all contain all of the numbers from 1 to 9 one time.
Implement an algorithm that will check whether the given grid of numbers represents a valid Sudoku puzzle according to the layout rules described above. Note that the puzzle represented by grid does not have to be solvable. — from CodeFights

I have my little test environment setup now so I was able to get started on this (locally) really quickly. Setting up a dev environment is significantly easier these days! All the tools available reminded me that it’s fun to try new languages/frameworks/stacks/etc. when you can just jump right in!

I like playing Sudoku; writing this simple validator was a fun quick challenge. My basic idea was check rows, columns, then squares. Rows and columns are easy but the squares… I knew there had to be a tricky way to reach the 9 slots for each square and I really had to force myself not to dwell on that — just solve it and then optimize later. I had to put the problem down several times because of interruptions but also just to refocus and remind myself not to get discouraged when I don’t see the tricky solution immediately…

function sudoku2(grid) {
var collapsed = [[], [], []];
    //Guaranteed to be 9x9. Guaranteed to have '.' or 1-9
for(var x = 0; x < grid.length; x++) {
//Check row
//grid[x][0-8]
for(var i = 1; i <= 9; i++) {
if(!isValid(i, grid[x].join(""))) {
return false;
}
}
        //Check column
//grid[0-8][x]
var column = [];
for(var y = 0; y < grid.length; y++) {
column.push(grid[y][x]);
collapsed[(x % 3)].push(grid[x][y]);
}

for(var i = 1; i <= 9; i++) {
if(!isValid(i, column.join(""))) {
return false;
}
}
}

//Check squares
// grid[0-2][0-2], grid[0-2][3-5], grid[0-2][6-8]
var squares = [[], [], [], [], [], [], [], [], []];
var k = 0;
while(k < 9) {
for(var j = 0; j < 3; j++) {
squares[k].push(collapsed[j].shift());
squares[k].push(collapsed[j].shift());
squares[k].push(collapsed[j].shift());
}
        for(var i = 1; i <= 9; i++) {
if(!isValid(i, squares[k].join(""))) {
return false;
}
}
       k++;
}
   return true;
}
function isValid(i, a) {
// No number is repeated
var first = a.indexOf(i);
if(first >= 0) {
if(a.indexOf(i, first + 1) >= 0) {
return false;
}
}
return true;
}

I traced through and verified with the couple of local tests that I had and shoved it through CodeFights… it passed and I’m moving on! I have some repeated code, I think I could make it faster, it’s not pretty but… I want to get quicker at putting together the first solution, that’s what I’m trying to practice for interviewing. I’m also working on talking about the problems, recalling terminology, calculating Big O… and that’s why I’m putting the words down here! Big O(n) — the worst case for my solution is you check each item 3 times (as a column, row, and square) plus the work to make the columns and squares but the grid is always 9x9.

I would like to optimize this solution but I don’t think it’s helpful to obsess over it — I want to spend my time on a variety of problems. I’m keeping this in the back of my mind, though! On GitHub.

After my solution passes their tests, I like to look at the other solutions. I was surprised that CodeFights supports the arrows but I was disappointed to see this in the top-rated solution:

This is totally objective, professional, and truly necessary. Please go give this dude another thumbs-up… Does being rude to strangers make you feel good about yourself? This is the kind of culture and attitude that I’d like to avoid. As an interviewer, I ask simple questions to help me evaluate your general attitude and social skills because those things are actually important too. 👍