The New Sudoku Players' Forum

[Maq777]

Regards,

my question is, someone has considered an approach to solving sudokus from an artificial neural network

Thank you.

[Maq777]

The main idea would be to create a Convolutional Neural Network capable of solving any 9x9 Sudoku problem that arises ... with a degree of accuracy of 100% ...

The restriction satisfaction approach works very well for a backtraking procedure, but it is not ideal to solve Any sudoku problem from the point of view of Neural Networks, for that you need another approach, another approach and that is what that I think I have

At a more basic level we are faced with the problem of P vs NP, solutions that see the problem as "Satisfaction of Constraints" are doomed to failure in what we move to higher order sudokus ... What I propose is something that can serve for the 9x9 and then be able to expand it to the 16x16 and more ...

I have already designed the architecture of the Network that is needed to solve the problem ... what I need is someone with enough knowledge in neural networks so that I can implement and test it

I do not know how to handle well with the tools to implement an RN, all my knowledge on the subject is self-taught, I know that there are people who are very fast using TensorFlow or Keras to do the implementation, that "Know How" is what I am requesting help...

My contributions would be: The set or Data Set necessary to train the neural network, the design of the network architecture and the extensive knowledge I have about the elements that make up sudoku as well as their way of relating ...

This man set up a repository on Github with a Neural Network that solves Sudokus.

https://towardsdatascience.com/solving-sudoku-with-convolution-neural-network-keras-655ba4be3b11

In the readme and on the blog there is data about the project. Unfortunately, it was not 100% accurate.

Although I think he did an excellent job, I think he lacked depth

What I propose is a "Serious" attempt to solve the "Sudoku" problem, I have been researching the subject for more than seven (7) years

Basically you have to be able to hold on against this ... 216x216 templates...

https://github.com/MiguelQuinteiro/ImagenesSudoku/blob/master/MegaSudoku.jpg

The other fundamental part that can differentiate this from other similar projects is that from the beginning the Neural Network should not be trained to solve Sudoku problems as if it were a "Brute Force" algorithm, for that we already have algorithms that they can "branch and prune" in a heuristic way and then run a brute force type or bactraking on a fairly small subset, which solves just about any sudoku problem in a few nanoseconds ...

What it is about here is that the architecture that we generate is one that can distinguish between Erroneous Sudoku, Ambiguous Sudoku or Well Planted Sudoku. In such a way that the RN is forced to try to solve Sudoku as part of a somewhat more complex task.

Most of the brute force algorithms that solve sudoku find a situation and if they can fill it in by completing all the empty boxes and if they succeed they stop and give it as a solved sudoku puzzle, but in reality they cannot be sure that it is. that they solved was a sudoku puzzle unless they try to find a second solution and cannot find it ....

Best Regards

[m_b_metcalf]

Most of the brute force algorithms that solve sudoku find a situation and if they can fill it in by completing all the empty boxes and if they succeed they stop and give it as a solved sudoku puzzle, but in reality they cannot be sure that it is. that they solved was a sudoku puzzle unless they try to find a second solution and cannot find it ....

Are you sure about that? I think that, in this neck of the woods, most brute force solvers do look for a second solution (and hope not to find one). How can you possibly generate correct puzzles otherwise?

Regards,

Mike Metcalf

[Maq777]

Here are three examples of what I say.

The first was a video that I saw of how to do to solve sudokus, in the end it is evident that what they are solving is an ambiguous case.

https://www.youtube.com/watch?v=Mfb4CQIoW5s

The second is a very good brute force development that solves sudoku puzzles in microseconds, but doesn't check for a second solution, so you don't know if what it solved was really a sudoku puzzle.

https://www.youtube.com/watch?v=H03E8_HImAU

and The third is a solver developed in Visual basic, very good at completing grids, but it does not check whether the completed situation is ambiguous or not.

https://www.youtube.com/watch?v=ltYyKxsyQaA

And I agree with you, true sudoku problem generators check very well if they have two or more solutions before they deliver the puzzle.

[Pupp]

I think if a puzzle has more than a single solution then you'd find the flaw using trivial techniques.

I'm not sure it's possible to create sudoku puzzies much harder than currently available without creating a new logic technique.

I don't keep up with the hardest sudoku puzzle thread, but last I checked, a normal "hardest" sudoku (not a varient), tops out at about 11.9 SE.

Perhaps it would be a better goal of creating an AI program that can create a new sudoku puzzle with a new technique that is even harder that nested (dynamic?) forcing chains. It's unlikely to succeed, though.

[dobrichev]

[Pupp]

A random thought here:

Because Sudoku is a game of pure logic, I think it would be a waste of time and energy to create an arificial intelligence program to solve sudoku puzzles

[Maq777]

And what would you say about chess and AlphaZero, it seems to me that chess is also a game of pure logic and now nobody plays it better than Artificial Intelligence.

[RSW]

Neural nets are a subset of AI. So, when one says that something uses AI, it doesn't necessarily mean that it uses neural nets. Neural nets are good at recognizing patterns. As for using neural nets for solving pure logic problems, I don't really see the benefit of using a pattern matcher.

The first chess programs used what is known as the minimax algorithm with alpha-beta tree pruning, which works well for extremely complex logic games where the number of game situations grows exponentially for each move ahead that needs to be checked. I believe that the same algorithm is still used in chess. The main difference is that the computers are immensely faster and therefore can look ahead many more moves.

[999_Springs]

sudoku is too deterministic. no ML or AI based algorithm can ever prove anything, it only does a "best guess". no human player would ever accept a computer's solution path to a sudoku that begins with "we think r3c8 = 6 with 90% probability", which is what AI based methods would tell you. this probabilistic logic is acceptable in chess, which is why top-level chess programs are implementing some ML based methods these days.

the only case in which this would be acceptable for sudoku is if you get a significant speed-up and you are in a situation where this time save is important (like with minimax in chess, as RSW said), but seeing as sudoku solvers can be very fast, i don't see this happening.

some of the more subjective elements of sudoku, such as how to rate a puzzle's difficulty for a human player, could in principle i suppose be done with ML, but a major problem with this is that ML based methods generally find it difficult to explain why a puzzle got that rating, compared to a rating system that is based off the hardest step needed to solve the puzzle and can tell you what that step was. so it may be hard to understand whether your rating was what you really wanted.

if you had some kind of a 2 player sudoku game where you take turns to put a number in a blank solution grid, with some win condition, then AI based methods would be very good for that. i think i remember getting one of those as a Christmas present in 2006 or 7 or 8 - i don't remember the details but it was a 2 player turn-based physical sudoku board game with plastic board and pieces, from a children's toy shop

[RSW]

I have already designed the architecture of the Network that is needed to solve the problem ... what I need is someone with enough knowledge in neural networks so that I can implement and test it

Perhaps you could explain this architecture that you've designed, and how you did it without having the knowledge to implement it.

[denis_berthier]

sudoku is too deterministic. no ML or AI based algorithm can ever prove anything, it only does a "best guess".

Neural nets are a subset of AI. So, when one says that something uses AI, it doesn't necessarily mean that it uses neural nets. Neural nets are good at recognizing patterns. As for using neural nets for solving pure logic problems, I don't really see the benefit of using a pattern matcher

Just a matter of vocabulary.
ML is indeed a subset of AI. The original part of AI is "symbolic AI".
Both ML and symbolic AI have their own notion of pattern-matching, but these notions are very different. In "symbolic AI" a pattern is (roughly speaking) a First-Order-Logic formula in the language of the application with free variables (that are to be matched by constants in any instantiation of the pattern).

A typical tool of symbolic AI is an inference engine, whose main part is a (symbolic) pattern-matcher.
My CSP-Rules solver (and its SudoRules part) is based on symbolic pattern-matching (as implemented in the CLIPS inference engine). One can say that the rules (e.g. the resolution rules of Sudoku) are the program (and the inference engine is the high-level compiler).

Because Sudoku is a game of pure logic, I think it would be a waste of time and energy to create an arificial intelligence program to solve sudoku puzzles

Just a too narrow view of AI.



Apart from this, I agree that neural nets are not the right tool for solving pure logic problems.