Sudoku Javascript
Silvana Fleischacker
I'm trying to write an algorithm that can solve sudoku. For now, my code works till supplyGrid is out of numbers. When it happens it should go back and try another number, right? To be honest I have no clue how to achive that.
I have used array.some which terminates the program as soon as the condition is not met and hence improves the performance. And no extra loop required to initialize 3*3 sub-matrix, I have done it in the some method only by checking if the matrix array already exists or not.
My wife has developed a passion for Sudoku. I do not share it, I've always thought that this is a problem for computers, not humans, so I've never tried to solve one by hand. However, even if it's a high school problem, I thought it'd be a cute little program to work on. This is the obligatory blog post about it.
You have to fill every empty cell with a non-zero digit [1..9], such that no digit appears twice on the same column, row, or within the same 3x3 square. Click any empty field to see a list of allowed digits.
It's a search problem, so the tool that comes to mind is backtracking. Some developers have an anxiety about this word, as if it's some kind of weird black magic, but really, it's pretty simple. I'll describe here my sudoku solver.
Since it has 81 cells, we'll keep it as an array with 81 digits (zero for empty cells). It will be convenient to access it both using an index 0..80, or as (row, column), so we'll have a couple of functions to convert between the two:
There are optimizations we could make (we could use a single loop, and we could skip converting between index/row,column with some clever tricks) but let's not bother. We better start working on the problem now, that is, let's write a function that figures out the solution for a given puzzle.
How does a human approach the problem? Intuitively, we look at the whole board and pick the cells where we have little choices. Ideally, if we can determine that only one value is possible, then we write it down and forget about it.
Maybe I'd stop here, but my wife, who actually solves sudoku with her brain, told me a little trick that I didn't consider (I probably would have thought about it, had I ever tried to solve sudoku by hand). Look at the board below and focus on the yellow cell. Click on it to see what my program thinks are the available moves.
You see, it claims that the allowed digits for that field are 2, 4, 5, 8, 9, and that's correct by the rules, but now if you look at the pink fields, you can see that 8 is not allowed on the 4th and 6th columns, nor on the 3rd row, because an 8 is already there. And still we know that the top-middle 3x3 square must contain an 8, and this leaves the yellow cell as the only option; clearly we have an unique choice there, we can fill it immediately and there's no need to try 2, 4, 5 or 9.
Implementing this new optimization is not hard and makes a new world of difference, because it applies not only to the initial configuration but also after every subsequent move that the algorithm tries. Check the new numbers:
The new unique function checks for uniqueness not only within the 3x3 block, but also on the whole row and column, which again drastically reduces the search tree. As for the engineering improvements: instead of storing digits as decimals, they are now bit-coded (each digit's corresponding bit is set). This allows us to use bitwise operations to detect available choices (getChoices was renamed getMoves), which turns out to be much faster. There are other improvements as well, but this post is a bit too long already, feel free to check the code.
A favorite CodeWars challenge of mine is the ever-wonderful "check my sudoku" puzzle. It starts with a large array of arrays representing a completed Sudoku puzzle. You need to function that checks if it's correct or not. It's complex yet understandable and requires a good amount of creativity.
For a while, I had no idea how to approach it. There were so many problems and so many ways to tackle them. So I finally settled on something I'd learned more recently - functional JavaScript!A while back I explained functional programming with angels, mutants, and farmhands. I recommend reading that first, but the short version defines functional programming as:
I followed these rules as much as possible for my solution. My final answer was longer and more robust, but easier to read and manage. That's a worthy trade-off since it most benefits fellow humans reading the code.
First, how does one see that Sudoku is valid? The core of any Sudoku problem is having the numbers 1-9 in all the right places - rows, columns, and the 3x3 squares. This puzzle gives a massive array of number arrays, and we need to navigate them and check their numbers.
Now I'm making progress! Writing a function to check numbers isn't too tough. But the data I get may not be easy to check as a row, column, or square. At the start, it's a big array of arrays. I'll likely need to rearrange the data a bit before doing a check. So the three steps to check data each need an extra one.
The function should take an array and ask "does this array use the numbers 1-9 once?" A quick way to compare simple arrays is to sort them, convert them to a string, and compare with ===. One array is an argument passed to the function. I hardcoded the other with the numbers one through nine. The result is simple and sticks to functional programming rules - pure, declarative, and gluten-free.
Functional JavaScript led me to a helpful array method called every(). It lets you run through each item in an array, and returns true only if each item returns true. This one method does exactly what I need. That means this function only needs to do one thing and can fit in one line.
Getting all the numbers in a column isn't done for me, but isn't too tricky either. In array terms, numbers from the same index of each row make up each column. Column one is the first number from each row, column two is the second from each, and so on. I need to gather these numbers for columns one through nine.
Let's think about this in JavaScript terms. If we define each array as row in a loop, column one would be row[0][0], row[1][0], row[2][0], and so on until row[8][0]. So the function first needs to loop through and gather data from each row.
When it comes to gathering data while looping, functional JavaScript has reduce! reduce is too vast to cover here, but what matters here is it gives you a variable that carries over in the loop. So you could make this variable an array, and add a value to it over each row number. Which I do in the below gatherColumn function.
In a nutshell reduce is saying it will start with an empty array (the [] at the end). It updates that array with whatever we want after each loop. I pick out the needed row number with row[columnNum] for each round. Then I use the ...total spread operator to add the current array. The result is it adds the new number to the list each time. The final result is all the numbers from a column.
With the column numbers gathered, I only need to run it for each row. That means getting the column numbers from indexes 0 to 8. Then I check them all against isSudokuArrayValid, which I can do in one line!
I wrote out the array of indexes, which is not too elegant but it works. Then I check the result of gatherColumn against isSudokuArrayValid. The resulting function does what I want, validating each Sudoku column.
This is the hardest check of all. Gathering numbers from grouped squares isn't a straightforward trick. Each square has a different collection of index values for rows and columns. Looping through them right takes some extra logic.
My approach here was, again, to tackle the smallest problem first and use it to handle larger ones. I didn't have a clear idea of how the final function would work at the start, but I figured it out as I went.
I started simple: get the indexes for each "square" on the board. Each number in a square has two indexes: the row index and the column index. So getting all the indexes for a square means getting nine pairs of indexes, one for each number.
Let's say the top-right square is "square one." The next one in the row is "square two," and it goes on until "square nine" on the bottom right. If I wanted all the indexes for square one, I'd need a function that returns the following array of arrays:
Now whether it's for rows or columns, I can use this to get the needed indexes for that group. That's nice and all, but useless without the related values. I wasn't even sure how I'd make use of this function. So I kept going by intuition for the next step.
Like with the row and column checks, I need to do some looping. But I've got two numbers to loop through, the row indexes and the column indexes, so it'll take two loops. For finding the values in square one, the two loops would go like this.
So it's two loops with one loop working inside the other. It took some brooding, trial and error, and prayer sessions at the Altar of JavaScript. But I got a working function for this, and I'll break it down step by step.
First, the function will need three values: the row group, the column group, and the board itself. The row and column groups correspond to the square setup. There are numbers between zero and two: square one is the first three rows and columns, so they'd be 0, 0. Square two is the first three rows and the second group of three columns, so they'd be 0, 1.
You may have read "numbers between zero and two" and recalled that getSquareIndexes function. Good catch, since that's what the numbers are for! This function uses each to get the needed indexes for the rows and columns.
With the needed indexes, I can now do my two loops: loop through the rows, and then loop through the columns in that row. I also need to declare an empty array I can push the values to as I find them.
c80f0f1006