+- Ludii Forum (https://ludii.games/forums)
+-- Forum: Problems (https://ludii.games/forums/forumdisplay.php?fid=5)
+--- Forum: Ludii Player Problems (https://ludii.games/forums/forumdisplay.php?fid=6)
+--- Thread: sudoku AI can't solve the problem. (/showthread.php?tid=569)
sudoku AI can't solve the problem. - yuandj - 05-17-2021
https://ludii.games/details.php?keyword=Sudoku
If it's my wrong programe seting, the sudoku sample lud can't got the result.
some number filling in several seconds, was disappear again many times.
I'm designed a low lever soduku, the problem appear also.
---
(game "Lucky Sudoku"
(players 1)
(equipment
{
(board (square 6) (values Cell (range 1 6)))
(regions {0 1 2 3 4 5})
(regions {6 7 8 9 10 11})
(regions {12 13 14 15 16 17})
(regions {18 19 20 21 22 23})
(regions {24 25 26 27 28 29})
(regions {30 31 32 33 34 35})
(regions {0 6 12 18 24 30})
(regions {1 7 13 19 25 31})
(regions {2 8 14 20 26 32})
(regions {3 9 15 21 27 33})
(regions {4 10 16 22 28 34})
(regions {5 11 17 23 29 35})
(regions {0 1 2 6 7 8})
(regions {3 4 5 9 10 11})
(regions {12 13 14 18 19 20})
(regions {15 16 17 21 22 23})
(regions {24 25 26 30 31 32})
(regions {27 28 29 33 34 35})
}
)
(rules
(start
(set
{
{6 2} {7 6} {9 3} {10 4}
{12 5} {13 1} {14 6} {15 2} {16 3}
{19 2} {21 6}
{24 6} {25 5} {26 4} {27 1} {28 2}
{30 1} {31 3} {33 4} {34 5}
}
)
)
(play (satisfy (all Different)))
(end (if (is Solved) (result P1 Win)))
)
)
(metadata
(graphics {
(show Line {
{0 6} {6 48} {48 42} {42 0}
{3 45} {14 20} {28 34}}
scale:2
)
})
)
---
Puzzle menu checked all items.
- show possible values.
---
Moves of Ludii AI:
1. (D1=5)
13. (Toggle D1=4)
14. (Toggle D1=3)
...
RE: sudoku AI can't solve the problem. - Eric Piette - 05-18-2021
Hi,
This is completely normal. This kind of puzzle is called "deduction puzzle" which is similar in AI research to a Constraint Satisfaction Problem (CSP), in which the rules of the puzzles are constraints and the solution of the puzzle is a set of values set to the variables of the problem which satisfy the constraints.
I am personally also involved (in my free time) on a side project which can connect a set of CSP solvers to Ludii to solve efficiently all the deduction puzzles of the system in converting them in a format called XCSP3 which is understood by any CSP solver.
The first results are encouraging and can solve much of our current deduction puzzles. In the long term, I hope to provide an extension to Ludii in which it will be possible to plug this work to solve any of these puzzles.
However, the AI you are trying to solve the puzzle here is UCT, which is the most famous Reinforcement Learning technique. This kind of techniques is terrible to solve problems in which (often) only one single solution exists and all the other playouts run by that kind of algorithm are not provided with any hint to find the solution. Consequently, currently in Ludii, you can not use an AI (providing with the software) to find the solution to our deduction puzzles.
Regards,
Eric
RE: sudoku AI can't solve the problem. - yuandj - 05-29-2021
(05-18-2021, 06:48 AM)Eric Piette Wrote: Hi,
This is completely normal. This kind of puzzle is called "deduction puzzle" which is similar in AI research to a Constraint Satisfaction Problem (CSP), in which the rules of the puzzles are constraints and the solution of the puzzle is a set of values set to the variables of the problem which satisfy the constraints.
I am personally also involved (in my free time) on a side project which can connect a set of CSP solvers to Ludii to solve efficiently all the deduction puzzles of the system in converting them in a format called XCSP3 which is understood by any CSP solver.
The first results are encouraging and can solve much of our current deduction puzzles. In the long term, I hope to provide an extension to Ludii in which it will be possible to plug this work to solve any of these puzzles.
However, the AI you are trying to solve the puzzle here is UCT, which is the most famous Reinforcement Learning technique. This kind of techniques is terrible to solve problems in which (often) only one single solution exists and all the other playouts run by that kind of algorithm are not provided with any hint to find the solution. Consequently, currently in Ludii, you can not use an AI (providing with the software) to find the solution to our deduction puzzles.
Regards,
Eric
Thanks so much, Eric. That's sounds good for our students, It's also the study direction of my students.
the result to using ludii tools, enabled the menu items could help human player to solve it.