Hodoko rating system question

Programs which generate, solve, and analyze Sudoku puzzles

Re: Hodoko rating system question

Postby m_b_metcalf » Tue Mar 02, 2021 3:20 pm

pierrenay2 wrote:re AI Generator: I can't find a concise document that offers info on its output , hence the need to find a solver/rating system that can be said to represent the current standard and work out if this generator is simply a randomizer.

as for Ai solvers, as far as i know , there are simple backtracking algorithms using grunt force, not much use really.

Could you kindly provide more information about this AI generator and solver. I wasn't aware that such programs existed. None of these links, for example, seem to show how AI is actually used to solve a puzzle in the way it's used for chess or go: https://medium.com/swlh/how-to-solve-sudoku-using-artificial-intelligence-8d5d3841b872, http://www.cs.toronto.edu/~lyan/csc384/a2/A2Sudoku.pdf, https://towardsdatascience.com/solving-sudoku-with-ai-d6008993c7de. Where are the neural networks?

Thanks,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 12289
Joined: 15 May 2006
Location: Berlin

Re: Hodoko rating system question

Postby denis_berthier » Tue Mar 02, 2021 4:02 pm

Hi Mike,
m_b_metcalf wrote:None of these links seem to show how AI is actually used to solve a puzzle: https://medium.com/swlh/how-to-solve-sudoku-using-artificial-intelligence-8d5d3841b872,

Some AI is used to read an image and to transform it into givens for a puzzle. The solver part is just backtracking.


Students project; solving is based on backtracking and similar techniques.


Based on backtracking also, but with improved choice of candidates to test.

m_b_metcalf wrote:Where are the neural networks?

AI is not limited to NN. That's only the big data part of AI.
CSP-Rules is based on the original, "symbolic" form of AI.
To be honest I have no idea how NN could be used to learn how to solve a Sudoku in a way that would make sense for us. I'm not aware of anyone trying to do it.
denis_berthier
2010 Supporter
 
Posts: 2678
Joined: 19 June 2007
Location: Paris

Re: Hodoko rating system question

Postby m_b_metcalf » Tue Mar 02, 2021 4:13 pm

denis_berthier wrote:To be honest I have no idea how NN could be used to learn how to solve a Sudoku in a way that would make sense for us. I'm not aware of anyone trying to do it.

Well, with my limited grasp of the subject, I would expect to give a NN a million puzzles and their solutions, ask it work out what the constraints are and then how to solve the puzzles, then ask it to tackle champagne's file of the hardest. We wouldn't know how it had done it, but it would be interseting to know whether it takes milliseconds or millenia!

Regards,

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 12289
Joined: 15 May 2006
Location: Berlin

Re: Hodoko rating system question

Postby denis_berthier » Tue Mar 02, 2021 5:27 pm

m_b_metcalf wrote:Well, with my limited grasp of the subject, I would expect to give a NN a million puzzles and their solutions, ask it work out what the constraints are and then how to solve the puzzles, then ask it to tackle champagne's file of the hardest. We wouldn't know how it had done it, but it would be interseting to know whether it takes milliseconds or millenia!

You can make it easier by giving it the constraints at the start.
It would probably require to be fed with very simple examples first and progressively increasing the difficulty. The hardest list is probably not a good testing set, a more balanced set would probably be more useful.

Even with these simplifying conditions, it would remain an interesting problem. But a fundamental question remains: what is the problem we really want to solve? Do we merely want the NN to find a solution (and shall we be happy if the NN learns a DFS algorithm?) or do we want it to learn resolution rules so that we can understand its resolution paths? It seems you consider only the first case ("we wouldn't know how it had done it").

Methinks we can't expect the final NN to be the implementation of a computable function: puzzle --> solution.
NN usually work for relatively fuzzy maps: input --> output. But what we'd want here is an exact map.
I strongly doubt this would be possible within the computational bounds of this universe.

As a result, it seems to me the final NN could only be (something equivalent to) a general algorithm (DFS, BFS... or some as yet unknown algorithm) or some implementation of sufficiently powerful resolution rules. That too is not what NNs are good at.
If I had to use learning for solving sudoku, I'd choose symbolic learning. Even so, I'm happy my life doesn't depend on it, because it seems terribly difficult.

PS.: homework for NN students: write a NN that learns (something equivalent to) DFS (make additional assumptions as you want).
PPS.: don't take this PS too seriously.
denis_berthier
2010 Supporter
 
Posts: 2678
Joined: 19 June 2007
Location: Paris

Re: SE Ratings

Postby Pupp » Fri Jul 02, 2021 3:25 am

1to9only wrote:Here is a finer breakdown of SE Ratings I copied off a very old thread here, found it whilst browsing/searching for somethings else!

Code: Select all
 1.0 Single
 1.2 Hidden Single in box
 1.5 Hidden Single in line
 1.7 Direct Pointing
 1.9 Direct Claiming
 2.0 Direct Hidden Pair
 2.3 Naked Single
 2.5 Direct Hidden Triplet
 2.6 Pointing
 2.8 Claiming
 3.0 Naked Pair
 3.2 X-Wing
 3.4 Hidden Pair
 3.6 Naked Triplet
 3.8 Swordfish
 4.0 Hidden Triplet
 4.2 XY-Wing
 4.3 [Direct Hidden Quad]
 4.4 XYZ-Wing
 4.5 UR Types 1 or 2 or 4 or 3 w/ hidden pair
 4.6 UR Type 3 w/ naked pair or hidden triplet
     UL Types 1 or 2 or 4 or 3 w/ hidden pair (6 cells)
 4.69 UL Type 3 w/ a naked pair or hidden triplet (6 cells)
 4.7 UR Type 3 w/ naked triplet or hidden quad
     UL Types 1 or 2 or 4 or 3 w/ hidden pair (8 cells)
 4.8 UR Type 3 w/ naked quad
     UL Type 3 w/ naked triplet [or hidden quad] (6 cells)
     UL Type 3 w/ naked pair or hidden triplet (8 cells)
 4.89 UL Type 3 w/ naked quad (6 cells)
 4.9 [UL Type 3 w/ naked triplet or hidden quad (8 cells)]
 5.0 Naked Quad or UL 1 or 2 or 4 (>=10 cells)
 5.1 UL Type 3 w/ naked pair (>=10 cells)
 5.2 Jellyfish
 5.3 Unknown
 5.4 Hidden Quad
 5.5 Unknown
 5.6 BUG Type 1
 5.7 BUG Type 2 or 4
 5.8 BUG Type 3 w/ naked pair
 5.9 BUG Type 3 w/ naked triplet
 6.0 BUG Type 3 w/ naked quad
 6.1 BUG Type 3 w/ naked quint
 6.2 Aligned Pair Exclusion
 6.3 Unknown
 6.4 Unknown
 6.5 Bidirectional X-Cycle or Bidirectional Y-Cycle (1-4 nodes)
 6.6 Turbot Fish
     Forcing X-chain or Bidirectional Y-Cycle (5-6 nodes)
 6.69 Forcing X-Chain (7-8 nodes)
 6.7 Bidirectional Y-cycle (7-8 nodes)
 6.8 Forcing X-Chain or Bidirectional Y-cycle (9-12 nodes)
 6.9 Forcing X-Chain or Bidirectional Y-cycle (13-16 nodes)
 7.0 Bidirectional Y-cycle (17-24 nodes)
     Forcing Chain or Bidirectional Cycle (1-4 nodes)
 7.1 Forcing Chain or Bidirectional Cycle (5-6 nodes)
 7.2 Forcing Chain or Bidirectional Cycle (7-8 nodes)
 7.3 Forcing Chain or Bidirectional Cycle (9-12 nodes)
 7.4 Forcing Chain (13-16 nodes)
 7.5 Forcing Chain (17-24 nodes)
     Aligned Triplet Exclusion
 7.6 Forcing Chain (25-36 nodes)
     Nishio Forcing Chain (5-6 nodes)
 7.7 Nishio Forcing Chain (7-8 nodes)
 7.8 Nishio Forcing Chain (9-12 nodes)
 7.9 Nishio Forcing Chain (13-16 nodes)
 8.0 Nishio Forcing Chain (17-24 nodes)
 8.1 Nishio Forcing Chain (25-36 nodes)
 8.2 Multiple (7-8 nodes) Region Forcing Chains
 8.3 Multiple (9-12 nodes) Cell/Region Forcing Chains
 8.4 Multiple (13-16 nodes) Cell/Region Forcing Chains
 8.5 Multiple (17-24 nodes) Cell/Region Forcing Chains
 8.6 Multiple (25-36 nodes)
     Dynamic (5-6 nodes) Cell/Region Forcing Chains
 8.7 Dynamic (7-8 nodes) Cell/Region Forcing Chains
 8.8 Dynamic (9-12 nodes) CRCD Forcing Chains
 8.9 Dynamic (13-16 nodes) CRCD Forcing Chains
 9.0 Dynamic (17-24 nodes) CRCD Forcing Chains
 9.1 Dynamic (25-36 nodes) CRCD Forcing Chains
 9.2 Dynamic (37-48 nodes) CRCD Forcing Chains
 9.3 Dynamic (49-72 nodes)
     Dynamic + (9-12 nodes) CRCD Forcing Chains
 9.4 Dynamic (73-96 nodes)
     Dynamic + (13-16 nodes) CRCD Forcing Chains
 9.5 Dynamic + (17-24 nodes) CRCD Forcing Chains
 9.6 Dynamic + (25-36 nodes) CRCD Forcing Chains
 9.7 Dynamic + (37-48 nodes) CRCD Forcing Chains
 9.8 Dynamic + (49-72 nodes) CRCD Forcing Chains
 9.9 Dynamic + (73-96 nodes) CRCD Forcing Chains
10.0 Dynamic + (97-144 nodes)
     Dynamic + Forcing Chains (17-24 nodes) CRCD Forcing Chains
10.1 Dynamic + (145-192 nodes)
     Dynamic + Forcing Chains (25-36 nodes) CRCD Forcing Chains
10.2 Dynamic + Forcing Chains (37-48 nodes) CRCD Forcing Chains
10.3 Dynamic + Forcing Chains (49-72 nodes) CRCD Forcing Chains
10.4 Dynamic + Forcing Chains (73-96 nodes) CRCD Forcing Chains
10.5 Dynamic + Forcing Chains (97-144 nodes) CRCD Forcing Chains
10.6 Dynamic + Forcing Chains (145-192 nodes) CRCD Forcing Chains
10.7 Dynamic + Forcing Chains (193-288 nodes) CRCD Forcing Chains
10.8 Dynamic + Forcing Chains (289-384 nodes) CRCD Forcing Chains
10.9 Dynamic + Multiple Forcing Chains (73-96 nodes) CRCD Forcing Chains
11.0 Dynamic + Multiple Forcing Chains (97-144 nodes) CRCD Forcing Chains
11.1 Dynamic + Multiple Forcing Chains (145-192 nodes) CRCD Forcing Chains
11.2 Dynamic + Multiple Forcing Chains (193-288 nodes) CRCD Forcing Chains
11.3 Dynamic + Multiple Forcing Chains (289-384 nodes) CRCD Forcing Chains
11.4 Dynamic + Multiple Forcing Chains (385-576 nodes) CRCD Forcing Chains
11.4 [Dynamic + Dynamic Forcing Chains (73-96 nodes) Region/Contradiction Forcing Chains]
11.5 [Dynamic + Dynamic Forcing Chains (97-144 nodes) Region Forcing Chains]
11.6 [Dynamic + Dynamic Forcing Chains (145-192 nodes) Cell Forcing Chains]
11.7 [Dynamic + Dynamic Forcing Chains (193-288 nodes) Double Forcing Chains]

CRCD=Cell/Region/Contradiction/Double
UL=Unique Loop
UR=Unique Rectangle
BUG=Bivalue Universal Grave



I read someplace that trivial techniques go to SE 4.4 (xyz-chain).
I took that to mean techniques likely to be found in tournament puzzles and more difficult puzzles in newspapers.

I think the intermediate levels ran to about 7.5 SE. Pretty much anything short of a Nishu forcing chain.

Expert was anything higher than that.

I suspect most higher forcing chains ( nested, dynamic, etc.), is more about retrograde analysis, which is more time consuming rather than difficult... assuming your brain can keep track of it all. That is, the difficulty is more about being able to remember and keep track of numbers than the logic of the technique. Although we are talking about stratopheric techniques even at the "easy" level of 7.0 to 7.9.
Pupp
 
Posts: 236
Joined: 18 October 2019

Previous

Return to Software