X-Wing Strategy. The reverse is also true for 2 columns with 2 common rows. Since this strategy works in the other direction as well, we will look at an example next. In this second example I've chosen a Sudoku puzzle where an enormous number of candidates can be removed using two X-Wings. The first is a '2-Wing'.
You're given a solution to a Sudoku puzzle. Write the code to check if it's a valid solution.
Your function signature should be:
boolean isValid(int starti, int startj, int endi, int endj)
boolean isValid(int starti, int startj, int endi, int endj)
Rules for those unfamiliar with Sudoku:
- Grid size is 9x9, divided into 9 regions of 3x3
- Each row must contain all digits from 1-9
- Each column must contain all digits from 1-9
- Each 3x3 square must contain all digits from 1-9
I wasn't asked this question, but saw it on severalplaces. Checking the last rule might be the interesting part
Sarp CentelSarp Centel1,1312 gold badges13 silver badges23 bronze badges
closed as too broad by l4mpi, gnat, Bhavesh Odedra, Alex, Adriano RepettiMar 11 '15 at 12:05
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
11 Answers
Fred FooFred Foo288k59 gold badges606 silver badges740 bronze badges
Sorry, I know this must be homework, but I can't help myself. It's just too much fun to come up with something :-)
A spoon full of LINQ makes the medicine go down:
The nice thing about this solution is, that no teacher will believe you if you say you came up with this ;-)
StevenSteven132k17 gold badges231 silver badges350 bronze badges
SQL allows you to define the rules as CONSTRAINTS: invalid puzzels are forbidden and cannot exist.
Now, the ->val members can be updated, but the resulting table can never violate any of the four constraints (three are actually INDEXES, but that is unimportant here).
Checking for a completely valid filled-in table means: checking if there are 81 non-NULL entries:
wildplasserwildplasser32.4k6 gold badges45 silver badges74 bronze badges
zc22zc22
Trenton6,9119 gold badges40 silver badges52 bronze badges
parolkarparolkar
the solution which use just one array iteration.through the whole iteration of array, posRec array is going to have each numbers availability in ROW/COL/GRID.if there is missing bit in posRec, we can say sudoku isn’t correct.
byengabyenga
Flexo♦71.1k22 gold badges153 silver badges237 bronze badges
BhawnaBhawna
In reference to the excellent answer from @Stephen, here is a solution in C# without resorting to LINQ, to show the difference between the two approaches.
This solution handles both 4x4 and 9x9 Sodoku boards.
ContangoContango42.7k48 gold badges192 silver badges241 bronze badges
I had a similar task, input coming from standard input.
I used sets.Put the element to the right row, column, and square (called box in my code).If all 3 set's size is 9, it's valid.
}
otisonozaotisonoza7932 gold badges10 silver badges26 bronze badges
I thought my solution was terse, but apparently so if everyone else's. Anyways, I think this is a very clear and easy to read answer in ruby I made for an interview question on 7/11/2014:
bhanbhan1,0743 gold badges11 silver badges24 bronze badges
The rows and columns can be validated in a single loop
}
vijayinanivijayinani9791 gold badge12 silver badges34 bronze badges
Not the answer you're looking for? Browse other questions tagged sudoku or ask your own question.
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.
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.
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.