• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

filling an n by n grid

 
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Something similar was posted as a homework assignment a while back, but I found it interesting so I thought I'd post the question (since some time has passed) to see if anyone else was interested.
The problem as I remeber it, is to have an N*N grid, a starting point (x1, y1) and finishing point (x2, y2) , and defining a path that starts at point one, finishes at point two, and includes every point in the grid once and once only by moving horizontally and vertically (no diagonals).
No code necessary, but anyone want to offer an algorithm?
and I just realised a 2*2 grid with points at opposite corners has no solution. Any other unsolvable conditions?
[ May 08, 2004: Message edited by: David O'Meara ]
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Any other unsolvable conditions?
Sure. Generalizing a bit from the N*N square - if the dimensions are M * N, then there must be M * N - 1 moves. Now imagine that the grid is a checkerboard of black and white. If the number of moves is even, then you must end on the same color you started on. If the number of moves is odd, you must end on the opposite color you started on. Otherwise there's no way to solve this. This condition can be formulated as:
(x2 - x1 + y2 - y1 + M*N - 1) % 2 == 0
If you were to choose M, N, x1, x2, y1, y2 all at random, you'd basically get an unsolvable configuration about half the time. A 2*2 grid with points at opposite corners is one example of this.
Note that if either M or N equals 1 while the other is > 2, there's no solution possible unless the points are at opposite ends. Otherwise though - as long as M and N are both >= 2, and the above condition is met, then I believe a solution is always possible.
A detailed algorithm for finding a solution is... ummm... left as an excercise for the student. Yeah, that's it.
[ May 09, 2004: Message edited by: Jim Yingst ]
 
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You could treat this as a graph theory problem, making each grid square a node. The problem of finding a solution then becomes "find a Hamiltonian path through this graph", which is NP-Complete.
So you can use the naive method of finding a Hamiltonian path. The downside is that it's O(2^n).
I reckon a more elegant algorithm must be possible which exploits the properties of the graph, but my lunch break just ended so it's back to work

--Tim
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic