Non-consecutive Windoku Madness

Everything about Sudoku that doesn't fit in one of the other sections

Non-consecutive Windoku Madness

Postby udosuk » Sat Mar 31, 2007 5:45 pm

Although this sounds like a Variants topic, I think it is also relevant here as the structure of a solution grid is involved. I hope the vast number of programming gurus here can give some insight to the problem, at least empirically if not logically...

Over in the djape forum, my friend HATMAN and I are discussing about the possibility of a non-consecutive Windoku (or NRC-Sudoku, see this link). By "non-consecutive" we mean that all horizontally/vertically adjacent neighbours cannot contain consecutive numbers (such as "23" or "98"). 1 & 9 are not considered consecutive so are allowed to be adjacent to each other.

To our surprise we could not find any Windoku solution grid being non-consecutive. Not even one with only 3 of the 4 "windows" as constraints (a window is one of r234c234, r234c678, r678c234, r678c678). HATMAN did find a grid with 2 windows side by side that allow a non-consecutive solution grid (as a result he even created 2 puzzles with only 1 killer-cage, which must be a record so far)...

This prompt us to the following conjecture:
The Non-consecutive Windoku Conjecture

For all solution grids, if you require the following three 9-cell groups to have no repeating:

r234c234, r234c678, r678c234

... then there must be a least one pair of adjacent neighbours containing consecutive values.

It is obviously too hard to prove this conjecture manually. So I hope the programming masters can help proving it using brute force. I think it wouldn't be too hard if you set the 3 windows aforementioned as additional constraints, and doing a forward check search with the non-consecutiveness as additional elimination rules. What we want to know is if it really is true that 3 windows must force consecutive neighbours.

I hope high-calibre programmers interested in solution grid structure (e.g. gsf, Red Ed, coloin and many others) could lend a hand here. Thanks in advance!:)
Posts: 2698
Joined: 17 July 2005

Postby djape » Fri Jun 22, 2007 6:47 am


I've just proven using brute force that Non-Cons Windoku grids do not exist. As you may have seen on the main page of my site, I have only recently implemented a Windoku (aka Hyper Sudoku) solver/generator and I found this thread and got interested in this stuff.

Anyway, it took my solver 9 minutes to give up in finding a Non-Cons Windoku solution from an empty grid, which means that it doesn't exist.

This is really sad, since I was just getting ready to prepare a Weekend Special Non-Cons Windoku Killer Samurai X. Oh well, I'll have to think of something else. ;)

Posts: 34
Joined: 27 September 2005

Postby udosuk » Sat Jun 23, 2007 3:45 pm

Djape, thanks for working it out. Nice to have someone post the first reply to a thread originally posted almost 3 months ago!:)

I suppose you have verified the result for the case of all 4 windows (r234678c234678). The conjecture I proposed actually only requires the grid to have 3 windows (i.e. one of the windows, say r678c678 without loss of generality, doesn't need to have the digits 1 to 9). Is it possible if you modify your program a bit and test if there are any NC grids with that property? Thanks!
Posts: 2698
Joined: 17 July 2005

Return to General