New 225x225 massive sudoku

For fans of Killer Sudoku, Samurai Sudoku and other variants

New 225x225 massive sudoku

Postby m_b_metcalf » Wed Feb 22, 2017 1:35 pm

blue wrote:Give SAT a try, if you like.
I used it with Mike Metcalf's 225x225 sudoku(s?), and it worked well.

However, the puzzle in question, from 2009, was lost when the Sudoku Programmers' Forum disappeared. In case it's of any further interest, I've used my (now faster) program to remove a few more clues, the result is attached. It's solvable with basic methods, but a slog.

Regards,

Mike Metcalf
Attachments
225x225_new.txt
(156.9 KiB) Downloaded 48 times
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8130
Joined: 15 May 2006
Location: Berlin

Re: New 225x225 massive sudoku

Postby hkociemba » Wed Aug 16, 2017 1:01 am

My SAT-solver now works for (in principle) arbitrary large grids. I tested it with this puzzle and it took 9 seconds to solve. Simplification with naked and hidden singles pairs and triples and row/column block interaction takes about 6 seconds, the SAT part with 549290 clauses remaining takes about 3 seconds using sat4j. I observed that using naked and hidden quadrupels or higher tuples in the simplification phase takes very long, so I did not use these here.
hkociemba
 
Posts: 14
Joined: 09 July 2017

Re: New 225x225 massive sudoku

Postby hkociemba » Wed Aug 16, 2017 7:30 am

Addition: Allowing naked and hidden quadrupels in the simplification phase completely solve the puzzle without making the SAT phase necessary. This takes about 20 minutes with my solver which of course is much more than the 9 seconds before. Btw, using the approach described in https://www.cs.cmu.edu/~wklieber/papers/2007_efficient-cnf-encoding-for-selecting-1.pdf dramatically slowed down the SAT-part, so I only use the obvious approach without commander-variables.
hkociemba
 
Posts: 14
Joined: 09 July 2017


Return to Sudoku variants