test_solver.rb

require 'minitest/autorun'

require_relative 'solver'

class TestSolver < Minitest::Test
  make_my_diffs_pretty!

  def test_box2rc
    [
      [[0, 0], [0, 0]],
      [[0, 1], [0, 1]],
      [[1, 0], [0, 3]],
      [[1, 1], [0, 4]],
      [[1, 2], [0, 5]],
      [[1, 3], [1, 3]],
      [[5, 0], [3, 6]],
      [[5, 3], [4, 6]],
      [[6, 0], [6, 0]],
      [[7, 0], [6, 3]],
      [[8, 0], [6, 6]],
      [[8, 7], [8, 7]],
    ].each { |args, res|
      box, i = args
      assert_equal res, box2rc(box, i)
    }
  end

  def _test_solver(data)
    data.each { |hash|
      sol = solve_first(init_sudoku(hash[:puzzle]))
      assert_equal hash[:solution], sol.grid.rows
      assert_equal hash[:branch_factor], sol.bf
    }
  end

  def test_solver_trivial
    _test_solver(@trivial)
  end

  def test_solver_backtracking
    _test_solver(@backtracking)
  end

  def test_solve_all
    @number.each { |hash|
      s = init_sudoku(hash[:puzzle])
      assert_equal hash[:solutions], solve_all(s).size
    }
    (@backtracking + @trivial).each { |hash|
      s = init_sudoku(hash[:puzzle])
      assert_equal 1, solve_all(s).size
    }
  end

  def test_multiple
    @number.each { |hash|
      s = init_sudoku(hash[:puzzle])
      assert_equal hash[:solutions] != 1, one_solution?(s).nil?
    }
    (@backtracking + @trivial).each { |hash|
      s = init_sudoku(hash[:puzzle])
      assert_equal hash[:solution], one_solution?(s).grid.rows
    }
  end

  def setup
    @number = [
      {
        puzzle: [
          [5, 3, 6, 0, 0, 0, 0, 0, 0],
          [0, 4, 7, 0, 8, 0, 5, 0, 0],
          [0, 8, 1, 2, 0, 7, 4, 6, 3],
          [0, 0, 0, 8, 0, 3, 9, 5, 0],
          [0, 0, 0, 7, 0, 0, 0, 0, 4],
          [0, 0, 0, 1, 0, 0, 0, 0, 2],
          [4, 6, 0, 5, 7, 0, 8, 0, 9],
          [7, 0, 5, 0, 0, 0, 0, 4, 6],
          [0, 0, 2, 6, 3, 0, 0, 0, 5]
        ],
        solutions: 1
      },
      {
        puzzle: [
          [5, 3, 6, 0, 0, 0, 0, 0, 0],
          [0, 4, 7, 0, 0, 0, 5, 0, 0],
          [0, 8, 1, 2, 0, 7, 4, 6, 3],
          [0, 0, 0, 8, 0, 3, 9, 5, 0],
          [0, 0, 0, 7, 0, 0, 0, 0, 4],
          [0, 0, 0, 1, 0, 0, 0, 0, 2],
          [4, 6, 0, 5, 7, 0, 8, 0, 9],
          [7, 0, 5, 0, 0, 0, 0, 4, 6],
          [0, 0, 2, 6, 3, 0, 0, 0, 5]
        ],
        solutions: 4
      }
    ]
    @trivial = [
      {
        puzzle: [
          [0, 0, 0, 2, 6, 0, 7, 0, 1],
          [6, 8, 0, 0, 7, 0, 0, 9, 0],
          [1, 9, 0, 0, 0, 4, 5, 0, 0],
          [8, 2, 0, 1, 0, 0, 0, 4, 0],
          [0, 0, 4, 6, 0, 2, 9, 0, 0],
          [0, 5, 0, 0, 0, 3, 0, 2, 8],
          [0, 0, 9, 3, 0, 0, 0, 7, 4],
          [0, 4, 0, 0, 5, 0, 0, 3, 6],
          [7, 0, 3, 0, 1, 8, 0, 0, 0],
        ],
        solution: [
          [4, 3, 5, 2, 6, 9, 7, 8, 1],
          [6, 8, 2, 5, 7, 1, 4, 9, 3],
          [1, 9, 7, 8, 3, 4, 5, 6, 2],
          [8, 2, 6, 1, 9, 5, 3, 4, 7],
          [3, 7, 4, 6, 8, 2, 9, 1, 5],
          [9, 5, 1, 7, 4, 3, 6, 2, 8],
          [5, 1, 9, 3, 2, 6, 8, 7, 4],
          [2, 4, 8, 9, 5, 7, 1, 3, 6],
          [7, 6, 3, 4, 1, 8, 2, 5, 9],
        ],
        branch_factor: 0
      },
      {
        puzzle: [
          [5, 3, 0, 0, 7, 0, 0, 0, 0],
          [6, 0, 0, 1, 9, 5, 0, 0, 0],
          [0, 9, 8, 0, 0, 0, 0, 6, 0],
          [8, 0, 0, 0, 6, 0, 0, 0, 3],
          [4, 0, 0, 8, 0, 3, 0, 0, 1],
          [7, 0, 0, 0, 2, 0, 0, 0, 6],
          [0, 6, 0, 0, 0, 0, 2, 8, 0],
          [0, 0, 0, 4, 1, 9, 0, 0, 5],
          [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ],
        solution: [
          [5, 3, 4, 6, 7, 8, 9, 1, 2],
          [6, 7, 2, 1, 9, 5, 3, 4, 8],
          [1, 9, 8, 3, 4, 2, 5, 6, 7],
          [8, 5, 9, 7, 6, 1, 4, 2, 3],
          [4, 2, 6, 8, 5, 3, 7, 9, 1],
          [7, 1, 3, 9, 2, 4, 8, 5, 6],
          [9, 6, 1, 5, 3, 7, 2, 8, 4],
          [2, 8, 7, 4, 1, 9, 6, 3, 5],
          [3, 4, 5, 2, 8, 6, 1, 7, 9],
        ],
        branch_factor: 0
      }
    ]
    @backtracking = [
      {
        puzzle: [
          [0, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 3, 0, 8, 5],
          [0, 0, 1, 0, 2, 0, 0, 0, 0],
          [0, 0, 0, 5, 0, 7, 0, 0, 0],
          [0, 0, 4, 0, 0, 0, 1, 0, 0],
          [0, 9, 0, 0, 0, 0, 0, 0, 0],
          [5, 0, 0, 0, 0, 0, 0, 7, 3],
          [0, 0, 2, 0, 1, 0, 0, 0, 0],
          [0, 0, 0, 0, 4, 0, 0, 0, 9],
        ],
        solution: [
          [9, 8, 7, 6, 5, 4, 3, 2, 1],
          [2, 4, 6, 1, 7, 3, 9, 8, 5],
          [3, 5, 1, 9, 2, 8, 7, 4, 6],
          [1, 2, 8, 5, 3, 7, 6, 9, 4],
          [6, 3, 4, 8, 9, 2, 1, 5, 7],
          [7, 9, 5, 4, 6, 1, 8, 3, 2],
          [5, 1, 9, 2, 8, 6, 4, 7, 3],
          [4, 7, 2, 3, 1, 9, 5, 6, 8],
          [8, 6, 3, 7, 4, 5, 2, 1, 9],
        ],
        branch_factor: 0
      },
      {
        puzzle: [
          [0, 0, 5, 3, 0, 0, 0, 0, 0],
          [8, 0, 0, 0, 0, 0, 0, 2, 0],
          [0, 7, 0, 0, 1, 0, 5, 0, 0],
          [4, 0, 0, 0, 0, 5, 3, 0, 0],
          [0, 1, 0, 0, 7, 0, 0, 0, 6],
          [0, 0, 3, 2, 0, 0, 0, 8, 0],
          [0, 6, 0, 5, 0, 0, 0, 0, 9],
          [0, 0, 4, 0, 0, 0, 0, 3, 0],
          [0, 0, 0, 0, 0, 9, 7, 0, 0],
        ],
        solution: [
          [1, 4, 5, 3, 2, 7, 6, 9, 8],
          [8, 3, 9, 6, 5, 4, 1, 2, 7],
          [6, 7, 2, 9, 1, 8, 5, 4, 3],
          [4, 9, 6, 1, 8, 5, 3, 7, 2],
          [2, 1, 8, 4, 7, 3, 9, 5, 6],
          [7, 5, 3, 2, 9, 6, 4, 8, 1],
          [3, 6, 7, 5, 4, 2, 8, 1, 9],
          [9, 8, 4, 7, 6, 1, 2, 3, 5],
          [5, 2, 1, 8, 3, 9, 7, 6, 4],
        ],
        branch_factor: 6
      },
      {
        puzzle: [
          [0, 0, 3, 0, 0, 0, 0, 0, 0],
          [8, 0, 9, 4, 6, 0, 7, 0, 2],
          [2, 0, 0, 0, 1, 8, 6, 0, 0],
          [0, 0, 0, 0, 0, 6, 0, 7, 0],
          [0, 0, 8, 0, 0, 0, 4, 0, 0],
          [0, 7, 0, 8, 0, 0, 0, 0, 0],
          [0, 0, 2, 9, 4, 0, 0, 0, 5],
          [4, 0, 6, 0, 3, 2, 8, 0, 7],
          [0, 0, 0, 0, 0, 0, 2, 0, 0],
        ],
        solution: [
          [7, 6, 3, 2, 9, 5, 1, 8, 4],
          [8, 1, 9, 4, 6, 3, 7, 5, 2],
          [2, 4, 5, 7, 1, 8, 6, 9, 3],
          [3, 2, 4, 1, 5, 6, 9, 7, 8],
          [6, 5, 8, 3, 7, 9, 4, 2, 1],
          [9, 7, 1, 8, 2, 4, 5, 3, 6],
          [1, 8, 2, 9, 4, 7, 3, 6, 5],
          [4, 9, 6, 5, 3, 2, 8, 1, 7],
          [5, 3, 7, 6, 8, 1, 2, 4, 9],
        ],
        branch_factor: 9
      },
      {
        puzzle: [
          [5, 3, 4, 0, 0, 8, 0, 1, 0],
          [0, 0, 0, 0, 0, 2, 0, 9, 0],
          [0, 0, 0, 0, 0, 7, 6, 0, 4],
          [0, 0, 0, 5, 0, 0, 1, 0, 0],
          [1, 0, 0, 0, 0, 0, 0, 0, 3],
          [0, 0, 9, 0, 0, 1, 0, 0, 0],
          [3, 0, 5, 4, 0, 0, 0, 0, 0],
          [0, 8, 0, 2, 0, 0, 0, 0, 0],
          [0, 6, 0, 7, 0, 0, 3, 8, 2],
        ],
        solution: [
          [5, 3, 4, 9, 6, 8, 2, 1, 7],
          [7, 1, 6, 3, 4, 2, 5, 9, 8],
          [2, 9, 8, 1, 5, 7, 6, 3, 4],
          [8, 7, 3, 5, 2, 4, 1, 6, 9],
          [1, 5, 2, 6, 7, 9, 8, 4, 3],
          [6, 4, 9, 8, 3, 1, 7, 2, 5],
          [3, 2, 5, 4, 8, 6, 9, 7, 1],
          [9, 8, 7, 2, 1, 3, 4, 5, 6],
          [4, 6, 1, 7, 9, 5, 3, 8, 2],
        ],
        branch_factor: 0
      },
      {
        puzzle: [
          [0, 4, 0, 0, 0, 7, 0, 9, 0],
          [0, 9, 1, 0, 8, 0, 0, 0, 0],
          [7, 0, 3, 9, 0, 1, 0, 0, 0],
          [0, 1, 0, 0, 6, 4, 2, 0, 0],
          [0, 0, 0, 5, 0, 8, 0, 0, 0],
          [0, 0, 5, 7, 1, 0, 0, 6, 0],
          [0, 0, 0, 1, 0, 5, 8, 0, 6],
          [0, 0, 0, 0, 4, 0, 9, 1, 0],
          [0, 5, 0, 8, 0, 0, 0, 2, 0],
        ],
        solution: [
          [8, 4, 2, 6, 3, 7, 5, 9, 1],
          [5, 9, 1, 4, 8, 2, 6, 3, 7],
          [7, 6, 3, 9, 5, 1, 4, 8, 2],
          [9, 1, 7, 3, 6, 4, 2, 5, 8],
          [4, 3, 6, 5, 2, 8, 1, 7, 9],
          [2, 8, 5, 7, 1, 9, 3, 6, 4],
          [3, 2, 9, 1, 7, 5, 8, 4, 6],
          [6, 7, 8, 2, 4, 3, 9, 1, 5],
          [1, 5, 4, 8, 9, 6, 7, 2, 3]
        ],
        branch_factor: 4
      }
    ]
  end
end