Click here to Skip to main content
15,867,141 members
Articles / LINQ

Solving a (Formula Based) Sudoku Puzzle using LINQ

Rate me:
Please Sign up or sign in to vote.
4.95/5 (5 votes)
31 May 2013CPOL4 min read 38.3K   13   3
Solving a formula based Sudoku puzzle

Introduction

I am a geocacher and one weekend in January 2012, we went to Heidelberg and while there a new geocache was published where one had to solve a formula based Sudoku puzzle. A group of us solved it manually (in about 30 minutes). Once back at work, I showed a work collogue (let's call him Bob) the puzzle and we started chatting if it would be possible to write a LINQ query to solve this puzzle.

Bob showed me the MSDN blog article, Using LINQ to solve puzzles and we used this as a basis to solve this Sudoku puzzle.

The original article was published by me on 25th of January 2013 here.

Background

This is what the formula based Sudoku puzzle looks like:

Image 1

First, I wanted to understand how this LINQ query would work by simplifying the problem.

Proof of Concept

I drew a small 3 by 3 grid and entered some numbers.

Image 2

I entered "random" numbers from 1 to 9 into each cell. At this stage, I am simulating one section of the Sudoku puzzle, so that when I write the LINQ query I can understand it better. It is much simpler to work with a 3x3 grid and understand what is going on than working with a 9x9 grid.

Once I had the numbers, then I made up some of my own formulas as follows:

Image 3

As it happened, I did enter three circular references. This helped me understand how the "from" and "joins" work later on (see further below).

I started with the brute force method as per the MSDN blog, and the code I started off with looked like this:

C#
var solveForNumbers =
  from a1 in Enumerable.Range(1, 9)
  from a2 in Enumerable.Range(1, 9)
  from a3 in Enumerable.Range(1, 9)
  from b1 in Enumerable.Range(1, 9)
  from b2 in Enumerable.Range(1, 9)
  from b3 in Enumerable.Range(1, 9)
  from c1 in Enumerable.Range(1, 9)
  from c2 in Enumerable.Range(1, 9)
  from c3 in Enumerable.Range(1, 9)
  where (a1 == b3 - 4)
      && (a2 == a3 - b2)
      && (a3 == b2 * c3)
      && (b1 == a3 + a1)
      && (b2 == c2 - a3)
      && (b3 == a1 + a2)
      && (c1 == a3 + c3)
      && (c2 == a2 * b2)
      && (c3 == b3 - b2)
  select new
  { a1, a2, a3, b1, b2, b3, c1, c2, c3};

Solving this basic puzzle took around 110 seconds on my laptop. For the big puzzle (9 x 9 grid) to be solved this way would take exponentially longer.

I then started, as per the MSDN blog post, to move each "where" clause into a "join". I wanted to see the speed improvements along the way.

I moved the 1st entry "c3" into a join as follows:

C#
var solveForNumbers1 =
  from a1 in Enumerable.Range(1, 9)
  from a2 in Enumerable.Range(1, 9)
  from a3 in Enumerable.Range(1, 9)
  from b1 in Enumerable.Range(1, 9)
  from b2 in Enumerable.Range(1, 9)
  from b3 in Enumerable.Range(1, 9)
  from c1 in Enumerable.Range(1, 9)
  from c2 in Enumerable.Range(1, 9)
  join c3 in Enumerable.Range(1, 9) on b3 - b2 equals c3
where (a1 == b3 - 4)
  && (a2 == a3 - b2)
  && (a3 == b2 * c3)
  && (b1 == a3 + a1)
  && (b2 == c2 - a3)
  && (b3 == a1 + a2)
  && (c1 == a3 + c3)
  && (c2 == a2 * b2)
select new
  { a1, a2, a3, b1, b2, b3, c1, c2, c3};

I reran the test and now it took only 12 seconds. Wow! That is a saving of almost 100 seconds.

With some help from Rankadu, I moved them all across and ended up with this code:

C#
var solveForNumbers1 =
  from b2 in Enumerable.Range(1, 9)
  from a3 in Enumerable.Range(1, 9)
  from a1 in Enumerable.Range(1, 9)
  join a2 in Enumerable.Range(1, 9) on a3 - b2 equals a2
  join b3 in Enumerable.Range(1, 9) on a1 + a2 equals b3
  join c3 in Enumerable.Range(1, 9) on b3 - b2 equals c3
  join c2 in Enumerable.Range(1, 9) on a2 * b2 equals c2
  join b1 in Enumerable.Range(1, 9) on a3 + a1 equals b1
  join c1 in Enumerable.Range(1, 9) on a3 + c3 equals c1
  where (b2 == c2 - a3)
      && (a3 == b2 * c3)
      && (a1 == b3 - 4)
  select new
  { a1, a2, a3, b1, b2, b3, c1, c2, c3};

Some explanation is required here:

The reason b2, a3, and a1 are left in the "from" portion is that there is a circular reference to that value. 

Image 4

  • b2 == c2 - a3
  • and c2 == a2 * b2
  • and a2 == a3 - b2
  • (b2 depends on c2, and c2 depends on b2)
  • (b2 depends on c2, and c2 has a2, and a2 depends on b2)

So there is no reliable way for the "join" to know what the value is therefore it must be left in the from section of the code. 

The Ordering of the Joins

Image 5

When a join is added, the values of the formula must already be known at the time (previously defined). Since c3 == b3 - b2, the value b3 and b2 must be defined before the c3 join.

Once I had this in place and the tests running, I now knew how to solve the 9x9 grid.

Using the Code 

While I was testing the proof of concept on the 3x3 grid Bob got going with the 9x9 grid brute force (or "where clause" method).

This is the result:

C#
var solveForNumbers =
    from a1 in Enumerable.Range(1, 9)
    from a2 in Enumerable.Range(1, 9)
    from a3 in Enumerable.Range(1, 9)
    from a4 in Enumerable.Range(1, 9)
    from a5 in Enumerable.Range(1, 9)
    from a6 in Enumerable.Range(1, 9)
    from a7 in Enumerable.Range(1, 9)
    from a8 in Enumerable.Range(1, 9)
    from a9 in Enumerable.Range(1, 9)
    from b1 in Enumerable.Range(1, 9)
    from b2 in Enumerable.Range(1, 9)
    from b3 in Enumerable.Range(1, 9)
    from b4 in Enumerable.Range(1, 9)
    from b5 in Enumerable.Range(1, 9)
    from b6 in Enumerable.Range(1, 9)
    from b7 in Enumerable.Range(1, 9)
    from b8 in Enumerable.Range(1, 9)
    from b9 in Enumerable.Range(1, 9)
    from c1 in Enumerable.Range(1, 9)
    from c2 in Enumerable.Range(1, 9)
    from c3 in Enumerable.Range(1, 9)
    from c4 in Enumerable.Range(1, 9)
    from c5 in Enumerable.Range(1, 9)
    from c6 in Enumerable.Range(1, 9)
    from c7 in Enumerable.Range(1, 9)
    from c8 in Enumerable.Range(1, 9)
    from c9 in Enumerable.Range(1, 9)
    from d1 in Enumerable.Range(1, 9)
    from d2 in Enumerable.Range(1, 9)
    from d3 in Enumerable.Range(1, 9)
    from d4 in Enumerable.Range(1, 9)
    from d5 in Enumerable.Range(1, 9)
    from d6 in Enumerable.Range(1, 9)
    from d7 in Enumerable.Range(1, 9)
    from d8 in Enumerable.Range(1, 9)
    from d9 in Enumerable.Range(1, 9)
    from e1 in Enumerable.Range(1, 9)
    from e2 in Enumerable.Range(1, 9)
    from e3 in Enumerable.Range(1, 9)
    from e4 in Enumerable.Range(1, 9)
    from e5 in Enumerable.Range(1, 9)
    from e6 in Enumerable.Range(1, 9)
    from e7 in Enumerable.Range(1, 9)
    from e8 in Enumerable.Range(1, 9)
    from e9 in Enumerable.Range(1, 9)
    from f1 in Enumerable.Range(1, 9)
    from f2 in Enumerable.Range(1, 9)
    from f3 in Enumerable.Range(1, 9)
    from f4 in Enumerable.Range(1, 9)
    from f5 in Enumerable.Range(1, 9)
    from f6 in Enumerable.Range(1, 9)
    from f7 in Enumerable.Range(1, 9)
    from f8 in Enumerable.Range(1, 9)
    from f9 in Enumerable.Range(1, 9)
    from g1 in Enumerable.Range(1, 9)
    from g2 in Enumerable.Range(1, 9)
    from g3 in Enumerable.Range(1, 9)
    from g4 in Enumerable.Range(1, 9)
    from g5 in Enumerable.Range(1, 9)
    from g6 in Enumerable.Range(1, 9)
    from g7 in Enumerable.Range(1, 9)
    from g8 in Enumerable.Range(1, 9)
    from g9 in Enumerable.Range(1, 9)
    from h1 in Enumerable.Range(1, 9)
    from h2 in Enumerable.Range(1, 9)
    from h3 in Enumerable.Range(1, 9)
    from h4 in Enumerable.Range(1, 9)
    from h5 in Enumerable.Range(1, 9)
    from h6 in Enumerable.Range(1, 9)
    from h7 in Enumerable.Range(1, 9)
    from h8 in Enumerable.Range(1, 9)
    from h9 in Enumerable.Range(1, 9)
    from i1 in Enumerable.Range(1, 9)
    from i2 in Enumerable.Range(1, 9)
    from i3 in Enumerable.Range(1, 9)
    from i4 in Enumerable.Range(1, 9)
    from i5 in Enumerable.Range(1, 9)
    from i6 in Enumerable.Range(1, 9)
    from i7 in Enumerable.Range(1, 9)
    from i8 in Enumerable.Range(1, 9)
    from i9 in Enumerable.Range(1, 9)
    where (a1 == e5 * e8)
	&& (a2 == h1 - 2)
	&& (a3 == c5 * e8)
	&& (a4 == h9 - 1)
	&& (a5 == d7 - e2)
	&& (a6 == f1 + g7)
	&& (a7 == e3 - h2)
	&& (a8 == h6 + a9)
	&& (a9 == g3 / g6)
	&& (b1 == d1 - a9)
	&& (b2 == g2 - h1)
	&& (b3 == e5 - 4)
	&& (b4 == c7 + 1)
	&& (b5 == d7 - 7)
	&& (b6 == i5 + d6)
	&& (b7 == f8 + 1)
	&& (b8 == a1 / i5)
	&& (b9 == g3 + 3)
	&& (c1 == i2 * a7)
	&& (c2 == b4 * a7)
	&& (c3 == c6 + 6)
	&& (c4 == a2 * f5)
	&& (c5 == c6 + 7)
	&& (c6 == f8 - i3)
	&& (c7 == d6 - 1)
	&& (c8 == h8 + 1)
	&& (c9 == g4 / c1)
	&& (d1 == a7 * 3)
	&& (d2 == i3 + a7)
	&& (d3 == c2 - e2)
	&& (d4 == f4 * i2)
	&& (d5 == c4 + 2)
	&& (d6 == h9 * e8)
	&& (d7 == c4 * a2)
	&& (d8 == d1 - a7)
	&& (d9 == c1 * d4)
	&& (e1 == i1 - e3)
	&& (e2 == e3 + 3)
	&& (e3 == d1 - g9)
	&& (e4 == f1 + d1)
	&& (e5 == d1 * 3)
	&& (e6 == a5 + 4)
	&& (e7 == g6 * h7)
	&& (e8 == d9 - 7)
	&& (e9 == i3 / e3)
	&& (f1 == a3 / i2)
	&& (f2 == b7 * e8)
	&& (f3 == b6 * d3)
	&& (f4 == h2 + 1)
	&& (f5 == d1 - 2)
	&& (f6 == g5 / b5)
	&& (f7 == e3 * h3)
	&& (f8 == h2 + h9)
	&& (f9 == i1 - 3)
	&& (g1 == c5 - f5)
	&& (g2 == a6 + 2)
	&& (g3 == e6 / a9)
	&& (g4 == e8 + 7)
	&& (g5 == d6 * a7)
	&& (g6 == b1 + 1)
	&& (g7 == h1 - 2)
	&& (g8 == h5 - f4)
	&& (g9 == a8 - a4)
	&& (h1 == d2 - i2)
	&& (h2 == h4 / i9)
	&& (h3 == c7 - 2)
	&& (h4 == f9 + 4)
	&& (h5 == h2 + 6)
	&& (h6 == d8 * 2)
	&& (h7 == h1 - e9)
	&& (h8 == f5 + 7)
	&& (h9 == a1 - b8)
	&& (i1 == f3 - b1)
	&& (i2 == c9 / h7)
	&& (i3 == i1 - c1)
	&& (i4 == a6 - 6)
	&& (i5 == d5 - d8)
	&& (i6 == f6 + 2)
	&& (i7 == c7 + 2)
	&& (i8 == e3 + i2)
	&& (i9 == f6 * g7)
    select new
    {
	a1,a2,a3,a4,a5,a6,a7,a8,a9,
	b1,b2,b3,b4,b5,b6,b7,b8,b9,
	c1,c2,c3,c4,c5,c6,c7,c8,c9,
	d1,d2,d3,d4,d5,d6,d7,d8,d9,
	e1,e2,e3,e4,e5,e6,e7,e8,e9,
	f1,f2,f3,f4,f5,f6,f7,f8,f9,
	g1,g2,g3,g4,g5,g6,g7,g8,g9,
	h1,h2,h3,h4,h5,h6,h7,h8,h9,
	i1,i2,i3,i4,i5,i6,i7,i8,i9
    };  

This brute force method will take a heck of a long time to get the final answer.

I ran it for an hour and the results at that point were only:

  • a1 to h9 all 1s and
  • i1=1, i3=1, i2=1, i4=1, i5=5, i6=1, i7=5, i8=5, i9=7

That is just over 33 000 iterations.

I took this code home and then over 4 hours of re-factoring the "where" clauses into "joins", and then re-ordering the joins, I got to this code:

C#
var solveForNumbers =
    from i2 in Enumerable.Range(1, 9)
    from i5 in Enumerable.Range(1, 9)
    from h2 in Enumerable.Range(1, 9)
    from e3 in Enumerable.Range(1, 9)
    from a9 in Enumerable.Range(1, 9)
    join a7 in Enumerable.Range(1, 9) on e3 - h2 equals a7
    join d1 in Enumerable.Range(1, 9) on a7 * 3 equals d1
    join b1 in Enumerable.Range(1, 9) on d1 - a9 equals b1
    join g6 in Enumerable.Range(1, 9) on b1 + 1 equals g6
    join d8 in Enumerable.Range(1, 9) on d1 - a7 equals d8
    join h6 in Enumerable.Range(1, 9) on d8 * 2 equals h6
    join a8 in Enumerable.Range(1, 9) on h6 + a9 equals a8
    join e5 in Enumerable.Range(1, 9) on d1 * 3 equals e5
    join b3 in Enumerable.Range(1, 9) on e5 - 4 equals b3
    join f5 in Enumerable.Range(1, 9) on d1 - 2 equals f5
    join h8 in Enumerable.Range(1, 9) on f5 + 7 equals h8
    join c8 in Enumerable.Range(1, 9) on h8 + 1 equals c8
    join c1 in Enumerable.Range(1, 9) on i2 * a7 equals c1
    join e2 in Enumerable.Range(1, 9) on e3 + 3 equals e2
    join i8 in Enumerable.Range(1, 9) on e3 + i2 equals i8
    join h5 in Enumerable.Range(1, 9) on h2 + 6 equals h5
    join f4 in Enumerable.Range(1, 9) on h2 + 1 equals f4
    join d4 in Enumerable.Range(1, 9) on f4 * i2 equals d4
    join d9 in Enumerable.Range(1, 9) on c1 * d4 equals d9
    join e8 in Enumerable.Range(1, 9) on d9 - 7 equals e8
    join a1 in Enumerable.Range(1, 9) on e5 * e8 equals a1
    join b8 in Enumerable.Range(1, 9) on a1 / i5 equals b8
    join h9 in Enumerable.Range(1, 9) on a1 - b8 equals h9
    join a4 in Enumerable.Range(1, 9) on h9 - 1 equals a4
    join g9 in Enumerable.Range(1, 9) on a8 - a4 equals g9
    join f8 in Enumerable.Range(1, 9) on h2 + h9 equals f8
    join b7 in Enumerable.Range(1, 9) on f8 + 1 equals b7
    join d6 in Enumerable.Range(1, 9) on h9 * e8 equals d6
    join b6 in Enumerable.Range(1, 9) on i5 + d6 equals b6
    join c7 in Enumerable.Range(1, 9) on d6 - 1 equals c7
    join b4 in Enumerable.Range(1, 9) on c7 + 1 equals b4
    join c2 in Enumerable.Range(1, 9) on b4 * a7 equals c2
    join d3 in Enumerable.Range(1, 9) on c2 - e2 equals d3
    join f3 in Enumerable.Range(1, 9) on b6 * d3 equals f3
    join i1 in Enumerable.Range(1, 9) on f3 - b1 equals i1
    join e1 in Enumerable.Range(1, 9) on i1 - e3 equals e1
    join f9 in Enumerable.Range(1, 9) on i1 - 3 equals f9
    join h4 in Enumerable.Range(1, 9) on f9 + 4 equals h4
    join i3 in Enumerable.Range(1, 9) on i1 - c1 equals i3
    join c6 in Enumerable.Range(1, 9) on f8 - i3 equals c6
    join c3 in Enumerable.Range(1, 9) on c6 + 6 equals c3
    join c5 in Enumerable.Range(1, 9) on c6 + 7 equals c5
    join g1 in Enumerable.Range(1, 9) on c5 - f5 equals g1
    join a3 in Enumerable.Range(1, 9) on c5 * e8 equals a3
    join f1 in Enumerable.Range(1, 9) on a3 / i2 equals f1
    join e4 in Enumerable.Range(1, 9) on f1 + d1 equals e4
    join d2 in Enumerable.Range(1, 9) on i3 + a7 equals d2
    join h1 in Enumerable.Range(1, 9) on d2 - i2 equals h1
    join g7 in Enumerable.Range(1, 9) on h1 - 2 equals g7
    join a6 in Enumerable.Range(1, 9) on f1 + g7 equals a6
    join a2 in Enumerable.Range(1, 9) on h1 - 2 equals a2
    join c4 in Enumerable.Range(1, 9) on a2 * f5 equals c4
    join d5 in Enumerable.Range(1, 9) on c4 + 2 equals d5
    join d7 in Enumerable.Range(1, 9) on c4 * a2 equals d7
    join a5 in Enumerable.Range(1, 9) on d7 - e2 equals a5
    join i4 in Enumerable.Range(1, 9) on a6 - 6 equals i4
    join g2 in Enumerable.Range(1, 9) on a6 + 2 equals g2
    join b2 in Enumerable.Range(1, 9) on g2 - h1 equals b2
    join e6 in Enumerable.Range(1, 9) on a5 + 4 equals e6
    join g3 in Enumerable.Range(1, 9) on e6 / a9 equals g3
    join b9 in Enumerable.Range(1, 9) on g3 + 3 equals b9
    join b5 in Enumerable.Range(1, 9) on d7 - 7 equals b5
    join e9 in Enumerable.Range(1, 9) on i3 / e3 equals e9
    join h7 in Enumerable.Range(1, 9) on h1 - e9 equals h7
    join e7 in Enumerable.Range(1, 9) on g6 * h7 equals e7
    join i7 in Enumerable.Range(1, 9) on c7 + 2 equals i7
    join g5 in Enumerable.Range(1, 9) on d6 * a7 equals g5
    join f6 in Enumerable.Range(1, 9) on g5 / b5 equals f6
    join i9 in Enumerable.Range(1, 9) on f6 * g7 equals i9
    join i6 in Enumerable.Range(1, 9) on f6 + 2 equals i6
    join h3 in Enumerable.Range(1, 9) on c7 - 2 equals h3
    join f7 in Enumerable.Range(1, 9) on e3 * h3 equals f7
    join f2 in Enumerable.Range(1, 9) on b7 * e8 equals f2
    join g4 in Enumerable.Range(1, 9) on e8 + 7 equals g4
    join c9 in Enumerable.Range(1, 9) on g4 / c1 equals c9
    join g8 in Enumerable.Range(1, 9) on h5 - f4 equals g8
    where
	(e3 == d1 - g9) &&
	(a9 == g3 / g6) &&
	(h2 == h4 / i9) &&
	(i2 == c9 / h7) &&
	(i5 == d5 - d8)
    select new
	{
	    a1, a2, a3, a4, a5, a6, a7, a8, a9,
	    b1, b2, b3, b4, b5, b6, b7, b8, b9,
	    c1, c2, c3, c4, c5, c6, c7, c8, c9,
	    d1, d2, d3, d4, d5, d6, d7, d8, d9,
	    e1, e2, e3, e4, e5, e6, e7, e8, e9,
	    f1, f2, f3, f4, f5, f6, f7, f8, f9,
	    g1, g2, g3, g4, g5, g6, g7, g8, g9,
	    h1, h2, h3, h4, h5, h6, h7, h8, h9,
	    i1, i2, i3, i4, i5, i6, i7, i8, i9
	};

I ran the code and then the answer was calculated in a mere 8 seconds.

Conclusion 

  1. LINQ can be used to solve different types of puzzles.
  2. Using joins greatly reduces the time spent to find the answer.
  3. Formulas in the sheet which refer back to themselves cannot be added to a join, and can only be used in the "from" section. This means the LINQ query must *guess* these values. The fewer guesses there are, the faster the answer will be calculated.

Points of Interest

It was fun solving the puzzle using LINQ, but it took about 8 hours of my time. Solving the puzzle using paper only would have been somewhat quicker.

History

  • Fixed the type highlighted by SoMad

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
South Africa South Africa
Dutch, married, father of 3, work in IT, love geocaching, riding motorbike on and off road, taking photos, taking/editing of video, and programming.

From Edenvale,
South Africa

Comments and Discussions

 
BugTypo. Pin
SoMad31-May-13 13:13
professionalSoMad31-May-13 13:13 
GeneralRe: Typo. Pin
Anton Damhuis31-May-13 19:20
Anton Damhuis31-May-13 19:20 
GeneralMy vote of 5 Pin
SoMad31-May-13 13:08
professionalSoMad31-May-13 13:08 
I love stuff like this, but I am wondering if in your effort to optimize it, you went past the point where you could have made it more generic instead of fixed to a single puzzle.

I wanted to vote 4 because I think you can improve it, but it made me think about some things and kept me awake a few hours last night. Because of that, here is my 5.

Soren Madsen

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.