sudoku pseudocode

6 1 9  _ 3 _  _ 4 _
2 7 _  _ 6 1  _ _ 8
_ _ _  _ 4 7  6 2 1

4 8 6  3 _ 2  _ 7 9
_ _ _  _ 1 4  5 8 _
_ 3 1  _ _ 9  _ 6 _

_ _ 5  7 2 _  8 _ 6
3 2 _  1 _ 6  _ 5 7
1 6 _  4 _ _  _ 3 _

class Sudoku
attr_reader :numbers

def initialize(numbers)
  @numbers = []
  @numbers.replace = numbers.split(//).map {|x| x.to_i}
end

def solve!
main loop: while puzzle not solved

end



def rowcol_length
look for rows/columns with most numbers
if a row and column both have the same number of blanks or if row has fewer blanks, examine_row
else examine_col

def examine_row
loop: while counter is <= 9
- determine which numbers are missing
- look at first column/row and see which of the missing numbers it has
  - if only 2 missing numbers, whichever one is not in the column is the one to put in that spot
    - put the other missing number in the other spot in the row
  - if 3 or more missing numbers, examine each column and note which of the missing numbers can fit in that column/row intersection
    - if any intersection only has one option, fill that in
    - else if all of the row's spots have more than 1 option, move to next row/column that has the most numbers
    - if any number has been filled in for that row, review row again
if numberAdded reset counter
else increment counter
end loop

def examine_col
same as examine_row


def examine_box
loop: while counter is <= 9
loop: while options still available without requiring guessing
- look for box with least number of spaces
- loop: look at options for each space
  - check row/column for each space to determine which option fits
  - if space is filled, restart loop
  end loop


def search (row/column, box, options)
- loop: look at col/row and box to see if any option is already in that col/row/box
  - if all options but one have been found in row/col or box, return remaining number
  - else return 0

def board

end #class

sudoku.rb

ONE_THRU_NINE = (1..9).to_a

class Sudoku

  def initialize(board_string)
    @numbers = []
    @numbers = board_string.split(//).map {|x| x.to_i}
  end

  def solve!
    # p @numbers
    not_solved = true
    checks = Array.new(3, false)
    while not_solved
      # p @numbers
      checks[0] = true if examineRow? # if examineRow returns true, no more changes to make
      checks[1] = true if examineCol? # if examineCol returns true, no more changes to make
      checks[2] = true if examineBox? # if examineBox returns true, no more changes to make
      not_solved = false if !checks.include?(true)  # if no more changes to make for all 3, problem solved/unsolveable
      # p @numbers
    end #while
    # p @numbers

  end

# def examineRow: iterate through rows to 
# 1) find the number of blanks in each row
# 2) choose the row with the least number of blanks
# 3) determine the list of number options for that spot in the row
# 4) create comparison array for search (col + box)
# 5) search the intersecting column and box to determine if one of the options works
  def examineRow?
    rowcounter = 1
    while rowcounter <= 9
      num_blanks = blanksPerRow.clone
      p num_blanks.min
      row_least_num_blanks = num_blanks.index(num_blanks.select {|i| i > 0 && i == num_blanks.min}) # step 1) and 2) / Find row to attack
      #attack row and iterate through each blank, then create row cell options
      p row_least_num_blanks
      lower_bound = row_least_num_blanks * 9
      # Step 3 (creates options array for individual cell)
      a = getRowArray(lower_bound)
      a.each_with_index do |cell, index| 
        if cell == 0
          numbers_index_from_row_number = (row_least_num_blanks * 9) + index
          options_array = createRowCellOptions(lower_bound)
          # Step 4
          comparison_array = []
          (0..8).each {|x|  comparison_array << @numbers[((9 * x) + index)]} # Row comparison calculation (col)
          top_left = (3*(numbers_index_from_row_number/3)) - ((row_least_num_blanks%3)*9) # top left of box by index
          (0..2).each do |x| # gets all numbers from box and puts into array
              comparison_array << @numbers[top_left + x]
              comparison_array << @numbers[top_left + x + 9]
              comparison_array << @numbers[top_left + x + 18]
          end # box each
          # Step 5
          remaining_options = search(comparison_array, options_array)
          if remaining_options.length == 1 
            a[index] = remaining_options[0] # number found, fill cell in
            @numbers[numbers_index_from_row_number] = remaining_options[0]
            rowcounter = 1  # restart checking all rows since a row has been changed
            #(0..8).each {|x| @numbers[numbers_index_from_row_number + x] = a[x]}
            p a
            # next
            # p @numbers
          end
        end #if
      end #each_with_index
      rowcounter += 1
    end #while
    true # finished checking all rows and no more changes available
  end #def

# def blanksPerRow: returns an ARRAY containing the number of blanks per row
  def blanksPerRow
    lower_bound = 0
    number_of_blanks = Array.new(9,0)
    row_number = 0
    until row_number == 9
      number_of_blanks[row_number] = countBlanks(getRowArray(lower_bound))
      row_number += 1
      lower_bound += 9
    end
    number_of_blanks
  end

  def createRowCellOptions(row_number)
    # lower_bound = 9 * row_number
    # ONE_THRU_NINE - @numbers.slice(lower_bound..(lower_bound + 8))
    ONE_THRU_NINE - getRowArray(row_number)
  end

  #Returns ARRAY of the numbers in a row
  def getRowArray(start)
    @numbers.slice(start..(start + 8))
  end



  def examineCol? # iterate through columns
    colcounter = 1
    while colcounter <= 9
      num_blanks = blanksPerColumn.clone
      col_least_num_blanks = num_blanks.index(num_blanks.min) # step 1) and 2) / Find column to attack
      # Step 3 (creates options array for individual cell)
      getColArray(col_least_num_blanks).each_with_index do |cell, index| 
        if cell == 0
          numbers_index_from_col_number = (index * 9) + col_least_num_blanks
          options_array = createColCellOptions(col_least_num_blanks)
          # Step 4
          comparison_array = []
          row_start = (numbers_index_from_col_number / 9) * 9
          comparison_array << @numbers.slice(row_start..(row_start + 8)) # col comparison calculation (row)
          top_left = (3*(numbers_index_from_col_number/3)) - (((row_start/9)%3)*9) # top left of box by index
          (0..2).each do |x| # gets all numbers from box and puts into array
              comparison_array << @numbers[top_left + x]
              comparison_array << @numbers[top_left + x + 9]
              comparison_array << @numbers[top_left + x + 18]
          end # box each
          # Step 5
          remaining_options = search(comparison_array, options_array)
          if remaining_options.length == 1 
            cell = remaining_options[0] # number found, fill cell in
            colcounter = 1   # restart checking all cols since a row has been changed
          end
        end #if
      end #each_with_index
      colcounter += 1
    end #while
    true # finished checking all rows and no more changes available
  end

  def createColCellOptions(col_number)
    lower_bound = col_number
    col_array = []
    (0..8).each {|i| col_array.push(@numbers.slice((9 * i) + col_number))}
    ONE_THRU_NINE - col_array
  end

  def blanksPerColumn
    lower_bound = 0
    number_of_blanks = Array.new(9,0)
    col_number = 0
    until col_number == 9
      number_of_blanks[col_number] = countBlanks(getColArray(lower_bound))
      col_number += 1
      lower_bound += 1
    end
    number_of_blanks
  end

#returns array of the numbers in a column
  def getColArray(start)
    col_array = []
    (0..8).each {|i| col_array.push(@numbers.slice((9 * i) + start))}
    col_array
  end



  def examineBox? # iterate through boxes
    boxcounter = 0
    while boxcounter < 9
      num_blanks = blanksPerBox.clone
      box_least_num_blanks = num_blanks.index(num_blanks.min) # step 1) and 2) / Find box to attack
      # Step 3 (creates options array for individual cell)
      getBoxArray(box_least_num_blanks).each_with_index do |cell, index| 
        if cell == 0
          numbers_index_from_box_number = ((boxcounter/3)*27) + ((index/3)*3) + ((boxcounter%3)*3) + (index % 3)
          options_array = createBoxCellOptions(box_least_num_blanks)
          # Step 4
          comparison_array = []
          row_start = (numbers_index_from_box_number / 9) * 9
          comparison_array << @numbers.slice(row_start..(row_start + 8)) # box comparison calculation (row)
          (0..8).each {|x|  comparison_array << @numbers[((9 * x) + index)]} # box comparison column
          # Step 5
          remaining_options = search(comparison_array, options_array)
          if remaining_options.length == 1 
            cell = remaining_options[0] # number found, fill cell in
            boxcounter = 0   # restart checking all cols since a row has been changed
          end
        end #if
      end #each_with_index
      boxcounter += 1
    end #while
    true # finished checking all rows and no more changes available
  end

  def createBoxCellOptions(box_number)
    lower_bound = box_number
    (0..2).each do |x| # gets all numbers from box and puts into array
      box_array << @numbers[start + x]
      box_array << @numbers[start + x + 9]
      box_array << @numbers[start + x + 18]
    end
    ONE_THRU_NINE - box_array
  end

  def blanksPerBox
    top_left = 0
    number_of_blanks = Array.new(9,0)
    box_number = 0
    row_number = 0
    col_number = 0
    until (box_number == 9) && (row_number == 9)
      number_of_blanks[box_number] = countBlanks(getBoxArray(top_left))
      top_left = (3*(box_number/3)) - (((row_number/9)%3)*9)
      row_number += 3 if (box_number % 3 == 0) && (box_number != 0)
      if box_number % 3 > 0
        col_number += 1
      else
        col_number = 0
      end
      box_number += 1
    end
    number_of_blanks
  end

#returns array of the numbers in a box
  def getBoxArray(start)
    box_array = []
    (0..2).each do |x| # gets all numbers from box and puts into array
      box_array << @numbers[start + x]
      box_array << @numbers[start + x + 9]
      box_array << @numbers[start + x + 18]
    end
    box_array
  end


  def search(comparison_array, options_array) # search through 9 numbers
    options_array - comparison_array
  end

  def countBlanks(set_of_nine)
    number_of_blanks = 0
    set_of_nine.each {|i| number_of_blanks += 1 if i == 0}
    number_of_blanks
  end

end #class



game = Sudoku.new("619030040270061008000047621486302079000014580031009060005720806320106057160400030")

game.solve!