Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Medium

A Sudoku Solver in Ruby 17

Author Adya Tiwari
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

A Sudoku game starts with a 9x9 network to some degree loaded up with values from 1 to 9. The objective for the player is to fill every one of the leftover boxes with values from 1-9. Notwithstanding, each number that a player embeds should pass three stringent standards. Backtracking is an algorithmic way to tackle issues under unambiguous imperatives (it seems like Sudoku to me!) in which worth is placed on the off chance that it meets the circumstances. The calculation continues to the following cost and many more algorithms that we will see further.

Ruby Logo         Sudoku

A Sudoku Solver in Ruby 17

Puzzle ūüß© games like Sudoku have consistently entranced me, and Sudoku specifically has assisted me with getting past many significant delays. It is a very well-known game, yet for those new to the principles, here is a fast rundown, or you can see the Wikipedia passage here.

In any case, each number that a player embeds should pass three strict principles:

An example of Sudoku board
  1. Each worth 1-9 must be available once in succession. So in the model board over, 5, 3, and 7 can't be composed of blank cells in the main line‚úÖ.
     
  2. Each worth 1-9 must be available once in a section. So in the model board over, 5, 6, 8, 4, and 7 can't be composed of any blank cells in the top section‚úÖ.
     
  3. Each worth 1-9 must be available once inside a matrix locale. A network locale is a more modest 3x3 framework inside the giant Sudoku board. These areas should be visible on the panel above by their bolded borders. For instance, the upper left site contains the qualities 5,3,6,8 and 9. Thus, these qualities can't be set again into any of the vacant cells staying around here‚úÖ.

 

Settling these riddles by hand includes carefully looking at values contrary to these standards and embedding them, assuming they pass. Involving comparative rationale in a backtracking calculation, we can compose a little content that can both produce and settle these sheets.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Backtracking

Backtracking is an algorithmic way to tackle issues under specific limitations (it seems like Sudoku to me!) in which worth is placed if it meets the circumstances. The calculation continues to the following value. Be that as it may, assuming the analysis can't put these following qualities, it will backtrack to the last effectively positioned worth and change it to the subsequent conceivable fruitful price and go on once more.

Backtracking

Implementation

We carried out the backtracking arrangement in Ruby. We have framed the cycle and parts in Javascript underneath. However, the complete code for Ruby can be found in the lower part of this article.

Placement Criteria

To start carrying out this calculation, we should initially characterize our fruitful models: rowSafe checks the uniqueness of the qualities in the line, colSafe takes a look at it in the section, and boxSafe in the 3x3 matrix. Then, at that point, we want to assess whether the directions of the emptyCell (which is a JS item or Ruby hash containing the two approaches)ūüé≤

  • To check the line, we can pick the column of puzzleArray that is determined in the emptyCell facilitates and check whether it contains the num esteem we are attempting to embed by searching for the file of that worth.
     
  • To check the section, we can inspect the segment file of emptyCell for each column and check whether any of them contain that worth. In Javascript .some() will return true on the off chance that no less than one of the upsides of the cluster meets the condition.
     
  • The district condition is trickier because we should initially figure out what locale the cell has a place. Every area starts on lines 0, 3, and 6 and segments 0, 3, and 6. Utilizing a mix of deduction and modulus with the directions of the unfilled cell, we can decide the upper left-most compartment of the district where the cell has a place. Then, at that point, we check through the community and search for a match.
     
  • Since each of the three rules should be met to pass, we can make sure that all conditions are met with a partner capability.

Producing a Game Board

We initially started by making a filled and accurately tackled board out of a clear board to produce a game board. The scope of values 1 to 9 is rearranged toward the beginning of every emphasis, guaranteeing that the likelihood of each new game being comparable is low. Since each influential position of a number will be trailed by one more endeavor to put a number, this fillPuzzleūüß© capability will recursively call itself. Since this can make a piece precarious, we should frame the means before we see the code:

Game board

 

  • Acquire a void 9x9 grid loaded up with zeros.
     
  • Check the lattice for the following cell with an ongoing worth of nothing.
  • Randomize the exhibit [0,1,2,3,4,5,6,7,8,9] and endeavour to put the initial worth of that rearranged cluster into the vacant cell seen above.
     
  • Embed a restrictive to cut short the content on the off chance that the board neglects to create inside a specific number of emphasis. Most loads up will produce in less than 500ms. However, arbitrary age can prompt significant delays every so often. We will examine this more in the introduction area.
     
  • If the worth from the rearranged cluster passes all of the wellbeing checks, embed it and return to stage 2.
     
  • Assuming that the worth from the rearranged exhibit bombs the security check, return the cell to nothing, return to the recently positioned number and attempt to transform it to the following conceivable worth from the rearranged cluster and rehash.

Full Ruby Code ūüßĎ‚ÄćūüíĽ

CN Ruby Sudoku Solver code

require_relative '../solver'

describe Solver do
  let(:board) do
    [
      [1, 7, 4, 0, 9, 0, 6, 0, 0],
      [0, 0, 0, 0, 3, 8, 1, 5, 7],
      [5, 3, 0, 7, 0, 1, 0, 0, 4],
      [0, 0, 7, 3, 4, 9, 8, 0, 0],
      [8, 4, 0, 5, 0, 0, 3, 6, 0],
      [3, 0, 5, 0, 0, 6, 4, 7, 0],
      [2, 8, 6, 9, 0, 0, 0, 0, 1],
      [0, 0, 0, 6, 2, 7, 0, 3, 8],
      [0, 5, 3, 0, 8, 0, 0, 9, 6]
    ]
  end

  describe '#solve' do
    let(:expected_board) do
      [
        [1, 7, 4, 2, 9, 5, 6, 8, 3],
        [9, 6, 2, 4, 3, 8, 1, 5, 7],
        [5, 3, 8, 7, 6, 1, 9, 2, 4],
        [6, 2, 7, 3, 4, 9, 8, 1, 5],
        [8, 4, 1, 5, 7, 2, 3, 6, 9],
        [3, 9, 5, 8, 1, 6, 4, 7, 2],
        [2, 8, 6, 9, 5, 3, 7, 4, 1],
        [4, 1, 9, 6, 2, 7, 5, 3, 8],
        [7, 5, 3, 1, 8, 4, 2, 9, 6]
      ]
    end

#    before { solver.board = board }
#    after { solver.board = board }

    subject(:solver) { described_class.new(board) }

    shared_examples 'correct guess' do |row, column, guess|
      it 'returns true' do
        expect(solver.valid?(row, column, guess)).to be_truthy
      end
    end

    shared_examples 'wrong guess' do |row, column, guess|
      it 'returns false' do
        expect(solver.valid?(row, column, guess)).to be_falsey
      end
    end

    describe '#valid?' do
      subject(:solver) { described_class.new(board) }

      before { solver.board = board }

      it_behaves_like 'correct guess', 0, 3, 2

      it_behaves_like 'wrong guess', 1, 0, 4
      it_behaves_like 'wrong guess', 1, 0, 1
      it_behaves_like 'wrong guess', 1, 1, 4
      it_behaves_like 'wrong guess', 1, 2, 4
      it_behaves_like 'wrong guess', 0, 3, 4
      it_behaves_like 'wrong guess', 0, 3, 3
      it_behaves_like 'wrong guess', 6, 6, 3
      it_behaves_like 'wrong guess', 8, 6, 1
    end

    it 'finds coordinates of next empty cell' do
      expect(solver.empty_cell).to eq([0, 3])
    end

    it 'return all the values that are' do
      expect(solver.possible_values(0, 3)).to eq([2])
    end

    it 'A should be a solved board' do
      expect(solver.solve).to eq(expected_board)
    end
  end
end

Output ūüď§

Sudoku output
output

Frequently Asked Questions ‚Ěď

Is there any recipe to address Sudoku?

For instance, in the first and fourth segments starting from the left of the 9√ó9 matrix, we can frame the accompanying conditions: m+n=a, g+n+f=g+c.

What is the 45 rule in Sudoku?

Every sudoku area (i.e., line, section, or nonet) contains the digits one through nine. Consequently, every sudoku district has an all-out worth of 45.

Is Ruby procedural language?

Ruby is an unadulterated OO language that can take on the appearance of a procedural one. It has no capabilities, just strategy calls. In a Ruby strategy, the recipient, likewise called self, is a secret contention like this in C++.

How to check indexing for sudoku while writing the code?

To check the segment, we can look at the section record of emptyCell for each line and check whether any of them contain that worth. In Javascript .some() will return valid on the off chance that no less than one of the upsides of the exhibit meets the condition.

Conclusion

Most games will be made in less than 500 ms, yet to forestall a significant periodic delay, the emphasis counter in fillPuzzle will toss a blunder and cut short the content after a predetermined time. We will get this blunder and use it to re-trigger the introduced capability. It is quicker to leave puzzles with strangely lengthy ages and begin once again than to endure them.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in pygameCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations. 

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Thank you
Previous article
How to Use Enums in Ruby?
Next article
Simple Ruby Examples to Learn Ruby
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass