1
\$\begingroup\$

I'm writing a Sudoku solver in Ruby to complete a coding challenge with the following restrictions.

Failing to follow the following restrictions will result in an invalid submission:

  • Do not create classes, you will only be creating (many) methods.
  • No instance variables and no globals, you will only use local variables.

To accomplish this, you will be writing methods that accept arguments as inputs and return useful values represnting their work. You should be writing many methods, and using them together to build up your solver.

The challenge gives my program the following board strings:

1) "1-58-2----9--764-52--4--819-19--73-6762-83-9-----61-5---76---3-43--2-5-16--3-89--"
2) "--5-3--819-285--6-6----4-5---74-283-34976---5--83--49-15--87--2-9----6---26-495-3"
3) "29-5----77-----4----4738-129-2--3-648---5--7-5---672--3-9--4--5----8-7---87--51-9"
4) "-8--2-----4-5--32--2-3-9-466---9---4---64-5-1134-5-7--36---4--24-723-6-----7--45-"
5) "6-873----2-----46-----6482--8---57-19--618--4-31----8-86-2---39-5----1--1--4562--"
6) "---6891--8------2915------84-3----5-2----5----9-24-8-1-847--91-5------6--6-41----"
7) "-3-5--8-45-42---1---8--9---79-8-61-3-----54---5------78-----7-2---7-46--61-3--5--"
8) "-96-4---11---6---45-481-39---795--43-3--8----4-5-23-18-1-63--59-59-7-83---359---7"
9) "----754----------8-8-19----3----1-6--------34----6817-2-4---6-39------2-53-2-----"
10) "3---------5-7-3--8----28-7-7------43-----------39-41-54--3--8--1---4----968---2--"
11) "3-26-9--55--73----------9-----94----------1-9----57-6---85----6--------3-19-82-4-"
12) "-2-5----48-5--------48-9-2------5-73-9-----6-25-9------3-6-18--------4-71----4-9-"
13) "--7--8------2---6-65--79----7----3-5-83---67-2-1----8----71--38-2---5------4--2--"
14) "----------2-65-------18--4--9----6-4-3---57-------------------73------9----------"
15) "---------------------------------------------------------------------------------"

Everything in my code works as expected. It solves all of the given puzzles except for 12, 14, and 15. These 3 take too long to run. My implementation uses backtracking depth first search in combination with some Sudoku logic. I'm looking for feedback on code readability, code smells, documentation, and anything I can do to make the code more performant. Thanks in advance!

# This program works with a matrix containing the possible input values,
# candidates, for every position on the board. It uses logic and guessing
# to elminate candidates from this matrix until there is a single candidate
# for every position, i.e., the board is solved.

# The term candidate refers to a possible valid input for a given position
# based on the current board state. The terms candidate and possibility are
# used interchangably.

# The term house refers to a particuar block, row, or column.

# poss = possibility (i.e. candidate)
# imposs = impossibilities (i.e. ruled out candidates)
###############################################################################



# Resources for explanations of implemented candidate elimination techniques.

# Naked Subsets: http://hodoku.sourceforge.net/en/tech_naked.php
# Nishio: https://www.sudokuoftheday.com/techniques/nishio/

###############################################################################

# These methods create and transform the data structures representing the board
###############################################################################

def board_string_to_array(board_string)
  i = 0
  board_array = []

  while i < 81
    board_array << board_string[i..(i + 8)].split('')
    i += 9
  end

  board_array
end

def board_poss_to_array(board_poss)
  board_array = Array.new(9) { Array.new(9, '-') }
  r = 0
  while r < 9
    c = 0
    while c < 9
      board_array[r][c] = board_poss[r][c][0] if board_poss[r][c].length == 1
      c += 1
    end
    r += 1
  end

  board_array
end

def to_board_array(board)
  if board.class == String
    board_string_to_array(board)
  elsif board.class == Array
    board_poss_to_array(board)
  end
end

def position_possibilities(board_array, r, c)
  val = board_array[r][c]

  return [val.to_i] unless val == '-'

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

  used_vals = (
    block(board_array, r, c) + row(board_array, r) + column(board_array, c)
  ).uniq

  (possibilities - used_vals)
end

def board_possibilities(board_array)
  board_array.map.with_index do |row, r|
    row.map.with_index do |_val, c|
      position_possibilities(board_array, r, c)
    end
  end
end

# These methods retrieve houses from data structures representing current
# values or candidates on the board, i.e., board_array or board_poss.
# Candidates are returned with their respective position as well.
############################################################################### 

def block(board, r, c)
  # finds starting indices for given position's block
  r += 1
  c += 1
  r_mod, c_mod = (r % 3), (c % 3)
  r_index = r_mod.zero? ? r - 3 : r - r_mod
  c_init = c_mod.zero? ? c - 3 : c - c_mod
  r_last, c_last = (r_index + 3), (c_init + 3)
  block_vals = []

  while r_index < r_last
     c_index = c_init
    while c_index < c_last
      val = board[r_index][c_index]
      if [String, Integer].include?(val.class)
        block_vals << val.to_i unless val == '-'
      elsif val.class == Array
        block_vals << [val, [r_index, c_index]]
      end
      c_index += 1
    end
    r_index += 1
  end

  block_vals
end

def row(board, r)
  row_vals = []
  c = 0

  while c < 9
    val = board[r][c]
    if [String, Integer].include?(val.class)
      row_vals << val.to_i unless val == '-'
    elsif val.class == Array
      row_vals << [val, [r, c]]
    end
    c += 1
  end

  row_vals
end

def column(board, c)
  column_vals = []
  r = 0

  while r < 9
    row = board[r]
    if [String, Integer].include?(row[c].class)
      column_vals << row[c].to_i unless row[c] == '-'
    elsif row[c].class == Array
      column_vals << [row[c], [r, c]]
    end
    r += 1
  end

  column_vals
end

# These methods perform candidate elmination techniques on board_poss.
###############################################################################

# Eliminates each position's candidates already found within its 
# containing houses.
def eliminate_used(board_poss)
  return board_poss if solved? to_board_array board_poss

  9.times do
    r = 0
    while r < 9
      c = 0
      while c < 9
        poss = board_poss[r][c]
        unless poss.length == 1
          c += 1
          next          
        end
        i = 0
        while i < 9
          board_poss[r][i] -= poss if board_poss[r][i].length > 1
          board_poss[i][c] -= poss if board_poss[i][c].length > 1
          i += 1
        end
        c += 1
      end
      r += 1
    end
  end

  board_poss
end

def naked_pair_elimination(board_poss)
  return board_poss if solved? to_board_array board_poss

  r = 0
  while r < 9
    c = 0
    while c < 9
      poss = board_poss[r][c]
      unless poss.length == 2
        c += 1
        next
      end
      houses = [
        row(board_poss, r),
        column(board_poss, c),
        block(board_poss, r, c)
      ]
      current_poss = [poss, [r, c]]

      houses.each do |house|
        matching_pair = (house - [current_poss]).select { |p| p[0] == poss }

        next if matching_pair.empty?
        house.each do |p|
          r_index = p[1][0]
          c_index = p[1][1]
          remaining_poss = board_poss[r_index][c_index] - poss

          unless (remaining_poss).empty?
            board_poss[r_index][c_index] = remaining_poss
          end
        end
      end
      c += 1
    end
    r += 1
  end

  board_poss
end

# These methods solve the board and validate the solution.
###############################################################################

# Checks if the matrix of candidates' state can lead to a valid solution
def valid?(board_poss)
  board_array = to_board_array(board_poss)

  (0..8).to_a.each do |i|
    row_vals = row(board_array, i)
    col_vals = column(board_array, i)

    row_duplicate = row_vals.length != row_vals.uniq.length
    col_duplicate = col_vals.length != col_vals.uniq.length

    row_contradiction = row(board_poss, i).any? do |poss|
      poss[0].length > 1 ? (poss[0] - row_vals).empty? : false
    end

    col_contradiction = column(board_poss, i).any? do |poss|
      poss[0].length > 1 ? (poss[0] - col_vals).empty? : false
    end

    if row_contradiction || col_contradiction || row_duplicate || col_duplicate
      return false
    end
  end

  [0, 3, 8].each do |r|
    [0, 3, 8].each do |c|
      block_vals = block(board_array, r, c)
      block_duplicate = block_vals.length != block_vals.uniq.length

      block_contradiction = block(board_poss, r, c).any? do |poss|
        poss[0].length > 1 ? (poss[0] - block_vals).empty? : false
      end

      return false if block_contradiction || block_duplicate
    end
  end

  true
end

def remove_board_imposs(board_poss)
  return board_poss unless valid?(board_poss)

  eliminate_used(board_poss)
  naked_pair_elimination(board_poss)
  eliminate_used(board_poss)

  board_poss
end

# Performs a brute force using a decision tree based on the
# Nishio guessing techniqe to find a solution.
def nishio(board_poss)
  board_array = to_board_array(board_poss)
  i = 2

  return board_poss if solved?(board_array)
  return nil unless valid?(board_poss)

  while i < 9
    r = 0
    while r < 9
      c = 0
      while c < 9
        poss = board_poss[r][c]
        unless poss.length == i
          c += 1
          next
        end

        poss.each do |val|
          working_board_poss = Marshal.load(Marshal.dump(board_poss))
          working_board_poss[r][c] = [val]

          remove_board_imposs(working_board_poss)
          # puts pretty_board to_board_array working_board_poss
          # p "-------------------------------------"
          solution = nishio(working_board_poss)

          return solution unless solution.nil?

          next
        end
        c += 1
      end
      r += 1
    end
    i += 1
  end

  nil
end

# Takes a board as a string in the format
# you see in the puzzle file. Returns
# something representing a board after
# your solver has tried to solve it.
# How you represent your board is up to you!
def solve(board_string)
  board_array = to_board_array(board_string)
  board_poss = board_possibilities(board_array)

  remove_board_imposs(board_poss)

  solution = nishio(board_poss)

  if solution.nil?
    puts "Couldn't find solution:(..."
    return board_array
  end 

  to_board_array(solution)
end

# Returns a boolean indicating whether
# or not the provided board is solved.
# The input board will be in whatever
# form `solve` returns.
def solved?(board_array)
  board_array.each { |row| row.each { |val| return false if val == '-' } }

  [0, 3, 8].each do |r|
    [0, 3, 8].each do |c|
      return false unless block(board_array, r, c).uniq.length == 9
    end
  end

  (0..8).to_a.each do |i|
    has_uniq_row_vals = row(board_array, i).uniq.length == 9
    has_uniq_col_vals = column(board_array, i).uniq.length == 9

    return false unless has_uniq_row_vals && has_uniq_col_vals
  end
  true
end

# Takes in a board in some form and
# returns a _String_ that's well formatted
# for output to the screen. No `puts` here!
# The input board will be in whatever
# form `solve` returns.
def pretty_board(board_array)
  return board_array if board_array.class == String

  board = ''

  board_array.each do |row|
    board += row.join(' ')
    board += "\n" if row != board_array[-1]
  end
  board
end
\$\endgroup\$
  • \$\begingroup\$ I would look through the standard library documentation for Array and Enumerable. The solution seems to be heavily reliant on while loops, which are rarely seen in Ruby programs. :-) \$\endgroup\$ – Drenmi Feb 19 '18 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.