[deleted]
Can Neural Networks Crack Sudoku?
41–50 of 111 posts
Re: Can Neural Networks Crack Sudoku?
#42So much missing-the-point in this thread. The point isn't "can we solve sudoku with a completely over-wrought solution", it's "can NN be applied to X class of problems with no human-added domain specific knowledge". And that I think is quite cool.
Re: Can Neural Networks Crack Sudoku?
#43That looks interesting. Sudoku is a fairly useful constraint satisfaction problem/testbed to test neural networks architectures on, since the most general version of sudoku is NP-complete. There was some interesting work a while ago that solved sudoku using spiking neural networks too [1] (Fig. 5) with some nice associated theory. [1] http://journals.plos.org/ploscompbiol/article?id=10.1371/jou...
I thought Sudoku can be solved in constant time. It would be a O(9! * 9! ) or something, which is just a O(1), isn't it?
"For the most general version of Sudoku" -- post doesn't detail what "general" means, but if the variable is board size, then it's O(N! * N!).
Re: Can Neural Networks Crack Sudoku?
#44If the wet ones can, I don't see why the ones of an arbitrary size made out of bits can't. Not a very good argument, but there's this: recurrent neural networks are Turing complete.
Humans don't learn how to play Sudoku by staring at a bunch of solved puzzles. We are given the rules up front.
Re: Can Neural Networks Crack Sudoku?
#45Earlier quoted context omitted.
There are no easy way to solve SAT as the size of sudoku. Modern day SAT solvers are very large and contains years of experience, containing 10s of heuristics and complex structures. If we can simplify using neural network, I think it's a great step.
Well, it is really more of a exact cover problem, which can be solved quite simply and elegantly with Knuth's algorithm X. A neural network isn't simpler in any sense of the word. You might as well throw a simulated annealer at the problem.
I am not saying it is not. My condition is in what if neural network can solve a problem without any domain knowledge. I think it's a huge win even if we don't understand anything about the solution. Be it well solved problems like approximate minimum distance in a graph to practically unsolvable like automatically proving unproved theorems in mathematics.
Re: Can Neural Networks Crack Sudoku?
#46Earlier quoted context omitted.
There are no easy way to solve SAT as the size of sudoku. Modern day SAT solvers are very large and contains years of experience, containing 10s of heuristics and complex structures. If we can simplify using neural network, I think it's a great step.
Reasonably modern SAT solvers (Say MiniSAT) have a lot less complexity than a modern neural network. Also, I set as a intro to C practical writing a SAT solver which can easily solve any real-world Sudoku instance.
Are you serious.. SAT solvers have some of the hardest code I have seen. Look at the SAT solvers that won satcompetition. On the other hand IMO, implementing a neural network on your own is very easy. But the point is not that. I consider the neural network libraries(e.g. tensorflow) as given, as it is in not related to the problem, and can be used in many different problems. I will consider only the code above the neural network API for the complexity(like models, encoding etc.). But a SAT solver has a specific function and is core part of the problems it is trying to solve.
Re: Can Neural Networks Crack Sudoku?
#47Earlier quoted context omitted.
Well, it is really more of a exact cover problem, which can be solved quite simply and elegantly with Knuth's algorithm X. A neural network isn't simpler in any sense of the word. You might as well throw a simulated annealer at the problem.
I am not saying it is not. My condition is in what if neural network can solve a problem without any domain knowledge. I think it's a huge win even if we don't understand anything about the solution. Be it well solved problems like approximate minimum distance in a graph to practically unsolvable like automatically proving unproved theorems in mathematics.
None of the alternatives I proposed require domain knowledge, they just require you to state the sudoku rules, which is inevitable.
Re: Can Neural Networks Crack Sudoku?
#48It's a fascinating subject. Worth reading this entry for more details:
https://en.wikipedia.org/wiki/Sudoku_solving_algorithms
And apparently quantum computers can solve them using sheer brute force alone, but these articles don't go into enough detail (i.e: can they solve the 'evil' puzzles?)
https://www.engadget.com/2007/02/14/worlds-first-commercial-...
https://www.scientificamerican.com/article/first-commercial-...
Re: Can Neural Networks Crack Sudoku?
#49You can solve sudoku with a SAT solver. You don't need neural networks, this was an assignment in cs 251 at UIC.
Indeed! Here is Sudoku, formulated as a SAT problem. You can use for example SICStus Prolog to run it:
sudoku(Rows) :-
length(Rows, 9), maplist(same_length(Rows), Rows),
maplist(row_booleans, Rows, BRows),
maplist(booleans_distinct, BRows),
transpose(BRows, BColumns),
maplist(booleans_distinct, BColumns),
BRows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is).
blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
booleans_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
blocks(Ns1, Ns2, Ns3).
booleans_distinct(Bs) :-
transpose(Bs, Ts),
maplist(card1, Ts).
card1(Bs) :- sat(card([1],Bs)).
row_booleans(Row, Bs) :-
same_length(Row, Bs),
maplist(cell_boolean, Row, Bs).
cell_boolean(Num, Bs) :-
length(Bs, 9),
sat(card([1],Bs)),
element(Num, Bs, 1).
Here is an example Soduku problem, taken from Donald Knuth's The Art of Computer Programming:
knuth(b, [[1,_,3,_,5,6,_,8,9],
[5,9,7,3,8,_,6,1,_],
[6,8,_,1,_,9,3,_,5],
[9,5,6,_,3,1,8,_,7],
[_,3,1,5,_,8,9,6,_],
[2,_,8,9,6,_,1,5,3],
[8,_,9,6,_,5,_,3,1],
[_,6,5,_,1,3,2,9,8],
[3,1,_,8,9,_,5,_,6]]).
?- knuth(b, Rows),
sudoku(Rows),
maplist(portray_clause, Rows).
[1, 2, 3, 4, 5, 6, 7, 8, 9].
[5, 9, 7, 3, 8, 2, 6, 1, 4].
[6, 8, 4, 1, 7, 9, 3, 2, 5].
[9, 5, 6, 2, 3, 1, 8, 4, 7].
[7, 3, 1, 5, 4, 8, 9, 6, 2].
[2, 4, 8, 9, 6, 7, 1, 5, 3].
[8, 7, 9, 6, 2, 5, 4, 3, 1].
[4, 6, 5, 7, 1, 3, 2, 9, 8].
[3, 1, 2, 8, 9, 4, 5, 7, 6].Re: Can Neural Networks Crack Sudoku?
#50Earlier quoted context omitted.
Well, it is really more of a exact cover problem, which can be solved quite simply and elegantly with Knuth's algorithm X. A neural network isn't simpler in any sense of the word. You might as well throw a simulated annealer at the problem.
I am not saying it is not. My condition is in what if neural network can solve a problem without any domain knowledge. I think it's a huge win even if we don't understand anything about the solution. Be it well solved problems like approximate minimum distance in a graph to practically unsolvable like automatically proving unproved theorems in mathematics.
I take it this way. How many problems can you solve using knowing mostly exact cover. Not very many. But, if we can build ML systems that can solve mostly any problem(we can't today) even without giving any insight, I would say it will be one of the things whose impact will surpass anything. Note, I am not getting into AGI, just saying a system that can solve objective problems. And while sudoku is not a very good example, but I think it shows we can do many cool things from neural networks. Neural networks are the most sure bet for such a system.