2
\$\begingroup\$

A valid Sudoku board has the following properties

  • The board must be square (n-by-n). Let m = sqrt(n)
  • All rows must contain the numbers 1-n
  • All columns must contain the numbers 1-n
  • All nine m-by-m blocks must contain all numbers 1-n

The following MATLAB code verifies a Sudoku board of arbitrary sizes (where n is a square number):

function correct_board = sudoku_checker(board)

correct_board = true;
[rows, cols] = size(board);
correct_size = (rows == cols) && mod(sqrt(rows),1) == 0;
if correct_size == false
    disp('The board is not square')
    correct_board = false
else
    disp('The board is square')
    for ii = 1:rows
        if ~(isequal(unique(board(:,ii)), (1:rows)') && isequal(unique(board(ii,:)), (1:rows)))
            disp(['Numbers ' num2str(1) '-' num2str(rows) ' are not present in all rows or columns'])
            correct_board = false;
            return
        end
    end
    disp(['Numbers ' num2str(1), '-' num2str(rows) ' are present in all rows and columns'])

    cell_blocks = mat2cell(board, repmat(sqrt(rows),sqrt(rows),1),repmat(sqrt(rows),sqrt(rows),1));
    blocks_ok = all(arrayfun(@(x) isequal(unique(cell_blocks{x}),(1:rows)'), 1:rows));
    if blocks_ok == true
        disp(['All blocks are OK'])
    else
        disp(['All blocks are not OK'])
        correct_board = false;
        return;
    end
    disp('Board is OK')
end
end

A valid board will give the following output:

sudoku_checker(board)
The board is square
Numbers 1-9 are present in all rows and columns
All blocks are OK
Board is OK

An incorrect board will give an output like this (dependent on which condition that fails):

sudoku_checker(board)
The board is square
Numbers 1-4 are present in all rows and columns
All blocks are not OK

I'm wondering if there are ways to improve this code. I'm looking for improvements in performance and algorithm, as well as improvement in coding style etc.

Can I simplify any expressions? Remove some boolean operators?

\$\endgroup\$
  • \$\begingroup\$ FWIW, I've seen 6x6 Sudoku boards. The blocks are 2x3. \$\endgroup\$ – Peter Taylor Jun 22 '16 at 11:09
  • \$\begingroup\$ Yea, there are all kinds of more complex Sudoku boards out there. One could try to solve them all, but you got to start somewhere. It's a good idea to keep modularity in mind if you intend to solve the complex ones later as well though. \$\endgroup\$ – Mast Jun 22 '16 at 11:20
1
\$\begingroup\$

A few general things first:

' is the conjugate transpose, not the transpose. These are the same for real values, but will behave differently when you have complex values. To avoid confusion, it is recommended that you always use .' when transposing a matrix, even if it's real.


You're using both disp('text') and disp('[text]'). The first one works for plain strings, while the other must be used when concatenating strings and numbers. I suggest you either use brackets on all calls to disp, or skip the brackets for all calls to disp where the string is plain text. Consistency is always nice.


Variable names:

The variable names are well chosen and descriptive. One minor comment is that you're using correct_size and correct_board, but blocks_ok. correct_blocks is probably a better word here, to keep consistency.


Frequently used variables:

There are a few variables that are used over and over again. You should declare the following variables outside the loop:

sq_rows = sqrt(rows); 
values= 1:rows;

Avoid the loop and calls to unique by sorting the board by rows and columns:

You can avoid the loops by sorting all columns of the regular board, and the board when it's transposed, instead of checking for unique values.

isequal(sort(board), sort(board.'), repmat(values.',1, rows))

repmat(values.',1,rows) produces a matrix looking like this:

1     1     1     1
2     2     2     2
3     3     3     3
4     4     4     4

Alternatives to repmat(sqrt(rows),sqrt(rows),1):

Using mat2cell to create cell_blocks is good, but the expression can be simplifed using the new pre-defined variables. There are some alternatives to repmat(sqrt(rows),sqrt(rows),1) that are more readable, such as:

ones(sq_rows,1) * sq_rows;
zeros(sq_rows,1) + sq_rows;

repelem is an option if you're using MATLAB version R2015a or newer.


Use cellfun when you're working with cells, and arrayfun when you are working with other "stuff".

Since cell_blocks is a cell array, you can use cellfun:

all(cellfun(@(x) isequal(unique(x),values.'), cell_blocks))

Simplifying the disp-calls:

You know that the first number in the sequence is 1, so you can simplify the two disp-calls in the middle:

disp(['Numbers 1-' num2str(rows) ' are present in all rows and columns'])

I believe you're missing a break after checking the size of the board (first if).


Comments!

I suggest you use a lot more comments! Explain what the different parts of your code do.

\$\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.