The final piece we need is the ability to iteratively guess each value in a cell and backtrack if the placement fails. So now we have the ability to place a value in a cell, and either detect a contradiction or return a copy of the puzzle with that value placed and all of the tumbling consequences. A computational Sudoku solver could do the same thing if we wanted, but it's just not necessary as we can cover that case with more generalized logic. Public int BoxSize case as naked twins, and preemptively eliminate 7 from the first cell. Let's define that, and a few constructors to initialize it.
So each element is itself an array of integers. What is each of those elements? As Peter demonstrates, the fundamental structure of a Sudoku solve-in-progress can be described as a list of possible candidates for each cell. So the sequence of 81 elements reads left-to-right and top-to-bottom as you would expect. A two-dimensional 9 x 9 array might be more intuitively obvious, but we'll see that operations are simpler if we can work on the entire puzzle as one flat region. My goal here is to explore LINQ set-based operations, so I'm storing the puzzle as a flat sequential array of 81 elements. I'm also going to expand past a simple solver to include a generator.įirst off, I'm dispensing with Peter Norvig's notion of "A1" style cell references and string storage. But his Python is mostly a foreign language to me, so it'll be up to me to take the description and implement it in C#. Norvig sets out a particularly elegant algorithm of constraint propagation. Please read that first, as that discussion covers most of the basics and forms a starting point for my work here. Peter Norvig's solution is particularly elegant.
There are many Sudoku solvers on the web, of course.
LINQ is made up of many set-based operators and commands, so a Sudoku solver seemed like a great way to practice and experiment with the capabilities. It would involve C# LINQ programming, which was new to me at the time. In 2011, I was interviewing for (and landing) a new job. One common challenge for modern programmers is a solver for Sudoku puzzles, reminiscent of classic programming hacks like the iterative "Guess the Number" game or "99 Bottles of Beer". If you're here, I assume you know what Sudoku is.
0 kommentar(er)
