Validate if Sudoku is correct

Question

Given a two-dimensional array, Sudoku class can create NxN Sudoku where N = size^2. Assume that the user gives only valid NxN matrixes for the constructor.

• Method is_correct? should return true if Sudoku is solved
• Method print / to_s should write on screen Sudoku.
• Method set should set specified position in Sudoku for a given value.

Is there any solution that does not involve so many iterations to validate? Is it good to override initialize method? Will this validation pass through every Sudoku? How can I improve my code to be more readable?

sudoku.rb

class Sudoku

attr_accessor :board, :size

def initialize (starting_board, size = 3)
    #default size is 3
    @board = starting_board
    @size = size
end

def is_correct?
    #valid all not null, then valid rows columns and squares sizeXsize
    valid_not_null? && valid_rows? && valid_columns? && valid_squares?
end 

def set (x, y , value)
    #set value of sudoku as something (no validation of value)
    if( x.between?(1, 9) && y.between?(1, 9))
        @board[y - 1 ][x - 1] = value
    end
end



def to_s    
    #o = 1 2 3
    #    4 5 6
    #    7 8 9

    #o | o | o
    #- - - - - 
    #o | o | o
    #- - - - -
    #o | o | o
    nums  = Array.new(@size)
    rows = Array.new(@size)
    multi_rows = Array.new(@size)
    sqr_multi_rows = Array.new(@size)
    for s in 0..@size -1
        for k in 0..@size -1 
            for j in 0..@size - 1
                # set 1 2 3 | 3 4 5 | 6 7 8 
                for i in 0..@size -1
                    # set 1 2 3 
                    nums[i] = ( board[3*s+ k ][3*j + i] || " " )
                end
                rows[j] = (nums.join(" "))
            end
            multi_rows[k] = (rows.join(" | "))
        end
        sqr_multi_rows[s] = multi_rows.join("\n")
    end
    line = "- " * (@size**2 + @size - 1)
    sqr_multi_rows.join("\n#{line}\n")
    #brings everything together
end
alias print to_s

    private

        def valid_rows?
            row =  0
            valid = true
            mask = Array.new(@size ** 2) {|e| e = e+1}

            while (valid && row < @size **2 )

                current_row = @board[row]
                #check if contains all from 1 to 9
                valid =  mask == current_row.sort
                row += 1
            end

            valid
        end

        def valid_columns?
            column = row=  0
            valid = true
            mask = Array.new(@size ** 2) {|e| e = e+1}
            current_col = Array.new(@size ** 2)

            while (valid && column < @size ** 2)
                while (valid && row < @size ** 2 )

                    current_col[row] = @board[column][row]
                    row += 1
                end
                #create col
                #check if contains all from 1 to 9
                valid =  mask == current_col.sort
                column += 1

            end

            valid
        end

        def valid_squares?
            current_sqr = Array.new(@size**2)
            mask = Array.new(@size ** 2) {|e| e = e+1}

            valid = true
                mask = Array.new(@size ** 2) {|e| e = e+1}
                i = 0
            for col in 0...@size
                for row in 0...@size
                    for j in 0...@size
                        for i in 0...@size
                            current_sqr[@size*i+j] = @board[3*col + j][3*row + i]
                        end
                    end
                    #create square
                    #check if contains all from 1 to 9
                    valid =  mask == current_sqr.sort
                end                 
            end
            valid
        end

        def valid_not_null?
            valid = true
            i = j = 0
            #for each element check if is not null
            while valid && j < @size
                while valid && i <@size
                    valid = valid != nil ?  true : false
                    i+= 1
                end
                j+=1
            end
            valid
        end     
end #end of Sudoku

test_sudoku.rb

require "test/unit"
require_relative "sudoku.rb"

class TestSudoku <Test::Unit::TestCase
def setup
    @goodSudoku1 = Sudoku.new([
        [7,8,4,  1,5,9,  3,2,6],
        [5,3,9,  6,7,2,  8,4,1],
        [6,1,2,  4,3,8,  7,5,9],

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

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

    @goodSudoku2 = Sudoku.new([
        [2,9,5, 7,4,3, 8,6,1],
        [4,3,1, 8,6,5, 9,2,7],
        [8,7,6, 1,9,2, 5,4,3],

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

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

    @badSudoku1 = Sudoku.new([
        [1,2,3, 4,5,6, 7,8,9],
        [1,2,3, 4,5,6, 7,8,9],
        [1,2,3, 4,5,6, 7,8,9],

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

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

    @badSudoku2 = Sudoku.new([
        [1,2,3, 4,5,6, 7,8,9],
        [2,3,4, 5,6,7, 8,9,1],
        [3,4,5, 6,7,8, 9,1,2],

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

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

def test_success

    assert_equal(@goodSudoku1.is_correct?, true)
    assert_equal(@goodSudoku2.is_correct?, true)
end

def test_failure
    assert_equal(@badSudoku1.is_correct?, false)
    assert_equal(@badSudoku2.is_correct?, false)
end

end

Answer 1

A couple comments:

Your is_correct? method is good as it expresses the logic and delegates the details to helper methods. (I wouldn't name it with the prefix is_ because that's not a ruby convention, but I realize you were given the test case so you have no choice.). The only thing that strikes me as a little odd about it is the valid_not_null? method. It shouldn't be necessary: if you check for valid rows, valid columns, and valid sub-squares, then there will be no nulls.

Now for the bad: Notice how you are creating new arrays everywhere? Your to_s method is creating several new arrays. Your validation methods each create new arrays. This is lots of extra code and a sign that you haven't properly modeled the "board". In fact, I think you're relying completely on the input format, when you probably should have an internal representation that makes everything else easier. One way to do that is to have a separate class representing the board so you can ask it to return its rows, e.g. board.rows, etc. If you were going to extend this Sudoku class to do anything else (e.g. generate, play, or solve puzzles) then I would definitely recommend splitting into multiple classes to avoid complexity. In this case, you can probably work within this single class, but I'd add helper methods like .rows and .columns etc.

By the way, it is convention to indent Ruby code 2 spaces, no tabs. But the main thing that stands out is that your methods are very long, partly due to the problems I mentioned above. It's best to try to keep them short, no more than 5 lines. How can this be accomplished? What I like to do is write code that assumes the use of other classes that I wish existed, then I write those classes. I'll provide an example. Here's a refactoring of your code that depends on a Board class, not yet written:

sudoku.rb

require './board.rb'

class Sudoku
  attr_accessor :board

  def initialize (board_spec)
    @board = Board.new(board_spec)
  end

  def is_correct?
    valid_rows? && valid_columns? && valid_squares?
  end

  def valid_rows?
    #check that the digits, when sorted, are 1 through 9
    board.rows.all? {|r| r.sort == (1..9).to_a}
  end

  def valid_columns?
    board.columns.all? {|c| c.sort == (1..9).to_a}
  end

  def valid_squares?
    board.squares.all? {|s| s.sort == (1..9).to_a}
  end
end

That simplifies things greatly, but it pushes all the complexity to the Board class, right? Those long methods have to be somewhere, right? As it turns out, you can keep applying this method until all your code is short. The Rails codebase is an amazing example, check it out sometime.

Let's implement a Board class that has the rows, columns, and squares methods. As I was doing this I realized we can use Matrix which has a way to retrieve columns (though you can also use transpose on an AoA) and a way to retrieve sub-matrices to get the 3x3 squares.

board.rb

require 'matrix'

class Board
  attr_accessor :board

  def initialize(board_spec)
    @board = Matrix[*board_spec]
  end

  def rows
    @board.row_vectors
  end

  def columns
    @board.column_vectors
  end

  def squares
    # The `Matrix#minor` method extracts sub-matrices specified by
    # index ranges. These are the 3x3 squares in Sudoku.
    [
      [0..2, 0..2], [3..5, 0..2], [6..8, 0..2],
      [0..2, 3..5], [3..5, 3..5], [6..8, 3..5],
      [0..2, 6..8], [3..5, 6..8], [6..8, 6..8]
    ].map {|sq| @board.minor(*sq)}
  end
end

So there you have it. This is a working implementation of a standard 9x9 board. I left as an exercise handling an nxn board and the to_s method on Board, but it should be simple to do (hint: use in_groups_of(n) which is a method on Array).