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   

recognizing text grids
Goto page Previous  1, 2
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
johnw

Joined: 21 Jun 2005
Posts: 1
:

Items
PostPosted: Tue Jun 21, 2005 11:53 am    Post subject: Reply with quote

After I read the original post, I decided to create a program to extract the cell data from grids of any text layout found in the forums, which will accept
- any size grid (eg 2x3, 4x4)
- numbers or letters as cell values
- grids with one or two errors (eg two 8s in one column, cells marked 'A' or 'B' for discussion purposes).

The logic will be:
study each 'row' and 'column' of text, identify chars that appear only once in that set of chars, assume these are the cell values.
Conversely, where the chars in a row/col are all duplicated, it is a 'punctuation' line, for example ' ---+---+--- '.

I'm sure this program will be a long chunk of Delphi code, hopefully not too long. I will put it here when progress made.
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Tue Jun 21, 2005 12:01 pm    Post subject: Reply with quote

johnw wrote:
I'm sure this program will be a long chunk of Delphi code, hopefully not too long.

Simes made a very good start on the previous page. I've adopted it into my own program and modified it slightly to recognise one or two more formats ...
Code:
procedure strReplaceAll(var s: string; oldChar, newChar: char);
var
  i: integer;
begin
  if (newChar = #0) then
  begin
    for i := length(s) downto 1 do if s[i] = oldChar then
      delete(s,i,1);
  end else
    for i := 1 to length(s) do if s[i] = oldChar then
      s[i] := newChar;
end;
//------------------------------------------------------------------------------

function formatClipboardText(const clipText: string): string;
var
  i: integer;
begin
  result := clipText;
  for i := length(result) downto 1 do
    if result[i] in [#13,#10,'|','#','=','+','!'] then delete(result,i,1);
  for i := 1 to length(result) do
    if result[i] in ['?','.','X','x','_'] then result[i] := '0';

  if pos('0', result) > 0 then
    strReplaceAll(result,'*',#0) else
    strReplaceAll(result,'*','0');
  if pos('0', result) > 0 then
    strReplaceAll(result,'-',#0) else
    strReplaceAll(result,'-','0');
  if pos('0', result) > 0 then
    strReplaceAll(result,' ',#0) else
    strReplaceAll(result,' ','0');

  if length(result) <> 81 then result := ''
  else for i := 1 to 8 do insert(#10,Result,i*10); //Add LF to format as 9 lines
end;
Back to top
View user's profile Send private message Visit poster's website
petef

Joined: 14 May 2005
Posts: 8
:
Location: West Sussex

Items
PostPosted: Wed Jun 22, 2005 10:03 pm    Post subject: Reply with quote

I use this style for output
Code:
***|*9*|84*    526|391|847
4*1|2**|***    481|257|396
7**|**6|*2*    793|846|125
---+---+---    ---+---+---
**5|*6*|*3*    945|768|231
3**|5*9|**4 => 317|529|684
*6*|*1*|5**    862|413|579
---+---+---    ---+---+---
*7*|1**|**3    279|185|463
***|**4|9*2    138|674|952
*54|*3*|***    654|932|718


For partial solutions, unsolved cells are * and unsolvable are !. The latter result from bad input.

For input I accept the above with some permitted relaxations.

1) The -+| are ignored
2) Anything that is not 1-9 is an unknown.
3) Trailing unknowns in a row can be omitted.

So my command line driven program is invoked thus.

python sudoku.py ....9.84 4.12 7....6.2 ..5.6..3 3..5.9..4 .6..1.5 .7.1....3 .....49.2 .54.3
Back to top
View user's profile Send private message
PaulS

Joined: 06 Jul 2005
Posts: 3
:
Location: Bath, UK

Items
PostPosted: Wed Jul 06, 2005 12:04 pm    Post subject: Reply with quote

scrose wrote:
Please mention any other programs that also perform input recognition and I will update this list.


Hi,

My page (paulspages.co.uk/sudoku) does text import/export. Here's the import routine (in javascript):
Code:

function convertTextToSerialPuzzle(t) {
if (t == null || t.length == 0) {return}
var s = "", i, g
for (i = 0; i < t.length; i++) {
   g = t.substr(i,1)
   if ((g >= "0" && g <= "9") || g == ".") {
      s += (g == ".") ? "0" : g
   }
}
return s
}



It converts something like this:
Code:

 7 . . | . . 5 | . 3 .
 1 . . | . . 2 | . . .
 . 9 . | . . . | . . 6
-------+-------+------
 . . 8 | . . 4 | . 5 .
 . . 6 | . . . | 9 . .
 . 2 . | . 7 . | 1 . .
-------+-------+------
 3 . . | . . . | . 8 .
 . . . | 1 . . | . . 4
 . 5 . | 2 . . | . . 3

to this:

700005030100002000090000006008004050006000900020070100300000080000100004050200003

It's designed to work on the .value property of an HTML <textarea> control (param t). It strips out anything that isn't 0 to 9 or . , so copes with an arbitrary set of linefeeds, spacer characters, blank lines etc. The only restriction is that empty cells must be represented by "0" or ".". The calling function just checks that the return value is 81 characters long.

This doesn't check that the data represents a valid puzzle, of course - that's done elsewhere.
Back to top
View user's profile Send private message Visit poster's website
flagitious

Joined: 14 Jul 2005
Posts: 3
:

Items
PostPosted: Thu Jul 14, 2005 11:32 pm    Post subject: Reply with quote

Here is my simple input routine, it is very generic and will work for any grid given that there is some character used for unknown cells and that there are 81 unknown cells + givens

Code:
sudoku::sudoku(string& s) {
   int hist[255], i, x, y, givens = 0;
   char c, u;
   for(i=0; i<255; i++) hist[i]=0;
   for(i=0; i<s.size(); i++) {
      c = s.c_str()[i];
      if(c <= '9' && c >= '1') givens++;
      else hist[unsigned(c)]++;
   }
   for(i=0; i<s.size() && givens + hist[i] != 81; i++);
   if(givens + hist[i] != 81) cerr<<"couldn't determine unknown character\n";
   u = i;
   for(i=0, x=0, y=0; i<s.size(); i++) {
      c = s.c_str()[i];
      if(c <= '9' && c >= '1') a[x++][y] = c - '0';
      else if(c == u) a[x++][y] = 0;
      if(x==9) { x = 0; y++; }
   }
}
Back to top
View user's profile Send private message
hoppy

Joined: 15 Jul 2005
Posts: 7
:

Items
PostPosted: Thu Jul 21, 2005 12:29 am    Post subject: Reply with quote

stolen into vb.net

Code:
      ' count the incidence of characters other than 1 - 9 and put in hist:
        Dim hist(255) As Integer
        Dim i As Integer
        Dim givens As Integer = 0 ' count the instances of numbers 1 - 9
        Dim c As Char
        Dim u As Char ' the char that stands for the unknown numbers
        For i = 0 To 254
            hist(i) = 0
        Next
        'go through each char in the string
        For i = 0 To s.Length - 1
            c = s.Chars(i)
            If Asc(c) > 48 AndAlso Asc(c) < 58 Then
                ' character is a number
                givens += 1
            Else
                ' increase the count for this character
                hist(Asc(c)) += 1
            End If
        Next
        i = 0
        Dim uIsUnknown As Boolean = True
        Do
            If hist(i) > 0 AndAlso hist(i) + givens = 81 Then
                '(count of chars that are numbers) + (char that has ascii i) = 81
                u = Chr(i)
                uIsUnknown = False
                Console.WriteLine("unknown is " & u)
            End If
            i += 1
        Loop While uIsUnknown AndAlso i < 256
        If uIsUnknown Then
            Console.WriteLine("didn't find unknown")
            Return ""
        End If


and then you know the unknown so do with the string as you will

(i will be learning other languages shortly at uni, so no comments on proper languages, lol.)
Back to top
View user's profile Send private message
flagitious

Joined: 14 Jul 2005
Posts: 3
:

Items
PostPosted: Fri Jul 22, 2005 7:36 pm    Post subject: Reply with quote

Ah that is like the exact same function I just posted except longer
Back to top
View user's profile Send private message
hoppy

Joined: 15 Jul 2005
Posts: 7
:

Items
PostPosted: Fri Jul 22, 2005 9:25 pm    Post subject: Reply with quote

Yaeh, thats what I meant when I said I stole it, lol.
Back to top
View user's profile Send private message
BTUx9

Joined: 24 Jul 2005
Posts: 4
:

Items
PostPosted: Sun Jul 24, 2005 4:13 am    Post subject: Reply with quote

Scanning for count of digits + some char add up to 81 is ok, but breaks on those programs that include extra "state" information (like simple sudoku)

Code:
..7|8.6|.5.
82.|1.5|.7.
...|2..|...
-----------
1..|...|.82
..4|...|7..
3..|...|.65
-----------
...|5..|...
75.|6.8|.2.
..8|4.7|.9.


..7|8.6|25.
82.|145|.7.
...|27.|.48
-----------
1..|..4|.82
.84|..2|7..
3.2|.81|465
-----------
...|52.|8.7
75.|6.8|.24
238|417|596


{49}   {149}  {7}    {8}    {39}   {6}    {2}    {5}    {139} 
{8}    {2}    {369}  {1}    {4}    {5}    {69}   {7}    {39}   
{569}  {169}  {1356} {2}    {7}    {39}   {169}  {4}    {8}   
{1}    {679}  {569}  {379}  {56}   {4}    {39}   {8}    {2}   
{56}   {8}    {4}    {39}   {56}   {2}    {7}    {13}   {19}   
{3}    {79}   {2}    {79}   {8}    {1}    {4}    {6}    {5}   
{469}  {1469} {169}  {5}    {2}    {39}   {8}    {13}   {7}   
{7}    {5}    {19}   {6}    {39}   {8}    {13}   {2}    {4}   
{2}    {3}    {8}    {4}    {1}    {7}    {5}    {9}    {6}   

Modifying your code to stop at the first blank would solve that problem (at least for this source, but I imagine it's fairly uncommon to have completely blank lines within a valid puzzle).

One other thing: angusj's format lists the original puzzle first, not the current state... I'll drop him a PM about it.

Ooops... spoke too soon... some of the * formats use a blank line for a divider... you could keep grabbing chunks until you reached your 81, I suppose.

FYI - if a puzzle were pasted from rubylips' program that contained 39 filled cells, your algorithm would break, choosing hyphens instead of periods.
Back to top
View user's profile Send private message AIM Address Yahoo Messenger
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page Previous  1, 2
Page 2 of 2

 
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