AI taught to beat Sudoku puzzles. Now how about a time machine to 2005?

AI can now solve some of the hardest Sudoku puzzles to a high degree of accuracy, according to new research that teaches machines to logically reason. Sudoku was, if you can recall, all the rage in the West at least a decade ago. Sure, there are computational algorithms to crack the puzzles within a second, however, it’s an …

Sudoku?

It's not a game.

There is no strategy.

It's the typical sort of problem that computers are good at (should be perfect at) and that humans find difficult.

Since about 2004 the puzzles are computer generated.

It's probably a Western invention, the article may have errors.

I'm puzzled why it is "to a high degree of accuracy" not perfect. Maybe a more defined in advance algorithm than a trained "neural net" would be better. At least the training input doesn't need to be human curated, just use the Sudoku generation program! It's unlikely to be an example of AI reasoning.

How good is it up to 9 x 9 (easy by a conventional algorithm) and how does it manage 12 x 12?

It's all well and good for an AI to solve Sudoku

But can it:

1) Explain the whys and wherefores

2) Enjoy the process

https://www.theguardian.com/lifeandstyle/2017/dec/01/sudoku-3920-hard

Reasoning?

I wouldn't call sudoku an exercise for "complex reasoning", since you can't reason with sudoku to get a solution (It'll defeat you with complex logic).

Been there done that

My automated python suduko solver does this using a combination of simple techniques and clone, guess and exclude in about 400 lines of source code. Haven't found a suduko it can't solve. Will link the source code if anyone's interested enough.

Re: Been there done that

Me Too. 2516 lines of C# code including an MIT expat open source license. Downloadable from my website.

Re: Been there done that

Same here -- used Sudoku to learn how to use a constraint programming library. Also used neural networks to classify images and time series. Can't see the advantage in using neural networks to solve Sudokus unless the purpose is to brag about "using neural networks to solve Sudokus".

I also seem to recall that either a Sudoku is solvable with 100% "accuracy" or it has more than one solution. It is possible to devise Sudokus that have only one solution and as few clues as possible (17: https://www.technologyreview.com/s/426554/mathematicians-solve-minimum-sudoku-problem/)

Re: Been there done that

I think the 'breakthrough' here is using RN to do it rather than the bleeding obvious. Which, TBH, is what AI will need to do a lot of the time.

Re: Been there done that

Yeah the fact it can be brute forced isn't the issue. It can obviously be brute forced. The trick is to solve in a way analogous to a human being and not brute forcing it.

Re: Been there done that

Is that not how you are supposed to solve Soduku puzzles?

Re: The trick is to solve in a way analogous to a human being

Except NO so called "computer AI" or so called "Neural net" is analogous to human reasoning.

Re: Been there done that

383 lines of C that I was going to convert to Verilog when I'm next between contracts. Was going to put it on an FPGA demo board with DVI in and out. Could have been put between a PC and a monitor to fill in sudokus on web pages as you browse the web.

Re: Been there done that

I think that's always been a matter of contention. If you need to hypothesize a number in a cell and then follow a chain that's 7-8 cells long, is that an acceptable logical way of solving things, or does this count as trial and error and therefore not such a logical way of getting to the solution?

Re: Been there done that

> If you need to hypothesize a number in a cell and then follow a chain that's 7-8 cells long, is that an acceptable logical way of solving things, or does this count as trial and error and therefore not such a logical way of getting to the solution?

Having been there and done that myself, I find it necessary to follow one *or more* such chains and seeing if the consequences a) rule out all the candidates from some cell, b) force more than one of a particular digit into row/column/other group, c) contradict the implications of another such chain, or d) force the puzzle to have multiple solutions with what the article suggests this algorithm would conclude has "equal" "probability".

After much thought, I have concluded these are reasonable steps based on the puzzle and its description and do not think they're trial and error at all (but in line with earlier commentary [Dave Cartwright article] I can see why you'd use such phrase/s for simplicity).

Colour me a slight tinge of underwhelmed....

When deep blue beat Kasparov, I was kinda impressed. Things that can solve suduko? A little bit 'meh' I'm afraid. As long as AI does not replace Rachel Riley, I'm happy.

Re: Colour me a slight tinge of underwhelmed....

I don't know - quite a few people are obsessed with her bot.

( has any non 1970s parent ever used the word "bot" for "bottom"? )

It feels like a lot of people are missing the point here - The achievement isn't that a computer can solve a sudoku, it's that a computer can learn to solve a sudoku without pre-programmed sudoku-solving algorithms.

But then, this is El Reg so we are all strong in the Cynic.

@ArrZarr

While you're right about the fact its learning from scratch its worth pointing out that there are many problem solving (well search algorithms really) that can solve sodoku with merely a list of rules. Even a simple program can use CSP (constraint satisfaction problem) to solve sudoku from the simple restrictions of 1-9 on a row and 1-9 in a 3*3 block - I had one on a pi zero that would solve it the moment you put in the last number required to solve it and if I could be arsed it could be modified to run on https://sourceforge.net/projects/gnusim8085/ if you upped the memory to 32k.

Doubleplusunimpressed

a computer can learn to solve a sudoku without pre-programmed sudoku-solving algorithms

Sorry, still not impressed -- I would be if the computer was taught to solve a problem for which there is no efficient or known algorithms, or that can beat those in speed or any other metric. Otherwise it is an interesting application, but not an impressive one. And I still don't buy that "accuracy" measure.

Disclaimer: I use NNs for classification and regression of moderately complex data, and still enjoy Sudoku (prefere KenKen, but...)

without pre-programmed sudoku-solving algorithms

It's not. Any neural net does nothing till it's "trained" with curated data. It's just a different sort of pre-programming. No AI able to recognise hotdogs can solve sudoku without human "training".

It's ultimately a fraud. Ignore the humans behind the curtains that set it up.

Re: without pre-programmed sudoku-solving algorithms

"It's ultimately a fraud. Ignore the humans behind the curtains that set it up."

Nailed it!

Product of the AI hype

Considering that Sudoku is fairly simple to solve by a computer.

Have a bitfield for every field. (9 bits)

1. Set all bits to 1

2. For the fields with clue n, set all bits to 0 except for the n-th

3. Reset the n-th bit of all fields related to clue n

4. If while doing 3 one field has only one bit set, see it as a clue and continue with 3

5. If there are no new clues, select one field with the lowest number of bits set.

6. Loop through all possible solutions for that field and recursively set it as a clue

7. If there are no fields with more than 1 set bit left, output solution

This simple 7 step sketch will give you all possible solutions to a given Sudoku. The Bitfield easily fits on the stack, making it possible to simply copy the whole field for the recursive step 6. (the step where you try out several possibilities) It may give you the same solution multiple times, but that's easy to fix with sort and uniq.

Of course doing it with neural networks is an interresting idea, but not really usefull if you want to have results.

Re: Product of the AI hype

I bet this could be adapted for fun: https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

Re: Product of the AI hype

Re: Algorithm X (Dancing Links). I've already done it a few years ago :-)

Re: Product of the AI hype

@Cowboy Bob: awesome! Have an upvote.

Not a number puzzle

The article keeps on referring to Sudoku as a number puzzle. It's not really a number puzzle - it would work just as well with letters, or shapes, or colours.

This isn't new

A group of us put together a computer program back in 2003 when I was a computer engineering student to do this.

The processing operation isn't much different from those used to crack passwords. Mathematics and tossing in stored data into entry points is what computers excel at.

Thinking this is new, is pretty boring and lazy reporting.

Re: This isn't new

I don't think you have actually read the article fully

Brute force or logic?

I often do the Sunday Times 'Very Hard' Sudoku and most weeks I can work it out by reasoning, but about 30% of the time I get stuck (The on line solvers I've tried also can't solve them) I then look for an 'X' must be 'here or there'' and try that.

I do wonder if sometimes they are only solvable by brute force. This paper doesn't seem to answer that question.

Author here

Hey. Rasmus, author of the paper here. I'm glad you're all interested in my work :)

I just want to comment that you're correct that solving Sudokus with a computer is in itself not very interesting. It's been done a hundred times over, and almost all of the algorithms are superior to the RRN in almost every respect (simpler, faster, more accurate, etc.).

But, the RRN can do one thing the original methods cannot: it can interface with other deep learning models and be trained end-to-end. That means it can be added to e.g. a convolutional neural network and the combined model can be trained together to, e.g. reason about an image. The original Deepmind paper shows how to do this. Since they showed how to do the interfacing part, we focused solely on improving the "reasoning" aspect. We picked Sudoku since it requires an order of magnitude more steps of reasoning than the problems in the Deepmind paper. It's simply a test-bed to show how to solve "complex" reasoning problems (complex compared to the previous work in the area). We don't care about solving Sudokus in and of itself. I tried to make this clear in the paper, but it wasn't really picked up in this story.

"Solving Sudokus computationally is in itself not a very laudable goal, as traditional symbolic and hand-crafted algorithms like constraint propagation and search can solve any Sudoku in fractions of a second. For a good explanation and code, see Norvig (2006). Many other symbolic algorithms exist that can also solve Sudokus, like dancing links (Knuth, 2000) and integer programming. These algorithms are superior in almost every respect but one: they don’t comply with the interface, as they don’t operate on a set of vectors, and they’re not differentiable. As such they cannot be used in a combined model with a deep learning perceptual front-end."

Now there's one "traditional" "general purpose" algorithm that I know of that also work on real valued vectors and is differentiable, which is loopy belief propagation. We compared the trained RRN to this algorithm and found that the RRN learned a better algorithm, solving 96.6% vs. 92.5% of the hardest (17 givens) Sudokus. This version of loopy belief propagation was heavily modified for solving Sudokus. A more standard implementation solved 61.7%. Given the widespread use of loopy belief propagation it's exciting to wonder how many more applications could benefit from replacing the loopy BP with a trained RRN. Now, the RRN is a lot more complex, requires many more flops than loopy BP, and requires training, etc. so it's not a clear cut, search and replace job.

Best,

Rasmus

Re: rasmusbergpalm

"We don't care about solving Sudokus in and of itself. I tried to make this clear in the paper, but it wasn't really picked up in this story."

Thanks for commenting! But ahem, ahem ;-) It's all over the story that this is more than cracking Sudoku. We wrote:

> it’s an interesting problem for deep-learning software to tackle, as it's an exercise for neural networks to practice complex reasoning.

[...]

> Although the recurrent RN is pretty good at cracking Sudoku puzzles, it’s designed to be a general purpose module that can be added to different types neural network models so that it can perform many-step relational reasoning.

>

> It’s still early stages and the applications have yet to be explored. It’s an important area for machines since logical reasoning is key to making them smarter in the future.

Congrats on the cool research. We made it clear this is more than breaking Sudoku. If you're put off by the sarcastic title, well, them's the breaks around here.

C.

Re: rasmusbergpalm

Yea, that wasn't really a fair assertion on my part. It's actually fairly well described in the story.

Of course ...

It is simple to write code that solves Sudoku.

It's just embarrassing to read ppl posting just that here.

It just makes it so obvious that you have missed the point on what the article is about.

POST COMMENT House rules

Not a member of The Register? Create a new account here.