SudokuSolver Forum
http://www.rcbroughton.co.uk/sudoku/forum/

Text representation for Killer Sudoku
http://www.rcbroughton.co.uk/sudoku/forum/viewtopic.php?f=11&t=107
Page 2 of 2

Author:  udosuk [ Fri Jun 06, 2008 12:43 pm ]
Post subject:  Re: Text representation for Killer Sudoku

Richard, here is a 6-cell cage which definitely needs a downward arrow: (edited to fix an embarassing typo :oops:)
Code:
..X
v.^
>>^

Of my scheme, the arrows don't point to the cage sum, instead they point to the neighbour (orthogonal or diagonal depending on cage structure) which share the same cage and has the smallest address (e.g topmost leftmost).

Afmob, your scheme is almost the same one the Puzzle Tiger software is using now. See here.

But they use 0-9,a-z,A-Z and you use 1-9 to represent singleton cages, so you only need 40 letters at most to represent the "proper cages", thus a-z,A-N (or A-Z,a-n) is enough.

Note this scheme is nothing new. As early as 2005/06 dukuso of the sudoku.com forum already wrote a killer program which uses this scheme. :geek:

I still prefer the 81-char arrow-string for the normal killers. Remote cages and overlap cages (and also repeat cages which Maurice likes a lot) are probably best dealt specially. As for the Puzzle Tiger/Afmob scheme, I really don't like the trouble to locate which letter representing which cage sum. :rambo:

Author:  Jean-Christophe [ Fri Jun 06, 2008 12:44 pm ]
Post subject:  Re: Text representation for Killer Sudoku

rcbroughton wrote:
if we're definig cage sum in the top left cell, do we need v ? we should only need to refer to a cell that is to the left or above, or if a cage starts in column 9, possibly to the right
I believe it's needed for 'U' shaped cages. The upper-right most cell is connected downward.
Code:
P v
^<<

Note: for clarity, I skipped the top center cell which belongs to some other cage

Author:  Jean-Christophe [ Fri Jun 06, 2008 12:52 pm ]
Post subject:  Re: Text representation for Killer Sudoku

udosuk wrote:
Richard, here is a 6-cell cage which definitely needs a downward arrow:
Code:
..X
V.^
>>^


I do not see any downward arrow. Indeed it's an invalid puzzle since the UPPER CASE V defines a cage 31/1 :twisted: :rambo: :whistle:

Author:  udosuk [ Fri Jun 06, 2008 1:19 pm ]
Post subject:  Re: Text representation for Killer Sudoku

:bigoops: :bigoops: :bigoops:

With a pie in the face I'll go up and edit my cage. You can keep that code box in your quote as an evidence for my inexplicable blunder. :oops:

Author:  Jean-Christophe [ Fri Jun 06, 2008 1:34 pm ]
Post subject:  Re: Text representation for Killer Sudoku

rcbroughton wrote:
When I suggested \ / for diagonals, we only need to point either to the above left and above right cells.


How about a 'V' shaped cage of 3 ? The upper-right-most cell is connected left-downward.
Code:
E ,
 `


And for a '√' shaped cage of 4. The mid-left-most cell is connected right-downward
Code:
   K
. '
 '

Author:  rcbroughton [ Fri Jun 06, 2008 2:31 pm ]
Post subject:  Re: Text representation for Killer Sudoku

You're right.

U shaped and O shaped cages occurred to me after I'd posted my comment . . .

The first versions of SudokuSolver, I saved cage information in human readable form following a convention of

XXaabbccdd;XXaabb;XXaabbccdd; . . .

where XX was the cage value and aa bb cc . . . were 01 - 81 to define the caged cells. This has the flexibility to handle any cage structure, including remote cages and overalpping cages, but at the expense of a minimm of 162 characters for the cells plus 3x number of cages. Slighlty morre economic than the PS format but with a degree more flexibility.

Author:  Afmob [ Fri Jun 06, 2008 4:09 pm ]
Post subject: 

You're right udosuk, this format is not new (like I said I've read about it before, but I didn't remember where) but I wanted to modify it, so that it's short (1-cell cages get directly defined by their numbers) and it's easy readible by programms and humans. It's about half the size of a normal PS code and also allows overlapping cages.

Udosuk and Tarek's format has the advantage that it's really short (less than half the size of my format if we use the identifier in front of the actual code) and it's easy to understand by humans but it cannot handle remote cages and overlapping cages (but I have to say that HS 1 is the only killer I've seen so far that has overlapping cages). And PS Code is standard so far and can handle remote cages but not overlapping cages and the code is really long and not understandable for humans.

Here are some examples of SudokuTiger's modified format I promised in my previous post:

A30 V2.1:
http://www.sudocue.net/forum/viewtopic.php?t=459
a a b b c d d e e
a f f f c g g g e
h f i i c j j g k
h f i l l l j g k
m m m l 3 l n n n
o p q l l l r s t
o p q q u r r s t
v p p p u s s s w
v v x x u y y w w

17, 16, 20, 7, 6, 22, 26, 10, 6, 21, 13, 42, 11, 18, 10, 31, 12, 16, 23, 9, 19, 17, 14, 9, 7

3x3::k:aabbcddeeafffcgggehfiicjjgkhfillljgkmmml3lnnnopqlllrstopqqurrstvpppussswvvxxuyyww::
17162007062226100621134211181031121623091917140907:

Human Solvable One:
http://www.rcbroughton.co.uk/sudoku/forum/viewtopic.php?f=3&t=73
a  b  a  c  c  c  d  e  d
b a f f g h h d e
a i a 0 g 0 d j d
0 i 0 k g l 0 j 0
m m m 0 kl 0 n n n
0 o 0 l p k 0 q 0
r o r 0 p 0 s q s
t r u u p v v s w
r t r x x x s w s

25, 7, 17, 25, 10, 13, 13, 12, 13, 12, 17, 10, 14, 10, 14, 15, 13, 25, 25, 6, 14, 13, 5, 16

3x3:d:k:abacccdedbaffghhdeaia0g0djd0i0kgl0j0mmm0:kl:0nnn0o0lpk0q0ror0p0sqstruupvvswrtrxxxsws::
250717251013131213121710141014151325250614130516:

Edit: To further shorten things we could also use letters for the cage sums (a=10,b=11, ...) but that might be confusing for humans since a,b, ... would have two meanings since it identifies a cage and a cage sum but those two properties are not necessarily connected (e.g. cage "a" might not have cage sum 10).

Author:  udosuk [ Sat Jun 07, 2008 2:20 pm ]
Post subject:  Re: Text representation for Killer Sudoku

Afmob, seeing you have posted a nice Assassin 106 with remote cages, I guess I have to take back my comment that remote cages were inelegant. BTW looking forward to your V2, as others have always solved V1. :)

Author:  Jean-Christophe [ Wed Jun 11, 2008 7:23 am ]
Post subject:  Re: Text representation for Killer Sudoku

I've added support in JSudoku for the 81 characters format (not released yet).
An identifier would have made the format easier to recognize but is not an absolute necessity. I currently detect this format when it contains at least one '<' and one '^'. When exporting, I follow Udosuk's order of preference which are maybe too restricted. For some cases, it's easier and faster for a program to scan and export if we allow '<' instead of '^' when both are valid.

Page 2 of 2 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/