recognizing text grids

scrose · Posted: Fri Jun 17, 2005 3:19 pm Post subject: recognizing text grids

This is a thread to discuss techniques on how to recognize text-based sudoku grids. The topic was raised in the Pappocom forum. The attached post got the ball rolling. I'll have my own two-cents to add in a day or two.

scrose · Posted: Fri Jun 17, 2005 5:06 pm Post subject:

Here is a list of programs (that I have encountered and used) that perform input recognition of text sudoku puzzles.

simes
rubylips - allows one format only
angusj

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

Animator · Posted: Fri Jun 17, 2005 6:04 pm Post subject:

I think it would be more intresting to see a list of different 'styles'/grids that are used... (it would allow a solution to be tested)

Making something that will work all the time sure is a complex thing... the main problem is how do you identify the charachter that is used to indicate an empty cell?

Making something that works 90% of the time should be slightly easier I guess...

scrose · Posted: Fri Jun 17, 2005 6:25 pm Post subject:

The format native to rubylips' java app.

scrose · Posted: Fri Jun 17, 2005 8:21 pm Post subject:

Here is a really simple list of tasks that a recognition script needs to accomplish.

Get your input and validate it. Less than nine lines or input without any digits are pretty good indications that the input is faulty.
Eliminate the lines which do not contain any digits. These lines are likely spacers between rows and/or blocks. However, be careful not to eliminate rows of the puzzle that naturally do not contain any digits.
Focusing on the lines that contain digits, try and figure out what character is being used as a placeholder for an empty cell. (As Animator pointed out, this is the key step.) Once this character is determined, all other non-digit characters (plus the digit zero) can be removed.
Take what you have left and plop it into some sort of data structure.

Here is a quick stab at some Perl code that incorporates steps 1 and 2. The data is read into @rawinput which is then quickly checked for at least nine lines and at least one digit. @rawinput is then examined for lines that contain no digits. These lines (and their location in the puzzle) are copied into %nodigits. Finally, a quick calulation is done to determine how many lines are acting as spacers and how many lines are rows of the puzzle that happen to have no digits.

Edit: Removed my code since it is more-or-less duplicated below.

angusj · Site Admin

Simes · Posted: Sat Jun 18, 2005 9:05 am Post subject:

require a minimum of 9 lines? How about requiring a minimum of 81 characters?

I've seen a solver somewhere that used a single 81 digit line.
_________________
Simes
www.sadmansoftware.com/sudoku

scrose · Posted: Sat Jun 18, 2005 11:36 am Post subject:

Another example.

scrose · Posted: Sat Jun 18, 2005 11:40 am Post subject:

scrose · Posted: Sat Jun 18, 2005 12:01 pm Post subject:

Animator · Posted: Sat Jun 18, 2005 5:01 pm Post subject:

Here are the steps that I would use:

1) reconisze the symbol used for empty cells.
2) remove all symbols except the digits and the symbol ere is a really simple list of tasks that a recognition script needs to accomplish (and perhaps newlines/line-endings too).
3) verify the symbol. The count of the numbers + the count of the symbol must equal 9 (for each row, column, box) (or whatever the size of the grid is)
4) Start parsing the grid. (Input now is something like: 1*34*678*\n*56789**3\n*****7***\n123456789...)

The main problem ofcourse is point 1.
point 2 is a problem when the symbol used for empty cells is the same as a seperator in the grid. (space or tabs for example)

Simes · Posted: Sun Jun 19, 2005 9:04 am Post subject:

Here's my code.

It takes a string, removes line breaks and any other characters I've seen used only for layout, replaces characters usually used for empty cells with zero. It then decides whether spaces and asterisks should be zero or layout depending on whether it's already got any.

Seems to work!

scrose · Posted: Mon Jun 20, 2005 7:50 pm Post subject:

I've banged out a rough bit of code that doesn't try to figure out what character is being used to represent the empty cell. Instead, it determines the coordinates of the digits in the text input. Using the x and y coordinates, the rows and columns respectively can be deduced. My code below scans the input, extracts the digits, and prints a 9x9 grid with periods to represent the empty cells. It doesn't quite work if the puzzle itself has digitless rows or columns. And it doesn't quite work with the tabbed Excel example. It does, however, successfully tackle grids that use spaces to represent empty cells. I'll try refining this to catch the exceptions.

Edit: Removed my code since it is more-or-less duplicated below.

scrose · Posted: Mon Jun 20, 2005 8:19 pm Post subject:

Another example.

scrose · Posted: Tue Jun 21, 2005 12:54 am Post subject:

I tinkered with my code a bit and it now successfully recognises all of the examples shown above, except for the tabbed Excel and Pete Wake formats. As long as each of the nine rows and columns has at least once digit, I can recognise the grid without having to determine what character is being used to represent the empty cell. However, if the puzzle happens to have at least one row and/or column that doesn't contain any digits, I look for a character that satisfies the following condition: (number of occurrences of the digits 1 through 9) + (number of occurrences of a particular character) = 81. Because of the simplicity of this condition, it is easy to cook up some grids that cause my code to fail. Here are two examples.