Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

program finds unavoidable sets, hitting sets

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
Moschopulus

Joined: 12 Aug 2005
Posts: 39
:

Items
PostPosted: Mon Dec 05, 2005 9:18 pm    Post subject: program finds unavoidable sets, hitting sets Reply with quote

New program "checker" available at http://www.maths.nuim.ie/staff/gmg/sudoku

This is the program used to show that the SF grid has no 16.

CHECKER will search a given grid for a puzzle with n clues. It stops when it finds one puzzle or has searched the grid completely and found none.

Downloads, details and examples at the above web site. Join the search for a 16-clue sudoku!

The method used by "checker" is this:

1. Find some unavoidable sets,
2. Enumerate all hitting sets of size n, i.e., enumerate all sets of n clues that intersect all the unavoidable sets found in part 1,
3. Check if any of these hitting sets uniquely determines the grid.

Input grids in a file grid.txt in this format:
259478316341956872786123594892341657674895231135267489968512743423789165517634928

Type "checker grid.txt 16" to search this grid for a 16-clue puzzle.

It can be used to search a given grid for a puzzle with, say, 25 clues, but there are better puzzle finders out there. It will find one (and only one) with 25 clues pretty quickly however.

Lots of room for improvement!

Co-written by a colleague (who wishes to remain anonymous) and myself.
Please report bugs, suggestions, etc.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron