trjhtr

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

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