Checking if a matrix is a Sudoku with one loop and none

In this post I will share a little snippet I wrote for my programming class some time ago. We were assigned to code a Sudoku resolver using MATLAB. If you have working with this programming tool before you may agree with me that is an excellent language for the task mostly because his syntax for expressing sub matrixs. The intention was to use some simple math towards removing lines of code whiteout affecting performance.

I will not discuss the resolver implementation, just only the routine that check if full matrix of size 9×9 is a Sudoku, if you want to see the code of the resolver follow this link.

The conditions needed for a given matrix to be a Sudoku is that in every row, column and 3×3 block must exist all the natural numbers from 1 to 9 without repetitions, viz. there can’t be any repetition on each of the 27 vectors we can form. An elegant way of checking this condition is using a property of the powers of two, that states that the exponents involved on a sum of two powers uniquely identifies the total sum. That is that in order to check if a nine length vector v is a valid Sudoku row the following expression must comply:

2^v[1] + 2^v[2] + 2^v[3] + 2^v[4] + 2^v[5] + 2^v[6] + 2^v[7] + 2^v[8] + 2^v[9] == 1022

Or in another words that the total sum of the powers divided by 1022 is 1.

(2^v[1] + 2^v[2] + 2^v[3] + 2^v[4] + 2^v[5] + 2^v[6] + 2^v[7] + 2^v[8] + 2^v[9] / 1022) == 1

On the other hand if we group each of the 27 vectors in terns of the form (rows, columns, cells) results that we get a set of nine tern identified by a number from 1 to 9. This enumeration just guide us to use only one loop to check is if the above condition holds for each components of a tern made by a row, column and block. Easily we can denote the above condition as C and the following expression will be sufficient to test if the nth tern is made by valid Sudoku vectors:

C(Row[n]) + C(Column[n]) + C(Block[n]) = 3 

Any other value will implies that the one of the vectors doesn’t have the first nine natural numbers and then the matrix is not a Sudoku. Taking this ideas to coding a MATLAB version can be code in the following way:

function R = IsSudoku(SU) 
f = @(x) sum(sum(power(2,min(10,max(0,x))))) / 1022; 
R = 1; 
for n = 1:9 
    r = sum([1 2 3 4 4 5 5 6 6 7 7 7 8 8 8 9 9 9] == n); 
    c = sum([1 2 2 3 3 3 4 5 5 6 6 6 7 8 8 9 9 9] == n); 
    if sum([f(SU(n,:)) f(SU(:,n)) f(SU(3*r-2:3*r,3*c-2:3*c))]) ~= 3 
        R = 0; return; 
    end 
end 

You can say it uses just one for loop. The code is very simple, being the more difficult to read the parts that compute the nth block boundaries, a proceeding for obtained that formula is explained in the following steps:

Step 1

(1) Lets assign an index for each block and tracks the boundaries.

sudoku2image 

(2) Write the start positions for each block compromising the row and the column (first column in the image). Think in a formula to build a mapping between the block and the beginning positions, no IF statements are allowed =). We can create simple integer mappings on MATLAB by using a vector, the sum function and the == operator as in the following example that is a very limited mapping to the Fibonacci sequence:

@(x) sum ([1 2 2 3 3 3 4 4 4 4 5 5 5 5 5] == x)

The == operator applied to a vector and the x parameter will produce that contains 0 for the positions in witch the element is not the same as x and 1 in the opposites cases, the sum function makes the rest as you may infer. If we follow this approach we will end with a very large vector both for the rows and columns. The method for using an small vector is to introduce a helper function that reduces the value and his inverse will transform back to the correct start positions. In the second column of the image you see the result of this approach using the linear function x = 3k – 2 and his inverse k = (x + 2)/3. Now the vectors for both column and rows can be simplified for the ones in the MATLAB code, notice that before computing the sub matrix we must transform back the reduced values.

An implementation entirely functional (no state, no loops) with the F# language can be coded using the same ideas but changing the remaining loop for a sequence expression and a consolidation operator:

let isSudoku (m : FMatrix) =
    requires (m.Dimension = (9,9)) "Not a 9x9 matrix"
    let f (a : FMatrix) = (a.Items |> Seq.map (fun x -> Math.Pow(2.0,Math.Min(10,Math.Max(0,x)))) 
                               |> Seq.sum) / 1022.0
    let pos arr n = arr |> Array.filter ((=) n) |> Array.length
    let h n = 
        let r,c = pos [|1;2;3;4;4;5;5;6;6;7;7;7;8;8;8;9;9;9|] n, 
                  pos [|1;2;2;3;3;3;4;5;5;6;6;6;7;8;8;9;9;9|] n
        f(m.[n .. n, *]) + f(m.[*, n .. n]) + f(m.[3 * r - 2 .. 3 * r, 3 * c - 2 .. 3 * c])
    seq {1..9} |> Seq.map h |> Seq.forall ((=) 3.0)

They data type FMatrix can be seeing in this page, this type supports the extraction of sub matrix using the F# array slice notation which is similar to the one proposed by MATLAB. In this version of the routine in the sake of use zero loops we recall on sequence expressions ({1 .. 9}) as an input sequence for a map (Seq.map) operation that will be later processed by the forall operator to check if the conditions comply.

The performance of both codes are good, and thanks for the min(10,max(0,x)) there is no risk for evaluating a huge power of 2. In the MATLAB specific case Im not 100% sure there is no internally any loop working while retrieving a sub matrix, for F# we can check that even within the chained iterations there is no use of mutable state (and so no loops).

hope you like it

-horacio

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s