Author Topic: Sudoku in Javascript  (Read 2328 times)

0 Members and 1 Guest are viewing this topic.

Offline combatking0

  • JavaScript lives!
  • Senior Member
  • DBF Aficionado
  • ********
  • Posts: 4569
  • Karma: 235
  • Retroman!
    • View Profile
    • Combat King's Barcode Battler Home
Sudoku in Javascript
« on: March 17, 2013 »
I've revived an old project involving Sudoku.

In theory, it should be possible to fill a blank grid based on any square number. Traditional puzzles use 9 symbols, and I'm sure I've seen hexadecimal puzzles before.

My program will, when finished, generate puzzles using the following options:
9 Symbols - 1-9
16 Symbols - 0-9, A-F
25 Symbols - A-I, K-Z
36 Symbols - 0-9, A-Z

Using a simple brute-force technique, I can fill a blank 9x9 grid within a few seconds, but the other grids don't seem to resolve. Here's my code so far. Given time, I will annotate it so that you know what it does.
http://fx.barcodebattler.co.uk/Sudoku.htm

The next step, once it can complete a blank grid properly, will be to remove some of the squares and generate a solvable puzzle.
« Last Edit: March 18, 2013 by combatking0 »
You are our 9001st visitor.
Challenge Trophies Won:

Offline Hotshot

  • DBF Aficionado
  • ******
  • Posts: 2114
  • Karma: 91
    • View Profile
Re: Sudoku in Javascript
« Reply #1 on: March 18, 2013 »
I used to do sudoku but coding sudoku can be bit of headache!

I am sure some guys on here will help ya :)

Good Luck :)


Offline combatking0

  • JavaScript lives!
  • Senior Member
  • DBF Aficionado
  • ********
  • Posts: 4569
  • Karma: 235
  • Retroman!
    • View Profile
    • Combat King's Barcode Battler Home
Re: Sudoku in Javascript
« Reply #2 on: March 18, 2013 »
I've tweaked the "brute force" grid filler to make it a bit less brutal. It still doesn't get it right first time, but it can fill a 9x9 grid in under a second, a 16x16 grid in a few seconds and a 25x25 grid in under 30 seconds.

36x36 grids are still taking too long, but I have a few more tricks to experiment with.

(edit) Maybe it was pure luck, but the 36x36 grid filled itself successfully while I wasn't watching - here's a flavour of the output:

Code: [Select]
5 E S N G V I F D 1 3 U C M P X Q R J Y 2 L K A Z 7 9 4 6 B H T 0 W 8 o
7 M J 2 P 9 C X 0 6 W L 5 Z Y I 8 E Q o 4 3 T H K 1 F D G A R B S V U N
4 B Z Y 1 8 E 7 V T R o A K J 3 6 W I S D 9 G C L H 0 5 U N X 2 F P Q M
0 U A 3 Q F J Y G P H K 4 N T V S 2 B W 6 M Z 7 o 8 I R X E L 1 5 9 D C
K 6 C o D X B 5 Q N M 2 9 0 H L 1 7 E 8 P F R U V S T 3 W Y I J 4 G A Z
W I H T R L Z 9 8 S 4 A o D B F G U V 0 1 N X 5 J M C P Q 2 K 3 7 Y 6 E
2 W X U 7 Z K 4 H F E V I Y J N L 0 1 T 5 8 P 3 R B 9 o 6 S D G C Q M A
R B 5 M o I 6 U 9 S G X C 8 W 7 H T V Z K A N E 3 2 D L Q 1 Y 0 4 P J F
D Y T Q 4 V J 2 C 7 A R E P 6 B X M G S F H L U K 0 N I Z W 5 1 o 8 9 3
6 J P 3 G E M W B Z o L D 4 F 1 5 K 0 Y I Q 2 9 7 A H 8 V C N S U R X T
S N L C H 0 Y P 5 3 1 8 9 2 U G A Q D 6 R M o B T X 4 E J F I W 7 K Z V
K F 1 8 A 9 N T Q 0 D I Z S o V R 3 W C J X 7 4 U P 5 M Y G L B 2 E 6 H
7 Z Y T E A W F B D K 3 6 M 8 I C X 4 5 9 H 1 L N 0 2 J P Q U R V o S G
G K X F 1 N L 9 I H 0 6 3 2 S E 5 R P Q D J U o A V W C M B 7 Y T 8 4 Z
9 o D M 2 P V 7 T S C J U 0 W H Q Y I R E 3 X B K G 5 Z 4 8 1 F N 6 L A
4 J 3 C H B Y U N 8 5 A o K L 1 G P V F M Z 6 0 9 R S 7 E T X W D 2 I Q
I 8 W Q U V E 4 P M R G A Z 7 F J D 2 N S K T C X L 6 1 Y o B H 0 3 5 9
6 S 5 L R 0 1 Q 2 Z o X 9 T 4 B V N 7 8 W Y A G U D 3 F I H E C M P K J
N 0 o U T L A 3 6 I Q B V S C E 1 8 9 Y 5 M R D Z X P G W 2 K 7 F 4 H J
J I W D 8 H E N Z C X R 3 9 7 M 6 0 G L F 1 4 T Q K o U Y S P V B A 2 5
F E K 2 V R o 0 8 5 J 7 G H Y A I Q P W 6 X B N T 4 1 L M C Z S 9 U 3 D
A C M 1 7 S V Y H W U 4 Z P K 2 F B E o J 3 Q I D 5 6 8 9 N R L T 0 X G
Z B 6 4 Y P 1 D 9 K G T R X 5 J L o S 0 A V U 2 3 7 F I E H N Q 8 M W C
5 Q G 3 X 9 F L S P M 2 W U T 4 N D Z H 8 K 7 C J A B V R 0 Y o I 6 1 E
o 5 V W B J G A Q 4 9 2 K E I 1 D F 8 T Z M P S H X 3 N 7 L R U Y 6 0 C
I F E U 2 X B V W 0 6 Y 4 7 Z T L 8 C 5 J K R G o Q S 9 M D 3 N 1 P H A
Y D Z H 9 S 8 1 T R 7 N 6 B A J 3 0 X U E 2 L o C P I K V F Q M 5 4 W G
Q N 6 C A R I U K M X D Y 9 2 P 5 S 3 F H 1 B W J G 0 T 4 E 8 L Z o V 7
4 T P 8 M G L Z J 3 o H C Q X U V W Y 9 7 0 N A B 6 R 2 5 1 F I D K E S
3 7 1 0 K L F P E 5 S C o G H M R N I 4 D 6 Q V 8 A U Z Y W T J 9 2 B X
B 3 V 6 R U W P Q S M X J 1 C E Y D 2 Z 5 A L F 7 4 0 8 G H o K N I T 9
o Z 7 L I S R T 6 8 0 V 4 U F 3 2 5 Q K H G Y C M 1 E B N 9 A W P J X D
Y 0 X D G A C 4 5 N U H 9 V L B K Q R W 1 o I 3 6 J S Z T P E 7 8 2 M F
H C 9 M K 8 D L A o 1 F R G 7 N I 6 E T S V P J W U 5 X Q 2 0 Z 4 3 B Y
E W Q T 1 J B 9 K 3 Z 2 o X 0 8 S P M U N D 4 7 R Y F A I V C G L 6 5 H
F 4 5 2 N P J Y E I 7 G Z M T A H W 6 8 0 X B 9 K C 3 D L o S V R Q 1 U

I'm sure I can improve upon this though.
« Last Edit: March 18, 2013 by combatking0 »
You are our 9001st visitor.
Challenge Trophies Won:

Offline Kirl

  • Senior Member
  • Pentium
  • ********
  • Posts: 1201
  • Karma: 230
    • View Profile
    • Homepage
Re: Sudoku in Javascript
« Reply #3 on: March 18, 2013 »
Ow, well done! I tried something like this, deemed it imposible for my inferior brain and gave up on it...

Turns out it's somewhat of a mathematical puzzle to figure out how many and which numbers you can hide, while keeping only one possible solution too.
www.kirl.nl
Challenge Trophies Won:

Offline combatking0

  • JavaScript lives!
  • Senior Member
  • DBF Aficionado
  • ********
  • Posts: 4569
  • Karma: 235
  • Retroman!
    • View Profile
    • Combat King's Barcode Battler Home
Re: Sudoku in Javascript
« Reply #4 on: March 19, 2013 »
I've realised there was a bug - it was only checking horizontally, so columns and large squares were being ignored!

I'll keep trying and I'll get it right one day.
You are our 9001st visitor.
Challenge Trophies Won:

Offline Kirl

  • Senior Member
  • Pentium
  • ********
  • Posts: 1201
  • Karma: 230
    • View Profile
    • Homepage
Re: Sudoku in Javascript
« Reply #5 on: March 20, 2013 »
Oh noes! Hate it when that happens. :telloff:
I've seen many of my revolutionary breakthroughs turn into meaningless bits upon closer inspection... 

Keep hammering them keys, the solution is under there somewhere! :hammer:
www.kirl.nl
Challenge Trophies Won:

Offline combatking0

  • JavaScript lives!
  • Senior Member
  • DBF Aficionado
  • ********
  • Posts: 4569
  • Karma: 235
  • Retroman!
    • View Profile
    • Combat King's Barcode Battler Home
Re: Sudoku in Javascript
« Reply #6 on: March 20, 2013 »
I have another approach - build a solver, test it, then...

build a system which seeds a blank grid with no more than 25 values for a 9x9 grid, increasing for the larger grids, and see if it is solvable.
You are our 9001st visitor.
Challenge Trophies Won: