Hi,
The speedest version of the sudoku, staying in the limit of lisibility
would include 3 nested "with",
timing with medium sudoku example :
'1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..'
2 nested with = 3.32 sec
1 nested with = 1.7sec
(1 nested with which could be 3 nested with) = 1.09 sec (see below 'annexe
1')
3 nested with .... well I get a "MemoryError: " event on the simplest
example. (see below 'annexe 2')
==> nobody in real life would do that, would he ?
Anyway, when I was trying to implement "fake" CTE, I was :
- creating views when the CTE was like " x as (select ...)"
- creating table when the cte was like "x(r) as (select ...)"
- creating table with index when the cte was like (x(r INTEGER
*PRIMARY KEY) as (select ...)"*
*==> So, if the if sudoku solving at the maximum speed with only virtual
table was a DEAD or ALIVE situation, I may suggest "embrassing and
extending" the CTE standard with a similar trick.*
**** example of "optimized" stupid-brut force sudoku 1 with **
drop table if exists ok;
create table ok(c,n);
CREATE INDEX ok_i
on ok (c, n);
with digits(z, lp) AS (
VALUES('1', 1),('2', 2) ,('3', 3),('4', 4),('5', 5),('6', 6),('7',
7),('8', 8),('9', 9)
)
,y(r) as (WITH RECURSIVE col(c) AS (
select 81 as c
union all
select c-1 from col where c>1
) select * from col)
, neighbors(r,n) as (select r, ((r-1)/9)*9 + lp from y, digits
union all select r, ((r-1)%9) + (lp-1)*9 + 1 from y, digits
union all select r, (((r-1)/3) % 3) * 3
+ ((r-1)/27) * 27 + lp
+ ((lp-1) / 3) * 6 from y, digits)
, goods (r,n) as (select * from neighbors where r <>n)
insert into ok select distinct * from goods;
-- easy (0 sec)
'53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'
-- medium (2 sec)
'1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..'
-- hard (200 s)
'8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'
WITH RECURSIVE input(sud) AS (
VALUES(
'1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..'
)
),
/* A table filled with digits 1..9, inclusive. */
digits(z, lp) AS (
VALUES('1', 1),('2', 2) ,('3', 3),('4', 4),('5', 5),('6', 6),('7',
7),('8', 8),('9', 9)
),
/* The tricky bit. */
x(s, ind) AS (
SELECT sud, instr(sud, '.') FROM input
UNION ALL
SELECT
substr(s, 1, ind-1) || z || substr(s, ind+1),
instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
FROM x, digits AS z
WHERE ind>0
AND NOT EXISTS (
SELECT 1 FROM ok AS lp
WHERE ind=lp.c and z.z = substr(s, n, 1)
)
)
SELECT * FROM x WHERE ind=0;
**** same with 3 nested with ... blow up even on the simplest case (bug of
me ? ) ***
drop table if exists ok;
create table ok(c,n);
CREATE INDEX ok_i
on ok (c, n);
with digits(z, lp) AS (
VALUES('1', 1),('2', 2) ,('3', 3),('4', 4),('5', 5),('6', 6),('7',
7),('8', 8),('9', 9)
)
,y(r) as (WITH RECURSIVE col(c) AS (
select 81 as c
union all
select c-1 from col where c>1
) select * from col)
, neighbors(r,n) as (select r, ((r-1)/9)*9 + lp from y, digits
union all select r, ((r-1)%9) + (lp-1)*9 + 1 from y, digits
union all select r, (((r-1)/3) % 3) * 3
+ ((r-1)/27) * 27 + lp
+ ((lp-1) / 3) * 6 from y, digits)
, goods (r,n) as (select * from neighbors where r <>n)
,input(sud) AS (
VALUES(
--
'1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..'
'53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79')
),
/* A table filled with digits 1..9, inclusive. */
--digits(z, lp) AS (
-- VALUES('1', 1),('2', 2) ,('3', 3),('4', 4),('5', 5),('6', 6),('7',
7),('8', 8),('9', 9)
-- ),
/* The tricky bit. */
x(s, ind) AS (
SELECT sud, instr(sud, '.') FROM input
UNION ALL
SELECT
substr(s, 1, ind-1) || z || substr(s, ind+1),
instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
FROM x, digits AS z
WHERE ind>0
AND NOT EXISTS (
SELECT 1 FROM ok AS lp
WHERE ind=lp.c and z.z = substr(s, n, 1)
)
)
SELECT * FROM x WHERE ind=0;
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
