Knight Non-Consecutive

For fans of Killer Sudoku, Samurai Sudoku and other variants

Knight Non-Consecutive

Postby HATMAN » Mon Jan 21, 2008 7:18 pm

I've been investigating a possible Restrained Sudoku formulation:

Cells a knights move apart must be nonconsecutive.

For each value placed it removes up to 16 extra candidates compared to plain sudoku.

I am not at present sure whether it has feasible solutions, but if it does the solution space will be small.

After a weekend of playing around with it manually this is the least unfeasible solution I've found: It contains 14 failures: five of 89, four of 78, three of 67 and two of 56.

Image

I would welcome any thoughts on how to take this further.
HATMAN
 
Posts: 204
Joined: 25 February 2006

Postby Smythe Dakota » Mon Jan 21, 2008 11:25 pm

Or, how about the following? Every entry (in the final solution) is a knight's move away from another entry which is either consecutive or identical? This sounds so restrictive that you almost shouldn't need any clues at all.

To make it even more restrictive, allow digit wrap-around, i.e. consider 9 and 1 to be adjacent. Maybe even allow wrap-around with respect to rows and columns as well, e.g. r9c4 is a knight's move away from r2c5.

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Postby HATMAN » Tue Jan 22, 2008 1:57 pm

Bill

I have used the nonconsecutive loop in NC90 as OverKillers 3 and 4 at:
http://www.djape.net/sudoku/forum/viewtopic.php?t=1188&start=0

The OverKiller idea is to have ten numbers instead of 9 distributed almost evenly so there are 9 of one number and 8 of each of the others - it works well as a Killer and I'm trying to do it on a Vanilla basis. My first vanilla overkiller posted on Ruud's site was a total wimp - which does not go well with the ethos on that site.

I am not convinced the knight nonconsecutive is solvable - never mind making it harder. I have (with udosuk's help) compiled a long list of "impossibles" (simple ones like NC Windoku fail) and I've a feeling that this is another one.

Maurice
Last edited by HATMAN on Wed Feb 27, 2008 6:51 pm, edited 1 time in total.
HATMAN
 
Posts: 204
Joined: 25 February 2006

Postby evert » Tue Feb 12, 2008 1:06 am

I did some programming on this. There seem to be no solutions at all.
I welcome everybody to search for an elegant ** mathematical ** proof.
:D
evert
 
Posts: 186
Joined: 26 August 2005

Postby HATMAN » Tue Feb 12, 2008 12:05 pm

Evert

Thanks for confirming that - from my T&E I was coming to the same conclusion. I think the primary problem is knight non-consecutive within a Nonet. So I've been trying the less constrained version where you only apply the night non-consecutive constraint to cell that are in different nonets. I have not got a solution yet but I've come much closer.

If you have some time to spare please try this out.

Thank you

Maurice
HATMAN
 
Posts: 204
Joined: 25 February 2006

Postby evert » Tue Feb 12, 2008 11:12 pm

I'll have to correct myself.
Code: Select all
123456789
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
has no solutions.

However, the general conclusion that there is no solution, is not justified.
Because not all numbers 1 to 9 play exactly the same role.

So today, I ran an algorithm that decides if a grid has no solution, one solution or more than one solution. The conclusion - after several hours - is that valid AN-grids do exist.

However it's very hard to find.
Right now I'm running another algorithm that tries to find a solution.
I'm afraid it will run for hours and have my computer crash.
evert
 
Posts: 186
Joined: 26 August 2005

Postby HATMAN » Wed Feb 13, 2008 1:36 pm

Wow - I await your results
HATMAN
 
Posts: 204
Joined: 25 February 2006

Postby evert » Wed Feb 13, 2008 11:33 pm

If I'm right this is a solution:
Code: Select all
129687354
543219876
768435192
687354921
912876543
435192768
354921687
876543219
291768435


And a puzzle based on it:
Code: Select all
100000000
000000800
000000000
000000000
010070000
000000760
300000080
000540000
000060400


Could you do a manual check if it's correct?

(Took my program about 4 hrs:D )
evert
 
Posts: 186
Joined: 26 August 2005

Postby evert » Thu Feb 14, 2008 12:23 am

Still playing around with this.
Finding a whole grid seems to be tough but deriving puzzles from it ...
Code: Select all
100000000
500000000
700000000
000000000
000000000
000000700
000000080
070540000
000000000

This one should be really fun!
evert
 
Posts: 186
Joined: 26 August 2005

Postby HATMAN » Thu Feb 14, 2008 12:34 pm

Well done

I'll check it and then try and solve them.
HATMAN
 
Posts: 204
Joined: 25 February 2006

Postby HATMAN » Thu Feb 14, 2008 6:35 pm

Evert

I've checked it and it is valid - well done. I'll do the puzzle later
HATMAN
 
Posts: 204
Joined: 25 February 2006

Postby evert » Fri Feb 15, 2008 2:08 am

Code: Select all
000000000
000000000
000009080
000000000
000800000
000000700
000007000
000040000
600000000

This puzzle is based upon an essentially different grid.
HATMANS brilliant idea, this whole knight non consecutive, my role is only bit of stupid programming and then sit next to my computer for 4 hrs:D:D
evert
 
Posts: 186
Joined: 26 August 2005

Postby HATMAN » Fri Feb 15, 2008 11:48 am

Evert

Flattery will get you everywhere with me.

I’ve not been able to try to solve any yet – too busy at work and on the Guinness last night.

I note with your last one that you’ve got the givens below 8 – well done. Given the very limited solution space we should be able to get to quite a low number of givens.

The next stage is adapting some of the non-consecutive techniques. Would anyone solving these please post any techniques they use.

Maurice
HATMAN
 
Posts: 204
Joined: 25 February 2006

Postby HATMAN » Fri Feb 15, 2008 2:30 pm

KNAC 1

Took about 3/4 hr almost all singles and plain KNAC elimination except:
Diagonal NP r4c2r3c5 = {28} -> r3c4 ~1379 =2|4
On redoing it this is not needed.
HATMAN
 
Posts: 204
Joined: 25 February 2006

Postby tarek » Fri Feb 15, 2008 2:41 pm

I won't probably attempt solving this by hand.

however it should be easy to include non-consecutive, A-King or A-Knight in a solver. I'm optimizing mine the moment & hopefully will see how it goes after that.

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Next

Return to Sudoku variants