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

• Captain Man: A quick comment because I think it's too short to be an answer. I don't believe comments like in this line end #end of Sudoku are needed. As long as everything is properly indented you shouldn't need stuff like that. I don't know Ruby though, so maybe it's a standard there.
• BenKoshy: you may find this helpful - other data structures possible to represent the sudoku grid: stackoverflow.com/questions/1391381/… - btw this looks like a very interesting problem

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).

• BenKoshy: quite simply brilliant and very readable. am envious of your application of matrix and enumerable methods to make it look so easy. i do not follow what the board.squares method does - btw should there be a third element in each array? thx for your post. i don't think i can emulate this
• Mark Thomas: @BKSpurgeon Thanks for the kind words. I wasn't familiar with the minor method before answering this question, but figured there had to be a way to specify a submatrix. According to the docs, for each submatrix you can either specify four params (start_row, nrows, start_col, ncols) or two ranges (row_start..row_end, col_start..col_end). I chose the latter.