To solve a sudoku, start by lining up and numbering all of the rows and columns. Be aware that the basic rule of sudoku is that every large square, column, and row must have all of the numbers from 1 to 9, so look for missing numbers. If you see a single empty in a larger square, fill that in first. A prime example is Arto Inkala's Worlds Hardest Sudoku it has been published with the point that it has a high number of required guesses. Another good example is SudokuWiki's Weekly Unsolvable Sudoku all of them have the property that they require guesses, although occasionally one of those turns out to be solvable by logical means.
For many who are new to Sudoku puzzles, finding a solution can be a complete mystery. On one hand, with so many numbers, Sudoku seems very mathematical. On the other hand, without the appropriate solution techniques, it can amount to a lot of guessing and checking.
In truth, Sudoku puzzles are very well structured and predictable – much like mathematics.
Before we cover how to solve Sudoku puzzles, let’s take a moment to review a few aspects of Sudoku including the rules, terminology, and game variations.
What is Sudoku?
A Sudoku puzzle is defined as a logic-based, number-placement puzzle. The objective is to fill a 9×9 grid with digits in such a way that each column, each row, and each of the nine 3×3 grids that make up the larger 9×9 grid contains all of the digits from 1 to 9. Each Sudoku puzzle begins with some cells filled in. The player uses these seed numbers as a launching point toward finding the unique solution.
It is important to stress the fact that no number from 1 to 9 can be repeated in any row or column (although, the can be repeated along the diagonals).
Buku Sudoku
What Defines a True Sudoku Puzzle?
For a puzzle to be a true Sudoku puzzle, it can have one (and only one) solution. There can be no ambiguity in Sudoku. Each number has a single location it must reside in. Otherwise, the player is forced to guess which location to choose thus changing the puzzle into a game of chance.
Sudoku Puzzle Variants
There are many variations on Sudoku including Mini Sudoku, Cross Sums Sudoku, Killer Sudoku, and Wordoku. We will not cover such variations here.
The Rules of Sudoku
While solving Sudoku puzzles can be significant challenge, the rules for traditional solution finding are quite straight forward:
- Each row, column, and nonet can contain each number (typically 1 to 9) exactly once.
- The sum of all numbers in any nonet, row, or column must match the small number printed in its corner. For traditional Sudoku puzzles featuring the numbers 1 to 9, this sum is equal to 45.
This is an important point to review as it isn’t uncommon for inexperienced players to get frustrated and to abandon the techniques we will lay out below. Don’t do it! In order to solve Sudoku puzzles reliably, you must be disciplined, focused, and patient.
How to Solve Sudoku Puzzles
There are two main techniques one can use to solve a Sudoku puzzle; Crosshatching and Penciling In. These two techniques are simple, straightforward, reliable, and sufficient in solving most standard Sudoku puzzles.
It is important to understand that all Sudoku puzzles require an iterative approach. Except for in the case of the most simple puzzles, players will have to visit each nonet more than one time. Fortunately, each successive application of the solution techniques yields more completed cells.
![Correct sudoku example for beginners Correct sudoku example for beginners](http://www.dailysudoku.com/sudoku/examples/classic.png)
Crosshatching
To begin with we will want to use the Crosshatching technique. With this technique, a player considers a single nonet (a single 3×3 square) and attempts to fill in empty cells based on the fact that a number can only appear once in any row or column. By looking across each row and down each column, we can determine if a number can or cannot go in a cell. Let’s look at an example to help illustrate the Crosshatching technique.
We will be solving a Sudoku puzzle taken from Sudoku Latin Squares. Let’s take a look:
In order to understand where we are focusing our puzzle solving efforts, we’ll take a moment to label each nonet, A – I.
![Sample sudoku puzzles Sample sudoku puzzles](https://sudoku.com/img/post-images/Sudoku-Part-4-Example-6.jpg)
Getting Started
Sudoku puzzles can be started anywhere, but we recommend you begin with nonet A and work alphabetically, left to right, top to bottom. This strategy helps players remember where they are and where they’ve been.
We will follow this advice and focus on nonet A. As there are 5 numbers missing in this nonet (1, 5, 6, 7, and 8), we will make 5 passes, attempting to place each of the five missing numbers in empty cells.
Crosshatching Nonet A
Below you’ll find screenshots of each Crosshatching attempt on nonet A.
Crosshatching for 1 (Nonet A)
In trying to place the number 1, we cross out all rows and columns that contain the number 1 and pass through the nonet we are focusing on. We’re left with 3 empty cells. As we know guessing is not an option, we’ll move on to the next missing number.
Crosshatching for 5 (Nonet A)
In trying to place the number 5, we again, cross out all rows and colums with 5 and are left with 3 empty cells. Again, we’ll move on to the next missing number.
Crosshatching for 6 (Nonet A)
In trying to place the number 6, we’re left with 3 empty cells. By the way, you might not think we’re making progress, but hang in there, such seemingly unproductive efforts are common and more useful than you might think.
Crosshatching for 7 (Nonet A)
In trying to place the number 7, we’re left with 2 empty cells. An improvement, but this still prevents us from placing the number.
Crosshatching for 8 (Nonet A)
In trying to place the number 8, we’re left with 3 empty cells.
It’s easy to think we’ve made no progress as we were unable to place any numbers in our first nonet. But, don’t despair! This is very common in Sudoku. You shouldn’t expect to have everything fall into place right away. Some puzzles are straightforward, while others take a bit more time to successfully solve. Let’s move on to nonet B.
Crosshatching Nonet B
Below you’ll find screenshots of each Crosshatching attempt on nonet B.
Crosshatching for 1 (Nonet B)
In trying to place the number 1, we’re left with 1 empty cell. Hurray! We can place our first number.
Crosshatching for 2 (Nonet B)
In trying to place the number 2, we’re left with 2 empty cells so we’ll move on to the next number.
Crosshatching for 3 (Nonet B)
We’re successful in placing 3!
Crosshatching for 5 (Nonet B)
We’re successful in placing 5!
Crosshatching for 2 (Nonet B)
We’ve filled in every box in nonet B except one. As such, we know the number 2 must go in the final empty box.
If we continue to apply the Crosshatching technique to nonets C through I, we complete our first Crosshatching pass with the following puzzle status.
Penciling In
Of course, we could continue to Crosshatch and possibly fill in more empty boxes. However, to best illustrate both Sudoku solving techniques, we’re going to switch to Penciling In.
Penciling In is the process of writing down all possible cell candidates in the empty cells of a given nonet. Then, through crosshatching, we cross off all unqualified candidates. Let’s take a look at how this done. Again, we’ll begin with nonet A.
Penciling In Nonet A
In looking at nonet A, we see we still have the same five missing numbers (1, 5, 6, 7, and 8). We will write all of these numbers at the top of each cell within nonet A as shown below:
Once we’ve written the numbers in to each empty cell, we’ll look down each row and column for matches. In the case of a match, we can cross out the matching number in the cell. This is very similar to the Crosshatching we already did, but when considering multiple cells, yields more insight. Let’s look at what numbers we can cross off based on the existing numbers in the rows.
Now, let’s look at what numbers we can cross off based on the existing numbers in the columns.
We’re able to fill in the 1, 5, and 8 following our Penciling In efforts! Fantastic!
Of course, Penciling In numbers effects what can or cannot go in the remaining empty cells. As such, we take a moment to repeat the Penciling In process for nonet A.
Following our Crosshatching and Penciling In efforts, we have completely filled in nonet A and nonet B. We’re really starting to make some progress!
Completing the Puzzle
Rather than continue to walk you through this puzzle step-by-step, we leave it to you to apply the Sudoku solving techniques we’ve discussed and illustrated to complete the puzzle.
To help you, we’re including the completed puzzle below so you can check your final solution. Remember, true Sudoku puzzles have one (and only one) correct solution. If your final work doesn’t match what you see below, we encourage you to go back and double-check your work.
For more puzzle solving fun, we encourage you to visit our Sudoku games page.
Given a Sudoku Board configuration, check whether it is valid or not.
Examples:
The basic idea is to check whether each row, column, and the 3×3 box is valid or not on the basis of following points:
- The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
- An empty Sudoku board is also valid.
- A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
Below is the implementation of above approach:
C++
// board is valid or not using namespace std; // Checks whether there is any duplicate bool notInRow( char arr[][9], int row) // Set to store characters seen so far. if (st.find(arr[row][i]) != st.end()) // at the current cell in the set st.insert(arr[row][i]); return true ; // in current column or not. { if (st.find(arr[i][col]) != st.end()) // insert value at the current cell in the set st.insert(arr[i][col]); return true ; // in current 3x3 box or not. bool notInBox( char arr[][9], int startRow, int startCol) set< char > st; for ( int row = 0; row < 3; row++) { char curr = arr[row + startRow][col + startCol]; // If already encountered before, return false return false ; // If it is not an empty cell, if (curr != '.' ) } return true ; // Checks whether current row and current column and bool isValid( char arr[][9], int row, int col) return notInRow(arr, row) && notInCol(arr, col) && } bool isValidConfig( char arr[][9], int n) for ( int i = 0; i < n; i++) { // current 3x3 box is not valid, return false return false ; } } // Drivers code { char board[9][9] = { { '5' , '3' , '.' , '.' , '7' , '.' , '.' , '.' , '.' }, { '.' , '9' , '8' , '.' , '.' , '.' , '.' , '6' , '.' }, { '4' , '.' , '.' , '8' , '.' , '3' , '.' , '.' , '1' }, { '.' , '6' , '.' , '.' , '.' , '.' , '2' , '8' , '.' }, { '.' , '.' , '.' , '.' , '8' , '.' , '.' , '7' , '9' } }; cout << (isValidConfig(board, 9) ? 'YESn' : 'NOn' ); } |
Python3
# Python3 program to check whether
# given sudoku board is valid or not
# Checks whether there is any
# duplicate in current row or not
def notInRow(arr, row):
# Set to store characters seen so far.
st = set()
for i in range(0, 9):
# If already encountered before,
# return false
if arr[row][i] in st:
return False
# If it is not an empty cell, insert value
# at the current cell in the set
if arr[row][i] != ‘.’:
st.add(arr[row][i])
return True
# Checks whether there is any
# duplicate in current column or not.
def notInCol(arr, col):
st = set()
for i in range(0, 9):
# If already encountered before,
# return false
if arr[i][col] in st:
return False
# If it is not an empty cell, insert
# value at the current cell in the set
if arr[i][col] != ‘.’:
st.add(arr[i][col])
return True
# Checks whether there is any duplicate
# in current 3×3 box or not.
def notInBox(arr, startRow, startCol):
st = set()
for row in range(0, 3):
for col in range(0, 3):
curr = arr[row + startRow][col + startCol]
# If already encountered before,
# return false
if curr in st:
return False
# If it is not an empty cell,
# insert value at current cell in set
if curr != ‘.’:
st.add(curr)
return True
# Checks whether current row and current
# column and current 3×3 box is valid or not
def isValid(arr, row, col):
return (notInRow(arr, row) and notInCol(arr, col) and
notInBox(arr, row – row % 3, col – col % 3))
def isValidConfig(arr, n):
for i in range(0, n):
for j in range(0, n):
# If current row or current column or
# current 3×3 box is not valid, return false
if not isValid(arr, i, j):
return False
return True
# Drivers code
if __name__ “__main__”:
board = [[ ‘5’, ‘3’, ‘.’, ‘.’, ‘7’, ‘.’, ‘.’, ‘.’, ‘.’ ],
[ ‘6’, ‘.’, ‘.’, ‘1’, ‘9’, ‘5’, ‘.’, ‘.’, ‘.’ ],
[ ‘.’, ‘9’, ‘8’, ‘.’, ‘.’, ‘.’, ‘.’, ‘6’, ‘.’ ],
[ ‘8’, ‘.’, ‘.’, ‘.’, ‘6’, ‘.’, ‘.’, ‘.’, ‘3’ ],
[ ‘4’, ‘.’, ‘.’, ‘8’, ‘.’, ‘3’, ‘.’, ‘.’, ‘1’ ],
[ ‘7’, ‘.’, ‘.’, ‘.’, ‘2’, ‘.’, ‘.’, ‘.’, ‘6’ ],
[ ‘.’, ‘6’, ‘.’, ‘.’, ‘.’, ‘.’, ‘2’, ‘8’, ‘.’ ],
[ ‘.’, ‘.’, ‘.’, ‘4’, ‘1’, ‘9’, ‘.’, ‘.’, ‘5’ ],
[ ‘.’, ‘.’, ‘.’, ‘.’, ‘8’, ‘.’, ‘.’, ‘7’, ‘9’ ]]
if isValidConfig(board, 9):
print(“YES”)
else:
print(“NO”)
# This code is contributed by Rituraj Jain
Recommended Posts:
If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to [email protected]. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please Improve this article if you find anything incorrect by clicking on the 'Improve Article' button below.