OJ Board

Posted: **Sat Dec 06, 2003 4:51 pm**

How to solve it ?
THX!

Posted: **Mon Dec 08, 2003 4:45 pm**

Posted: **Mon May 03, 2004 4:42 am**

Is it true that one doesn't need to backtrack? i.e. if there is a scan line with imperfect information, then we can pick any cell and color it either way and still get a solution (assuming a solution exists). I believe I have a proof of this, but my program is giving me wrong answer. An assertion shows that there is at least one case has triggers this condition.

I don't know if my proof is wrong or my implementation is wrong...

Posted: **Wed Aug 18, 2004 3:14 pm**

Any one else?
Plz give me some hint?

Thank you all!

Posted: **Sat Aug 21, 2004 7:19 am**

howard, what exactly do you mean?

how are you checking for ambiguous cases (more than one solution)?

Posted: **Wed Sep 01, 2004 10:23 pm**

What I mean is this:

- if there is a scanline in which the number of black cells is the same as the number of cells in the line, then you can fill the whole line black

- similarly, if there is a scanline with no black cells then all cells are white

- every time we fill in some cells (black/white) we have to update the counts.

So we repeatedly look for scanlines which are either completely black or completely white (for the undetermined cells). My claim is that if there is some cell which has not been filled but there is no scanline with complete information, then coloring this cell either way will lead to a valid solution (assuming that there was a solution to begin with).

Posted: **Thu Sep 02, 2004 6:23 pm**

Do you know why it is a special corrector problem?

Posted: **Thu Sep 02, 2004 6:27 pm**

No idea.

Posted: **Sat Dec 03, 2005 11:03 am**

Hi!

I keep getting WA for this one.

My test input is currently :

Code: Select all

7
10 10 6 4 6 8 13 15 11 6
0 1 2 2 2 2 4 5 5 6 7 6 5 6 6 5 5 6 6 3 2 2 1 0
2 4 5 5 7 6 7 10 10 10 7 3 3 5 5
0 0 1 3 4 4 4 4 3 4 5 7 8 8 9 9 6 4 4 2 0 0 0 0
10 10 6 4 6 8 13 15 11 6
0 1 2 2 2 2 4 5 5 6 7 6 5 6 6 5 5 6 6 3 2 2 1 0
2 4 5 5 7 6 7 10 10 10 7 3 3 5 5
0 0 1 3 4 4 4 4 3 2 5 7 8 8 9 9 6 4 4 2 0 0 0 0
9 11 5 4 2 2 5 14 9 6
0 0 0 2 2 2 3 5 4 5 6 7 5 5 3 3 3 3 4 3 2 0 0 0
2 2 3 4 5 6 7 10 7 7 4 3 2 2 3
0 0 1 3 4 3 3 3 3 3 4 4 6 5 5 5 4 3 3 3 2 0 0 0
0 0 0 5 3 3 13 13 4 0
0 0 0 0 0 0 0 1 2 5 4 4 3 3 3 3 3 3 3 3 1 0 0 0 
0 2 3 3 3 3 3 3 3 3 5 5 3 2 0
0 0 0 2 3 2 2 2 3 2 3 3 4 3 3 5 4 0 0 0 0 0 0 0
0 13 2 11 4 4 11 2 13 0
0 0 1 2 2 2 3 4 4 4 4 4 4 4 4 4 4 3 2 2 2 1 0 0
0 8 2 6 4 4 4 4 4 4 4 6 2 8 0
0 0 1 2 2 2 3 4 4 4 4 4 4 4 4 4 4 3 2 2 2 1 0 0
3 9 10 7 9 13 11 8 4 1
0 1 1 2 2 3 3 5 6 5 3 7 8 7 4 4 3 3 3 3 2 0 0 0 
0 5 5 8 9 9 4 1 2 5 6 8 7 4 2
0 0 1 1 3 3 4 3 4 6 6 4 4 6 6 5 5 5 5 2 2 0 0 0 
2 7 9 8 9 6 4 11 8 2
0 1 1 2 1 2 5 6 6 6 4 1 2 5 8 6 3 1 1 1 2 1 1 0
1 6 8 6 4 4 6 5 5 4 3 3 5 4 2
0 1 2 2 1 2 2 4 5 6 6 6 6 6 4 4 1 1 2 1 2 1 1 0

And my program outputs

Code: Select all

.##########....
.##########....
....######.....
......####.....
.......####..##
.......########
#####..########
###############
..#########..##
....######.....

...............
...............
...............
...............
...............
...............
...............
...............
...............
...............

...#########...
..###########..
.....#####.....
......####.....
.......#......#
.......#......#
##.....#.....##
##############.
..#########....
....######.....

...............
...............
...............
......#####....
.....#....##...
....#......##..
.#############.
.#############.
..##......##...
...............

...............
.#############.
.#...........#.
.#.#########.#.
.#.#.......#.#.
.#.#.......#.#.
.#.#########.#.
.#...........#.
.#############.
...............

.#...#.....#...
.######...###..
.######..####..
...###...####..
...###..######.
..#############
..#####..######
.#####.....###.
.#.###.........
....#..........

...............
...............
...............
...............
...............
...............
...............
...............
...............
...............

Could anyone check my output and give me some other input to try ?

Thanks in advance.

Posted: **Tue Mar 21, 2006 11:20 am**

Remember that the input doesn't need to correspond to a valid scan. The sensor data could be too high or too low for any images found by backtracking.

Also, I've checked the judge that backtracking is absolutely needed, just computing without backtracking will not solve some inputs. A hybrid of backtracking and computing must be done. There are unambiguous cases that contains undetermined squares that can't be solved using Howard's method.

The output given above is CORRECT.

Posted: **Tue Jul 15, 2014 9:33 pm**

I solved it without backtracking.

Code: Select all

set all cells to unknown

do {
  for every scan line {
    count the number of unknown, blank, and filled cells
    if the count of filled cells equals the number of filled cells, then change unknown cells to blank
    if the count of unknown cells plus the count of filled cells equals the number of filled cells, then change unknown cells to filled
  }
} while(a cell was modified)

If any cells are unknown or any scan line's count of filled cells doesn't equal the number of filled cells, then print a blank grid, otherwise print the completed grid.

Posted: **Wed Jul 16, 2014 12:48 am**

Hi BrianFry,

Thanks for sketching out the algo. Will try it.

OJ Board

229 - Scanner

229 - Scanner

Re: 229 Scanner

Re: 229 Scanner